A NATURAL COUNTING OF LAMBDA TERMS

Abstract : We study the sequences of numbers corresponding to lambda terms of given sizes, where the size is this of lambda terms with de Bruijn indices in a very natural model where all the operators have size 1. For plain lambda terms, the sequence corresponds to two families of binary trees for which we exhibit bijections. We study also the distribution of normal forms, head normal forms and strongly normalizing terms. In particular we show that strongly normalizing terms are of density 0 among plain terms.
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01159746
Contributeur : Pierre Lescanne <>
Soumis le : vendredi 13 mai 2016 - 15:19:32
Dernière modification le : mardi 24 avril 2018 - 13:52:47

Fichiers

natural_counting.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-01159746, version 3
  • ARXIV : 1506.02367

Collections

Citation

Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, Marek Zaionc. A NATURAL COUNTING OF LAMBDA TERMS. 2016. 〈ensl-01159746v3〉

Partager

Métriques

Consultations de la notice

324

Téléchargements de fichiers

161