×

zbMATH — the first resource for mathematics

On some enumerative problems in lambda calculus. (English. Russian original) Zbl 07253502
J. Math. Sci., New York 247, No. 3, 442-456 (2020); translation from Zap. Nauchn. Semin. POMI 475, 99-121 (2018).
Summary: Combinatorial problems related to the enumeration of lambda terms in the untyped lambda calculus and in the Church-style simply typed lambda calculus with a single atom are considered. For the case of untyped lambda calculus, a system of equations for generating functions that enumerate lambda terms is derived. For the typed lambda calculus, the inhabited types are enumerated, as well as their primitive inhabitants.
MSC:
68N18 Functional programming and lambda calculus
05A15 Exact enumeration problems, generating functions
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Lescanne, P., On counting untyped lambda terms, Theoretical Computer Science, 474, 80-97 (2013) · Zbl 1259.68028
[2] Grygiel, K.; Lescanne, P., Counting and generating lambda terms, J. Functional Programming, 23, 5, 594-628 (2013) · Zbl 1311.68045
[3] J. Tromp, “Binary Lambda Calculus and Combinatory Logic,” Kolmogorov Complexity and Applications, Vol. 06051 of Dagstuhl Seminar Proceedings, Schloss Dagstuhl, Germany (2006). · Zbl 1137.68020
[4] O. Bodini, D. Gardy, and B. Gittenberger, “Lambda-terms of bounded unary height,” in: 2011 Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (2011). · Zbl 1429.68155
[5] K. Grygiel and P. Lescanne, “Counting and generating terms in the binary lambda calculus,” J. Functional Programming, 25, No. e24 (2015). · Zbl 1419.68039
[6] Zeilberger, N.; Giorgetti, A., A correspondence between rooted planar maps and normal planar lambda terms, Logical Methods in Computer Science, 11, 1-39 (2015) · Zbl 1448.03010
[7] N. Zeilberger, “Linear lambda terms as invariants of rooted trivalent maps,” J. Functional Programming, 26, No. e21 (2016). · Zbl 1420.68050
[8] Barendregt, H.; Dekkers, W.; Statman, R., Lambda Calculus with Types (2013), New York: Cambridge University Press, New York
[9] Hindley, JR, Basic Simple Type Theory (1997), New York: Cambridge University Press, New York
[10] R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press (1999). · Zbl 0928.05001
[11] P. Flajolet, E. Fusy, X. Gourdon, D. Panario, and N. Pouyanne, “A hybrid of Darboux’s method and singularity analysis in combinatorial asymptotics,” Electronic Journal of Combinatorics, 13, #R103 (2006). · Zbl 1111.05006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.