Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.9 — realizing algorithms correspond to accepting uncompressed component trees; effective extraction

Proved
DistLTLSynth.Char.lemma_3_9

by Shuze Chen · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

automata-theorydistributed-synthesisp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1trees

Let D≥1D\ge1D≥1 and let BBB (a deterministic parity automaton over blocks ΣD×ΩD\Sigma^D\times\Omega^DΣD×ΩD with finitely many states) and QliveQ_{\mathrm{live}}Qlive​ satisfy the conclusion of Lemma 3.7 for AAA and φ\varphiφ. Then

  1. a distributed algorithm realizing φ\varphiφ under AAA exists if and only if an accepting uncompressed component tree exists;
  2. from an effectively given accepting uncompressed tree one can compute the local output functions of a realizing algorithm: there is a computable map FFF on codes such that, whenever ccc effectively gives an accepting uncompressed component tree, F(c)F(c)F(c) computes f1,f2f_1,f_2f1​,f2​ of an algorithm realizing φ\varphiφ under AAA.

It turns synthesis into a question about trees with finitely many labels per node.

Differences from the source:

  • generalization: D is the uniform consensus bound of Lemma 3.6 and B, Q_live are the block automaton built in the proof of Lemma 3.7 from A_live and A_ϕ, for an ω-regular A with nowhere-dense image → any D ≥ 1, any finite deterministic parity automaton B over blocks and any Q_live satisfying the two properties of Lemma 3.7, for any A; reason: the correspondence uses only those two properties and D ≥ 1, not the consensus property; the paper's D, B, Q_live are an instance
  • encoding: edges {v_1(h), v_2(h)} of view complexes; positions (K, q) and output labelings λ → edges as their histories h; labels as finite lists of (edge, state) and (view, output) pairs read by first match; reason: the paper notes that the pair of views determines the history; finite lists make labels encodable
  • encoding: 'one can compute the local output functions' from an effectively given tree → a computable F : Nat.Partrec.Code → Nat.Partrec.Code mapping every code effectively giving an accepting tree to a code computing (f_1, f_2); reason: the uniform reading of 'from … one can compute'
  • encoding: finite nonempty X_p, Y_p → Fintype + Nonempty/Inhabited with Encodable and DecidableEq instances; reason: every finite type has them; computability does not depend on the choice of encoding of a finite type
  • encoding: f_p : Views_p → Y_p → f_p is a total function on the inductive type of view terms; reason: values on terms that are not process-p views never enter an execution, so the realizable specifications are the same
  • encoding: a rooted tree whose children are the connected components of K^(D)_live → LabeledTree: a label and a number of children at each address (list of child numbers), nodes the valid addresses; reason: K is finite and Σ^D is finite, so K^(D)_live has finitely many components and every uncompressed component tree is finitely branching; this is the child numbering that 'effectively given' (p. 13) uses
Preamble
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
Formal statement
namespace DistLTLSynth.Char

/-- Lemma 3.9: (for a block length `D ≥ 1` and a block automaton `B` with `Q_live` as in
Lemma 3.7) a distributed algorithm realizing `ϕ` under `A` exists iff an accepting
uncompressed component tree exists; and from an effectively given accepting uncompressed
tree one can compute the local output functions of a realizing algorithm. -/
theorem lemma_3_9 {X1 X2 Y1 Y2 QB : Type} [Fintype X1] [Nonempty X1] [DecidableEq X1]
    [Encodable X1] [Fintype X2] [Nonempty X2] [DecidableEq X2] [Encodable X2]
    [Fintype Y1] [Inhabited Y1] [Encodable Y1] [Fintype Y2] [Inhabited Y2] [Encodable Y2]
    [Fintype QB] [Encodable QB]
    (A : Set (ℕ → CommGraph)) (φ : Formula X1 X2 Y1 Y2) (D : ℕ) (hD : 1 ≤ D)
    (B : DPA QB (Fin D → Signal X1 X2 × (Y1 × Y2))) (Qlive : Set QB)
    (hB : IsBlockAutomaton A φ D B Qlive) :
    ((∃ f : Algorithm X1 X2 Y1 Y2, FRealizes f A φ) ↔
        ∃ t : LabeledTree (NodeLabel X1 X2 Y1 Y2 QB),
          IsUncompressedComponentTree B Qlive t ∧ IsAcceptingTree B t) ∧
      ∃ F : Nat.Partrec.Code → Nat.Partrec.Code, Computable F ∧
        ∀ (t : LabeledTree (NodeLabel X1 X2 Y1 Y2 QB)) (c : Nat.Partrec.Code),
          IsUncompressedComponentTree B Qlive t → IsAcceptingTree B t → EffectivelyGiven t c →
            ∃ f : Algorithm X1 X2 Y1 Y2, CodeComputes (F c) f ∧ FRealizes f A φ := by sorry

end DistLTLSynth.Char
Source
Bollig, Bouyer-Decitre, Függer, Ghosh, Nowak, Sznajder, Distributed LTL Synthesis under Arbitrary Message Adversaries, STOC 2027 submission (PDF sha256 71476b49…), p. 13 (PDF 14), Lemma 3.9 (Definition 3.8 and 'effectively given', p. 13)
Human review
  • Endorsed by Community (Bot) · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

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