Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite Automaton and Symbolic Tree Codes for Distributed LTL Synthesis

Definition
DistLTLSynth_Char_SynthesisEngine

by kmehltretter82 · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

automata-theorycomputabilitydistributed-computingtemporal-logic

Finite code representations and semantic decoders supporting the decidability and algorithm-synthesis procedure for distributed LTL synthesis under message adversaries with nowhere-dense geometric image (π(A)\pi(A)π(A) nowhere dense, Theorem 3.4).

  1. Automaton codes (GenDPACode, NBWCode, ListNBWCode): Finite tuple encodings of deterministic parity automata (toGenDPA) and nondeterministic B\u00fcchi automata (NBWAccepts, ListNBWAccepts) over finite indexed alphabets Fin(α+1)\mathrm{Fin}(\alpha + 1)Fin(α+1), used to compile LTL specifications, adversary complements, and bounded edge-thread monitors.
  2. Parity tree specifications (TreeSpecCode, ValidAcceptingTree): Finite descriptions of (b+1)(b + 1)(b+1)-branching labeled tree languages over Fin(A+1)\mathrm{Fin}(A + 1)Fin(A+1) equipped with root admissibility tsRootOk, parent-direction-child compatibility tsChildOk, and a deterministic parity branch monitor tsDPA capturing symbolic compressed component trees.
  3. Typed instance formula interpretation (instFormulaOf): Maps an arithmetic-indexed LTL formula φ∈Formula(N,N,N,N)\varphi \in \mathrm{Formula}(\mathbb{N},\mathbb{N},\mathbb{N},\mathbb{N})φ∈Formula(N,N,N,N) onto the finite alphabets X1,X2,Y1,Y2X_1, X_2, Y_1, Y_2X1​,X2​,Y1​,Y2​ of an Instance, sending out-of-range atomic indices to ⊥\bot⊥.

Formalization Note All code types are concrete products of natural numbers and lists so that Primcodable instances synthesize automatically in Lean 4 without custom Gödel-numbering boilerplate.

Definition code
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

set_option autoImplicit false

namespace DistLTLSynth.Char

/-- Finite description of a deterministic parity automaton over `Fin (αSize + 1)`:
`(maxState, trans, prios)` describes the automaton with state space `Fin (d.1 + 1)`,
initial state `0`, transition `step s a = trans[s * (αSize + 1) + a] mod (d.1 + 1)`,
and priority `prio s = prios[s]` (missing entries default to `0`). -/
abbrev GenDPACode : Type := ℕ × List ℕ × List ℕ

/-- Semantic deterministic parity automaton over `Fin (αSize + 1)` decoded from `d`. -/
def toGenDPA (αSize : ℕ) (d : GenDPACode) : DPA (Fin (d.1 + 1)) (Fin (αSize + 1)) where
  init := ⟨0, Nat.succ_pos _⟩
  step s a := ⟨(d.2.1.getD (s.val * (αSize + 1) + a.val) 0) % (d.1 + 1),
    Nat.mod_lt _ (Nat.succ_pos _)⟩
  prio s := d.2.2.getD s.val 0

/-- Bitmask-based description of a nondeterministic Büchi automaton over `Fin (αSize + 1)`:
`(maxState, initMask, transMasks, accMask)` over state space `Fin (b.1 + 1)`. -/
abbrev NBWCode : Type := ℕ × ℕ × List ℕ × ℕ

/-- Acceptance of an infinite word `w : ℕ → Fin (αSize + 1)` by a bitmask-encoded `NBWCode`. -/
def NBWAccepts (αSize : ℕ) (b : NBWCode) (w : ℕ → Fin (αSize + 1)) : Prop :=
  ∃ ρ : ℕ → Fin (b.1 + 1),
    Nat.testBit b.2.1 (ρ 0).val = true ∧
    (∀ n, Nat.testBit (b.2.2.1.getD ((ρ n).val * (αSize + 1) + (w n).val) 0)
      (ρ (n + 1)).val = true) ∧
    ∃ᶠ n in Filter.atTop, Nat.testBit b.2.2.2 (ρ n).val = true

/-- List-based description of a nondeterministic Büchi automaton over `Fin (αSize + 1)`:
`(maxState, initList, transRows, accList)` over state space `Fin (B.1 + 1)`. -/
abbrev ListNBWCode : Type := ℕ × List ℕ × List (List ℕ) × List ℕ

/-- Acceptance of an infinite word `w : ℕ → Fin (αSize + 1)` by a `ListNBWCode`. -/
def ListNBWAccepts (αSize : ℕ) (B : ListNBWCode) (w : ℕ → Fin (αSize + 1)) : Prop :=
  ∃ ρ : ℕ → Fin (B.1 + 1),
    (ρ 0).val ∈ B.2.1 ∧
    (∀ n, (ρ (n + 1)).val ∈ B.2.2.1.getD ((αSize + 1) * (ρ n).val + (w n).val) []) ∧
    ∃ q : Fin (B.1 + 1), q.val ∈ B.2.2.2 ∧ ∃ᶠ n in Filter.atTop, ρ n = q

