Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Primitive-Recursive Determinization of Nondeterministic Büchi Automata to DPAs

Proved
DistLTLSynth.Char.nbw_determinization

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

automata-theorycomputabilitytemporal-logic

Primitive-recursive determinization of finite nondeterministic B\u00fcchi automata into finite state-based deterministic parity automata over indexed finite alphabets Fin(α+1)\mathrm{Fin}(\alpha + 1)Fin(α+1).

Given an alphabet bound α∈N\alpha \in \mathbb{N}α∈N and a finite nondeterministic B\u00fcchi automaton encoded either via transition bitmasks (B∈NBWCodeB \in \mathrm{NBWCode}B∈NBWCode) or adjacency lists (B∈ListNBWCodeB \in \mathrm{ListNBWCode}B∈ListNBWCode), there exist primitive-recursive compilers detNBW\mathrm{detNBW}detNBW and detListNBW\mathrm{detListNBW}detListNBW producing deterministic parity automaton codes in GenDPACode\mathrm{GenDPACode}GenDPACode that recognize the exact same ω\omegaω-language:

L(toGenDPA(α,detNBW(α,B)))=LNBW(α,B).\mathcal{L}\bigl(\mathrm{toGenDPA}(\alpha, \mathrm{detNBW}(\alpha, B))\bigr) = \mathcal{L}_{\mathrm{NBW}}(\alpha, B).L(toGenDPA(α,detNBW(α,B)))=LNBW​(α,B).

This theorem supplies the ω\omegaω-regular determinization engine needed both to compile LTL specifications and adversary complements into deterministic parity block automata (Lemma 3.7) and to determinize universal edge-thread parity monitors on symbolic component trees (Theorem 3.4).

Formalization Note Both bitmask (NBWCode) and list-based (ListNBWCode) encodings are provided so downstream constructions can work with whichever representation matches their transition tables.

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
import Definitions.Def_DistLTLSynth_Char_SynthesisEngine
Formal statement
namespace DistLTLSynth.Char

theorem nbw_determinization :
    (∃ detNBW : ℕ → NBWCode → GenDPACode, Primrec₂ detNBW ∧
      ∀ (αSize : ℕ) (b : NBWCode) (w : ℕ → Fin (αSize + 1)),
        (toGenDPA αSize (detNBW αSize b)).Accepts w ↔ NBWAccepts αSize b w) ∧
    (∃ detListNBW : ℕ → ListNBWCode → GenDPACode, Primrec₂ detListNBW ∧
      ∀ (αSize : ℕ) (B : ListNBWCode) (w : ℕ → Fin (αSize + 1)),
        (toGenDPA αSize (detListNBW αSize B)).Accepts w ↔ ListNBWAccepts αSize B w) := by sorry

end DistLTLSynth.Char
Source
arXiv:2611.04561, Distributed LTL Synthesis under Arbitrary Message Adversaries, Section 3.3 (Lemma 3.7, p. 13) 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