Are Buchberger's Criteria Necessary For the Chain Condition?

Document Type

Article

Publication Date

7-1-2007

Department

Mathematics

Abstract

Buchberger's Grobner 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 ail extension to Buchberger's criteria that is necessary as well as sufficient. (c) 2007 Elsevier Ltd. All rights reserved.

Publication Title

Journal of Symbolic Computation

Volume

42

Issue

7

First Page

717

Last Page

732

Link to Full Text

Find in your library

Share

COinS