Clemens Grabmayer

Linear Depth Increase of Lambda Terms along Leftmost-Outermost Beta-Reduction

2016 · arXiv (Cornell University)

Performing $n$ steps of $β$-reduction to a given term in the $λ$-calculus can lead to an increase in the size of the resulting term that is exponential in $n$. The same is true for the …