[Zurück]

B. Gittenberger:
"On the number of Lambda terms with prescribed size of their De Bruijn representation";
in: "33rd Symposium on Theoretical Aspects of Computer Science", 40; STACS 2016 - Leibniz International Proceedings in Informatics (LIPIcs), 2016, S. 1 - 13.

John Tromp introduced the so-called ´binary lambda calculus´ as a way to encode lambda terms in
terms of 0−1-strings. Later, Grygiel and Lescanne conjectured that the number of binary lambda
terms with m free indices and of size n (encoded as binary words of length n) is o
for τ ≈ 1.963448 . . .. We generalize the proposed notion of size and show that for several classes
of lambda terms, including binary lambda terms with m free indices, the number of terms of
size n is Θ

n
−3/2
ρ
−n

with some class dependent constant ρ, which in particular disproves the
above mentioned conjecture. A way to obtain lower and upper bounds for the constant near the
leading term is presented and numerical results for a few previously introduced classes of lambda
terms are given.