Counting Terms in the Binary Lambda Calculus

2014/01/02 by Grygiel, Katarzyna, Lescanne, Pierre
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1401.0379

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ⁿ.

Related

• On the number of lambda terms with prescribed size of their De Bruijn\n representation
• Enumerating Lambda Terms by Weighted Length of Their De Bruijn\n Representation
• Counting and generating lambda terms
• Binary Lambda Calculus and Combinatory Logic
• A natural counting of lambda terms