×

On some enumerative problems in lambda calculus. (English. Russian original) Zbl 1484.03022

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:

03B40 Combinatory logic and lambda calculus
05A15 Exact enumeration problems, generating functions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lescanne, P., On counting untyped lambda terms, Theoretical Computer Science, 474, 80-97 (2013) · Zbl 1259.68028 · doi:10.1016/j.tcs.2012.11.019
[2] Grygiel, K.; Lescanne, P., Counting and generating lambda terms, J. Functional Programming, 23, 5, 594-628 (2013) · Zbl 1311.68045 · doi:10.1017/S0956796813000178
[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 · doi:10.2168/LMCS-11(3:22)2015
[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 · Zbl 1347.03001
[9] Hindley, JR, Basic Simple Type Theory (1997), New York: Cambridge University Press, New York · Zbl 0906.03012
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.