Discrete Mathematics & Theoretical Computer Science 
In this paper we present an averagecase analysis of closed lambda terms with restricted values of De Bruijn indices in the model where each occurrence of a variable contributes one to the size. Given a fixed integer k, a lambda term in which all De Bruijn indices are bounded by k has the following shape: It starts with k De Bruijn levels, forming the socalled hat of the term, to which some number of kcolored Motzkin trees are attached. By means of analytic combinatorics, we show that the size of this hat is constant on average and that the average number of De Bruijn levels of kcolored Motzkin trees of size n is asymptotically Θ(√ n). Combining these two facts, we conclude that the maximal nonempty De Bruijn level in a lambda term with restrictions on De Bruijn indices and of size n is, on average, also of order √ n. On this basis, we provide the average unary profile of such lambda terms.
Source : ScholeXplorer
IsRelatedTo ARXIV 1805.09419 Source : ScholeXplorer IsRelatedTo DOI 10.37236/8491 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1805.09419
