Scalar formulas for finite fixed-point equation systems
Lax369799.FiniteMuEquations · concepts/Lax369799/FiniteMuEquations.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A simultaneous least or greatest solution of finitely many positive modal equations is expressed by ordinary nested scalar fixed points. Eliminate the tail equations with the head variable as a parameter, solve the head equation, and substitute that solution in the tail.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.MuSubstitution |
| 2 | import Mathlib.Data.Fin.Tuple.Basic |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Scalar formulas for finite fixed-point equation systems |
| 7 | type: theorem |
| 8 | --- |
| 9 | A simultaneous least or greatest solution of finitely many positive |
| 10 | modal equations is expressed by ordinary nested scalar fixed points. |
| 11 | Eliminate the tail equations with the head variable as a parameter, |
| 12 | solve the head equation, and substitute that solution in the tail. |
| 13 | -/ |
| 14 | namespace Lax369799.FiniteMuEquations |
| 15 | open ModalMuCalculus TransitionSystems MuSubstitution |
| 16 | |
| 17 | inductive Binder where | least | greatest |
| 18 | |
| 19 | def bind {P : Type} {m : ℕ} : Binder → Formula P (m + 1) → Formula P m |
| 20 | | .least, φ => .mu φ |
| 21 | | .greatest, φ => .nu φ |
| 22 | |
| 23 | def move (n m : ℕ) : Fin ((n + 1) + m) → Fin (n + (m + 1)) := |
| 24 | Fin.addCases (Fin.cases (Fin.natAdd n 0) (fun i => Fin.castAdd (m + 1) i)) |
| 25 | (fun j => Fin.natAdd n j.succ) |
| 26 | |
| 27 | def headSubstitution {P : Type} {n m : ℕ} (g : Fin n → Formula P (m + 1)) : |
| 28 | Fin ((n + 1) + m) → Formula P (m + 1) := |
| 29 | Fin.addCases (Fin.cases (.variable 0) g) (fun j => .variable j.succ) |
| 30 | |
| 31 | def solve {P : Type} (b : Binder) : {n m : ℕ} → (Fin n → Formula P (n + m)) → Fin n → Formula P m |
| 32 | | 0, _, _ => Fin.elim0 |
| 33 | | n + 1, m, φ => |
| 34 | let g := solve b (fun i : Fin n => rename (move n m) (φ i.succ)) |
| 35 | let a := bind b (substitute |
| 36 | (Fin.addCases (Fin.cases (.variable 0) g) (fun j => .variable j.succ)) (φ 0)) |
| 37 | Fin.cases a (fun i => substitute (Fin.cases a Formula.variable) (g i)) |
| 38 | |
| 39 | def value {P : Type} (b : Binder) (S : TransitionSystem P) {n m : ℕ} |
| 40 | (φ : Fin n → Formula P (n + m)) (ρ : Fin m → Set S.Vertex) : Fin n → Set S.Vertex := |
| 41 | match b with |
| 42 | | .least => sInf {X | ∀ i, (φ i).eval S (Fin.addCases X ρ) ⊆ X i} |
| 43 | | .greatest => sSup {X | ∀ i, X i ⊆ (φ i).eval S (Fin.addCases X ρ)} |
| 44 | |
| 45 | axiom solve_correct {P : Type} (b : Binder) (S : TransitionSystem P) {n m : ℕ} |
| 46 | (φ : Fin n → Formula P (n + m)) (ρ : Fin m → Set S.Vertex) : |
| 47 | (fun i => (solve b φ i).eval S ρ) = value b S φ ρ |
| 48 | |
| 49 | end Lax369799.FiniteMuEquations |
| 50 |
Builds on
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments