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

The finite modal acceptance game

Lax369799.ModalAcceptanceGame · concepts/Lax369799/ModalAcceptanceGame.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

    At a position consisting of a word state and an input vertex, Eve chooses a marking satisfying the modal transition. Adam chooses a marked successor. An empty legal marking ends in the winning terminal; absence of any legal marking ends in the losing terminal. Both terminals have self-loops, so the arena is total. The two-move predecessor operation is exactly the modal one-step condition. Reversed bounded priorities implement the least-even word condition using the greatest-even convention of finite parity games.

    Concept map
    15 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.
    Evidence

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

    Lean source view on GitHub

    1import Lax369799.ModalTransitions
    2import Lax369799.ParityWinningRegions
    3import Lax369799.ParityGameEquations
    4import Mathlib.Data.Finset.Lattice.Fold
    5
    6/-!
    7---
    8title: The finite modal acceptance game
    9type: theorem
    10---
    11At a position consisting of a word state and an input vertex, Eve chooses
    12a marking satisfying the modal transition. Adam chooses a marked successor.
    13An empty legal marking ends in the winning terminal; absence of any legal
    14marking ends in the losing terminal. Both terminals have self-loops, so the
    15arena is total. The two-move predecessor operation is exactly the modal
    16one-step condition. Reversed bounded priorities implement the least-even
    17word condition using the greatest-even convention of finite parity games.
    18-/
    19
    20namespace Lax369799.ModalAcceptanceGame
    21open TransitionEncoding TransitionSystems UnfoldAutomata ModalTransitions FiniteParityGames
    22
    23def Pre {V : Type} (G : Game V) (X : Set V) : Set V :=
    24 ParityWinningRegions.Pre G X
    25
    26abbrev Marking {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    27 (S : TransitionSystem P) := Fin M.condition.states → Set S.Vertex
    28
    29abbrev Vertex {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    30 (S : TransitionSystem P) :=
    31 (Fin M.condition.states × S.Vertex) ⊕ ((S.Vertex × Marking M S) ⊕ Bool)
    32
    33def position {P : Type} {M : UnfoldAutomaton (TransitionAlphabet P)} {S : TransitionSystem P}
    34 (q : Fin M.condition.states) (v : S.Vertex) : Vertex M S := .inl (q, v)
    35
    36def selection {P : Type} {M : UnfoldAutomaton (TransitionAlphabet P)} {S : TransitionSystem P}
    37 (v : S.Vertex) (ρ : Marking M S) : Vertex M S := .inr (.inl (v, ρ))
    38
    39def terminal {P : Type} {M : UnfoldAutomaton (TransitionAlphabet P)} {S : TransitionSystem P}
    40 (b : Bool) : Vertex M S := .inr (.inr b)
    41
    42def Edge {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) :
    43 Vertex M S → Vertex M S → Prop
    44 | .inl (q, v), .inr (.inl (w, ρ)) => v = w ∧ OneStep M q S v ρ
    45 | .inl (q, v), .inr (.inr false) => ¬ ∃ ρ, OneStep M q S v ρ
    46 | .inr (.inl (v, ρ)), .inl (q, w) => S.edge v w ∧ w ∈ ρ q
    47 | .inr (.inl (v, ρ)), .inr (.inr true) => ¬ ∃ q w, S.edge v w ∧ w ∈ ρ q
    48 | .inr (.inr b), .inr (.inr c) => b = c
    49 | _, _ => False
    50
    51def eve {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) :
    52 Vertex M S → Prop
    53 | .inl _ => True
    54 | .inr _ => False
    55
    56def ceiling {u z : ℕ} (D : WordCondition u z) : ℕ :=
    57 2 * (Finset.univ.sup D.priority + 1)
    58
    59def priority {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) :
    60 Vertex M S → ℕ
    61 | .inl (q, _) => ceiling M.condition - M.condition.priority q
    62 | .inr (.inr false) => 1
    63 | _ => 0
    64
    65noncomputable def game {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    66 (S : TransitionSystem P) : Game (Vertex M S) where
    67 eve := eve M S
    68 edge := Edge M S
    69 priority := priority M S
    70 total := by
    71 classical
    72 intro v
    73 rcases v with ⟨q, v⟩ | (⟨v, ρ⟩ | b)
    74 · by_cases h : ∃ ρ, OneStep M q S v ρ
    75 · exact ⟨selection v h.choose, rfl, h.choose_spec⟩
    76 · exact ⟨terminal false, h⟩
    77 · by_cases h : ∃ q w, S.edge v w ∧ w ∈ ρ q
    78 · obtain ⟨q, w, h⟩ := h
    79 exact ⟨position q w, h⟩
    80 · exact ⟨terminal true, h⟩
    81 · exact ⟨terminal b, rfl⟩
    82
    83def target {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    84 (S : TransitionSystem P) (X : Marking M S) : Set (Vertex M S)
    85 | .inl (q, v) => v ∈ X q
    86 | .inr (.inr true) => True
    87 | _ => False
    88
    89axiom predecessor {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    90 (S : TransitionSystem P) (q : Fin M.condition.states) (v : S.Vertex) (X : Marking M S) :
    91 position q v ∈ Pre (game M S) (Pre (game M S) (target M S X)) ↔ OneStep M q S v X
    92
    93axiom finite {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) :
    94 Finite (Vertex M S)
    95
    96axiom determined {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) :
    97 ∃ f g : Vertex M S → Vertex M S,
    98 (game M S).Legal true f ∧ (game M S).Legal false g ∧
    99 ∀ v, (game M S).WinsFrom true f v ∨ (game M S).WinsFrom false g v
    100
    101axiom priority_positive {u z : ℕ} (D : WordCondition u z) (q : Fin D.states) :
    102 0 < ceiling D - D.priority q
    103
    104axiom reverse_parity {u z : ℕ} (D : WordCondition u z) (w : ℕ → Fin u) :
    105 D.AcceptsInfinite w ↔ ∃ c, Even c ∧
    106 (∀ N, ∃ n, N ≤ n ∧ ceiling D - D.priority (D.run w n) = c) ∧
    107 ∀ b, c < b → ¬ ∀ N, ∃ n, N ≤ n ∧ ceiling D - D.priority (D.run w n) = b
    108
    109axiom terminal_winning {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    110 (S : TransitionSystem P) (b : Bool) :
    111 ParityWinningRegions.Winning (game M S) true (terminal b) ↔ b = true
    112
    113axiom winning_equation {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    114 (S : TransitionSystem P) (q : Fin M.condition.states) (v : S.Vertex) :
    115 ParityWinningRegions.Winning (game M S) true (position q v) ↔
    116 OneStep M q S v (fun p => {w | ParityWinningRegions.Winning (game M S) true (position p w)})
    117
    118axiom winning_nested {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    119 (S : TransitionSystem P) (q : Fin M.condition.states) (v : S.Vertex) :
    120 ParityWinningRegions.Winning (game M S) true (position q v) ↔
    121 position q v ∈ ParityGameEquations.solve (game M S) (ceiling M.condition + 1) (fun _ => ∅)
    122
    123end Lax369799.ModalAcceptanceGame
    124
    Show ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…