Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable
cs.FL, cs.LO
Submitted: 2026-10-29
Updated: 2026-10-29
Comments: 31 pages, 3 figures. Rocq artifact: https://doi.org/10.5281/zenodo.23734555
License: http://creativecommons.org/licenses/by/4.0/
The gist: Higher-order recursion schemes (HORS) are finite, simply typed recursive programs that generate potentially infinite trees.
Abstract
Higher-order recursion schemes (HORS) are finite, simply typed recursive programs that generate potentially infinite trees. Their monadic second-order model-checking problem is decidable. We prove that tree equivalence of deterministic HORS is undecidable and, more precisely, Π 0 1-complete under total computable many-one reductions. The lower bound holds for safe, productive schemes of order at most four over the fixed ranked alphabet Σ 2=e:0,d:2, consisting of one nullary and one binary symbol. Adapting the counter-guard witness of Boiret, Piorkowski, and Schmude, we generate all candidate executions of a two-counter machine by producing both continuations at every counter test. An integer weight is nonzero exactly on legal prefixes. Functions at fixed simple types represent the polynomial of growing degree. A shift recurrence updates them without storing a separate step counter, allowing the witness to be implemented by safe applicative HORS rules. At candidate halts, the intermediate schemes generate unary observation subtrees whose lengths encode the two natural-number components of the signed weight. Invalid candidates give matching observations; a legal halt produces a finite discrepancy. Fixed constructor contexts encode these intermediate trees over Σ 2. For the upper bound, a finite monotone semantics decides head convergence and supports an algorithm computing exact tree prefixes at any prescribed finite depth, including positions labelled.
Related papers
- Quantitative Verification of Infinite-State Networks
- A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
- Positive-Data Learning of Fixed-Observation Linear MCFGs from Working Binary Presentations
- On the Separability Problem of VASS Reachability Languages
- Exact Accepting-State Spectrum for Reversal of Permutation Automata
- On Word Representations and Embeddings in Complex Matrices