Determinization of infinite-word automata
Lax369799.OmegaDeterminization · concepts/Lax369799/OmegaDeterminization.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Every nondeterministic Büchi word automaton has an equivalent finite deterministic parity word automaton. This is the word-automaton ingredient of Section 6.3. The parity condition uses the least recurring priority.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.UnfoldAutomata |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Determinization of infinite-word automata |
| 6 | type: theorem |
| 7 | --- |
| 8 | Every nondeterministic Büchi word automaton has an equivalent finite |
| 9 | deterministic parity word automaton. This is the word-automaton ingredient |
| 10 | of Section 6.3. The parity condition uses the least recurring priority. |
| 11 | -/ |
| 12 | |
| 13 | namespace Lax369799.OmegaDeterminization |
| 14 | open UnfoldAutomata |
| 15 | |
| 16 | structure Buchi (alphabet : ℕ) where |
| 17 | states : ℕ |
| 18 | initial : Set (Fin states) |
| 19 | transition : Fin states → Fin alphabet → Fin states → Prop |
| 20 | accepting : Set (Fin states) |
| 21 | |
| 22 | def Buchi.Accepts {u : ℕ} (B : Buchi u) (w : ℕ → Fin u) : Prop := |
| 23 | ∃ r : ℕ → Fin B.states, r 0 ∈ B.initial ∧ |
| 24 | (∀ n, B.transition (r n) (w n) (r (n + 1))) ∧ |
| 25 | {n | r n ∈ B.accepting}.Infinite |
| 26 | |
| 27 | axiom determinization {u z : ℕ} (B : Buchi u) : |
| 28 | ∃ D : WordCondition u z, ∀ w, D.AcceptsInfinite w ↔ B.Accepts w |
| 29 | |
| 30 | end Lax369799.OmegaDeterminization |
| 31 |
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments