Combinatorics of -terms: a natural approach

DOI10.1093/LOGCOM/EXX018zbMATH Open1444.03017arXiv1609.07593OpenAlexW2963578516MaRDI QIDQ4555458FDOQ4555458

Authors: Maciej Bendkowski, Pierre Lescanne, Marek Zaionc, Katarzyna Grygiel 

Publication date: 20 November 2018

Published in: Journal Of Logic And Computation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1609.07593

Recommendations

• A natural counting of lambda terms
• Enumerating lambda terms by weighted length of their de Bruijn representation
• On counting untyped lambda terms
• Counting and generating lambda terms
• On the number of lambda terms with prescribed size of their de Bruijn representation

zbMATH Keywords

combinatoricsfunctional programmingasymptotic densitylambda-calculus

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Combinatory logic and lambda calculus (03B40)

Cited In (20)

• Asymptotics and random sampling for BCI and BCK lambda terms
• Enumeration of generalized BCI lambda-terms
• Statistical properties of lambda terms
• A correspondence between rooted planar maps and normal planar lambda terms
• On the enumeration of closures and environments with an application to random generation
• On the asymptotic number of BCK(2)-terms
• Asymptotic properties of combinatory logic
• Lambda terms definable as combinators
• Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
• On the likelihood of normalization in combinatory logic
• On some enumerative problems in lambda calculus
• Distribution of variables in lambda-terms with restrictions on De Bruijn indices and De Bruijn levels
• On uniquely closable and uniquely typable skeletons of lambda terms
• Counting environments and closures
• Theoretical PearlsEnumerators of lambda terms are reducing
• On the number of unary-binary tree-like structures with restrictions on the unary height
• A natural counting of lambda terms
• Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata
• On counting untyped lambda terms
• Unary profile of lambda terms with restricted De Bruijn indices

This page was built for publication: Combinatorics of \(\lambda\)-terms: a natural approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4555458)