Theorem 1.2 — for an ω-regular message adversary A, LL-Synthesis(A) is decidable iff π(A) is nowhere dense
ProvedDistLTLSynth.Char.theorem_1_2decidabilitydistributed-synthesisp2o-gran-per-chapterp2o-plan-paperp2o-v1topology
Let be an ω-regular message adversary, i.e. the language of a deterministic parity automaton with finitely many states ( allowed). The problem LL-Synthesis asks, given finite nonempty alphabets and an LTL formula , whether some distributed algorithm realizes under . Then
where decidable means that the set of yes-instances is a computable predicate on encoded instances and nowhere dense means that the closure of has empty interior. It is the paper's main result; the undecidability of the lossy-link model (, Theorem 1.1) is the case .
Differences from the source:
- encoding: an instance consists of finite nonempty alphabets X_1, X_2, Y_1, Y_2 (with the interpretation of atomic propositions) and an LTL formula → Instance = (k1, k2, m1, m2, token list) with X_p = Fin (k_p+1), Y_p = Fin (m_p+1); the formula is a prefix-notation token list over ℕ-indexed atoms; an atom whose index is out of range is false, and a token list that is not exactly one formula is a no-instance; reason: a standard primitive-recursive encoding (Primcodable from ℕ, List and products through a computable, definitional equivalence); every paper instance has a code, and the two extra cases are decidable syntactic checks, so they change no decidability question
- encoding: decidable → ComputablePred on the Primcodable instance type; reason: Mathlib's notion of a decidable problem, as in the authors' Appendix B
- encoding: A is ω-regular (given by a parity automaton) → A is the language of a deterministic parity automaton with a finite state type (least priority seen infinitely often is even); reason: the paper's own standing assumption (§1.1, §3.3, Def. 7.6); deterministic parity automata recognize exactly the ω-regular languages
- encoding: π(A) nowhere dense in [0, 1] → IsNowhereDense (piMap '' A) in ℝ; reason: π(A) ⊆ [0, 1] and [0, 1] is closed in ℝ, so nowhere density in the subspace and in ℝ coincide
- encoding: j(h) is the left-to-right index of h's edge in the inputless round-|h| view complex; π(h) is the common point of the nested intervals J(h[...r]) → j is defined by the recursion of Lemma 4.4 (jIdx), and piMap w is the supremum of the left endpoints j(w[...r])/3^r; reason: Lemma 4.4 proves the recursion for the geometric index; the left endpoints of nested intervals of length 3^{-r} increase to their common point
- 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
Preamble
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
Formal statement
namespace DistLTLSynth.Char
/-- Theorem 1.2: for every ω-regular message adversary `A` (the language of a deterministic
parity automaton with finitely many states), `LL-Synthesis(A)` is decidable iff `π(A)` is
nowhere dense. -/
theorem theorem_1_2 {S : Type} [Fintype S] (M : DPA S CommGraph) :
ComputablePred (fun I : Instance => I.Realizable M.lang) ↔
IsNowhereDense (piMap '' M.lang) := 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. 2 (PDF 3), Theorem 1.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.