Unification in commutative theories, Hilbert's basis theorem, and Gröbner bases

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Unification in commutative theories, Hilbert's basis theorem, and Gröbner bases

Full text

Pdf (1.88 MB)

Source

Journal of the ACM (JACM) archive
Volume 40 , Issue 3 (July 1993) table of contents

Pages: 477 - 503

Year of Publication: 1993

ISSN:0004-5411

Author

Franz Baader

German Research Center for Artificial Intelligence (DFKI), Saarbru¨cken, Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 62, Citation Count: 2

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/174130.174133 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	J. Apel , W. Lassner, An extension of Buchberger's algorithm and calculations in enveloping fields of lie algebras, Journal of Symbolic Computation, v.6 n.2-3, p.361-370, Oct./Dec. 1988 [doi>10.1016/S0747-7171(88)80053-1]
	2	Franz Baader, The theory of idempotent semigroups is of unification type zero, Journal of Automated Reasoning, v.2 n.3, p.283-286, Aug. 1987 [doi>10.1007/BF02328451]
	3	~BAADER, F. Unification in varieties of idempotent semigroups. Semigroup Forum 36 (1987), ~127-145.
	4	F. Baader, Unification in commutative theories, Journal of Symbolic Computation, v.8 n.5, p.479-497, Nov. 1989 [doi>10.1016/S0747-7171(89)80055-0]
	5	Franz Baader, Unification Properties of Commutative Theories: A Categorical Treatment, Category Theory and Computer Science, p.273-299, September 05-08, 1989
	6	Franz Baader , Wolfram Büttner, Unification in commutative idempotent monoids, Theoretical Computer Science, v.56 n.3, p.345-353, March, 1988 [doi>10.1016/0304-3975(88)90140-5]
	7	Franz Baader , Werner Nutt, Adding homomorphisms to commutative/monoidal theories or how algebra can help in equational unification, Proceedings of the 4th international conference on Rewriting techniques and applications, p.124-135, March 1991, Como, Italy
	8	L. Bachmair , B. Buchberger, A simplified proof of the characterization theorem for Gröbner-bases, ACM SIGSAM Bulletin, v.14 n.4, p.29-34, November 1980 [doi>10.1145/1089235.1089238]
	9	~BUCHBERGER, B. Gr6bner bases: An algorithmic method in polynomial ideal theory. In ~Recent Trends in Multidimensional System Theory, N. K. Bose, ed., Reidel, Dordrecht, Ger- ~many, 1985, pp. {84-232.
	10	Wolfram Büttner, Unification in datastructure multisets, Journal of Automated Reasoning, v.2 n.1, p.75-88, 1986
	11	~COHN.P.MUniversal Algebra. Harper and row ,New york,1965.
	12	Nachum Dershowitz , Zohar Manna, Proving termination with multiset orderings, Communications of the ACM, v.22 n.8, p.465-476, Aug. 1979 [doi>10.1145/359138.359142]
	13	~DICKSON, L. E. Finiteness of the odd perfect and primitive abundant numbers with n ~distinct factors. Amer. J. Math. 35 (1913), 413 422.
	14	Samuel Eilenberg, Automata, Languages, and Machines, Academic Press, Inc., Orlando, FL, 1974
	15	François Fages, Associative-Commutative Unification, Proceedings of the 7th International Conference on Automated Deduction, p.194-208, May 14-16, 1984
	16	F Fages , G Huet, Complete sets of unifiers and matchers in equational theories, Theoretical Computer Science, v.43 n.2-3, p.189-200, July 1986
	17	Albrecht Fortenbacher, An algebraic approach to unification under associativity and commutativity, Proc. of the first international conference on Rewriting techniques and applications, p.381-397, December 1985, Dijon, France
	18	~FREYD, P. Abelian Categories. Harper and Row, New York, 1964.
	19	A. Furukawa , T. Sasaki , H. Kobayashi, The Grobner basis of a module over KUX1,...,Xne and polynomial solutions of a system of linear equations, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.222-224, July 21-23, 1986, Waterloo, Ontario, Canada [doi>10.1145/32439.32483]
	20	~GRXTZER, G. Universal Algebra. Van Nostrand Company, Princeton, N.J., 1968.
	21	~HEROLD, A. Combination of unification algorithms in equational theories, Ph.D. Disserta- ~tion, Universitiit Kaiserslautern, 1987.
	22	~HERRHCH, H., AND STRECKER, G.E. Category Theory. Allyn and Bacon, Boston, Mass., 1973.
	23	Gérard Huet, Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems, Journal of the ACM (JACM), v.27 n.4, p.797-821, Oct. 1980 [doi>10.1145/322217.322230]
	24	~JACOBSON, N. Basic Algebra H. Freeman and Company, San Francisco, Calif., 1980.
	25	~JAFFAR, J., LASSEZ, J. L., AND MAHER, M. J. A theory of complete logic programs with ~equality. J. Logic Prog. 1 (1984), 175-184.
	26	Jean-Pierre Jouannaud , Hélène Kirchner, Completion of a set of rules modulo a set of equations, SIAM Journal on Computing, v.15 n.4, p.1155-1194, Nov. 1986 [doi>10.1137/0215084]
	27	Abdelilah Kandri-Rody , Deepak Kapur, Algorithms for Computing Groebner Bases of Polynomial Ideals over Various Euclidean Rings, Proceedings of the International Symposium on Symbolic and Algebraic Computation, p.195-206, July 09-11, 1984
	28	~KANDRI-RODY, A., AND KAPUR, D. An algorithms for computing the Gr6bner basis of a ~polynomial ideal over a Euclidean ring. General Electric Research and Development Report ~No. 84CRD045. General Electric, Schnectady, N.Y.
	29	A. Kandri-Rody , D. Kapur, Computing a Gro¨bner basis of a polynomial ideal over a Euclidian domain, Journal of Symbolic Computation, v.6 n.1, p.37-57, August 1988 [doi>10.1016/S0747-7171(88)80020-8]
	30	A. Kandr-Rody , V. Weispfenning, Non-commutative Gro¨bner bases in algebras of solvable type, Journal of Symbolic Computation, v.9 n.1, p.1-26, Jan. 1990 [doi>10.1016/S0747-7171(08)80003-X]
	31	Werner Kuich , Arto Salomaa, Semirings, Automata and Languages, Springer-Verlag New York, Inc., Secaucus, NJ, 1985
	32	~LANKFORD, D., BUTLER, G., AND BRADY, B. Abelian group unification algorithms for ~elementary terms. Cont. Math. 29 (1984), 193-199.
	33	~LEEB, K., AND PIRmLO, G. Shuffle-compatible total orders. Ann. Mat. PuraAppl. 153 (1988), ~1-26.
	34	~LIVESEY, M., AND SIEKMANN, J. Unification in sets and multisets. SEKI Tech. Rep. ~universitiit Karlsruhe.
	35	~MARTIN, U. A geometrical approach to multiset orderings. Tech. Rep. Univ. London, ~London, England, 1988.
	36	Ferdinando Mora, Groebner Bases for Non-Commutative Polynomial Rings, Proceedings of the 3rd International Conference on Algebraic Algorithms and Error-Correcting Codes, p.353-362, July 15-19, 1985
	37	~NUTT, W. Talk at the second workshop on unification (Val d' Ajol, France), 1988.
	38	Wern Nutt, Unification in monoidal theories, Proceedings of the tenth international conference on Automated deduction, p.618-632, July 1990, Kaiserslautern, Germany
	39	~PLOTKIN, G. Building in equational theories. Mach. hzt. 7 (1972), 73-90.
	40	Lorenzo Robbiano, Term Orderings on the Polynominal Ring, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.513-517, April 01-03, 1985
	41	D E Rydeheard , R M Burstall, A categorical unification algorithm, Proceedings of a tutorial and workshop on Category theory and computer programming, p.493-505, November 1986, Guildford, United Kingdom
	42	Manfred Schmidt-Schauss, Unification under associativity and idempotence is of type nullary, Journal of Automated Reasoning, v.2 n.3, p.277-281, Aug. 1987 [doi>10.1007/BF02328450]
	43	Jörg H. Siekmann, Unification theory, Journal of Symbolic Computation, v.7 n.3-4, p.207-274, March/April 1989 [doi>10.1016/S0747-7171(89)80012-4]
	44	Mark E. Stickel, A Unification Algorithm for Associative-Commutative Functions, Journal of the ACM (JACM), v.28 n.3, p.423-434, July 1981 [doi>10.1145/322261.322262]
	45	M E Stickel, Automated deduction by theory resolution, Journal of Automated Reasoning, v.1 n.4, p.333-355, 1985
	46	~TREVISAN, G. Classificazione dei semplici ordinamenti di un gruppo libero commutativo con ~m generatori. Rendiconti clel Semhzado Matematico della Universita di Padot,a 22 (1953), 143.
	47	~ZAICEVA, M.I. On the set of ordered Abelian groups. Uspehi Matern. Nauk (N.S.) 8 0953), ~ 135-137.

CITED BY 2

	Thierry Boy de la Tour , Mnacho Echenim, Permutative rewriting and unification, Information and Computation, v.205 n.4, p.624-650, April, 2007
	Stéphanie Delaune , Pascal Lafourcade , Denis Lugiez , Ralf Treinen, Symbolic protocol analysis for monoidal equational theories, Information and Computation, v.206 n.2-4, p.312-351, February, 2008