An Optimal Algorithm for Constructing the Reduced Grobner Basis of Binomial Ideals, and Applications to Commutative Semigroups

摘要

It is known that the reduced Grobner basis of general polynomial ideals can be computed in exponential space. The algorithm, obtained by Kuhnle and Mayr, is, however, 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 Grobner 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 com- mutative semigroups.