Reduction graphs in the lambda calculus

DOI10.1016/0304-3975(84)90002-1MaRDI QIDQ792994zbMATH OpenOpenAlexFDO

Authors Marisa Venturini Zilli

Publication date 1984

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(84)90002-1

zbMATH Keywords

lambda calculusreduction graphs of lambda termsspectrum

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40)

Review text

The author studies some properties of the reduction graphs of lambda terms and she gives the characterization of some classes of reduction graphs. Condensed reduction graphs obtained by dividing out cyclic equivalence and spectra, i.e., the partially ordered set of all reductions, are also considered. Reductions to normal form and cofinal reductions are the most significant reductions. The spectrum is proved to be the completion of the condensed reduction graph.

Recommendations

• scientific article; zbMATH DE number 1546504
• Orders, reduction graphs and spectra
• scientific article; zbMATH DE number 3851045
• scientific article; zbMATH DE number 1523048
• Refining reduction in the lambda calculus

Cites work

• scientific article; zbMATH DE number 3851045 (Why is no real title available?)
• scientific article; zbMATH DE number 3672266 (Why is no real title available?)
• scientific article; zbMATH DE number 3730111 (Why is no real title available?)
• scientific article; zbMATH DE number 3609633 (Why is no real title available?)
• scientific article; zbMATH DE number 3280068 (Why is no real title available?)
• scientific article; zbMATH DE number 3423994 (Why is no real title available?)
• Infinite graphs—A survey
• Lambda-calculus terms that reduce to themselves
• Parallel concepts in graph theory
• The lambda calculus, its syntax and semantics
• Varieties of ordered algebras

Cited in

(13)

• Needed reduction and spine strategies for the lambda calculus
• One-step recurrent terms in \(\lambda\)-\(\beta\)-calculus
• Orders, reduction graphs and spectra
• Three Syntactic Theories for Combinatory Graph Reduction
• scientific article; zbMATH DE number 1546504 (Why is no real title available?)
• scientific article; zbMATH DE number 10088 (Why is no real title available?)
• scientific article; zbMATH DE number 1868923 (Why is no real title available?)
• Refining reduction in the lambda calculus
• Open problems in rewriting
• More problems in rewriting
• The combinator M and the Mockingbird lattice
• scientific article; zbMATH DE number 7084951 (Why is no real title available?)
• Anagopos: a reduction graph visualizer for term rewriting and lambda calculus

This page was built for publication: Reduction graphs in the lambda calculus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792994)