Bisimulation-invariant algebraic recognition implies mu-calculus definability
Lax369799.AlgebraToMuCalculus · concepts/Lax369799/AlgebraToMuCalculus.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A bisimulation-invariant language over the transition alphabet recognised by a rankwise-finite algebra is definable by a modal mu-calculus sentence on its decoded transition systems. This is in Section 6.4.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.SupportedAlgebras |
| 2 | import Lax369799.Algebras |
| 3 | import Lax369799.ModalMuCalculus |
| 4 | import Lax369799.TransitionEncoding |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Bisimulation-invariant algebraic recognition implies mu-calculus definability |
| 9 | type: theorem |
| 10 | --- |
| 11 | A bisimulation-invariant language over the transition alphabet recognised |
| 12 | by a rankwise-finite algebra is definable by a modal mu-calculus sentence |
| 13 | on its decoded transition systems. This is `thm:alg2mu` in Section 6.4. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.AlgebraToMuCalculus |
| 17 | open RankedSystems Algebras TransitionEncoding |
| 18 | |
| 19 | axiom algebra_to_mu {P : Type} [Finite P] (L : Language (TransitionAlphabet P)) |
| 20 | (hL : ∀ S T, RankedBisimilar S T → (S ∈ L ↔ T ∈ L)) |
| 21 | (hA : SupportedAlgebras.Recognizable L) : |
| 22 | ∃ φ : ModalMuCalculus.Sentence P, ∀ S, S ∈ L ↔ ModalMuCalculus.Models (decode S) φ |
| 23 | |
| 24 | end Lax369799.AlgebraToMuCalculus |
| 25 |
Builds on
Used by
none
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments