Maciej Bendkowski
Jagiellonian University
Statistical properties and evaluation of random λ-terms -- a survey
In the talk we discuss selected enumerative and statistical results regarding random λ-terms in the de Bruijn notation. In particular, we investigate the distribution of various combinatorial parameters of closed lambda terms, including the number of β-redexes, head abstractions, free variables or the de Bruijn index value profile. Moreover, we analyse the cost of finding the leftmost-outermost β-redex in a random λ-term, showing that it is, on average, constant. Finally, we overview a recent, new approach towards the average-case analysis of substitution resolution in λ-calculus, based on the quantitative analysis of so-called calculi of explicit substitutions.
