More Web Proxy on the site http://driver.im/

Article

Free access

Canonical representatives for residue classes of a polynomial ideal

Author:

Markus LauerAuthors Info & Claims

SYMSAC '76: Proceedings of the third ACM symposium on Symbolic and algebraic computation

Pages 339 - 345

https://doi.org/10.1145/800205.806353

Published: 10 August 1976 Publication History

Abstract

At the EUROSAM Conference 1974 it was conjectured that there exist probably no canonical forms for polynomial expressions under polynomial side relations. In 1965, however, Buchberger had already implemented a reduction algorithm solving the problem over fields. Positive results were also attained independently since 1974 by R. Shtokhamer and the author. In this note a general theorem on canonical representatives is obtained and by application to Buchberger's and Shtokhamer's algorithms it is proven that the stated problem is solved.

References

[1]

B.F. Caviness, On Canonical Forms and Simplification, J.ACM 17, April, 1970, (385-396)

Digital Library

[2]

W.S. Brown, Rational Exponential Expressions and a Conjecture Concerning &pgr; and e, Amer. Math. Monthly 76, Jan., 1969, (28-34)

[3]

J. Moses, Algebraic Simplification, a Guide for the Perplexed, Comm. ACM 14, Aug. 1971, (527-538)

Digital Library

[4]

R. Loos, Toward a Formal Implementation of Computer Algebra, Proceedings of EUROSAM, Aug. 1-2, 1974, as SIGSAM Bulletin 8, Aug. 1974, (9-16)

Digital Library

[5]

R.D. Jenks, The SCRATCHPAD Language, Proceedings of a SIGPLAN Symposium on Very High Level Languages, March 1974

Digital Library

[6]

B. Buchberger, Ein Algorithmisches Kriterium für die Lösbarkeit eines Algebraischen Gleichungssystems, Aequationes mathematicae Vol. 4, 1970

[7]

R. Shtokhamer, A Canonical Form of Polynomials in the Presence of Side Relations, Physics Department, Technion, Haifa, Israel, Technion-PH-76-25

[8]

B.F. Caviness, P.L.Pollak, C.M. Rubald, An Existence Lemma For Canonical Forms in Symbolic Mathematics, Information Processing Letters (1971) 45-46

[9]

A. Szekeres, A Canonical Basis for the Ideals of a Polynomial Domain, Amer. Math. Monthly 59, (1952) (379-386)

[10]

G.E. Collins, Algebraic Algorithms, Prentice Hall, Chap. 2 ( to appear )

[11]

D.R. Musser, Algorithms for Polynomial Factorization, Comp. Science Dept. Technical Report No. 134, Sept. 1971, Univ. of Wisconsin

[12]

A. Seidenberg, On the Length of a Hilbert Ascending Chain, Proc. of the Amer. Proc. Soc., Vol 29 (1971) (433-450)

[13]

A. Seidenberg, Constructions in Algebra, Trans. of Amer. Math. Soc., Vol. 197 (1974), 273-313

[14]

F. Richman, Constructive Aspects of Noetherian Rings, Proc. of Amer. Math. Soc., Vol. 44 (1974), 436-441

[15]

S.L. Kleiman, Computing with Rational Expressions in Several Algebraically Independent Variables, Bell Labs Tech. Report, Murray Hill, N.J.

[16]

B. Buchberger, On Certain Bases of Polynomial Ideals, Universität Linz, Institut für Mathematik, Bericht Nr. 53, May 1976

Cited By

Kuijper MSchindelar K(2011)Minimal Gröbner bases and the predictable leading monomial propertyLinear Algebra and its Applications10.1016/j.laa.2010.08.030434:1(104-116)Online publication date: Jan-2011
https://doi.org/10.1016/j.laa.2010.08.030
Byrne EMora T(2009)Gröbner Bases over Commutative Rings and Applications to Coding TheoryGröbner Bases, Coding, and Cryptography10.1007/978-3-540-93806-4_14(239-261)Online publication date: 21-May-2009
https://doi.org/10.1007/978-3-540-93806-4_14
Kandri-Rody AKapur DNarendran P(2005)An ideal-theoretic approach to word problems and unification problems over finitely presented commutative algebrasRewriting Techniques and Applications10.1007/3-540-15976-2_17(345-364)Online publication date: 29-May-2005
https://doi.org/10.1007/3-540-15976-2_17
Show More Cited By

Index Terms

Canonical representatives for residue classes of a polynomial ideal
1. Computing methodologies
  1. Symbolic and algebraic manipulation

Recommendations

Certain classes of polynomial expansions and multiplication formulas

The authors first present a class of expansions in a series of Bernoulli polyomials and then show how this general result can be applied to yield various (known or new) polynomial expansions. The corresponding expansion problem involving the Euler ...
Computing a Gröbner basis of a polynomial ideal over a Euclidean domain

An algorithm for computing a Grobner basis of a polynomial ideal over a Euclidean domain is presented. The algorithm takes an ideal specified by a finite set of polynomials as its input; it produces another finite basis of the same ideal with the ...
Rational simplification modulo a polynomial ideal
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

We present two algorithms for simplifying rational expressions modulo an ideal of the polynomial ring k[x₁, . . . , x_n]. The first method generates the set of equivalent expressions as amodule over k[x₁, . . . , x_n] and computes a reduced Gröbner basis. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SYMSAC '76: Proceedings of the third ACM symposium on Symbolic and algebraic computation

August 1976

393 pages

ISBN:9781450377904

DOI:10.1145/800205

Copyright © 1976 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SYMSAC: SYMSAC

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 August 1976

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
260
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)4

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kuijper MSchindelar K(2011)Minimal Gröbner bases and the predictable leading monomial propertyLinear Algebra and its Applications10.1016/j.laa.2010.08.030434:1(104-116)Online publication date: Jan-2011
https://doi.org/10.1016/j.laa.2010.08.030
Byrne EMora T(2009)Gröbner Bases over Commutative Rings and Applications to Coding TheoryGröbner Bases, Coding, and Cryptography10.1007/978-3-540-93806-4_14(239-261)Online publication date: 21-May-2009
https://doi.org/10.1007/978-3-540-93806-4_14
Kandri-Rody AKapur DNarendran P(2005)An ideal-theoretic approach to word problems and unification problems over finitely presented commutative algebrasRewriting Techniques and Applications10.1007/3-540-15976-2_17(345-364)Online publication date: 29-May-2005
https://doi.org/10.1007/3-540-15976-2_17
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
Buchberger B(2005)A critical-pair/completion algorithm for finitely generated ideals in ringsLogic and Machines: Decision Problems and Complexity10.1007/3-540-13331-3_39(137-161)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-13331-3_39
Winkler F(2005)An algorithm for constructing detaching bases in the ring of polynomials over a fieldComputer Algebra10.1007/3-540-12868-9_101(168-179)Online publication date: 29-May-2005
https://doi.org/10.1007/3-540-12868-9_101
Buchberger B(2005)A criterion for detecting unnecessary reductions in the construction of Gröbner-basesSymbolic and Algebraic Computation10.1007/3-540-09519-5_52(3-21)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-09519-5_52
Möller H(1988)On the construction of Gröbner bases using syzygiesJournal of Symbolic Computation10.1016/S0747-7171(88)80052-X6:2-3(345-359)Online publication date: 1-Dec-1988
https://dl.acm.org/doi/10.1016/S0747-7171%2888%2980052-X
Bach E(1987)Realistic analysis of some randomized algorithmsProceedings of the nineteenth annual ACM symposium on Theory of computing10.1145/28395.28444(453-461)Online publication date: 1-Jan-1987
https://dl.acm.org/doi/10.1145/28395.28444
Bronstein M(1986)Gsolve: a faster algorithm for solving systems of algebraic equationsProceedings of the fifth ACM symposium on Symbolic and algebraic computation10.1145/32439.32489(247-249)Online publication date: 1-Oct-1986
https://dl.acm.org/doi/10.1145/32439.32489
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents