Translating the modal acceptance game to a sentence
Lax369799.ModalGameTranslation · concepts/Lax369799/ModalGameTranslation.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Translate the projected priority equations into formulas by binding a finite vector of variables at each priority. Capture-avoiding substitution supplies the boundary parameters; finite equation elimination implements each vector binder in the scalar mu-calculus. The resulting sentence is independent of the input graph and defines the game's winning region.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.ModalGameEquations |
| 2 | import Lax369799.FiniteMuEquations |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Translating the modal acceptance game to a sentence |
| 7 | type: theorem |
| 8 | --- |
| 9 | Translate the projected priority equations into formulas by binding a |
| 10 | finite vector of variables at each priority. Capture-avoiding substitution |
| 11 | supplies the boundary parameters; finite equation elimination implements |
| 12 | each vector binder in the scalar mu-calculus. The resulting sentence is |
| 13 | independent of the input graph and defines the game's winning region. |
| 14 | -/ |
| 15 | namespace Lax369799.ModalGameTranslation |
| 16 | open TransitionSystems TransitionEncoding UnfoldAutomata ModalTransitions ModalAcceptanceGame |
| 17 | open ModalMuCalculus MuSubstitution |
| 18 | open ModalGameEquations (statePriority) |
| 19 | attribute [local instance] Classical.propDecidable |
| 20 | |
| 21 | noncomputable def bindBoundary {P : Type} |
| 22 | (M : UnfoldAutomaton (TransitionAlphabet P)) {m : ℕ} |
| 23 | (n : ℕ) (θ : ℕ → Fin M.condition.states → Formula P m) : |
| 24 | ℕ → Fin M.condition.states → Formula P (M.condition.states + m) := |
| 25 | fun p q => if p = n then .variable (Fin.castAdd m q) |
| 26 | else rename (Fin.natAdd M.condition.states) (θ p q) |
| 27 | |
| 28 | noncomputable def formulas {P : Type} [Fintype P] |
| 29 | (M : UnfoldAutomaton (TransitionAlphabet P)) : |
| 30 | (n : ℕ) → {m : ℕ} → (ℕ → Fin M.condition.states → Formula P m) → |
| 31 | Fin M.condition.states → Formula P m |
| 32 | | 0, _, θ => fun q => substitute (θ (statePriority M q)) (transitionFormula M q) |
| 33 | | n + 1, _, θ => Lax369799.FiniteMuEquations.solve |
| 34 | (if Even n then .greatest else .least) (formulas M n (bindBoundary M n θ)) |
| 35 | |
| 36 | noncomputable def sentence {P : Type} [Fintype P] |
| 37 | (M : UnfoldAutomaton (TransitionAlphabet P)) (q : Fin M.condition.states) : Sentence P := |
| 38 | formulas M (ceiling M.condition + 1) (fun _ _ => .bot) q |
| 39 | |
| 40 | axiom formulas_correct {P : Type} [Fintype P] |
| 41 | (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) |
| 42 | (n : ℕ) {m : ℕ} (θ : ℕ → Fin M.condition.states → Formula P m) |
| 43 | (ρ : Fin m → Set S.Vertex) : |
| 44 | (fun q => (formulas M n θ q).eval S ρ) = |
| 45 | Lax369799.ModalGameEquations.solve M S n (fun p q => (θ p q).eval S ρ) |
| 46 | |
| 47 | axiom sentence_correct {P : Type} [Fintype P] |
| 48 | (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) |
| 49 | (q : Fin M.condition.states) (v : S.Vertex) : |
| 50 | v ∈ (sentence M q).eval S Fin.elim0 ↔ |
| 51 | Lax369799.ParityWinningRegions.Winning (game M S) true (position q v) |
| 52 | |
| 53 | axiom game_to_mu {P : Type} [Finite P] |
| 54 | (M : UnfoldAutomaton (TransitionAlphabet P)) : |
| 55 | ∃ φ : Sentence P, ∀ S, |
| 56 | Lax369799.ParityWinningRegions.Winning (game M S) true |
| 57 | (position M.condition.initial S.initial) ↔ Models S φ |
| 58 | |
| 59 | end Lax369799.ModalGameTranslation |
| 60 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments