a pommaret division algorithm for computing grobner bases in boolean rings
In 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 [x 1 ,...,x n ], 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.
pommaret division boolean ring involutive algorithm groebner basis