Boolean closure and inverse relabelling of recognizable languages
Lax369799.RecognitionClosure · concepts/Lax369799/RecognitionClosure.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Rankwise-finite algebraic recognition is preserved by Boolean operations and inverse relabelling. Products combine recognizing algebras; complement changes the accepting subset, and inverse relabelling composes letter maps. These are the Boolean and cylindrification clauses of Section 3.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.Algebras |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Boolean closure and inverse relabelling of recognizable languages |
| 6 | type: theorem |
| 7 | --- |
| 8 | Rankwise-finite algebraic recognition is preserved by Boolean operations |
| 9 | and inverse relabelling. Products combine recognizing algebras; complement |
| 10 | changes the accepting subset, and inverse relabelling composes letter maps. |
| 11 | These are the Boolean and cylindrification clauses of Section 3. |
| 12 | -/ |
| 13 | namespace Lax369799.RecognitionClosure |
| 14 | open RankedSystems Algebras |
| 15 | |
| 16 | axiom complement {A : RankedSet} (L : Language A) (h : Recognizable L) : Recognizable Lᶜ |
| 17 | |
| 18 | axiom intersection {A : RankedSet} (L K : Language A) |
| 19 | (hL : Recognizable L) (hK : Recognizable K) : Recognizable (L ∩ K) |
| 20 | |
| 21 | axiom union {A : RankedSet} (L K : Language A) |
| 22 | (hL : Recognizable L) (hK : Recognizable K) : Recognizable (L ∪ K) |
| 23 | |
| 24 | axiom inverse_relabel {A B : RankedSet} (η : RankedMap A B) (L : Language B) |
| 25 | (hL : Recognizable L) : Recognizable {S | relabelSystem η S ∈ L} |
| 26 | |
| 27 | end Lax369799.RecognitionClosure |
| 28 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments