Correctness of the binary-output recursion-scheme translation
ProvedTreeEquivalenceHORS.Equivalence.binary_translation_correctcomputabilityrecursion-schemes
Replacing source terminals by their binary constructor rules preserves validity, productivity and safety. The translated scheme has the binary alphabet, its order is bounded by the larger of one and the source order, and its value tree is exactly the binary encoding of the source tree.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_BinaryOutput import Definitions.Def_TreeEquivalenceHORS_Equivalence_Encoding
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem binary_translation_correct (G : HORS) (vg : G.Valid) (ag : G.alphabet = sigma0) (pg : G.Prod) :
(binaryScheme G).Valid ∧ (binaryScheme G).alphabet = sigma2 ∧ (binaryScheme G).Prod ∧
(binaryScheme G).order ≤ max 1 G.order ∧ (binaryScheme G).BT = encAt G.BT ∧ (G.Safe → (binaryScheme G).Safe) := by sorry
end TreeEquivalenceHORS.EquivalenceSource
Mingkun Xiao and Yixuan Sun, Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable, §§3 and 5.6. https://arxiv.org/html/2610.39678v1