Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

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 metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Pierre Lescanne Connect in order to contact the contributor
Submitted on : Tuesday, November 17, 2015 - 11:11:05 AM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM
Long-term archiving on: : Friday, April 28, 2017 - 4:03:17 PM


Files produced by the author(s)


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



Katarzyna Grygiel, Pierre Lescanne. Counting and Generating Terms in the Binary Lambda Calculus (Extended version). {date}. ⟨ensl-01229794⟩



Record views


Files downloads