Regular-tree recognition from unfold-invariant recognition
Lax369799.Regularization · concepts/Lax369799/Regularization.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
An unfold-invariant language recognized by a rankwise-finite algebra has a rankwise-finite unfolding-invariant recognizing algebra. First restrict to values realized by systems over the original alphabet. Then quotient by all closed polynomial acceptance tests.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.GeneratedAlgebra |
| 2 | import Lax369799.PolynomialUnfolding |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Regular-tree recognition from unfold-invariant recognition |
| 7 | type: theorem |
| 8 | --- |
| 9 | An unfold-invariant language recognized by a rankwise-finite algebra has |
| 10 | a rankwise-finite unfolding-invariant recognizing algebra. First restrict |
| 11 | to values realized by systems over the original alphabet. Then quotient by |
| 12 | all closed polynomial acceptance tests. |
| 13 | -/ |
| 14 | namespace Lax369799.Regularization |
| 15 | open RankedSystems Algebras |
| 16 | |
| 17 | axiom generated_closed_invariant {A B : RankedSet} (E : Algebra B) (η : RankedMap A B) |
| 18 | (G : Algebra (GeneratedAlgebra.Carrier E η)) |
| 19 | (hG : ∀ n (S : System (GeneratedAlgebra.Carrier E η) n), |
| 20 | (G.eval n S).val = E.eval n (relabelSystem (GeneratedAlgebra.projection E η) S)) |
| 21 | (F : Set (B 0)) (L : Language A) (hL : UnfoldInvariantLanguage L) (hrec : Recognizes E η F L) : |
| 22 | PolynomialUnfolding.ClosedInvariant G {b | b.val ∈ F} |
| 23 | |
| 24 | axiom regular_tree_recognizable {A : RankedSet} (L : Language A) |
| 25 | (hL : UnfoldInvariantLanguage L) (hrec : Recognizable L) : RegularTreeRecognizable L |
| 26 | |
| 27 | end Lax369799.Regularization |
| 28 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments