Executable finite model checking for both logics
Lax369799.FiniteModelChecking · concepts/Lax369799/FiniteModelChecking.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Finite graphs and set assignments are Boolean tables. Quantifiers range over explicitly finite types, including all Boolean set assignments. The fixed-point clauses test every pre-fixed or post-fixed subset.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.UnrestrictedLogic |
| 2 | import Mathlib.Data.Fintype.Pi |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Executable finite model checking for both logics |
| 7 | type: theorem |
| 8 | --- |
| 9 | Finite graphs and set assignments are Boolean tables. Quantifiers range |
| 10 | over explicitly finite types, including all Boolean set assignments. |
| 11 | The fixed-point clauses test every pre-fixed or post-fixed subset. |
| 12 | -/ |
| 13 | |
| 14 | namespace Lax369799.FiniteModelChecking |
| 15 | |
| 16 | abbrev Graph (P : Type) (k : ℕ) := |
| 17 | Fin (k+1) × (Fin (k+1) → Fin (k+1) → Bool) × (Fin (k+1) → P → Bool) |
| 18 | |
| 19 | def semantics {P : Type} {k : ℕ} (G : Graph P k) : UnrestrictedTransitionSystems.TransitionSystem P := |
| 20 | ⟨Fin (k+1),G.1,(fun v w => G.2.1 v w = true),(fun v => {p | G.2.2 v p = true})⟩ |
| 21 | |
| 22 | def msoCheck {P : Type} {k : ℕ} (G : Graph P k) : |
| 23 | {m n : ℕ} → MonadicSecondOrder.Formula P m n → (Fin m → Fin (k+1)) → |
| 24 | (Fin n → Fin (k+1) → Bool) → Bool |
| 25 | | _, _, .equal x y, ρ, _ => decide (ρ x = ρ y) |
| 26 | | _, _, .initial x, ρ, _ => decide (ρ x = G.1) |
| 27 | | _, _, .proposition p x, ρ, _ => G.2.2 (ρ x) p |
| 28 | | _, _, .edge x y, ρ, _ => G.2.1 (ρ x) (ρ y) |
| 29 | | _, _, .member x X, ρ, σ => σ X (ρ x) |
| 30 | | _, _, .neg φ, ρ, σ => !(msoCheck G φ ρ σ) |
| 31 | | _, _, .disj φ ψ, ρ, σ => msoCheck G φ ρ σ || msoCheck G ψ ρ σ |
| 32 | | _, _, .existsVertex φ, ρ, σ => decide (∃ v,msoCheck G φ (Fin.cases v ρ) σ = true) |
| 33 | | _, _, .existsSet φ, ρ, σ => decide (∃ X : Fin (k+1) → Bool,msoCheck G φ ρ (Fin.cases X σ) = true) |
| 34 | |
| 35 | def muCheck {P : Type} {k : ℕ} (G : Graph P k) : |
| 36 | {n : ℕ} → ModalMuCalculus.Formula P n → (Fin n → Fin (k+1) → Bool) → Fin (k+1) → Bool |
| 37 | | _, .top, _, _ => true |
| 38 | | _, .bot, _, _ => false |
| 39 | | _, .proposition p, _, v => G.2.2 v p |
| 40 | | _, .negProposition p, _, v => !(G.2.2 v p) |
| 41 | | _, .variable i, ρ, v => ρ i v |
| 42 | | _, .conj φ ψ, ρ, v => muCheck G φ ρ v && muCheck G ψ ρ v |
| 43 | | _, .disj φ ψ, ρ, v => muCheck G φ ρ v || muCheck G ψ ρ v |
| 44 | | _, .diamond φ, ρ, v => decide (∃ w,G.2.1 v w = true ∧ muCheck G φ ρ w = true) |
| 45 | | _, .box φ, ρ, v => decide (∀ w,G.2.1 v w = true → muCheck G φ ρ w = true) |
| 46 | | _, .mu φ, ρ, v => decide (∀ X : Fin (k+1) → Bool, |
| 47 | (∀ w,muCheck G φ (Fin.cases X ρ) w = true → X w = true) → X v = true) |
| 48 | | _, .nu φ, ρ, v => decide (∃ X : Fin (k+1) → Bool, |
| 49 | X v = true ∧ ∀ w,X w = true → muCheck G φ (Fin.cases X ρ) w = true) |
| 50 | |
| 51 | def mso {P : Type} {k : ℕ} (G : Graph P k) (φ : MonadicSecondOrder.Sentence P) : Bool := |
| 52 | msoCheck G φ Fin.elim0 Fin.elim0 |
| 53 | |
| 54 | def mu {P : Type} {k : ℕ} (G : Graph P k) (φ : ModalMuCalculus.Sentence P) : Bool := |
| 55 | muCheck G φ Fin.elim0 G.1 |
| 56 | |
| 57 | axiom mso_correct {P : Type} {k m n : ℕ} (G : Graph P k) |
| 58 | (φ : MonadicSecondOrder.Formula P m n) (ρ : Fin m → Fin (k+1)) |
| 59 | (σ : Fin n → Fin (k+1) → Bool) : |
| 60 | msoCheck G φ ρ σ = true ↔ UnrestrictedLogic.msoEval (semantics G) φ ρ (fun i => {v | σ i v = true}) |
| 61 | |
| 62 | axiom mu_correct {P : Type} {k n : ℕ} (G : Graph P k) |
| 63 | (φ : ModalMuCalculus.Formula P n) (ρ : Fin n → Fin (k+1) → Bool) (v : Fin (k+1)) : |
| 64 | muCheck G φ ρ v = true ↔ v ∈ UnrestrictedLogic.muEval (semantics G) φ (fun i => {w | ρ i w = true}) |
| 65 | |
| 66 | end Lax369799.FiniteModelChecking |
Builds on
Used by
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments