Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
We investigate the number of variables in two special subclasses of lambda-terms that are restricted by a bound of the number of abstractions between a variable and its binding lambda, and by a bound of the nesting levels of abstractions, respectively. These restrictions are on the one hand very natural from a practical point of view, and on the other hand they simplify the counting problem compared to that of unrestricted lambda-terms in such a way that the common methods of analytic combinatorics are applicable. We will show that the total number of variables is asymptotically normally distributed for both subclasses of lambda-terms with mean and variance asymptotically equal to C_1 n and C_2 n, respectively, where the constants C_1 and C_2 depend on the bound that has been imposed. So far we just derived closed formulas for the constants in case of the class of lambda-terms with a bounded number of abstractions between each variable and its binding lambda. However, for the other class of lambda-terms that we consider, namely lambda-terms with a bounded number of nesting levels of abstractions, we investigate the number of variables in the different abstraction levels and thereby exhibit very interesting results concerning the distribution of the variables within those lambda-terms.