Acceptance from finite families of covering components
Lax369799.FiniteCoverFamilies · concepts/Lax369799/FiniteCoverFamilies.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A finite family of presentation maps jointly covers a target if it covers all vertices and marks and lifts every successor at each source vertex. Acceptance of the components implies acceptance of the target.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.ExpandedSyntacticAlgebra |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Acceptance from finite families of covering components |
| 6 | type: theorem |
| 7 | --- |
| 8 | A finite family of presentation maps jointly covers a target if it covers |
| 9 | all vertices and marks and lifts every successor at each source vertex. |
| 10 | Acceptance of the components implies acceptance of the target. |
| 11 | -/ |
| 12 | namespace Lax369799.FiniteCoverFamilies |
| 13 | open RankedSystems (RankedSet) |
| 14 | open FinitePresentations FiniteSyntacticAlgebra FiniteContextualOrder FiniteAcceptance |
| 15 | open ExpandedSyntacticAlgebra |
| 16 | |
| 17 | structure JointCover {A : RankedSet} {m : ℕ} (T : Fin m → FiniteSystem A 0) |
| 18 | (P : FiniteSystem A 0) where |
| 19 | map : ∀ i, FiniteMorphisms.Morphism (T i) P |
| 20 | edges : ∀ i v d t, P.graph.edge ((map i).toFun v) d t → |
| 21 | ∃ s, (T i).graph.edge v d s ∧ Sum.map (map i).toFun id s = t |
| 22 | vertices : ∀ v : P.Vertex, ∃ i w, (map i).toFun w = v |
| 23 | initials : ∀ v, v ∈ P.graph.initial → ∃ i w, w ∈ (T i).graph.initial ∧ (map i).toFun w = v |
| 24 | roots : ∀ v, v ∈ P.graph.root → ∃ i w, w ∈ (T i).graph.root ∧ (map i).toFun w = v |
| 25 | |
| 26 | |
| 27 | axiom acceptance {A : RankedSet} (L : Algebras.Language A) |
| 28 | [Finite (Carrier (Accepting L) 0)] (E : SyntacticAlgebra L) |
| 29 | {m : ℕ} (hm : 0 < m) (T : Fin m → FiniteSystem (Carrier (Accepting L)) 0) |
| 30 | (P : FiniteSystem (Carrier (Accepting L)) 0) (F : JointCover T P) |
| 31 | (hT : ∀ i, AcceptingClass (Accepting L) (E.algebra.eval 0 (T i))) : |
| 32 | AcceptingClass (Accepting L) (E.algebra.eval 0 P) |
| 33 | |
| 34 | end Lax369799.FiniteCoverFamilies |
| 35 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments