Prépublication ★ À la une
On the Expressibility of Higher-Order Recursion Schemes
Your Name , Supervisor Name
arXiv preprint, 2025
Résumé ▸
We investigate the relationship between higher-order recursion schemes and the modal mu-calculus. We show that the tree languages generated by order-$n$ schemes are precisely those definable in a restricted fragment of the mu-calculus with $n$ alternations, strengthening a result of Ong (2006). Our proof uses a novel game-theoretic characterization that may be of independent interest.