Termination for direct sums of left-linear complete term rewriting systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Termination for direct sums of left-linear complete term rewriting systems

Full text

Pdf (1.78 MB)

Source

Journal of the ACM (JACM) archive
Volume 42 , Issue 6 (November 1995) table of contents

Pages: 1275 - 1304

Year of Publication: 1995

ISSN:0004-5411

Authors

Y. Toyama	JAIST, Tatsunokuchi, Ishikawa, Japan
J. W. Klop	CWI, Amsterdam, and Free Univ., Amsterdam, The Netherlands
H. P. Barendregt	Catholic Univ., Nijmegen, The Netherlands

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms 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/227683.227689 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	L Bachmair , N Dershowitz, Commutation, transformation, and termination, Proc. of the 8th international conference on Automated deduction, p.5-20, August 1986, Oxford, United Kingdom
	2	Val Tannen , Jean H. Gallier, Polymorphic Rewriting Conserves Algebraic Strong Normalization and Confluence, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.137-150, July 11-15, 1989
	3	Nachum Dershowitz, Termination of Linear Rewriting Systems (Preliminary Version), Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.448-458, July 13-17, 1981
	4	Nachum Dershowitz , Jean-Pierre Jouannaud, Rewrite systems, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	5	~GANZINGER, H., AND G-IEGERICH, R. 1987. A note on termination in combinations of heteroge- ~nous term rewriting systems. In Bulletin of the EATCS (European Association for Theoretical ~Computer Science), vol. 37. (Feb.). Mohien, Paderborn, Germany, pp. 22-28.
	6	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]
	7	~HUET, G., AND OPPEN, D.C. 1980. Equations and rewrite rules: A survey. In Formal Language ~Theory: Perspectives and Open Problems, R. Book, ed. Academic Press, London, England, ~pp. 349-405.
	8	J. W. Klop, Term rewriting systems, Handbook of logic in computer science (vol. 2): background: computational structures, Oxford University Press, Inc., New York, NY, 1993
	9	Jan Willem Klop , Aart Middeldorp , Yoshihito Toyama , Roel de Vrijer, Modularity of confluence: a simplified proof, Information Processing Letters, v.49 n.2, p.101-109, Jan. 28, 1994 [doi>10.1016/0020-0190(94)90034-5]
	10	M. Kurihara , I. Kaji, Modular term rewriting systems and the termination, Information Processing Letters, v.34 n.1, p.1-4, February 1990 [doi>10.1016/0020-0190(90)90221-I]
	11	~KURIHARA, M., AND OHUCHI, A. 1989/1990. Modularity of simple termination of term rewrt- ~ing systems. Rep. 89~SF-31, Hokkaido Univ., Sapporo, Japan. (Also in J. 1PS Japan 31, 5, ~633-642.)
	12	A. Middeldorp, A sufficient condition for the termination of the direct sum of term rewriting systems, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.396-401, June 1989, Pacific Grove, California, United States
	13	A. Middeldorp, Modular aspects of properties of term rewriting systems related to normal forms, Proceedings of the 3rd international conference on Rewriting Techniques and Applications, p.163-277, January 1989
	14	~MIDDELDORP, A. 1990. Modular properties of term rewriting systems. Ph.D. dissertation. Free ~Univ. Amsterdam, Amsterdam, The Netherlands.
	15	Aart Middeldorp , Yoshihito Toyama, Completeness of combinations of constructor systems, Proceedings of the 4th international conference on Rewriting techniques and applications, p.188-199, March 1991, Como, Italy
	16	M. Okada, Strong normalizability for the combined system of the typed lmbda calculus and an arbitrary convergent term rewrite system, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.357-363, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74582]
	17	Michael Rusinowitch, On termination of the direct sum of term-rewriting systems, Information Processing Letters, v.26 n.2, p.65-70, 19 Oct. 1987 [doi>10.1016/0020-0190(87)90039-1]
	18	Yoshihito Toyama, On the Church-Rosser property for the direct sum of term rewriting systems, Journal of the ACM (JACM), v.34 n.1, p.128-143, Jan. 1987 [doi>10.1145/7531.7534]
	19	Yoshihito Toyama, Counterexamples to termination for the direct sum of term rewriting systems, Information Processing Letters, v.25 n.3, p.141-143, May 29, 1987 [doi>10.1016/0020-0190(87)90122-0]
	20	~TOYAMA, Y. 1988. Commutativity of term rewriting systems. In Programming of Future Genera- ~tion Computers H, K. Fuchi and L. Kott, eds. North-Holland, Amsterdam, The Netherlands, pp. ~393-407.
	21	Y. Toyama , J. W. Klop , H. P. Barendregt, Termination for the direct sum of left-linear term rewriting systems, Proceedings of the 3rd international conference on Rewriting Techniques and Applications, p.477-491, January 1989

CITED BY 2

	Bernhard Gramlich , Salvador Lucas, Modular termination of context-sensitive rewriting, Proceedings of the 4th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.50-61, October 06-08, 2002, Pittsburgh, PA, USA
	Jürgen Giesl , Thomas Arts , Enno Ohlebusch, Modular termination proofs for rewriting using dependency pairs, Journal of Symbolic Computation, v.34 n.1, p.21-58, July 2002