Counting Terms in the Binary Lambda Calculus

Abstract : In a paper entitled Binary lambda calculus and combinatory logic, John Tromp presents a simple way of encoding lambda calculus terms as binary sequences. In what follows, we study the numbers of binary strings of a given size that represent lambda terms and derive results from their generating functions, especially that the number of terms of size n grows roughly like 1.963447954^n.
Type de document :
Communication dans un congrès
DMTCS. 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Jun 2014, Paris, France. pp.13, 2014, Discrete Mathematics & Theoretical Computer Science
Liste complète des métadonnées

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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00923203
Contributeur : Pierre Lescanne <>
Soumis le : jeudi 2 janvier 2014 - 08:15:13
Dernière modification le : mardi 24 avril 2018 - 13:52:47
Document(s) archivé(s) le : samedi 8 avril 2017 - 09:29:47

Fichiers

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

Identifiants

  • HAL Id : ensl-00923203, version 1
  • ARXIV : 1401.0379

Collections

Citation

Katarzyna Grygiel, Pierre Lescanne. Counting Terms in the Binary Lambda Calculus. DMTCS. 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Jun 2014, Paris, France. pp.13, 2014, Discrete Mathematics & Theoretical Computer Science. 〈ensl-00923203〉

Partager

Métriques

Consultations de la notice

329

Téléchargements de fichiers

379