Cyclic lambda graph rewriting
- 17 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 416-425
- https://doi.org/10.1109/lics.1994.316066
Abstract
This paper is concerned with the study of cyclic -graphs. The starting point is to treat a -graph as asystem of recursion equations involving -terms, andto manipulate such systems in an unrestricted manner,using equational logic, just as is possible for firstorderterm rewriting. Surprisingly, now the confluenceproperty breaks down in an essential way.Confluence can be restored by introducing a restrainingmechanism on the `copying" operation. Thisleads to a family of -graph calculi,...Keywords
This publication has 13 references indexed in Scilit:
- Syntactic definitions of undefined: On defining the undefinedPublished by Springer Nature ,1994
- Combinatory reduction systems: introduction and surveyTheoretical Computer Science, 1993
- Categorical Combinators, Sequential Algorithms, and Functional ProgrammingPublished by Springer Nature ,1993
- EditorialJournal of Logic and Computation, 1992
- The geometry of optimal lambda reductionPublished by Association for Computing Machinery (ACM) ,1992
- Explicit substitutionsJournal of Functional Programming, 1991
- Transfinite reductions in orthogonal term rewriting systemsPublished by Springer Nature ,1991
- An algorithm for optimal lambda calculus reductionPublished by Association for Computing Machinery (ACM) ,1990
- Lambda lifting: Transforming programs to recursive equationsPublished by Springer Nature ,1985
- Super-combinators a new implementation method for applicative languagesPublished by Association for Computing Machinery (ACM) ,1982