Unpruned leaf fusion preserves exactly the complete witness multisets
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.leaf_fusion_preserves_assembliesalgorithmsclusteringdynamic-programming
Merge the leaf word into its unique surviving neighbor or into the empty root. This map preserves the assembled multiset. Conversely each merged option explicitly contains a compatible leaf state and two earlier words, so every new assembly splits into an old one.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_MenuAssembly open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.leaf_fusion_preserves_assemblies (I : Instance) (i : ℕ) (xs : Block) (R : Messages)
(nd : (i::xs).Nodup) (bd : ∀j∈i::xs,j<I.1.length) (th : (neighbors I.1 xs i).length≤1) (m : Multiset Key) :
Assembly I (i::xs) (lookup R) m ↔
Assembly I xs (options I i ((neighbors I.1 xs i).headD I.1.length) R) m := by
sorry
Source
Complete-witness invariant for tree message elimination in the stable sum-of-radii mission, Appendix A.6 of arXiv:2611.03547.