Component traces and introduction depths in a tight-block policy
DefinitionStableMSR_Recovery_Supplement_BlockTraceSemanticsalgorithmsclustering
Describe the semantic states visited by the executable per-vertex tracer, including stopping at introduction and strictly shrinking surviving interiors.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_BlockPolicyDecoder
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch
open DecompositionSearch
def stage (z : GraphInput) (rs : List Rule) (k : ℕ) (x : Vertex z) : Rule :=
(descend z rs x.val)^[k] (startRow z rs x.val)
abbrev interior (z : GraphInput) (r : Rule) := cuts z r.1
abbrev bagSet (z : GraphInput) (r : Rule) := cuts z r.2.1
def TraceFacts (z : GraphInput) (rs : List Rule) : Prop :=
let G := scopeGraph z.1 z.2
let s := stage z rs
(∀ k x, s k x=blank ∨ (s k x∈rs ∧ x∈interior z (s k x) ∧
∀ y∈interior z (s k x),s k y=s k x)) ∧
(∀ x, s 0 x≠blank ∧ boundary G (interior z (s 0 x))=∅) ∧
(∀ k x, s (k+1) x=blank ↔ s k x=blank ∨ x∈bagSet z (s k x)) ∧
∀ k x,s (k+1) x≠blank →
interior z (s (k+1) x) ⊂ interior z (s k x) ∧
boundary G (interior z (s (k+1) x))⊆bagSet z (s k x)
def HomeLevels (z : GraphInput) (rs : List Rule) (h : Vertex z→ℕ) : Prop :=
(∀x,h x<z.1.length ∧ x∈bagSet z (stage z rs (h x) x)) ∧
(∀k x,stage z rs k x≠blank ↔ k≤h x) ∧
∀k x, stage z rs k x≠blank → x∈bagSet z (stage z rs k x) → k=h x
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch
Source
Proof invariants for polynomial reconstruction of a tree decomposition.