Primitive-Recursive Determinization of Nondeterministic Büchi Automata to DPAs
ProvedDistLTLSynth.Char.nbw_determinizationPrimitive-recursive determinization of finite nondeterministic B\u00fcchi automata into finite state-based deterministic parity automata over indexed finite alphabets .
Given an alphabet bound and a finite nondeterministic B\u00fcchi automaton encoded either via transition bitmasks () or adjacency lists (), there exist primitive-recursive compilers and producing deterministic parity automaton codes in that recognize the exact same -language:
This theorem supplies the -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.
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
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