An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals and Applications
It is known that the reduced Gröbner basis of general polynomial
ideals can be computed in exponential space. The algorithm obtained by
Kühnle and Mayr, however,
is based on rather complex parallel computations, and, above that,
makes extensive use of the Parallel Computation Thesis. In this paper,
we exhibit an exponential space algorithm for generating the reduced
Gröbner basis of binomial ideals which can be implemented without
any complex parallel computations. This result is then applied
to derive space optimal decision procedures for the finite enumeration
and subword problems for commutative semigroups.
