An Optimal Algorithm for Constructing the Reduced Gröbner Basis of
Binomial Ideals
In this paper, we present an optimal, exponential space algorithm for
generating the reduced Gröbner basis of binomial ideals. We make use
of the close relationship between commutative semigroups and pure
difference binomial ideals. Based on the algorithm for the uniform
word problem in commutative semigroups exhibited by Mayr and Meyer we
first derive an exponential space algorithm for constructing
the reduced Gröbner basis of a pure difference binomial
ideal. In addition to some applications to finitely presented commutative
semigroups, this algorithm is then extended to an exponential
space algorithm for generating the reduced Gröbner basis of binomial
ideals in general.
