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

Accepting runs and modal game plays

Lax369799.AutomatonRunGame · concepts/Lax369799/AutomatonRunGame.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 accepting run supplies winning modal choices. Finite branches use the final-state test, while infinite branches use the parity condition. Inserting zero-priority marking positions between word positions does not alter the acceptance condition.

    Concept map
    16 concepts; 1 descendant hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 2 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.ModalAcceptanceGame
    2
    3/-!
    4---
    5title: Accepting runs and modal game plays
    6type: theorem
    7---
    8Every accepting run supplies winning modal choices. Finite branches use
    9the final-state test, while infinite branches use the parity condition.
    10Inserting zero-priority marking positions between word positions does
    11not alter the acceptance condition.
    12-/
    13
    14namespace Lax369799.AutomatonRunGame
    15open TransitionEncoding TransitionSystems UnfoldAutomata ModalAcceptanceGame
    16
    17axiom parity_interleave {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    18 (S : TransitionSystem P) (w : ℕ → Fin M.unary) (p : ℕ → Vertex M S)
    19 (he : ∀ n, (game M S).priority (p (2*n)) =
    20 ceiling M.condition - M.condition.priority (M.condition.run w n))
    21 (ho : ∀ n, (game M S).priority (p (2*n+1)) = 0) :
    22 M.condition.AcceptsInfinite w ↔ (game M S).EveWins p
    23
    24axiom run_winning {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    25 {S : RankedSystems.System (TransitionAlphabet P) 0} (r : Run M S) (hr : r.Accepting) :
    26 ParityWinningRegions.Winning (game M (decode S)) true
    27 (position M.condition.initial (decode S).initial)
    28
    29end Lax369799.AutomatonRunGame
    30
    Show ProofShow Proof
    Builds on
    Used by
    From Mathlib

    none

    Discussion

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

    Loading discussion…