Lemma 6.17 — ϕ (safety) is realizable under Γ^ω iff the guarded ϕ̂ is realizable under A
ProvedDistLTLSynth.Char.lemma_6_17distributed-synthesisp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1safety
Inputs are singletons. Let be a finite graph history such that is dense in (as provided by Lemma 6.16) and let with . For every safety formula ,
This transfers undecidability from the full adversary to every adversary whose image is not nowhere dense.
Differences from the source:
- generalization: A is ω-regular with π(A) not nowhere dense, and h is the history of Lemma 6.16 → any A and any finite graph history h with leftQuot h A dense; reason: the proof uses only density of h⁻¹A; the paper's A and h satisfy this
- encoding: singleton input sets → X_1 = X_2 = Unit; reason: the same instances
- 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
Formal statement
namespace DistLTLSynth.Char
/-- Lemma 6.17: (singleton inputs) let `h` be a finite graph history such that `h⁻¹A` is
dense in `Γ^ω` (as given by Lemma 6.16). A safety formula `ϕ` is realizable under `Γ^ω` iff
the guarded formula `ϕ̂ = Prefix_h → X^{|h|} ϕ` is realizable under `A`. -/
theorem lemma_6_17 {Y1 Y2 : Type} [Fintype Y1] [Nonempty Y1] [Fintype Y2] [Nonempty Y2]
(A : Set (ℕ → CommGraph)) (h : List CommGraph) (hdense : Dense (leftQuot h A))
(φ : Formula Unit Unit Y1 Y2) (hφ : φ.IsSafety) :
Realizable Set.univ φ ↔ Realizable A (hatFormula h φ) := 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. 29 (PDF 30), Lemma 6.17 (h and ϕ̂: p. 11, PDF 12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.