Exact-count witness messages under leaf elimination
DefinitionStableMSR_Recovery_Supplement_TreeMenuMessagesalgorithmsclustering
A message stores words of node and local-state pairs. Merge a leaf into its only later neighbor or the empty root, concatenate compatible witnesses, and keep one least-weight witness per explicit total. State and resource bounds make malformed inputs finite as well.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_TreeLeafSchedules
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
abbrev Word := List Key
abbrev Messages := List (Key × List Word)
def choicesAt (I : Instance) (i : ℕ) : Block :=
if i == I.1.length then [0] else List.range (menu I i).length
def catalog (I : Instance) : List Key :=
((List.range I.1.length)++[I.1.length]).flatMap (fun i => (choicesAt I i).map (i,·))
def evaluate (I : Instance) (k : Key) : Cell := (menu I k.1)[k.2]?.getD ([],0)
def resources (I : Instance) : Pack := I.2.1.flatMap (fun r => r.flatMap Prod.fst)
def bins (I : Instance) := 0::(List.range (resources I).length).map (·+1)
def load (I : Instance) (w : Word) := (w.flatMap (fun k => (evaluate I k).1)).length
def price (I : Instance) (w : Word) := (w.map (fun k => (evaluate I k).2)).sum
def fitsB (I : Instance) (w : Word) : Bool :=
decide (w.length≤(catalog I).length) && w.all (fun k => (catalog I).contains k)
def compress (I : Instance) (ps : List Word) : List Word :=
(bins I).flatMap (fun j =>
let good := ps.filter (fun w => fitsB I w && (load I w == j))
(good.filter (fun w => good.all (fun u => decide (price I w ≤ price I u)))).take 1)
def joinable (I : Instance) (a b : Key) : Bool :=
(a.1 == I.1.length) || (b.1 == I.1.length) || !(adjB I.1 a.1 b.1) ||
(I.2.2.contains (a,b) && I.2.2.contains (b,a))
def lookup (R : Messages) (k : Key) : List Word :=
((R.filter (fun r => r.1 == k)).headD (k,[])).2
def initial (I : Instance) : Messages :=
(catalog I).map (fun k => (k,if k.1 == I.1.length then [[]] else [[k]]))
def options (I : Instance) (i p : ℕ) (R : Messages) (k : Key) : List Word :=
if k.1 == p then
(lookup R k).flatMap (fun u => (choicesAt I i).flatMap (fun s =>
if joinable I (i,s) k then (lookup R (i,s)).map (u++·) else []))
else lookup R k
def fuse (I : Instance) (i p : ℕ) (R : Messages) : Messages :=
(catalog I).map (fun k => (k,compress I (options I i p R k)))
def instructions (L : FactorLayout) : Block→List Key
| [] => []
| i::is => (i,(neighbors L is i).headD L.length)::instructions L is
def finalWords (I : Instance) (order : Block) :=
lookup ((instructions I.1 order).foldl (fun R k => fuse I k.1 k.2 R) (initial I)) (I.1.length,0)
def readLabels (I : Instance) (w : Word) : Block :=
(List.range I.1.length).map (fun i => ((w.filter (fun k => k.1 == i)).headD (i,0)).2)
def optimize (I : Instance) (order : Block) := (finalWords I order).map (readLabels I)
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
Source
Finite-tree message passing with exact-count pruning, implementing the tree dynamic program in Appendix A.6 of arXiv:2611.03547.