LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals and Applications

Ulla Koppenhagen and Ernst W. Mayr


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.