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).
Type de document :
Communication dans un congrès
Dirk Pattinson; Lutz Schröder. 11th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Mar 2012, Tallinn, Estonia. Springer, Lecture Notes in Computer Science, LNCS-7399, pp.130-149, 2012, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-642-32784-1_8〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01539877
Contributeur : Hal Ifip <>
Soumis le : jeudi 15 juin 2017 - 15:02:41
Dernière modification le : jeudi 15 juin 2017 - 15:25:49
Document(s) archivé(s) le : mercredi 13 décembre 2017 - 13:09:46

Fichier

978-3-642-32784-1_8_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Alexander Kurz, Daniela Petrişan, Paula Severi, Fer-Jan Vries. An Alpha-Corecursion Principle for the Infinitary Lambda Calculus. Dirk Pattinson; Lutz Schröder. 11th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Mar 2012, Tallinn, Estonia. Springer, Lecture Notes in Computer Science, LNCS-7399, pp.130-149, 2012, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-642-32784-1_8〉. 〈hal-01539877〉

Partager

Métriques

Consultations de la notice

32

Téléchargements de fichiers

25