Skip to Main content Skip to Navigation
Conference papers

Counting Terms in the Binary Lambda Calculus

Katarzyna Grygiel 1 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
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
https://hal-ens-lyon.archives-ouvertes.fr/ensl-00923203
Contributor : Pierre Lescanne Connect in order to contact the contributor
Submitted on : Thursday, January 2, 2014 - 8:15:13 AM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM
Long-term archiving on: : Saturday, April 8, 2017 - 9:29:47 AM

Files

Vignette du document
tromp_numbers.pdf
Files produced by the author(s)

Identifiers

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

Collections

ENS-LYON | CNRS | INRIA | UNIV-LYON1 | LIP_PLUME | UDL

Citation

Katarzyna Grygiel, Pierre Lescanne. Counting Terms in the Binary Lambda Calculus. 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Jun 2014, Paris, France. pp.13. ⟨ensl-00923203⟩

Export

BibTeX TEI DC DCterms EndNote Datacite

Share

Metrics

Record views

251

Files downloads

496