Executable bounded comparison of MSO and modal formulas
Lax369799.FiniteTesting · concepts/Lax369799/FiniteTesting.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Enumerate finite Boolean graph tables up to the prescribed vertex bound. A second-order closure test filters exactly the reachable models, and the verified model checkers compare the two sentence semantics.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.FiniteModelChecking |
| 2 | import Lax369799.FiniteModalData |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Executable bounded comparison of MSO and modal formulas |
| 7 | type: theorem |
| 8 | --- |
| 9 | Enumerate finite Boolean graph tables up to the prescribed vertex bound. |
| 10 | A second-order closure test filters exactly the reachable models, and |
| 11 | the verified model checkers compare the two sentence semantics. |
| 12 | -/ |
| 13 | |
| 14 | namespace Lax369799.FiniteTesting |
| 15 | open FiniteModelChecking |
| 16 | |
| 17 | def valid {P : Type} {k : ℕ} (G : Graph P k) : Bool := |
| 18 | decide (∀ X : Fin (k+1) → Bool,X G.1 = true → |
| 19 | (∀ v w,X v = true → G.2.1 v w = true → X w = true) → ∀ v,X v = true) |
| 20 | |
| 21 | def agree {P : Type} {k : ℕ} (G : Graph P k) (φ : MonadicSecondOrder.Sentence P) |
| 22 | (ψ : ModalMuCalculus.Sentence P) : Bool := |
| 23 | if valid G then (mso G φ == mu G ψ) else true |
| 24 | |
| 25 | def test {P : Type} [Fintype P] [Encodable P] [DecidableEq P] (K : ℕ) |
| 26 | (φ : MonadicSecondOrder.Sentence P) (ψ : ModalMuCalculus.Sentence P) : Bool := |
| 27 | (List.range K).all (fun k => (FiniteModalData.elements (Graph P k)).all (fun G => agree G φ ψ)) |
| 28 | |
| 29 | open TransitionSystems |
| 30 | |
| 31 | axiom test_correct {P : Type} [Fintype P] [Encodable P] [DecidableEq P] (K : ℕ) |
| 32 | (φ : MonadicSecondOrder.Sentence P) (ψ : ModalMuCalculus.Sentence P) : |
| 33 | test K φ ψ = true ↔ ∀ S : TransitionSystem P,S.size ≤ K → |
| 34 | (MonadicSecondOrder.Models S φ ↔ ModalMuCalculus.Models S ψ) |
| 35 | |
| 36 | end Lax369799.FiniteTesting |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments