Abstract
We investigate various classes of Motzkin trees as well as lambda-terms for which we derive asymptotic enumeration results. These classes are defined through various restrictions concerning the unary nodes or abstractions, respectively: we either bound their number or the allowed levels of nesting. The enumeration is done by means of a generating function approach and singularity analysis. The generating functions are composed of nested square roots and exhibit unexpected phenomena in some of the cases. Furthermore, we present some observations obtained from generating such terms randomly and explain why usually powerful tools for random generation, such as Boltzmann samplers, face serious difficulties in generating lambda-terms.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aho, A.V., Sloane, N.J.A.: Some doubly exponential sequences. Fibonacci Quart. 11(4), 429–437 (1973)
Banderier, C., Drmota, M.: Formulae and asymptotics for coefficients of algebraic functions. Combin. Probab. Comput. 24(1), 1–53 (2015)
Barendregt, H.P.: The Lambda Calculus: its Syntax and Semantics. Stud. Logic Found. Math., Vol. 103. North-Holland Publishing Co., Amsterdam (1984)
Bendkowski, M., Grygiel, K., Lescanne, P., Zaionc, M.: A natural counting of lambda terms. In: Freivalds, R.M., Engels, G., Catania, B. (eds.) SOFSEM 2016: Theory and Practice of Computer Science, Lecture Notes in Comput. Sci., Vol. 9587, pp. 183–194. Springer, Berlin (2016)
Bergeron, F., Flajolet, P., Salvy, B.: Varieties of increasing trees. In: Raoult, J.-C. (ed.) CAAP '92 (Rennes, 1992), Lecture Notes in Comput. Sci., Vol. 581, pp. 24–48. Springer, Berlin (1992)
Bodini, O., Gardy, D., Gittenberger, B.: Lambda terms of bounded unary height. In: Flajolet, P., Panario, D. (eds.) 2011 Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pp. 23–32. SIAM, Philadelphia, PA (2011)
Bodini, O., Gardy, D., Gittenberger, B., Jacquot, A.: Enumeration of generalized BCI lambda-terms. Electron. J. Combin. 20(4), #P30 (2013)
Bodini, O., Gardy, D., Jacquot, A.: Asymptotics and random sampling for BCI and BCK lambda terms. Theoret. Comput. Sci. 502, 227–238 (2013)
Bodini, O., Gardy, D.: Roussel, O,: Boys-and-girls birthdays and Hadamard products. Fund. Inform. 117(1–4), 85–101 (2012)
Bodini, O., Gittenberger, B.: On the asymptotic number of BCK(2)-terms. In: Drmota, M., Ward, M.D. (eds.) ANALCO14-Meeting on Analytic Algorithmics and Combinatorics, pp. 25–39. SIAM, Philadelphia, PA (2014)
Bodini, O., Jacquot, A.: Boltzmann samplers for colored combinatorial objects. In: Proceedings of Gascom'08, pp. 16–19. Bibbiena (2008)
Bodini, O., Lumbroso, J., Rolin, N.: Analytic samplers and the combinatorial rejection method. In: Sedgewick, R., Ward, M.D. (eds.) Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2015, pp. 40–50. San Diego, CA (2015)
Bodini, O., Ponty, Y.: Multi-dimensional Boltzmann sampling of languages. In: Drmota, M., Gittenberger, B. (eds.) 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), Discrete Math. Theor. Comput. Sci. Proc., AM, pp. 49–63. Assoc. Discrete Math. Theor. Comput. Sci., Nancy (2010)
Bodirsky, M., Fusy, E., Kang, M., Vigerske, S.: Boltzmann samplers, Polya theory, and cycle pointing. SIAM J. Comput. 40(3), 721–769 (2011)
Bóna, M., Flajolet, P.: Isomorphism and symmetries in random phylogenetic trees. J. Appl. Probab. 46(4), 1005–1019 (2009)
Bouttier, J., Guitter, E.: Planar maps and continued fractions. Comm. Math. Phys. 309(3), 623–662 (2012)
Church, A.: An unsolvable problem of elementary number theory. Amer. J. Math. 58(2), 345–363 (1936)
Darboux, G.: Mémoire sur l’approximation des fonctions de très-grands nombres, et sur une classe étendue de développements en série. J. Math. Pures Appl. (9) 4, 5–56, 377–416 (1878)
David, R., Grygiel, K., Kozik, J., Raffalli, C., Theyssier, G., Zaionc, M.: Asymptotically almost all λ-terms are strongly normalizing. Log. Methods Comput. Sci. 9(1), 1–30 (2013)
David, R., Zaionc, M.: Counting proofs in propositional logic. Arch. Math. Logic 48(2), 185–199 (2009)
de Bruijn, N.G.: Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Nederl. Akad. Wetensch. Indag. Math. (N.S.) 75(5), 381–392 (1972)
Drmota, M.: Random Trees: an Interplay Between Combinatorics and Probability. Springer, Vienna (2009)
Duchon, P., Flajolet, P., Louchard, G., Schaeffer, G.: Boltzmann samplers for the random generation of combinatorial structures. Combin. Probab. Comput. 13(4–5), 577–625 (2004)
Flajolet, P.: Combinatorial aspects of continued fractions. Discrete Math. 32(2), 125–161 (1980)
Flajolet, P., Fusy, E., Pivoteau, C.: Boltzmann sampling of unlabelled structures. In: Applegate, D., Brodal, G.S., Panario, D., Sedgewick, R. (eds.) Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics, pp. 201–211. SIAM, PA (2007)
Flajolet, P., Odlyzko, A.: Singularity analysis of generating functions. SIAM J. Discrete Math. 3(2), 216–240 (1990)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Flajolet, P., Zimmerman, P., Van Cutsem, B.: A calculus for the random generation of labelled combinatorial structures. Theoret. Comput. Sci. 132(1–2), 1–35 (1994)
Fournier, H., Gardy, D., Genitrini, A., Gittenberger, B.: The fraction of large random trees representing a given Boolean function in implicational logic. Random Structures Algorithms 40(3), 317–349 (2012)
Genitrini, A., Kozik, J., Zaionc, M.: Intuitionistic vs. classical tautologies, quantitative comparison. In: Miculan, M., Scagnetto, I., Honsell, F. (eds.) Types for Proofs and Programs, Lecture Notes in Comput. Sci., Vol. 4941, pp. 100–109. Springer, Berlin (2008)
Gittenberger, B., Gołębiewski, Z.: On the number of lambda terms with prescribed size of their de bruijn representation. In: Ollinger, N., Vollmer, H. (eds.) 33rd Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., Vol. 47, Art. No. 40. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2016)
Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics: a foundation for computer science. Addison-Wesley Publishing Company, Reading, MA (1994)
Grygiel, K., Lescanne, P.: Counting and generating lambda terms. J. Funct. Programming 23(5), 594–628 (2013)
Grygiel, K., Lescanne, P.: Counting terms in the binary lambda calculus. In: Bousquet-Mélou, M., Soria, M. (eds.) Proceedings of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Discrete Math. Theor. Comput. Sci. Proc., BA, pp. 133–144. Assoc. Discrete Math. Theor. Comput. Sci., Nancy (2014)
Hindley, J.R.: BCK and BCI logics, condensed detachment and the 2-property. Notre Dame J. Formal Logic 34(2), 231–250 (1993)
Imai, Y., Iséki, K.: Corrections to: “On axiom systems of propositional calculi. I”. Proc. Japan Acad. 41, 669 (1965)
Imai, Y., Iséki, K.: On axiom systems of propositional calculi. I. Proc. Japan Acad. 41, 436–439 (1965)
Iséki, K., Tanaka, S.: An introduction to the theory of BCK-algebras. Math. Japon. 23(1), 1–26 (1978/79)
Kleene, S.C.: A theory of positive integers in formal logic. Part I. Amer. J. Math. 57(1), 153–173 (1935)
Kleene, S.C.: A theory of positive integers in formal logic. Part II. Amer. J. Math. 57(2), 219–244 (1935)
Landin, P.J.: A correspondence between ALGOL 60 and Church's lambda-notation. I. Comm. ACM 8, 89–101 (1965)
Landin, P.J.: A correspondence between ALGOL 60 and Church's lambda-notation. II. Comm. ACM 8, 158–165 (1965)
Lescanne, P.: On counting untyped lambda terms. Theoret. Comput. Sci. 474, 80–97 (2013)
Meir, A., Moon, J.W.: On the altitude of nodes in random trees. Canad. J. Math. 30(5), 997–1015 (1978)
Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms for Computers and Calculators, 2nd edn. Academic Press, New York-London (1978)
Otter, R.: The number of trees. Ann. of Math. 2(49), 583–599 (1948)
Pivoteau, C., Salvy, B., Soria, M.: Algorithms for combinatorial structures: well-founded systems and Newton iterations. J. Combin. Theory Ser. A 119(8), 1711–1773 (2012)
Roussel, O., Soria, M.: Boltzmann sampling of ordered structures. In: Liebling, T.M., Szwarcfiter, J.L., Ferreira, C.E., Protti, F. (eds.) LAGOS'09 – V Latin-American Algorithms, Graphs and Optimization Symposium, Electron. Notes Discrete Math., Vol. 35, pp. 305–310. Elsevier Sci. B. V., Amsterdam (2009)
Sørensen, M.H., Urzyczyn, P.: Lectures on the Curry-Howard Isomorphism. Elsevier, Amsterdam (2006)
Tromp, J.: Binary lambda calculus and combinatory logic. In: Calude, C.S. (ed.) Randomness and Complexity, pp. 237–260. World Sci. Publ. Hackensack, NJ (2007)
Tutte, W.T.: The number of planted plane trees with a given partition. Amer. Math. Monthly 71, 272–277 (1964)
Yang, X., Chen, Y., Eide, E., Regehr, J.: Finding and understanding bugs in C compilers. ACM SIGPLAN Notices 46(6), 283–294 (2011)
Zaionc, M.: On the asymptotic density of tautologies in logic of implication and negation. Rep. Math. Logic 39, 67–87 (2005)
Acknowledgments
Open access funding provided by TU Wien (TUW).
Author information
Authors and Affiliations
Corresponding author
Additional information
The first author’s work was supported by ANR Metaconc project (France) 2015-18. Part of the work of the second author was done during a long-term visit at the Institute of Discrete Mathematics and Geometry of the TU Wien. She was partially supported by the P.H.C. Amadeus project Boolean expressions: compactification, satisfiability and distribution of functions (2013-14) and by the ANR project BOOLE (2009-13). Both the third author and the fourth author were supported by FWF grant SFB F50-03. The third author was also supported by ÖAD, grant F01/2015.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Bodini, O., Gardy, D., Gittenberger, B. et al. On the Number of Unary-Binary Tree-Like Structures with Restrictions on the Unary Height. Ann. Comb. 22, 45–91 (2018). https://doi.org/10.1007/s00026-018-0371-7
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00026-018-0371-7
Keywords
- asymptotic enumeration
- generating functions
- lambda-terms
- trees
- directed acyclic graphs
- nested square-roots
- singularity analysis