Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/12689
Title: | Confluence of untyped lambda calculus via simple types | Authors: | Gilezan, Silvia Kunčak V. |
Issue Date: | 1-Jan-2001 | Journal: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Abstract: | © Springer-Verlag Berlin Heidelberg 2001. We present a new proof of confluence of the untyped lambda calculus by reducing the confluence of β-reduction in the untyped lambda calculus to the confluence of β-reduction in the simply typed lambda calculus. This is achieved by embedding typed lambda terms into simply typed lambda terms. Using this embedding, an auxiliary reduction, and β-reduction on simply typed lambda terms we define a new reduction on all lambda terms. The transitive closure of the reduction defined is β-reduction on all lambda terms. This embedding allows us to use the confluence of β-reduction on simply typed lambda terms and thus prove the confluence of the reduction defined. As a consequence we obtain the confluence of β-reduction in the untyped lambda calculus. | URI: | https://open.uns.ac.rs/handle/123456789/12689 | ISBN: | 9783540454465 | ISSN: | 3029743 |
Appears in Collections: | FTN Publikacije/Publications |
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.