Forward completeness of compressed symbolic component trees (Lemma 3.12)
ProvedDistLTLSynth.Char.lemma_3_12Let be a deterministic parity automaton code defining a message adversary with , let be a distributed synthesis instance whose token list parses to an LTL formula , and let be a uniform binary-consensus horizon such that binary consensus is solvable within rounds under every live left quotient (). Let be the deterministic parity -block automaton compiled from , and let be the corresponding compressed symbolic component-tree parity specification with retraction bound .
If admits an accepting uncompressed component tree , then admits a valid accepting compressed symbolic tree, and therefore the regular tree parity game solver returns a winning strategy:
This theorem establishes the forward completeness direction of component-tree compression, showing that bounding compressed positions to edges via endpoint-table retractions preserves the existence of winning strategies whenever uniform -round consensus holds.
Formalization Note In Lean, the consensus horizon is parameterized by (D_m1 : Nat) so that is definitionally positive, and the block automaton and tree parity game solver are supplied via an arbitrary Thm34Engine instance E.
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_12 (E : Thm34Engine)
(c : DPACode) (I : Instance) (D_m1 : ℕ) (φ : Formula ℕ ℕ ℕ ℕ)
(hparse : parse I.tokens = some φ)
(hCons : ∀ g ∈ Pref c.lang, ConsensusSolvableWithin Bool (leftQuot g c.lang) (D_m1 + 1))
(hlive0 : ([] : List CommGraph) ∈ Pref c.lang)
(t0 : LabeledTree (NodeLabel I.X1 I.X2 I.Y1 I.Y2
(Fin ((E.compileBlock (c, I, D_m1)).1.1 + 1))))
(ht0 : IsUncompressedComponentTree
(let D := D_m1 + 1
let res := E.compileBlock (c, I, D_m1)
let dpa := toGenDPA (E.blockAlphaMinusOne I D) res.1
⟨dpa.init, fun q blk => dpa.step q (E.encIOBlockTyped I D blk), dpa.prio⟩)
{q | (E.compileBlock (c, I, D_m1)).2.getD q.val false = true} t0)
(hacc0 : IsAcceptingTree
(let D := D_m1 + 1
let res := E.compileBlock (c, I, D_m1)
let dpa := toGenDPA (E.blockAlphaMinusOne I D) res.1
⟨dpa.init, fun q blk => dpa.step q (E.encIOBlockTyped I D blk), dpa.prio⟩) t0) :
let res := E.compileBlock (c, I, D_m1)
let ctx : SymCtx := (I, D_m1, res.1, res.2)
E.solveTreePG (buildTreeSpec E ctx) ≠ none := by sorry
end DistLTLSynth.Char