Abstract
In 1965, the author introduced a "critical-pair/completion" algorithm that starts from a finite set F of polynomials in K[x1,...,xn] (K a field) and produces a set G of polynomials such that the ideals 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 into 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 the 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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ayoub, C. W., 81: On Constructing Bases for Ideals in Polynomial Rings over the Integers. The Pennsylvania State University, Dept. of Mathematics, Report Nr. 8184, 1981, submitted to publication.
Ballantyne, A. M., Lankford, D. S., 81: New Decision Algorithms for Finitely Presented Commutative Semigroups. Comp. and Maths. with Appls. 7 (1981), 159–165.
Bauer, G., 81: The Representation of Monoids by Confluent Rule Systems. University of Kaiserlautern, FRG, Fachbereich Informatik, Ph.D. Thesis, 1981.
Bergman, G. M., 78: The Diamond Lemma for Ring Theory. Adv. Math. 29, (1978), 178–218.
Buchberger, B., 65: An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-Dimensional Polynomial Ideal (German). Univ. of Innsbruck, Austria, Math. Inst., Ph.D. Thesis, 1965.
Buchberger, B., 70: An Algorithmical Criterion for the Sovability of Algebraic Systems of Equations (German). Aequationes mathematicae 4/3 (1970), 374–383.
Buchberger, B., 76: A Theoretical Basis for the Reduction of Polynomials to Canonical Form. ACM SIGSAM Bull. 10/3 (1976), 19–29.
Buchberger, B., 76a: Some Properties of Gröbner Bases for Polynomial Ideals. ACM SIGSAM Bull. 10/4 (1976), 19–24.
Buchberger, B., 79: A Criterion for Detecting Unnecessary Reductions in the Construction of Gröbner-Bases. Proc. EUROSAM 79, Marseille (Ng, W., ed.), Lecture Notes in Computer Science 72 (1979), 3–21.
Buchberger, B., 83: A Note on the Complexity of Constructing Gröbner-Bases. Proc. of the EUROCAL 83 Conf., London, Lecture Notes in Computer Science, Sringer, 1983, to appear.
Buchberger, B., 83a: A Critical-Pair/Completion Algorithm in Reduction Rings. University of Linz, Austria, Math. Institute, Technical Report Nr. CAMP 83-21.0, 1983.
Buchberger, B., Loos, R., 82: Algebraic Simplification. In: Computer Algebra (B. Buchberger, G. Collins, R. Loos eds.), Springer, Wien New York, 1982, 11–43.
Guiver, J. P., 82: Contributions to Two-Dimensional System Theory. Univ. of Pittsburgh, Math. Dept., Ph.D. Thesis, 1982.
Hurd, C. B., 70: Concerning Ideals in Z[x] and Zpn[x]. The Pennsylvania State University, Department of Mathematics, Ph.D. Thesis, 1970.
Knuth, D. E., Bendix, P. B., 67: Simple Word Problems in Universal Algebras. Proc. of the Conf. on Computational Problems in Abstract Algebra, Oxford, 1967, (Leech, J., ed.), Oxford: Pergamon Press, 1970.
Kronecker, L., Hensel, K., 01: Lectures on Number Theory (German). Leipzig, 1901.
Lauer, M., 76: Canonical Representatives for the Residue Classes of a Polynomial Ideal. University of Kaiserslautern, FRG, Dept. of Mathematics, Diploma Thesis, 1976.
Llopis de Trias, R., 83: Canonical Forms for Residue Classes of Polynomial Ideals and Term Rewriting Systems. Univ. Aut. de Madrid, Division de Mathematicas, submitted to publication, 1983.
Redei, L., 56: Equivalence of the Theorems of Kronecker-Hensel and Szekeres (German). Acta Sci. Math. Szeged 17 (1956), 198–202.
Richman, F., 74: Constructive Aspects of Noetherian Rings. Proc. AMS 44/2 (1974), 436–441.
Schaller, S., 79: Algorithmic Aspects of Polynomial Residue Class Rings. University of Wisconsin, Madison, Ph.D. Thesis, Comput. Sci. Tech. Rep. 370, 1979.
Simmons, H., 70: The Solution of a Decision Problem for Several Classes of Rings. Pac. J. Math. 34 (1970), 547–557.
Sims, C., 78: The Role of Algorithms in the Teaching of Algebra. In: Topics in Algebra (Newman, M. F. ed.), Lecture Notes in Mathematics 697 (1978), Springer, 95–107.
Spear, D., 77: A Constructive Approach to Commutative Ring Theory. Proc. of the MACSYMA Users' Conference, Berkeley, 1977, (Fateman, R.J., ed.), published by MIT, 369–376.
Szekeres, G., 52: A Canonical Basis for the Ideals of a Polynomial Domain. Am. Math. Monthly 59 (1952), 379–386.
Szekeres, G., 65: Metabelian Groups with Two Generators. Proc. Internat. Conf. Theory of Groups (Canberra 1965), Gordon & Breach, 1967, 323–346.
Szekeres, G., 75: Homogeneous Ideals in K[x,y,z]. Acta Math. Acad. Sci. Hungar. 26 (1975), 355–367.
Trinks, W., 78: On B. Buchberger's method for Solving Algebraic Equations (German). J. Number Theory 10/4 (1978), 475–488 (preprint 1977).
Trotter, P. G., 69: A Canonical Basis for Ideals of Polynomials in Several Variables and With Integer Coefficients. Univ. of New South Wales, Ph.D. Thesis, 1969.
Trotter, P. G., 78: Ideals in Z[x,y]. Acta Math. Acad. Sci. Hungar. 32 (1–2) (1978), 63–73.
Winkler, F., Buchberger, B., 83: A Criterion for Eliminating Unnecessary Reductions in the Knuth-Bendix Algorithm. Coll. on Algebra, Combinatorics and Logic in Computer Science, Györ, Sept. 12–16, 1983, 21 p.
Zacharias, G., 78: Generalized Gröbner Bases in Commutative Polynomial Rings. MIT, Dept. Comput. Sci., Bachelor Thesis, 1978.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1984 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buchberger, B. (1984). A critical-pair/completion algorithm for finitely generated ideals in rings. In: Börger, E., Hasenjaeger, G., Rödding, D. (eds) Logic and Machines: Decision Problems and Complexity. LaM 1983. Lecture Notes in Computer Science, vol 171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-13331-3_39
Download citation
DOI: https://doi.org/10.1007/3-540-13331-3_39
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-13331-5
Online ISBN: 978-3-540-38856-2
eBook Packages: Springer Book Archive