Geodesic
Enumeration of generalized BCI lambda-terms
The electronic journal of combinatorics, Tome 20 (2013) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 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. $BCK(p)$-terms are discussed briefly.
DOI : 10.37236/3051
Classification : 05A16, 03B40 
@article{10_37236_3051,
     author = {Olivier Bodini and Dani\`ele Gardy and Bernhard Gittenberger and Alice Jacquot},
     title = {Enumeration of generalized {BCI} lambda-terms},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {4},
     doi = {10.37236/3051},
     zbl = {1295.05040},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3051/}
}
TY  - JOUR
AU  - Olivier Bodini
AU  - Danièle Gardy
AU  - Bernhard Gittenberger
AU  - Alice Jacquot
TI  - Enumeration of generalized BCI lambda-terms
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3051/
DO  - 10.37236/3051
ID  - 10_37236_3051
ER  - 
%0 Journal Article
%A Olivier Bodini
%A Danièle Gardy
%A Bernhard Gittenberger
%A Alice Jacquot
%T Enumeration of generalized BCI lambda-terms
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/3051/
%R 10.37236/3051
%F 10_37236_3051
Olivier Bodini; Danièle Gardy; Bernhard Gittenberger; Alice Jacquot. Enumeration of generalized BCI lambda-terms. The electronic journal of combinatorics, Tome 20 (2013) no. 4. doi: 10.37236/3051

Cité par Sources :