Recognition of local vertex and edge tests
Lax369799.LocalRecognition · concepts/Lax369799/LocalRecognition.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Finite path-summary algebras recognize the presence of a vertex satisfying a letter predicate, and the presence of an edge whose endpoints satisfy two specified letter predicates. Reachability from the unique initial vertex makes these global existence tests into path tests.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.PathAlgebra |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Recognition of local vertex and edge tests |
| 6 | type: theorem |
| 7 | --- |
| 8 | Finite path-summary algebras recognize the presence of a vertex satisfying |
| 9 | a letter predicate, and the presence of an edge whose endpoints satisfy |
| 10 | two specified letter predicates. Reachability from the unique initial |
| 11 | vertex makes these global existence tests into path tests. |
| 12 | -/ |
| 13 | namespace Lax369799.LocalRecognition |
| 14 | open RankedSystems Algebras |
| 15 | |
| 16 | axiom occurrence {A : RankedSet} (p : ∀ n, A n → Prop) : |
| 17 | Recognizable {S : System A 0 | ∃ v, p _ (S.val.graph.label v).2} |
| 18 | |
| 19 | axiom edge {A : RankedSet} (p q : ∀ n, A n → Prop) : |
| 20 | Recognizable {S : System A 0 | ∃ v w d, |
| 21 | p _ (S.val.graph.label v).2 ∧ q _ (S.val.graph.label w).2 ∧ S.val.graph.edge v d (.inl w)} |
| 22 | |
| 23 | end Lax369799.LocalRecognition |
| 24 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments