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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01229794
Contributor : Pierre Lescanne <>
Submitted on : Tuesday, November 17, 2015 - 11:11:05 AM
Last modification on : Friday, February 8, 2019 - 10:40:29 AM
Long-term archiving on : Friday, April 28, 2017 - 4:03:17 PM

Files

Grygiel_Lescanne_ArXiv.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

148

Files downloads

201