Counting and Generating Terms in the Binary Lambda Calculus (Extended version)

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. In a second part we use this approach to generate random lambda terms using Boltzmann samplers.
Type de document :
Pré-publication, Document de travail
2015
Liste complète des métadonnées

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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01229794
Contributeur : Pierre Lescanne <>
Soumis le : mardi 17 novembre 2015 - 11:11:05
Dernière modification le : mardi 16 janvier 2018 - 15:36:04
Document(s) archivé(s) le : vendredi 28 avril 2017 - 16:03:17

Fichiers

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

Identifiants

  • HAL Id : ensl-01229794, version 1
  • ARXIV : 1511.05334

Collections

Citation

Katarzyna Grygiel, Pierre Lescanne. Counting and Generating Terms in the Binary Lambda Calculus (Extended version). 2015. 〈ensl-01229794〉

Partager

Métriques

Consultations de la notice

99

Téléchargements de fichiers

120