Seminars

Groebner Bases Computation in Boolean Rings for Model Checking and Their Applications in BioInformatics
Quoc-Nam Tran, Professor
Lamar University (Texas State), Beaumont, Texas

10/08/2010, 2pm, GHC-6501

Abstract

The theory of Groebner Bases has become a crucial building block to computer algebra, and is widely used in science, engineering, and computer science. It is well-known that Groebner bases computation is EXP-SPACE in a general setting. In this talk, we present some recent developments in this area including an algorithm to show that Groebner bases computation is actually P-SPACE in Boolean rings. We also show that with this discovery, the Groebner bases method can theoretically be as efficient as other methods for automated verification of hardware and software. Additionally, many useful and interesting properties of Groebner bases including the ability to efficiently convert the bases for different orders of variables making Groebner bases a promising method in automated verification.

In contrast to other known algebraic approaches, the degree of intermediate polynomials during the calculation of Groebner bases using our method will never grow resulted in a significant improvement in running time and memory space consumption. We also show how calculation in temporal logic for model checking can be done by means of our direct and efficient Groebner basis computation in Boolean rings. We present our experimental results in finding attractors and control strategies of Boolean networks to illustrate our theoretical arguments.

Biography

Dr. Tran is currently a tenured Full Professor of Computer Science at Lamar University. He got his Ph.D. with the “Goedel Prize” for The Best Ph.D. Dissertation of The Year in 1996 from the Research Institute for Symbolic Computation (RISC-Linz), in Austria (Europe).

Dr. Tran was a Visiting Professor at Rice University in 2006-2007 and developer of Mathematica at Wolfram Research in 1998-1999. Dr. Tran's expertise areas include the computational methods, especially the Groebner bases, and their applications. He is the author/editor of 55 publications in his research areas. Dr. Tran also served on three NSF review panels.