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, and Applications to Commutative Semigroups
Author(s) Ulla Koppenhagen, Ernst W. Mayr
TypeArticle in Journal
AbstractIt 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, 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 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.
Length18
File
URL dx.doi.org/10.1006/jsco.1999.1015
LanguageEnglish
JournalJournal of Symbolic Computation
Volume31
Number1-2
Pages259-276
Year2001
MonthJanuary
Translation No
Refereed No
Webmaster