MSO translation and bisimulation invariance of the mu-calculus
Lax369799.MuCalculusTheorems · concepts/Lax369799/MuCalculusTheorems.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Every modal mu-calculus sentence has an equivalent MSO sentence, and its truth is preserved by bisimulation. These standard results supply the reverse implication of the main theorem. The semantic monotonicity lemma justifies the fixed-point clauses of the mu-calculus semantics.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.MonadicSecondOrder |
| 2 | import Lax369799.ModalMuCalculus |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: MSO translation and bisimulation invariance of the mu-calculus |
| 7 | type: theorem |
| 8 | --- |
| 9 | Every modal mu-calculus sentence has an equivalent MSO sentence, and its |
| 10 | truth is preserved by bisimulation. These standard results supply the |
| 11 | reverse implication of the main theorem. The semantic monotonicity lemma |
| 12 | justifies the fixed-point clauses of the mu-calculus semantics. |
| 13 | -/ |
| 14 | |
| 15 | namespace Lax369799.MuCalculusTheorems |
| 16 | open TransitionSystems |
| 17 | |
| 18 | axiom eval_monotone {P : Type} (S : TransitionSystem P) {n : ℕ} |
| 19 | (φ : ModalMuCalculus.Formula P n) (ρ σ : Fin n → Set S.Vertex) |
| 20 | (h : ∀ i, ρ i ⊆ σ i) : φ.eval S ρ ⊆ φ.eval S σ |
| 21 | |
| 22 | axiom mu_to_mso {P : Type} (φ : ModalMuCalculus.Sentence P) : |
| 23 | ∃ ψ : MonadicSecondOrder.Sentence P, ∀ S, |
| 24 | ModalMuCalculus.Models S φ ↔ MonadicSecondOrder.Models S ψ |
| 25 | |
| 26 | axiom mu_bisimulation_invariant {P : Type} (φ : ModalMuCalculus.Sentence P) : |
| 27 | BisimulationInvariant {S | ModalMuCalculus.Models S φ} |
| 28 | |
| 29 | end Lax369799.MuCalculusTheorems |
| 30 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments