While this submission is a draft, it cannot be used by other submissions.

Determinization of infinite-word automata

Lax369799.OmegaDeterminization · concepts/Lax369799/OmegaDeterminization.lean · lax-369799

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    6 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.UnfoldAutomata
    2
    3/-!
    4---
    5title: Determinization of infinite-word automata
    6type: theorem
    7---
    8Every nondeterministic Büchi word automaton has an equivalent finite
    9deterministic parity word automaton. This is the word-automaton ingredient
    10of Section 6.3. The parity condition uses the least recurring priority.
    11-/
    12
    13namespace Lax369799.OmegaDeterminization
    14open UnfoldAutomata
    15
    16structure 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
    22def 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
    27axiom determinization {u z : ℕ} (B : Buchi u) :
    28 ∃ D : WordCondition u z, ∀ w, D.AcceptsInfinite w ↔ B.Accepts w
    29
    30end Lax369799.OmegaDeterminization
    31
    Show Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…