2019/03/12 by Bernhard Gittenberger, Gittenberger, Bernhard, Isabella Larcher +1
Computer Science · Mathematics · #05A16 (Primary) 60C05 #05C20 (Secondary) #30B40 #Advanced Algebra and Logic #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1903.05243
openalex publication_date 2019/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the number of variables in two special subclasses of\nlambda-terms that are restricted by a bound of the number of abstractions\nbetween a variable and its binding lambda, the so-called De-Bruijn index, or by\na bound of the nesting levels of abstractions, \i.e., the number of De\nBruijn levels, respectively. These restrictions are on the one hand very\nnatural from a practical point of view, and on the other hand they simplify the\ncounting problem compared to that of unrestricted lambda-terms in such a way\nthat the common methods of analytic combinatorics are applicable.\n We will show that the total number of variables is asymptotically normally\ndistributed for both subclasses of lambda-terms with mean and variance\nasymptotically equal to Cn and \Cn, respectively, where the\nconstants C and \C depend on the bound that has been imposed. So far\nwe just derived closed formulas for the constants in case of the class of\nlambda-terms with bounded De Bruijn index. However, for the other class of\nlambda-terms that we consider, namely lambda-terms with a bounded number of De\nBruijn levels, we investigate the number of variables, as well as abstractions\nand applications, in the different De Bruijn levels and thereby exhibit a\nso-called "unary profile" that attains a very interesting shape.\n