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


TitleA critical-pair/completion algorithm for finitely generated ideals in rings
Author(s) Bruno Buchberger
TypeArticle in Conference Proceedings
AbstractIn 1965, the author introduced a "critical-pair/completion" algorithm that starts from a finite set F of polynomials in K[x1,...,xn] (K is a field) and produces a set G of polynomials such that the ideal generated by F and G are identical, but G is in a certain standard form (G is a "Gröbner-basis"), for which a number of important decision and computability problems in polynomial ideal theory can be solved elegantly. In this paper, it is shown how the critical-pair/completion approach can be extended to general rings. One of the difficulties lies in the fact that, in general, the generators of an ideal in a ring do not naturally decompose in a "head" and a "rest" (left-hand side and right-hand side). Thus, the crucial notions of "reduction" and "critical pair" must be formulated in a new way that does not depend on any "rewrite" nature of the generators. The solution of this problem is the starting point of this paper. Furthermore, a set of reduction axioms is given, under which the correctness of the algorithm can be proven and which are preserved when passing from a ring R to the polynomial ring R[x1,...,xn]. Z[x1,...,xn] is an important example of a ring in which the critical-pair/completion approach is possible.
CopyrightSpringer - Verlag Berlin
AddressLondon, UK
Translation No
Refereed Yes
Organization Johannes Kepler University Linz
Institution RISC (Research Institute for Symbolic Computation)