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.     «

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 t...     »