Exact bounds for acyclic higher-order recursion schemes

Beckmann [1] derives bounds on the length of reduction chains of classes of simply typed λ-calculus terms which are exact up-to a constant factor in their highest exponent. Afshari et al. [2] obtain similar bounds on acyclic higher-order recursion schemes (HORS) by embedding them in the simply typed λ-calculus and applying Beckmann's result. In this article, we apply Beckmann's proof strategy directly to acyclic HORS, proving exactness of the bounds on reduction chain length and obtaining exact bounds on the size of languages generated by acyclic HORS.

Authors

• Bahareh Afshari
• Dominik Wehr

Keywords

• Higher-order recursion schemes
• Simply typed λ-calculus
• Language bounds