Enumeration of generalized BCI lambda-terms

MaRDI QIDQ396960zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1305.0640, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p30

Mathematics Subject Classification ID

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

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.

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

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
• scientific article; zbMATH DE number 845591 (Why is no real title available?)
• 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)