The binary tree encoding reflects equality of productive value trees
ProvedTreeEquivalenceHORS.Equivalence.binary_encoding_reflects_tree_equalitycomputabilityrecursion-schemes
For two valid productive schemes over the intermediate ranked alphabet, equality of their binary encodings is equivalent to equality of their original value trees.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_Encoding
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem binary_encoding_reflects_tree_equality (G H : HORS) (vg : G.Valid) (vh : H.Valid)
(ag : G.alphabet = sigma0) (ah : H.alphabet = sigma0) (pg : G.Prod) (ph : H.Prod) :
encAt G.BT = encAt H.BT ↔ G.BT = H.BT := 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