Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleAn Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals
Author(s) Ulla Koppenhagen, Ernst W. Mayr
TypeArticle in Journal
AbstractIn 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.
Length22
CopyrightAcademic Press
File
LanguageEnglish
JournalJournal of Symbolic Computation
Volume28
Number3
Pages317-338
Year1999
MonthSeptember
Translation No
Refereed No
Webmaster