article

Free access

A simplified proof of the characterization theorem for Gröbner-bases

Authors:

L. Bachmair,

B. BuchbergerAuthors Info & Claims

ACM SIGSAM Bulletin, Volume 14, Issue 4

Pages 29 - 34

https://doi.org/10.1145/1089235.1089238

Published: 01 November 1980 Publication History

PDF eReader

Abstract

In /2/ a certain type of bases ("Gröbner-Bases") for polynomial ideals has been introduced whose usefulness stems from the fact that a number of important computability problems in the theory of polynomial ideals are reducible to the construction of bases of this type. The key to an algorithmic construction of Gröbner-bases is a characterization theorem for Gröbner-bases whose proof in /2/is rather complex.In this paper a simplified proof is given. The simplification is based on two new lemmas that are of some interest in themselves. The first lemma characterizes the congruence relation modulo a polynomial ideal as the reflexive-transitive closure of a particular reduction relation ("M-reduction") used in the definition of Gröbner-bases and its inverse. The second lemma is a lemma on general reduction relations, which allows to guarantee the Church-Rosser property under very weak assumptions.

References

[1]

B. Buchberger, Ph.D. Thesis, Univ. Innsbruck, 1965 (see also Aequationes mathematicae, Vol. 4/3, pp. 374--383, 1970).

Google Scholar

[2]

B. Buchberger, A Theoretical Basis for the Reduction of Polynomials to Canonical Forms, ACM-SIGSAM Bulletin 39, August 1976, p. 19--29.

Digital Library

Google Scholar

[3]

B. Buchberger, A Criterion for Detecting Unnecessary Reductions in the Construction of Gröbner-Bases, in: Proc. EUROSAM 79, Marseille, (Lecture Notes in Computer Science, Vol. 72), pp. 3--21, 1979.

Digital Library

Google Scholar

[4]

B. Buchberger, F. Winkler, Miscellaneous Results on the Construction of Gröbner-Bases for Polynomial Ideals, Bericht Nr. 137, Institut für Mathematik, Universität Linz, 1979.

Google Scholar

[5]

G. Huet, Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems, 18th IEEE Symp. on Found. Comp. Scie, 30--45, 1977.

Google Scholar

[6]

D. Knuth, P. Bendix, Simple word problems in universal algebras, Computational problems in abstract algebra, Ed. J. Leech, Pergamon Press, pp. 263--297, 1970.

Google Scholar

[7]

C. Kollreider, B. Buchberger, An Improved Algorithmic Construction of Gröbner-Bases for Polynomial Ideals, Bericht Nr. 110, Institut für Mathematik, Universität Linz, 1978.

Google Scholar

[8]

R. Loos, personal communication, 1979.

Google Scholar

Cited By

View all

Bose NBose N(2016)Multivariate Polynomial Fundamentals for Multidimensional SystemsApplied Multidimensional Systems Theory10.1007/978-3-319-46825-9_1(1-36)Online publication date: 25-Dec-2016
https://doi.org/10.1007/978-3-319-46825-9_1
Poli A(2005)Some algebraic tools for error-correcting codesAlgebraic Algorithms and Error-Correcting Codes10.1007/3-540-16776-5_708(43-60)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-16776-5_708
Buchberger B(2005)Basic features and development of the critical-pair/completion procedureRewriting Techniques and Applications10.1007/3-540-15976-2_1(1-45)Online publication date: 29-May-2005
https://doi.org/10.1007/3-540-15976-2_1
Show More Cited By

Recommendations

Canonical comprehensive Gröbner bases
Special issue: International symposium on symbolic and algebraic computation (ISSAC 2002)

Comprehensive Gröbner bases for parametric polynomial ideals were introduced, constructed, and studied by the author in 1992. Since then the construction has been implemented in the computer algebra systems ALDES/SAC-2, MAS, REDUCE and MAPLE. A ...
Janet-like gröbner bases
CASC'05: Proceedings of the 8th international conference on Computer Algebra in Scientific Computing

We define a new type of Gröbner bases called Janet-like, since their properties are similar to those for Janet bases. In particular, Janet-like bases also admit an explicit formula for the Hilbert function of polynomial ideals. Cardinality of a Janet-...
Letterplace ideals and non-commutative Gröbner bases

In this paper we propose a 1-to-1 correspondence between graded two-sided ideals of the free associative algebra and some class of ideals of the algebra of polynomials, whose variables are double-indexed commuting ones. We call these ideals the ''...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGSAM Bulletin Volume 14, Issue 4

November 1980

40 pages

ISSN:0163-5824

DOI:10.1145/1089235

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1980

Published in SIGSAM Volume 14, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
140
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)2

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bose NBose N(2016)Multivariate Polynomial Fundamentals for Multidimensional SystemsApplied Multidimensional Systems Theory10.1007/978-3-319-46825-9_1(1-36)Online publication date: 25-Dec-2016
https://doi.org/10.1007/978-3-319-46825-9_1
Poli A(2005)Some algebraic tools for error-correcting codesAlgebraic Algorithms and Error-Correcting Codes10.1007/3-540-16776-5_708(43-60)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-16776-5_708
Buchberger B(2005)Basic features and development of the critical-pair/completion procedureRewriting Techniques and Applications10.1007/3-540-15976-2_1(1-45)Online publication date: 29-May-2005
https://doi.org/10.1007/3-540-15976-2_1
Bündgen R(1998)Symmetrization Based CompletionSymbolic Rewriting Techniques10.1007/978-3-0348-8800-4_3(47-70)Online publication date: 1998
https://doi.org/10.1007/978-3-0348-8800-4_3
Baader F(1993)Unification in commutative theories, Hilbert's basis theorem, and Gröbner basesJournal of the ACM10.1145/174130.17413340:3(477-503)Online publication date: 1-Jul-1993
https://dl.acm.org/doi/10.1145/174130.174133
Geddes KCzapor SLabahn GGeddes KCzapor SLabahn G(1992)Gröbner Bases for Polynomial IdealsAlgorithms for Computer Algebra10.1007/978-0-585-33247-5_10(429-471)Online publication date: 1992
https://doi.org/10.1007/978-0-585-33247-5_10
Herfort WPenz H(1991)A new notion of reductionJournal of Symbolic Computation10.1016/S0747-7171(08)80143-512:6(585-605)Online publication date: 1-Dec-1991
https://dl.acm.org/doi/10.1016/S0747-7171%2808%2980143-5
KÜCHLIN W(1989)Inductive Completion by Ground Proof TransformationRewriting Techniques10.1016/B978-0-12-046371-8.50013-4(211-244)Online publication date: 1989
https://doi.org/10.1016/B978-0-12-046371-8.50013-4
CHOU SSCHELTER WYANG J(1989)Characteristic Sets and Gröbner Bases in Geometry Theorem ProvingAlgebraic Techniques10.1016/B978-0-12-046370-1.50008-5(33-92)Online publication date: 1989
https://doi.org/10.1016/B978-0-12-046370-1.50008-5
Mishra BYap C(1989)Notes on Grobner basesInformation Sciences: an International Journal10.1016/0020-0255(89)90037-648:3(219-252)Online publication date: 1-Aug-1989
https://dl.acm.org/doi/10.1016/0020-0255%2889%2990037-6
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

Canonical comprehensive Gröbner bases

Janet-like gröbner bases

Letterplace ideals and non-commutative Gröbner bases

Comments

Information

Published In

Publisher

Publication History

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations