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

Details:

   
TitleA pommaret division algorithm for computing Grobner bases in boolean rings
Author(s) Vladimir P. Gerdt, Mikhail V. Zinn
TypeBook, Chapter in Book, Conference Proceeding
AbstractIn this paper an involutive algorithm for construction of Grobner bases in Boolean rings is presented. The algorithm exploits the Pommaret monomial division as an involutive division. In distinction to other approaches and due to special properties of Pommaret division the algorithm allows to perform the Grobner basis computation directly in a Boolean ring which can be defined as the quotient ring F_2[x1,...,xn],1^2+x_1,...,x_n ^2+x_n>. Some related cardinality bounds for Pommaret and Grobner bases are derived. Efficiency of our first implementation of the algorithm is illustrated by a number of serial benchmarks.
Keywordsboolean ring, groebner basis, involutive algorithm, pommaret division
ISBN978-1-59593-904-3
URL http://doi.acm.org/10.1145/1390768.1390784
LanguageEnglish
SeriesISSAC '08
Pages95--102
PublisherACM
Year2010
Translation No
Refereed No
BookA pommaret division algorithm for computing Grobner bases in boolean rings
ConferencenameISSAC 2008 The twenty-first international symposium on Symbolic and algebraic computation
Webmaster