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

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

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.

Review text

Summary: We investigate the asymptotic number of elements of size \(n\) in a particular class of closed lambda-terms (so-called \(\mathrm{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 \(\mathrm{BCK}(p)\)-terms and that of closed lambda-terms. Using elementary arguments we obtain upper and lower estimates 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. \(\mathrm{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

(20)

• 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
• Enumerators of lambda terms are reducing constructively
• On some enumerative problems in lambda calculus
• Asymptotic enumeration of compacted binary trees of bounded right height
• Statistical properties of lambda terms
• Asymptotic properties of combinatory logic
• Asymptotics and random sampling for BCI and BCK lambda terms
• scientific article; zbMATH DE number 845591 (Why is no real title available?)
• On the enumeration of closures and environments with an application to random generation
• On the number of variables in special classes of random lambda-terms
• Families of Monotonic Trees: Combinatorial Enumeration and Asymptotics
• On properties of \(B\)-terms
• On the asymptotic number of BCK(2)-terms
• 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
• Asymptotic distribution of parameters in trivalent maps and linear lambda terms
• Bijections between planar maps and planar linear normal -terms with connectivity condition

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)