Executable compilation of modal priority equations
Lax369799.PriorityCompilation · concepts/Lax369799/PriorityCompilation.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
An explicit finite family of positive modal transition formulas and a priority map compile to a scalar sentence by structural recursion. The compiler uses only finite syntax operations. A semantic certificate for the transition formulas identifies its output with the modal acceptance game. This is the effective final stage, with the finite transition table provided as input.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FiniteMuEquations |
| 2 | import Lax369799.ModalGameEquations |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Executable compilation of modal priority equations |
| 7 | type: theorem |
| 8 | --- |
| 9 | An explicit finite family of positive modal transition formulas and a |
| 10 | priority map compile to a scalar sentence by structural recursion. The |
| 11 | compiler uses only finite syntax operations. A semantic certificate for |
| 12 | the transition formulas identifies its output with the modal acceptance |
| 13 | game. This is the effective final stage, with the finite transition table |
| 14 | provided as input. |
| 15 | -/ |
| 16 | |
| 17 | namespace Lax369799.PriorityCompilation |
| 18 | open ModalMuCalculus MuSubstitution TransitionEncoding TransitionSystems UnfoldAutomata |
| 19 | open ModalAcceptanceGame |
| 20 | |
| 21 | def boundary {P : Type} {d m : ℕ} (n : ℕ) |
| 22 | (θ : ℕ → Fin d → Formula P m) : ℕ → Fin d → Formula P (d+m) := |
| 23 | fun p q => if p = n then .variable (Fin.castAdd m q) |
| 24 | else rename (Fin.natAdd d) (θ p q) |
| 25 | |
| 26 | def compile {P : Type} {d : ℕ} (priority : Fin d → ℕ) |
| 27 | (transition : Fin d → Formula P d) : |
| 28 | (n : ℕ) → {m : ℕ} → (ℕ → Fin d → Formula P m) → Fin d → Formula P m |
| 29 | | 0, _, θ => fun q => substitute (θ (priority q)) (transition q) |
| 30 | | n+1, _, θ => FiniteMuEquations.solve |
| 31 | (if n % 2 = 0 then .greatest else .least) (compile priority transition n (boundary n θ)) |
| 32 | |
| 33 | def sentence {P : Type} {d : ℕ} (priority : Fin d → ℕ) |
| 34 | (transition : Fin d → Formula P d) (depth : ℕ) (initial : Fin d) : Sentence P := |
| 35 | compile priority transition depth (fun _ _ => .bot) initial |
| 36 | |
| 37 | axiom compile_correct {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) |
| 38 | (δ : Fin M.condition.states → Formula P M.condition.states) |
| 39 | (S : TransitionSystem P) |
| 40 | (hδ : ∀ q ρ v, v ∈ (δ q).eval S ρ ↔ ModalTransitions.OneStep M q S v ρ) |
| 41 | (n : ℕ) {m : ℕ} (θ : ℕ → Fin M.condition.states → Formula P m) |
| 42 | (ρ : Fin m → Set S.Vertex) : |
| 43 | (fun q => (compile (ModalGameEquations.statePriority M) δ n θ q).eval S ρ) = |
| 44 | ModalGameEquations.solve M S n (fun p q => (θ p q).eval S ρ) |
| 45 | |
| 46 | axiom sentence_correct {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) |
| 47 | (δ : Fin M.condition.states → Formula P M.condition.states) |
| 48 | (S : TransitionSystem P) |
| 49 | (hδ : ∀ q ρ v, v ∈ (δ q).eval S ρ ↔ ModalTransitions.OneStep M q S v ρ) : |
| 50 | Models S (sentence (ModalGameEquations.statePriority M) δ (ceiling M.condition+1) |
| 51 | M.condition.initial) ↔ |
| 52 | ParityWinningRegions.Winning (game M S) true (position M.condition.initial S.initial) |
| 53 | |
| 54 | end Lax369799.PriorityCompilation |
| 55 |
Used by
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments