Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleNew developments in the theory of Gröbner bases and applications to formal verification
Author(s) Michael Brickenstein, Alexander Dreyer, Gert-Martin Greuel, Markus Wedler, Oliver Wienand
TypeArticle in Journal
AbstractWe present foundational work on standard bases over rings and on Boolean Gröbner bases in the framework of Boolean functions. The research was motivated by our collaboration with electrical engineers and computer scientists on problems arising from formal verification of digital circuits. In fact, algebraic modelling of formal verification problems is developed on the word-level as well as on the bit-level. The word-level model leads to Gröbner basis in the polynomial ring over Z/2^l while the bit-level model leads to Boolean Gröbner bases. In addition to the theoretical foundations of both approaches, the algorithms have been implemented. Using these implementations we show that special data structures and the exploitation of symmetries make Gröbner bases competitive to state-of-the-art tools from formal verification but having the advantage of being systematic and more flexible.
Length24
LanguageEnglish
JournalJournal of Pure and Applied Algebra
Volume213
Number8
Pages1612-1635
Year2009
Translation No
Refereed No
Webmaster