Finite prefixes characterize equality of two value trees
ProvedTreeEquivalenceHORS.Equivalence.trees_equal_iff_prefixescomputabilityrecursion-schemes
Two closed ground terms in valid schemes with the same ranked alphabet generate identical value trees if and only if all their finite prefixes agree.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_FiniteSemantics
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem trees_equal_iff_prefixes (G H : HORS) (vg : G.Valid) (vh : H.Valid)
(alph : G.alphabet = H.alphabet) (t u : Tm)
(ht : G.typeOf [] t = some .o) (hu : H.typeOf [] u = some .o) :
G.BTat t = H.BTat u ↔ ∀ d, G.Pref t d = H.Pref u d := 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