Can I read Towards the Average-case Analysis of Substitution Resolution in $\Lambda$-calculus on EtoBox?

Towards the Average-case Analysis of Substitution Resolution in $\Lambda$-calculus by Bendkowski, Maciej is a scholarly article available to read on EtoBox.

What is Towards the Average-case Analysis of Substitution Resolution in $\Lambda$-calculus about?

Substitution resolution supports the computational character of $\beta$-reduction, complementing its execution with a capture-avoiding exchange of terms for bound variables. Alas, the meta-level definition of substitution, masking a non-trivial computation, turns $\beta$-reduction into an atomic rewriting rule, despite its varying operational complexity. In the current paper we propose a somewhat indirect average-case analysis of substitution resolution in the classic $\lambda$-calculus, based on the quantitative analysis of substitution in $\lambda\upsilon$, an extension of $\lambda$-calculus internalising the $\upsilon$-calculus of explicit substitutions. Within this framework, we show that for any fixed $n \geq 0$, the probability that a uniformly random, conditioned on size, $\lambda\upsilon$-term $\upsilon$-normalises in $n$ normal-order (i.e. leftmost-outermost) reduction steps tends to a computable limit as the term size tends to infinity. For that purpose, we establish an effective hierarchy $\left(\mathscr{G}_n\right)_n$ of regular tree grammars partitioning $\upsilon$-normalisable terms into classes of terms normalising in $n$ normal-order rewriting steps. The main techni

Author

Bendkowski, Maciej

Published

2018

Language

EN