MSO-definable languages are algebraically recognisable
Lax369799.MSORecognition · concepts/Lax369799/MSORecognition.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
An MSO sentence on finite transition systems defines, through decoding, a language of ranked systems recognised by a rankwise-finite algebra. This is in Section 6.2. The vocabulary uses a finite set of proposition letters uniformly across all ranks.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.Algebras |
| 2 | import Lax369799.MonadicSecondOrder |
| 3 | import Lax369799.TransitionEncoding |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: MSO-definable languages are algebraically recognisable |
| 8 | type: theorem |
| 9 | --- |
| 10 | An MSO sentence on finite transition systems defines, through decoding, a |
| 11 | language of ranked systems recognised by a rankwise-finite algebra. |
| 12 | This is `lemma:MSO-is-recognisable` in Section 6.2. The vocabulary uses a |
| 13 | finite set of proposition letters uniformly across all ranks. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.MSORecognition |
| 17 | open Algebras TransitionEncoding |
| 18 | |
| 19 | axiom mso_recognizable {P : Type} [Finite P] (φ : MonadicSecondOrder.Sentence P) : |
| 20 | Recognizable {S | MonadicSecondOrder.Models (decode S) φ} |
| 21 | |
| 22 | end Lax369799.MSORecognition |
| 23 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments