Name
Abstract | ||
|---|---|---|
We consider combinatorial aspects of lambda-terms in the model based on de Bruijn indices where each building constructor is of size one. Surprisingly, the counting sequence for lambda-terms corresponds also to two families of binary trees, namely black-white trees and zigzag-free ones. We provide a constructive proof of this fact by exhibiting appropriate bijections. Moreover, we identify the sequence of Motzkin numbers with the counting sequence for neutral lambda-terms, giving a bijection which, in consequence, results in an exact-size sampler for the latter based on the exact-size sampler for Motzkin trees of Bodini et alli. Using the powerful theory of analytic combinatorics, we state several results concerning the asymptotic growth rate of lambda-terms in neutral, normal, and head normal forms. Finally, we investigate the asymptotic density of lambda-terms containing arbitrary fixed subterms showing that, inter alia, strongly normalising or typeable terms are asymptotically negligible in the set of all lambda-terms. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1093/logcom/exx018 | JOURNAL OF LOGIC AND COMPUTATION |
Keywords | Field | DocType |
Lambda calculus,combinatorics,asymptotic density,functional programming | Analytic combinatorics,Discrete mathematics,Combinatorics,Constructive proof,Bijection,Algorithm,Binary tree,Bijection, injection and surjection,De Bruijn sequence,Natural density,Mathematics,Lambda | Journal |
Volume | Issue | ISSN |
27 | 8 | 0955-792X |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maciej Bendkowski | 1 | 13 | 5.47 |
| Katarzyna Grygiel | 2 | 44 | 6.95 |
| Pierre Lescanne | 3 | 925 | 123.70 |
| Marek Zaionc | 4 | 111 | 17.27 |