Skip to Main content Skip to Navigation
Conference papers

An Alpha-Corecursion Principle for the Infinitary Lambda Calculus

Abstract : Gabbay and Pitts proved that lambda-terms up to alpha-equivalence constitute an initial algebra for a certain endofunctor on the category of nominal sets. We show that the terms of the infinitary lambda-calculus form the final coalgebra for the same functor. This allows us to give a corecursion principle for alpha-equivalence classes of finite and infinite terms. As an application, we give corecursive definitions of substitution and of infinite normal forms (Böhm, Lévy-Longo and Berarducci trees).
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01539877
Contributor : Hal Ifip <>
Submitted on : Thursday, June 15, 2017 - 3:02:41 PM
Last modification on : Thursday, June 15, 2017 - 3:25:49 PM
Long-term archiving on: : Wednesday, December 13, 2017 - 1:09:46 PM

File

978-3-642-32784-1_8_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Alexander Kurz, Daniela Petrişan, Paula Severi, Fer-Jan Vries. An Alpha-Corecursion Principle for the Infinitary Lambda Calculus. 11th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Mar 2012, Tallinn, Estonia. pp.130-149, ⟨10.1007/978-3-642-32784-1_8⟩. ⟨hal-01539877⟩

Share

Metrics

Record views

96

Files downloads

161