Counting Terms in the Binary Lambda Calculus

Katarzyna Grygiel; Pierre Lescanne

Counting Terms in the Binary Lambda Calculus

Katarzyna Grygiel ¹ Pierre Lescanne ^{2, 3}

1 TCS - Theoretical Computer Science Department [Krakow]

2 LIP - Laboratoire de l'Informatique du Parallélisme

3 PLUME - Preuves et Langages

LIP - Laboratoire de l'Informatique du Parallélisme

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.

Keywords : lambda calculus combinatorics functional programming test random generator ranking unranking

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

Domaine :

Informatique [cs] / Algorithme et structure de données [cs.DS]

Informatique [cs] / Langage de programmation [cs.PL]

Informatique [cs] / Logique en informatique [cs.LO]

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

tromp_numbers.pdf

Fichiers produits par l'(les) auteur(s)

Counting Terms in the Binary Lambda Calculus

Fichiers

Identifiants

Collections

Citation

Exporter

Métriques

340

390

Contact

Counting Terms in the Binary Lambda Calculus

Fichiers

Identifiants

Collections

Citation

Exporter

Partager

Métriques

340

390

Contact