The finite modal acceptance game
Lax369799.ModalAcceptanceGame · concepts/Lax369799/ModalAcceptanceGame.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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
Evidence
This concept declares 8 statements. Each proof establishes one of them relative to its assumptions.
1 determined proven
2 finite proven
3 predecessor proven
4 priority_positive proven
5 reverse_parity proven
6 terminal_winning proven
7 winning_equation proven
8 winning_nested proven
Lean source view on GitHub
| 1 | import Lax369799.ModalTransitions |
| 2 | import Lax369799.ParityWinningRegions |
| 3 | import Lax369799.ParityGameEquations |
| 4 | import Mathlib.Data.Finset.Lattice.Fold |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: The finite modal acceptance game |
| 9 | type: theorem |
| 10 | --- |
| 11 | At a position consisting of a word state and an input vertex, Eve chooses |
| 12 | a marking satisfying the modal transition. Adam chooses a marked successor. |
| 13 | An empty legal marking ends in the winning terminal; absence of any legal |
| 14 | marking ends in the losing terminal. Both terminals have self-loops, so the |
| 15 | arena is total. The two-move predecessor operation is exactly the modal |
| 16 | one-step condition. Reversed bounded priorities implement the least-even |
| 17 | word condition using the greatest-even convention of finite parity games. |
| 18 | -/ |
| 19 | |
| 20 | namespace Lax369799.ModalAcceptanceGame |
| 21 | open TransitionEncoding TransitionSystems UnfoldAutomata ModalTransitions FiniteParityGames |
| 22 | |
| 23 | def Pre {V : Type} (G : Game V) (X : Set V) : Set V := |
| 24 | ParityWinningRegions.Pre G X |
| 25 | |
| 26 | abbrev Marking {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) |
| 27 | (S : TransitionSystem P) := Fin M.condition.states → Set S.Vertex |
| 28 | |
| 29 | abbrev 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 | |
| 33 | def 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 | |
| 36 | def selection {P : Type} {M : UnfoldAutomaton (TransitionAlphabet P)} {S : TransitionSystem P} |
| 37 | (v : S.Vertex) (ρ : Marking M S) : Vertex M S := .inr (.inl (v, ρ)) |
| 38 | |
| 39 | def terminal {P : Type} {M : UnfoldAutomaton (TransitionAlphabet P)} {S : TransitionSystem P} |
| 40 | (b : Bool) : Vertex M S := .inr (.inr b) |
| 41 | |
| 42 | def 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 | |
| 51 | def eve {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) : |
| 52 | Vertex M S → Prop |
| 53 | | .inl _ => True |
| 54 | | .inr _ => False |
| 55 | |
| 56 | def ceiling {u z : ℕ} (D : WordCondition u z) : ℕ := |
| 57 | 2 * (Finset.univ.sup D.priority + 1) |
| 58 | |
| 59 | def 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 | |
| 65 | noncomputable 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 | |
| 83 | def 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 | |
| 89 | axiom 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 | |
| 93 | axiom finite {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) : |
| 94 | Finite (Vertex M S) |
| 95 | |
| 96 | axiom 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 | |
| 101 | axiom priority_positive {u z : ℕ} (D : WordCondition u z) (q : Fin D.states) : |
| 102 | 0 < ceiling D - D.priority q |
| 103 | |
| 104 | axiom 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 | |
| 109 | axiom 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 | |
| 113 | axiom 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 | |
| 118 | axiom 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 | |
| 123 | end Lax369799.ModalAcceptanceGame |
| 124 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments