Modal mu-calculus
Lax369799.ModalMuCalculus · concepts/Lax369799/ModalMuCalculus.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
The modal mu-calculus is presented in negation normal form: negation is allowed on proposition letters, and all fixed-point variables occur positively. Formulas have conjunction, disjunction, box, diamond, and least and greatest fixed points. A binder introduces variable zero and shifts the previous free variables. Least fixed points are intersections of pre-fixed points; greatest fixed points are unions of post-fixed points. A closed formula is evaluated at the initial vertex.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.TransitionSystems |
| 2 | import Mathlib.Order.CompleteLattice.Basic |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Modal mu-calculus |
| 7 | type: definition |
| 8 | --- |
| 9 | The modal mu-calculus is presented in negation normal form: negation is |
| 10 | allowed on proposition letters, and all fixed-point variables occur |
| 11 | positively. Formulas have conjunction, disjunction, box, diamond, and least |
| 12 | and greatest fixed points. A binder introduces variable zero and shifts |
| 13 | the previous free variables. Least fixed points are intersections of |
| 14 | pre-fixed points; greatest fixed points are unions of post-fixed points. |
| 15 | A closed formula is evaluated at the initial vertex. |
| 16 | -/ |
| 17 | |
| 18 | namespace Lax369799.ModalMuCalculus |
| 19 | open TransitionSystems |
| 20 | |
| 21 | inductive Formula (P : Type) : ℕ → Type |
| 22 | | top {n} : Formula P n |
| 23 | | bot {n} : Formula P n |
| 24 | | proposition {n} : P → Formula P n |
| 25 | | negProposition {n} : P → Formula P n |
| 26 | | variable {n} : Fin n → Formula P n |
| 27 | | conj {n} : Formula P n → Formula P n → Formula P n |
| 28 | | disj {n} : Formula P n → Formula P n → Formula P n |
| 29 | | diamond {n} : Formula P n → Formula P n |
| 30 | | box {n} : Formula P n → Formula P n |
| 31 | | mu {n} : Formula P (n + 1) → Formula P n |
| 32 | | nu {n} : Formula P (n + 1) → Formula P n |
| 33 | |
| 34 | def Formula.eval {P : Type} (S : TransitionSystem P) : |
| 35 | {n : ℕ} → Formula P n → (Fin n → Set S.Vertex) → Set S.Vertex |
| 36 | | _, .top, _ => Set.univ |
| 37 | | _, .bot, _ => ∅ |
| 38 | | _, .proposition p, _ => {v | p ∈ S.valuation v} |
| 39 | | _, .negProposition p, _ => {v | p ∉ S.valuation v} |
| 40 | | _, .variable x, ρ => ρ x |
| 41 | | _, .conj φ ψ, ρ => φ.eval S ρ ∩ ψ.eval S ρ |
| 42 | | _, .disj φ ψ, ρ => φ.eval S ρ ∪ ψ.eval S ρ |
| 43 | | _, .diamond φ, ρ => {v | ∃ w, S.edge v w ∧ w ∈ φ.eval S ρ} |
| 44 | | _, .box φ, ρ => {v | ∀ w, S.edge v w → w ∈ φ.eval S ρ} |
| 45 | | _, .mu φ, ρ => sInf {X | φ.eval S (Fin.cases X ρ) ⊆ X} |
| 46 | | _, .nu φ, ρ => sSup {X | X ⊆ φ.eval S (Fin.cases X ρ)} |
| 47 | |
| 48 | abbrev Sentence (P : Type) := Formula P 0 |
| 49 | |
| 50 | def Models {P : Type} (S : TransitionSystem P) (φ : Sentence P) : Prop := |
| 51 | S.initial ∈ φ.eval S Fin.elim0 |
| 52 | |
| 53 | def Definable {P : Type} (L : Set (TransitionSystem P)) : Prop := |
| 54 | ∃ φ : Sentence P, ∀ S, S ∈ L ↔ Models S φ |
| 55 | |
| 56 | end Lax369799.ModalMuCalculus |
| 57 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments