Lemma 3.7: Executable Block Automaton and Live State Construction
ProvedDistLTLSynth.Char.lemma_3_7Executable construction of the deterministic parity block automaton and its live state set (Lemma 3.7).
Given a primitive-recursive B\u00fcchi-to-parity determinizer, an adversary deterministic parity automaton code recognizing , a synthesis instance whose token list parses to an LTL formula , and a positive block length , one can primitive-recursively construct a finite deterministic parity automaton over block alphabet together with a decidable subset such that for every execution and block index :
This theorem formalizes Lemma 3.7 of the source paper, reducing distributed LTL synthesis over -round consensus blocks to parity acceptance of component trees.
Formalization Note The finite block alphabet is bridged to the code interface via the primitive-recursive block encoder encIOBlockNat and its typed counterpart encIOBlockTyped.
import Mathlib import Definitions.Def_DistLTLSynth_Char_Model import Definitions.Def_DistLTLSynth_Char_LTL import Definitions.Def_DistLTLSynth_Char_Automata import Definitions.Def_DistLTLSynth_Char_ComponentTree import Definitions.Def_DistLTLSynth_Char_SynthesisEngine
namespace DistLTLSynth.Char
theorem lemma_3_7 :
(∃ detNBW : ℕ → NBWCode → GenDPACode, Primrec₂ detNBW ∧
∀ (αSize : ℕ) (b : NBWCode) (w : ℕ → Fin (αSize + 1)),
(toGenDPA αSize (detNBW αSize b)).Accepts w ↔ NBWAccepts αSize b w) →
∃ (blockAlphaMinusOne : Instance → ℕ → ℕ)
(encIOBlockNat : Instance → ℕ → List (ℕ × ℕ × ℕ × ℕ × ℕ) → ℕ)
(encIOBlockTyped : ∀ (I : Instance) (D : ℕ),
(Fin D → Signal I.X1 I.X2 × (I.Y1 × I.Y2)) → Fin (blockAlphaMinusOne I D + 1))
(compileBlock : DPACode × Instance × ℕ → GenDPACode × List Bool),
Primrec₂ blockAlphaMinusOne ∧
(Primrec fun p : (Instance × ℕ) × List (ℕ × ℕ × ℕ × ℕ × ℕ) =>
encIOBlockNat p.1.1 p.1.2 p.2) ∧
(∀ (I : Instance) (D : ℕ) (blk : Fin D → Signal I.X1 I.X2 × (I.Y1 × I.Y2)),
(encIOBlockTyped I D blk).val =
encIOBlockNat I D
((List.ofFn blk).map fun s => (s.1.1.val, s.1.2.1.val, s.1.2.2.idx, s.2.1.val, s.2.2.val)) %
(blockAlphaMinusOne I D + 1)) ∧
Primrec compileBlock ∧
(∀ (c : DPACode) (I : Instance) (D_m1 : ℕ) (φ : Formula ℕ ℕ ℕ ℕ),
parse I.tokens = some φ →
let D := D_m1 + 1
let res := compileBlock (c, I, D_m1)
let dpa := toGenDPA (blockAlphaMinusOne I D) res.1
let B : DPA (Fin (res.1.1 + 1)) (Fin D → Signal I.X1 I.X2 × (I.Y1 × I.Y2)) :=
⟨dpa.init, fun q blk => dpa.step q (encIOBlockTyped I D blk), dpa.prio⟩
let Qlive : Set (Fin (res.1.1 + 1)) := {q | res.2.getD q.val false = true}
IsBlockAutomaton c.lang (instFormulaOf I φ) D B Qlive) := by sorry
end DistLTLSynth.Char