Geodesic
On some enumerative problems of lambda calculus
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part X, Tome 475 (2018), pp. 99-121 
E. C. Krasko; I. N. Labutin; D. N. Moskvin; A. V. Omelchenko; A. I. Khrabrov. On some enumerative problems of lambda calculus. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part X, Tome 475 (2018), pp. 99-121. http://geodesic.mathdoc.fr/item/ZNSL_2018_475_a4/
@article{ZNSL_2018_475_a4,
     author = {E. C. Krasko and I. N. Labutin and D. N. Moskvin and A. V. Omelchenko and A. I. Khrabrov},
     title = {On some enumerative problems of lambda calculus},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {99--121},
     year = {2018},
     volume = {475},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2018_475_a4/}
}
TY  - JOUR
AU  - E. C. Krasko
AU  - I. N. Labutin
AU  - D. N. Moskvin
AU  - A. V. Omelchenko
AU  - A. I. Khrabrov
TI  - On some enumerative problems of lambda calculus
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2018
SP  - 99
EP  - 121
VL  - 475
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2018_475_a4/
LA  - ru
ID  - ZNSL_2018_475_a4
ER  - 
%0 Journal Article
%A E. C. Krasko
%A I. N. Labutin
%A D. N. Moskvin
%A A. V. Omelchenko
%A A. I. Khrabrov
%T On some enumerative problems of lambda calculus
%J Zapiski Nauchnykh Seminarov POMI
%D 2018
%P 99-121
%V 475
%U http://geodesic.mathdoc.fr/item/ZNSL_2018_475_a4/
%G ru
%F ZNSL_2018_475_a4

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

The article considers combinatorial problems associated with the enumeration of lambda-terms in a untyped lambda calculus, as well as in simply typed systems with a single atom in the style of Church. For the case of untyped lambda calculus a system of equations for generating functions is constructed which describes the number of lambda terms. In the case of typed lambda calculus, both the inhabited types and the simplest inhabitants in them are enumerated.

[1] P. Lescanne, “On counting untyped lambda terms”, Theor. Comput. Sci., 474 (2013), 80–97 | DOI | MR | Zbl

[2] K. Grygiel, P. Lescanne, “Counting and generating lambda terms”, J. Funct. Programming, 23:5 (2013), 594–628 | DOI | MR | Zbl

[3] J. Tromp, “Binary lambda calculus and combinatory logic”, Kolmogorov Complexity and Applications, Dagstuhl Seminar Proceedings, 06051, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2006

[4] O. Bodini, D. Gardy, B. Gittenberger, “Lambda-terms of bounded unary height”, 2011 Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2011) | MR

[5] K. Grygiel, P. Lescanne, “Counting and generating terms in the binary lambda calculus”, J. Funct. Programming, 25:e24 (2015) | MR | Zbl

[6] N. Zeilberger, A. Giorgetti, “A correspondence between rooted planar maps and normal planar lambda terms”, Logical Methods in Computer Science, 11 (2015), 1–39 | DOI | MR

[7] N. Zeilberger, “Linear lambda terms as invariants of rooted trivalent maps”, J. Functional Programming, 26:24 (2016) ; (2015), arXiv: 1512.06751 | MR | Zbl

[8] H. Barendregt, W. Dekkers, R. Statman, Lambda Calculus with Types, Cambridge University Press, New York, 2013 | MR | Zbl

[9] J. R. Hindley, Basic Simple Type Theory, Cambridge University Press, New York, 1997 | MR | Zbl

[10] R. Stenli, Perechislitelnaya kombinatorika. Derevya, proizvodyaschie funktsii i simmetricheskie funktsii, Mir, M., 2005

[11] P. Flajolet, E. Fusy, X. Gourdon, D. Panario, N. Pouyanne, “A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics”, The electronic journal of combinatorics, 13 (2006), #R103 | MR | Zbl