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

Details:

   
TitleAre Buchberger’s criteria necessary for the chain condition?
Author(s) Hoon Hong, John Perry
TypeArticle in Journal
AbstractBuchberger’s Gröbner basis theory plays a fundamental role in symbolic computation. The resulting algorithms essentially carry out several S -polynomial reductions. In his Ph.D. thesis and later publication Buchberger showed that sometimes one can skip S -polynomial reductions if the leading terms of polynomials satisfy certain criteria. A question naturally arises: Are Buchberger’s criteria also necessary for skipping S -polynomial reductions? In this paper, after making the question more precise (in terms of a chain condition), we show the answer to be “almost, but not quite”: necessary when there are four or more polynomials, but not necessary when there are exactly three polynomials. For that case, we found an extension to Buchberger’s criteria that is necessary as well as sufficient.
KeywordsGröbner bases, S -polynomials, Buchberger criteria
ISSN0747-7171
URL http://www.sciencedirect.com/science/article/pii/S0747717107000326
LanguageEnglish
JournalJournal of Symbolic Computation
Volume42
Number7
Pages717 - 732
Year2007
Edition0
Translation No
Refereed No
Webmaster