Symbolic compressed component-tree arena and universal bad-thread parity monitor (Lemma 3.13)
ProvedDistLTLSynth.Char.lemma_3_13Let be a two-process distributed synthesis instance with input alphabets , output alphabets , and signal alphabet , where is the set of directed communication graphs on . Fix a consensus block length and a compiled deterministic parity block automaton with state set , priority map , retraction bound , and full extension bound .
Write for the finite set of compressed symbolic positions consisting of a size , equivalence tables on , and a state labeling , and write for the finite set of admissible symbolic compression actions consisting of an idempotent retraction with preserving , , and , together with view-coherent -round local output tables . For each admissible pair , let be the set of -reaching -round extensions and its partition into connected components under combined - and -indistinguishability.
Then the symbolic arena, formula parser, and deterministic parity branch monitor satisfy the following properties:
- Prefix-Polish LTL parsing and semantic instantiation: Testing whether parses to a unique linear temporal logic formula is primitive recursive, and for every message adversary and distributed algorithm , realizing the typed instantiation of under is equivalent to realizing the trace language .
- Primitive-recursive symbolic arena and component decomposition: Enumerating valid symbolic position-action labels , single-block state transitions, live extension sets (of cardinality at most ), connected components (), and child symbolic positions is primitive recursive; moreover, incremental view-equivalence propagation across finite signal blocks tracks exact local view equality for both processes .
- Universal bad-thread branch acceptance: The tree specification is primitive recursive, enforces root initialization and child position matching along every valid branch, and its deterministic parity branch automaton accepts an infinite branch if and only if no infinite folded edge thread has odd minimum infinitely-occurring priority:
This result provides the computable finite-alphabet regular tree parity game representation of compressed component trees required to decide realizability and synthesize finite-state controllers in distributed LTL synthesis.
Formalization Note In Lean, the automaton compilation and tree-game solver primitives from earlier subsections are bundled in a record Thm34Engine, symbolic contexts are represented as tuples SymCtx storing , and -based label indices reserve as an absorbing padding symbol for unused arity directions.
import Mathlib import Definitions.Def_DistLTLSynth_Char_Model import Definitions.Def_DistLTLSynth_Char_LTL import Definitions.Def_DistLTLSynth_Char_Geometric import Definitions.Def_DistLTLSynth_Char_Automata import Definitions.Def_DistLTLSynth_Char_Consensus import Definitions.Def_DistLTLSynth_Char_ComponentTree import Definitions.Def_DistLTLSynth_Char_SynthesisEngine import Definitions.Def_DistLTLSynth_Char_SymbolicArena set_option autoImplicit false
namespace DistLTLSynth.Char
theorem lemma_3_13 :
(Primrec parseOk) ∧
(∀ ts : List Token, parseOk ts = true ↔ ∃ φ, parse ts = some φ) ∧
(∀ (I : Instance) (φ : Formula ℕ ℕ ℕ ℕ) (A : Set (ℕ → CommGraph)) (f : Algorithm I.X1 I.X2 I.Y1 I.Y2),
FRealizes f A (instFormulaOf I φ) ↔ RealizesLang f A (I.Lang φ)) ∧
(Primrec validSymLabels) ∧
(∀ c : SymCtx, (validSymLabels c).Nodup) ∧
(∀ (c : SymCtx) (pa : SymPosCode × SymActCode),
pa ∈ validSymLabels c ↔
pa.1 ∈ allSymPos c ∧ pa.2 ∈ allSymActsFor c pa.1 ∧ actValid c pa.1 pa.2 = true) ∧
(∀ E : Thm34Engine, Primrec (symNextStatePacked E)) ∧
(∀ E : Thm34Engine, Primrec (symComponentsPacked E)) ∧
(∀ E : Thm34Engine, Primrec (buildTreeSpec E)) ∧
(∀ (E : Thm34Engine) (c : SymCtx) (a : Fin ((buildTreeSpec E c).2.1 + 1)),
tsRootOk (buildTreeSpec E c) a =
if a.val = 0 then false
else decide (((validSymLabels c).getD (a.val - 1) (initSymPos, ([], [], []))).1 = initSymPos)) ∧
(∀ (E : Thm34Engine) (c : SymCtx) (a : Fin ((buildTreeSpec E c).2.1 + 1))
(d : Fin ((buildTreeSpec E c).1 + 1)) (a' : Fin ((buildTreeSpec E c).2.1 + 1)),
tsChildOk (buildTreeSpec E c) a d a' =
if a.val = 0 then decide (a'.val = 0)
else
let pa := (validSymLabels c).getD (a.val - 1) (initSymPos, ([], [], []))
let comps := symComponents E c pa.1 pa.2
if d.val < comps.length then
if a'.val = 0 then false
else
let pa' := (validSymLabels c).getD (a'.val - 1) (initSymPos, ([], [], []))
decide (pa'.1 = childSymPos (ctxI c) pa.1 (comps.getD d.val []))
else decide (a'.val = 0)) ∧
(∀ (E : Thm34Engine) (c : SymCtx)
(ad : ℕ → Fin ((buildTreeSpec E c).2.1 + 1) × Fin ((buildTreeSpec E c).1 + 1)),
(tsDPA (buildTreeSpec E c)).Accepts ad ↔
¬ ∃ (iSeq : ℕ → Fin (ctxBFull c)) (pSeq : ℕ → Fin (maxList (ctxBCode c).2.2 + 1)),
(iSeq 0).val = 0 ∧
(∀ n, edgeStepOk E c (validSymLabels c) (ad n).1.val (ad n).2.val
(iSeq n).val (pSeq n).val (iSeq (n + 1)).val = true) ∧
OddParityCond (fun n => (pSeq n).val)) ∧
(∀ (E : Thm34Engine) (ctx : SymCtx) (pos : SymPosCode) (act : SymActCode) (e : SymExtElem),
e ∈ symLiveExts E ctx pos act ↔
e.1 ∈ fixedIdxs pos act ∧
e.2.1 ∈ fullBlocks (ctxI ctx) (ctxD ctx) ∧
e.2.2 = symNextState E ctx pos act e.1 e.2.1 ∧
(ctxLive ctx).getD e.2.2 false = true) ∧
(∀ (E : Thm34Engine) (ctx : SymCtx) (pos : SymPosCode) (act : SymActCode),
(fixedIdxs pos act).length ≤ ctxBRed ctx →
(symLiveExts E ctx pos act).Nodup ∧ (symLiveExts E ctx pos act).length ≤ ctxBFull ctx) ∧
(∀ (E : Thm34Engine) (ctx : SymCtx) (pos : SymPosCode) (act : SymActCode),
(fixedIdxs pos act).length ≤ ctxBRed ctx →
let S := symLiveExts E ctx pos act
let comps := symComponents E ctx pos act
comps.length ≤ ctxBFull ctx ∧
∀ (d : ℕ) (hd : d < comps.length),
let comp := comps[d]'hd
1 ≤ comp.length ∧ comp.length ≤ ctxBFull ctx ∧ comp.Nodup ∧
(∀ e ∈ comp, e ∈ S) ∧
((∀ a ∈ S, ∀ b ∈ S, symExtAdj (ctxI ctx) pos a b = symExtAdj (ctxI ctx) pos b a) →
∀ j1 j2 : Fin comp.length,
Relation.ReflTransGen
(fun x y : Fin comp.length => symExtAdj (ctxI ctx) pos comp[x] comp[y] = true) j1 j2)) ∧
(∀ (I : Instance) (pos : SymPosCode) (comp : List SymExtElem),
let pos' := childSymPos I pos comp
pos'.1 = comp.length ∧
(∀ a (ha : a < comp.length) b (hb : b < comp.length),
eq1At pos' a b = (extEqNat I pos (comp[a]'ha).1 (comp[a]'ha).2.1 (comp[b]'hb).1 (comp[b]'hb).2.1).1) ∧
(∀ a (ha : a < comp.length) b (hb : b < comp.length),
eq2At pos' a b = (extEqNat I pos (comp[a]'ha).1 (comp[a]'ha).2.1 (comp[b]'hb).1 (comp[b]'hb).2.1).2) ∧
(∀ a (ha : a < comp.length), stateAt pos' a = (comp[a]'ha).2.2)) ∧
(∀ (I : Instance) {h1 h2 : List (Signal I.X1 I.X2)}, h1.length = h2.length →
∀ (w1 w2 : List ℕ),
extEqFrom I (decide (view1 h1 = view1 h2)) (decide (view2 h1 = view2 h2)) w1 w2 =
(decide (view1 (h1 ++ decHist I w1) = view1 (h2 ++ decHist I w2)),
decide (view2 (h1 ++ decHist I w1) = view2 (h2 ++ decHist I w2)))) ∧
(∀ (I : Instance) {h1 h2 : List (Signal I.X1 I.X2)}, h1.length = h2.length →
∀ {b1 b2 : Bool}, (view1 h1 = view1 h2 → b1 = true) → (view2 h1 = view2 h2 → b2 = true) →
∀ (w1 w2 : List ℕ),
(view1 (h1 ++ decHist I w1) = view1 (h2 ++ decHist I w2) → (extEqFrom I b1 b2 w1 w2).1 = true) ∧
(view2 (h1 ++ decHist I w1) = view2 (h2 ++ decHist I w2) → (extEqFrom I b1 b2 w1 w2).2 = true)) ∧
(∀ {α : Type} (inh : α) (S : List α) (adj : α → α → Bool) {i : ℕ}, i < S.length →
∀ y : ℕ,
y ∈ compIdxOf inh S adj i ↔
y < S.length ∧
Relation.ReflTransGen
(fun a b => a < S.length ∧ b < S.length ∧ adj (S.getD a inh) (S.getD b inh) = true) i y) ∧
(∀ {α : Type} (inh : α) (S : List α) (adj : α → α → Bool) {i : ℕ}, i < S.length →
(compIdxOf inh S adj i).Nodup ∧ i ∈ compIdxOf inh S adj i ∧
(compIdxOf inh S adj i).length ≤ S.length ∧
∀ y ∈ compIdxOf inh S adj i, y < S.length) ∧
(∀ {α : Type} (inh : α) (S : List α) (adj : α → α → Bool),
(∀ a < S.length, ∀ b < S.length,
adj (S.getD a inh) (S.getD b inh) = adj (S.getD b inh) (S.getD a inh)) →
∀ {i j : ℕ}, i < S.length → j < S.length →
Relation.ReflTransGen
(fun a b => a < S.length ∧ b < S.length ∧ adj (S.getD a inh) (S.getD b inh) = true) i j →
compIdxOf inh S adj i = compIdxOf inh S adj j) := by sorry
end DistLTLSynth.Char