Optimal derivations in weak lambda-calculi and in orthogonal term rewriting systems
- 1 January 1991
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 255-269
- https://doi.org/10.1145/99583.99618
Abstract
We introduce the new framework of Labeled TermsRewriting Systems (TlRS), a general framework to expresssharing in Term Rewriting Systems (TRS). ForOrthogonal TlRS, an important subclass of TlRS, wecharacterize optimal derivations. This result is appliedto weak -calculi, showing the optimality of the lazystrategy, that is, the call-by-name with sharing strategy.The result is also valid in the presence of ffi -rules,as in PCF. Orthogonal TlRS is also useful as a calculus...Keywords
This publication has 0 references indexed in Scilit: