Enumeration of generalized BCI lambda-terms

zbMATH Open1295.05040arXiv1305.0640MaRDI QIDQ396960FDOQ396960

Authors: Olivier Bodini, Bernhard Gittenberger, Alice Jacquot, Danièle Gardy 

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We investigate the asymptotic number of elements of size $n$ in a particular class of closed lambda-terms (so-called $BCI(p)$-terms) which are related to axiom systems of combinatory logic. By deriving a differential equation for the generating function of the counting sequence we obtain a recurrence relation which can be solved asymptotically. We derive differential equations for the generating functions of the counting sequences of other more general classes of terms as well: the class of $BCK(p)$-terms and that of closed lambda-terms. Using elementary arguments we obtain upper and lowerestimates for the number of closed lambda-terms of size $n$. Moreover, a recurrence relation is derived which allows an efficient computation of the counting sequence. $BCK(p)$-terms are discussed briefly.

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

Recommendations

• On the asymptotic number of BCK(2)-terms
• Asymptotics and random sampling for BCI and BCK lambda terms
• Counting and generating lambda terms
• Combinatorics of \(\lambda\)-terms: a natural approach
• A natural counting of lambda terms

Mathematics Subject Classification ID

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

Cited In (17)

• Asymptotics and random sampling for BCI and BCK lambda terms
• Families of Monotonic Trees: Combinatorial Enumeration and Asymptotics
• Statistical properties of lambda terms
• On the enumeration of closures and environments with an application to random generation
• Asymptotic enumeration of compacted binary trees of bounded right height
• Enumerators of lambda terms are reducing constructively
• On the asymptotic number of BCK(2)-terms
• Asymptotic properties of 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
• How big is BCI fragment of BCK logic
• Counting and generating terms in the binary lambda calculus
• Bijections between planar maps and planar linear normal \(\lambda\)-terms with connectivity condition
• On the number of variables in special classes of random lambda-terms
• Title not available (Why is that?)
• Enumerating lambda terms by weighted length of their de Bruijn representation
• On the number of unary-binary tree-like structures with restrictions on the unary height

This page was built for publication: Enumeration of generalized BCI lambda-terms

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