Exact bounds for acyclic higher-order recursion schemes

DOI10.1016/j.ic.2022.104982OpenAlexW4309768891MaRDI QIDQ2112794

Bahareh Afshari, Dominik Wehr

Publication date: 12 January 2023

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2022.104982

zbMATH Keywords

higher-order recursion schemeslanguage boundssimply typed \(\lambda \)-calculus

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• A semantic measure of the execution time in linear logic
• Herbrand's theorem as higher order recursion
• An upper bound for reduction sequences in the typed \(\lambda\)-calculus
• Exact bounds for lengths of reductions in typed λ-calculus
• Non-idempotent intersection types and strong normalisation
• Bounding linear head reduction and visible interaction through skeletons
• Estimation of the Length of Interactions in Arena Game Semantics
• Quantitative Game Semantics for Linear Logic
• Upper bounds for standardizations and an application
• Analyzing Gödel's T Via Expanded Head Reduction Trees
• Streett Automata Model Checking of Higher-Order Recursion Schemes
• Model Checking Higher-Order Programs