Complete assemblies of partial tree-label witnesses
DefinitionStableMSR_Recovery_Supplement_MenuAssemblyalgorithmsclustering
An active node contributes one legal local state and a word from that state’s message. Active states must be mutually compatible. The multiset sum of their words, including the empty-root accumulator, records the full witness independently of the contraction order.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_TreeMenuMessages
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
def active (I : Instance) (xs : Block) := xs++[I.1.length]
def summands (xs : Block) (w : ℕ→Word) : Multiset Key :=
(xs.map (fun i => (w i : Multiset Key))).sum
def mass (I : Instance) (m : Multiset Key) : ℕ×ℚ :=
(m.map (fun k => ((evaluate I k).1.length,(evaluate I k).2))).sum
def canonical (I : Instance) (x : Block) : Word :=
(List.range I.1.length).map (fun i => (i,num x i))
def Assembly (I : Instance) (xs : Block) (R : Key→List Word) (m : Multiset Key) : Prop :=
∃ (s : ℕ→ℕ) (w : ℕ→Word),
(∀i∈active I xs,s i∈choicesAt I i ∧ w i∈R (i,s i)) ∧
(∀i∈active I xs, ∀j∈active I xs,joinable I (i,s i) (j,s j)=true) ∧
m=summands (active I xs) w
def RepresentsOptima (I : Instance) (P : Multiset Key→Prop) : Prop :=
(∀m,P m → ∃x,Legal I x ∧ m=(canonical I x : Multiset Key)) ∧
∀x,Legal I x → ∃m,P m ∧ (mass I m).1=(total I x).1 ∧ (mass I m).2≤(total I x).2
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
Source
Invariant for exact-count leaf-message fusion, Appendix A.6 of arXiv:2611.03547.