Details:
Title  An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals  Author(s)  Ulla Koppenhagen, Ernst W. Mayr  Type  Article in Journal  Abstract  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 an optimal algorithm for the uniform word problem in commutative semigroups, we first derive an exponential space algorithm for constructing the reduced Gröbner basis of pure difference binomial ideals. 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 over Q in general.  Length  22  Copyright  Academic Press 
File 
 Language  English  Journal  Journal of Symbolic Computation  Volume  28  Number  3  Pages  317338  Year  1999  Month  September  Translation 
No  Refereed 
No 