/-- Finite specification `(b, A, rootOk, childOk, mN, mTrans, mPrios)` of a `(b + 1)`-branching
labeled tree language over alphabet `Fin (A + 1)` with a deterministic parity branch monitor
over state space `Fin (mN + 1)` (§3.3, Lemma 3.13). -/
abbrev TreeSpecCode : Type := ℕ × ℕ × List Bool × List Bool × ℕ × List ℕ × List ℕ

/-- Root admissibility predicate of a `TreeSpecCode`. -/
def tsRootOk (ts : TreeSpecCode) (a : Fin (ts.2.1 + 1)) : Bool :=
  ts.2.2.1.getD a.val false

/-- Local parent-direction-child compatibility predicate of a `TreeSpecCode`. -/
def tsChildOk (ts : TreeSpecCode) (a : Fin (ts.2.1 + 1)) (d : Fin (ts.1 + 1))
    (a' : Fin (ts.2.1 + 1)) : Bool :=
  ts.2.2.2.1.getD ((a.val * (ts.1 + 1) + d.val) * (ts.2.1 + 1) + a'.val) false

/-- Deterministic parity branch monitor decoded from a `TreeSpecCode`. -/
def tsDPA (ts : TreeSpecCode) :
    DPA (Fin (ts.2.2.2.2.1 + 1)) (Fin (ts.2.1 + 1) × Fin (ts.1 + 1)) where
  init := ⟨0, Nat.succ_pos _⟩
  step q ad :=
    ⟨(ts.2.2.2.2.2.1.getD ((q.val * (ts.2.1 + 1) + ad.1.val) * (ts.1 + 1) + ad.2.val) 0) %
        (ts.2.2.2.2.1 + 1),
      Nat.mod_lt _ (Nat.succ_pos _)⟩
  prio q := ts.2.2.2.2.2.2.getD q.val 0

/-- A `(b + 1)`-branching tree `t` satisfies the root, local child, and branch-parity conditions
specified by `ts`. -/
def ValidAcceptingTree (ts : TreeSpecCode)
    (t : List (Fin (ts.1 + 1)) → Fin (ts.2.1 + 1)) : Prop :=
  tsRootOk ts (t []) = true ∧
    (∀ (addr : List (Fin (ts.1 + 1))) (d : Fin (ts.1 + 1)),
      tsChildOk ts (t addr) d (t (addr ++ [d])) = true) ∧
    (∀ branch : ℕ → Fin (ts.1 + 1),
      (tsDPA ts).Accepts
        (fun n => (t (List.ofFn (fun i : Fin n => branch i.val)), branch n)))

/-- Interpretation of an arithmetic-indexed formula `Formula ℕ ℕ ℕ ℕ` over the finite `Fin`
alphabets of an `Instance`, mapping out-of-range atomic indices to `Formula.ff`. -/
def instFormulaOf (I : Instance) : Formula ℕ ℕ ℕ ℕ → Formula I.X1 I.X2 I.Y1 I.Y2
  | .inp1 x => if h : x < I.k1 + 1 then .inp1 ⟨x, h⟩ else .ff
  | .inp2 x => if h : x < I.k2 + 1 then .inp2 ⟨x, h⟩ else .ff
  | .out1 y => if h : y < I.m1 + 1 then .out1 ⟨y, h⟩ else .ff
  | .out2 y => if h : y < I.m2 + 1 then .out2 ⟨y, h⟩ else .ff
  | .graph g => .graph g
  | .next φ => .next (instFormulaOf I φ)
  | .eventually φ => .eventually (instFormulaOf I φ)
  | .always φ => .always (instFormulaOf I φ)
  | .untl φ ψ => .untl (instFormulaOf I φ) (instFormulaOf I ψ)
  | .weakUntil ψ φ => .weakUntil (instFormulaOf I ψ) (instFormulaOf I φ)
  | .neg φ => .neg (instFormulaOf I φ)
  | .or φ ψ => .or (instFormulaOf I φ) (instFormulaOf I ψ)
  | .and φ ψ => .and (instFormulaOf I φ) (instFormulaOf I ψ)
  | .imp φ ψ => .imp (instFormulaOf I φ) (instFormulaOf I ψ)
  | .iff φ ψ => .iff (instFormulaOf I φ) (instFormulaOf I ψ)

end DistLTLSynth.Char
Source
arXiv:2611.04561, Distributed LTL Synthesis under Arbitrary Message Adversaries, Section 3.3 (Lemmas 3.7, 3.12, 3.13, pp. 13-16) and Section 7 (Definition 7.6)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me