Modal equations on input vertices
Lax369799.ModalGameEquations · concepts/Lax369799/ModalGameEquations.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Project winning regions to word-state/input positions. Marking positions are determined by universal successor conditions and terminals by their outcomes. The projection and its monotone section preserve the least and greatest solutions of each stopped priority game. The resulting nested equations have one coordinate per word state and are evaluated on the original input graph.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.ModalAcceptanceGame |
| 2 | import Lax369799.FixedPointRetraction |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Modal equations on input vertices |
| 7 | type: theorem |
| 8 | --- |
| 9 | Project winning regions to word-state/input positions. Marking positions |
| 10 | are determined by universal successor conditions and terminals by their |
| 11 | outcomes. The projection and its monotone section preserve the least and |
| 12 | greatest solutions of each stopped priority game. The resulting nested |
| 13 | equations have one coordinate per word state and are evaluated on the |
| 14 | original input graph. |
| 15 | -/ |
| 16 | namespace Lax369799.ModalGameEquations |
| 17 | open TransitionSystems TransitionEncoding UnfoldAutomata ModalTransitions ModalAcceptanceGame |
| 18 | open FiniteParityGames ParityWinningRegions ParityFixedPoints |
| 19 | attribute [local instance] Classical.propDecidable |
| 20 | |
| 21 | def project {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) : |
| 22 | Set (Vertex M S) →o Marking M S where |
| 23 | toFun := fun X q => {v | position q v ∈ X} |
| 24 | monotone' := fun _ _ h _ _ hv => h hv |
| 25 | |
| 26 | def lift {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) : |
| 27 | Marking M S →o Set (Vertex M S) where |
| 28 | toFun := fun X t => match t with |
| 29 | | .inl (q, v) => v ∈ X q |
| 30 | | .inr (.inl (v, ρ)) => ∀ q w, S.edge v w → w ∈ ρ q → w ∈ X q |
| 31 | | .inr (.inr b) => b = true |
| 32 | monotone' := by |
| 33 | intro X Y h t ht |
| 34 | rcases t with ⟨q, v⟩ | (⟨v, ρ⟩ | b) |
| 35 | · exact h q ht |
| 36 | · exact fun q w hw hρ => h q (ht q w hw hρ) |
| 37 | · exact ht |
| 38 | |
| 39 | def statePriority {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) |
| 40 | (q : Fin M.condition.states) : ℕ := ceiling M.condition - M.condition.priority q |
| 41 | |
| 42 | def boundary {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) |
| 43 | (B : Fin M.condition.states → S.Vertex → Prop) : Set (Vertex M S) := |
| 44 | {t | match t with |
| 45 | | .inl (q, v) => B q v |
| 46 | | _ => False} |
| 47 | |
| 48 | noncomputable def stopped {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) |
| 49 | (S : TransitionSystem P) (n : ℕ) (ρ : ℕ → Marking M S) : Game (Vertex M S) := |
| 50 | stop (game M S) (boundary M S (fun q _ => n ≤ statePriority M q)) |
| 51 | (boundary M S (fun q v => OneStep M q S v (ρ (statePriority M q)))) |
| 52 | |
| 53 | noncomputable def solve {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) |
| 54 | (S : TransitionSystem P) : ℕ → (ℕ → Marking M S) → Marking M S |
| 55 | | 0, ρ => fun q => {v | OneStep M q S v (ρ (statePriority M q))} |
| 56 | | n + 1, ρ => if Even n then |
| 57 | sSup {X : Marking M S | X ≤ solve M S n (Function.update ρ n X)} |
| 58 | else sInf {X : Marking M S | solve M S n (Function.update ρ n X) ≤ X} |
| 59 | |
| 60 | axiom solve_stopped {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) |
| 61 | (S : TransitionSystem P) (n : ℕ) (ρ : ℕ → Marking M S) : |
| 62 | project M S (Winning (stopped M S n ρ) true) = solve M S n ρ |
| 63 | |
| 64 | axiom winning {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) |
| 65 | (S : TransitionSystem P) (n : ℕ) (hn : ∀ q, statePriority M q < n) |
| 66 | (ρ : ℕ → Marking M S) : |
| 67 | project M S (Winning (game M S) true) = solve M S n ρ |
| 68 | |
| 69 | end Lax369799.ModalGameEquations |
| 70 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments