Call by need computations to root-stable form

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Call by need computations to root-stable form

Full text

Pdf (932 KB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Paris, France

Pages: 94 - 105

Year of Publication: 1997

ISBN:0-89791-853-3

Author

Aart Middeldorp

Institute of Information Scinces and Electronics, University of Tsukuba, Tsukuba 305, Japan

Sponsors

L'Ecole des Mines de Paris : L'Ecole des Mines de Paris
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Ctr Natl de la Recherche Sci :
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 21, Citation Count: 9

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/263699.263711 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	Sergio Antoy , Aart Middeldorp, A sequential reduction strategy, Theoretical Computer Science, v.165 n.1, p.75-95, Sept. 30, 1996
	2	A. Arnold and M. Nivat. The Metric Space of infinite Trees. Algebraic and Topological Properties, Fundamenta Informaticae 4, pp. 445-476, 1980.
	3	H. P. Barendregt , J. R. Kennaway , J. W. Klop , M. R. Sleep, Needed reduction and spine strategies for the lambda calculus, Information and Computation, v.75 n.3, p.191-231, Dec. 1987 [doi>10.1016/0890-5401(87)90001-0]
	4	H. Comon, Sequentiality, Second-order Monadic Logic and Tree Automata, Proceedings of the 10th Annual IEEE Symposium on Logic in Computer Science, p.508, June 26-29, 1995
	5	Nachum Dershowitz , Jean-Pierre Jouannaud, Rewrite systems, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	6	G. Huet and J.-J. L6vy, Computations in Orthogohal Rewriting Systems, I and II, in: Computational Logic, Essays in Honor of Alan Robinson (eds. J.- L. Lassez and G. Plotkin), The MIT Press, pp. 396- 443, 1991. Previous version: Call by Need Computations in Non-Ambiguous Linear Term Rewriting Systems, report 359, INRIA, 1979.
	7	Florent Jacquemard, Decidable Approximations of Term Rewriting Systems, Proceedings of the 7th International Conference on Rewriting Techniques and Applications, p.362-376, July 27-30, 1996
	8	Richard Kennaway, A Conflict Between Call-by-Need Computation and Parallelism, Proceedings of the 4th International Workshop on Conditional and Typed Rewriting Systems, p.247-261, July 13-15, 1994
	9	Richard Kennaway , Jan Willem Klop , Ronan Sleep , Fer-Jan de Vries, Transfinite reductions in orthogonal term rewriting systems, Information and Computation, v.119 n.1, p.18-38, May 15, 1995 [doi>10.1006/inco.1995.1075]
	10	Zurab Khasidashvili, Optimal Normalization in Orthogonal Term Rewriting Systems, Proceedings of the 5th International Conference on Rewriting Techniques and Applications, p.243-258, June 16-18, 1993
	11	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
	12	L. Maranget, La Strategic Paresseuse, Th#se de Doctorat, Universit6 de Paris 7, 1992 (in French).
	13	Michael J. O'Donnell, Computing in Systems Described by Equations, Springer-Verlag New York, Inc., Secaucus, NJ, 1977
	14	Michio Oyamaguchi, NV-sequentiality: a decidable condition for call-by-need computations in term-rewriting systems, SIAM Journal on Computing, v.22 n.1, p.114-135, Feb. 1993 [doi>10.1137/0222010]
	15	R. C. Sekar , I. V. Ramakrishnan, Programming in equational logic: beyond strong sequentiality, Information and Computation, v.104 n.1, p.78-109, May 1993 [doi>10.1006/inco.1993.1026]

CITED BY 9

	Salvador Lucas, Context-sensitive rewriting strategies, Information and Computation, v.178 n.1, p.294-343, October 10, 2002
	Sergio Antoy , Bart Massey , Michael Hanus , Frank Steiner, An implementation of narrowing strategies, Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.207-217, September 05-07, 2001, Florence, Italy
	Rafael del Vado Vírseda, A demand-driven narrowing calculus with overlapping definitional trees, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.253-263, August 27-29, 2003, Uppsala, Sweden
	Santiago Escobar, Refining weakly outermost-needed rewriting and narrowing, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.113-123, August 27-29, 2003, Uppsala, Sweden
	Salvador Lucas, Strong and NV-sequentiality of constructor systems, Information Processing Letters, v.89 n.4, p.191-201, 28 February 2004
	María Alpuente , Moreno Falaschi , Ginés Moreno , Germán Vidal, Rules + strategies for transforming lazy functional logic programs, Theoretical Computer Science, v.311 n.1-3, p.479-525, 23 January 2004
	Irène Durand , Aart Middeldorp, Decidable call-by-need computations in term rewriting, Information and Computation, v.196 n.2, p.95-126, January 29, 2005
	Salvador Lucas, Proving termination of context-sensitive rewriting by transformation, Information and Computation, v.204 n.12, p.1782-1846, December, 2006
	Michael Hanus , Christian Prehofer, Higher-order narrowing with definitional trees, Journal of Functional Programming, v.9 n.1, p.33-75, January 1999