Existential projection of recognizable languages
Lax369799.RecognitionProjection · concepts/Lax369799/RecognitionProjection.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Forgetting vertex marks preserves recognizability. More generally, a surjective rank-preserving letter map induces an existential projection: a system is accepted if its vertices admit labels above their old labels that form an accepted system. Nonempty powerset evaluation records all possible evaluations of these choices.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.NonemptyPowersets |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Existential projection of recognizable languages |
| 6 | type: theorem |
| 7 | --- |
| 8 | Forgetting vertex marks preserves recognizability. More generally, a |
| 9 | surjective rank-preserving letter map induces an existential projection: |
| 10 | a system is accepted if its vertices admit labels above their old labels |
| 11 | that form an accepted system. Nonempty powerset evaluation records all |
| 12 | possible evaluations of these choices. |
| 13 | -/ |
| 14 | namespace Lax369799.RecognitionProjection |
| 15 | open RankedSystems Algebras PolynomialContexts |
| 16 | |
| 17 | def Projected {A B : RankedSet} (η : RankedMap A B) (L : Language A) : Language B := |
| 18 | {S | ∃ q : ∀ v, A (S.val.graph.label v).1, |
| 19 | (∀ v, η _ (q v) = (S.val.graph.label v).2) ∧ withLabels S q ∈ L} |
| 20 | |
| 21 | axiom recognizable {A B : RankedSet} (η : RankedMap A B) |
| 22 | (hη : ∀ n, Function.Surjective (η n)) (L : Language A) (hL : Recognizable L) : |
| 23 | Recognizable (Projected η L) |
| 24 | |
| 25 | end Lax369799.RecognitionProjection |
| 26 |
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments