The path criterion and the automaton property
Lax369799.ExtremalPaths · concepts/Lax369799/ExtremalPaths.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A regular branch is a closed unary/nullary system admitting a morphism into the tested set-system. Lemma 95 says that a root-free set-system with all vertices initially reachable and with no blocked unary vertex is accepted exactly when all its regular branches are accepted, provided its unary labels are extremal. Together with canonical direction decomposition this is Definition 90. Corollary 96 establishes both conditions for the rankwise-finite yield-syntactic set-algebra.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.DirectionProjections |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: The path criterion and the automaton property |
| 6 | type: theorem |
| 7 | --- |
| 8 | A regular branch is a closed unary/nullary system admitting a morphism |
| 9 | into the tested set-system. Lemma 95 says that a root-free set-system |
| 10 | with all vertices initially reachable and with no blocked unary vertex |
| 11 | is accepted exactly when all its regular branches are accepted, provided |
| 12 | its unary labels are extremal. Together with canonical direction |
| 13 | decomposition this is Definition 90. Corollary 96 establishes both |
| 14 | conditions for the rankwise-finite yield-syntactic set-algebra. |
| 15 | -/ |
| 16 | |
| 17 | namespace Lax369799.ExtremalPaths |
| 18 | open RankedSystems (RankedSet System) |
| 19 | open FinitePresentations FiniteContextualOrder FiniteSyntacticAlgebra FiniteAcceptance |
| 20 | open ExpandedSyntacticAlgebra |
| 21 | |
| 22 | def Unary {A : RankedSet} (P : FiniteSystem A 0) : Prop := |
| 23 | ∀ v, (P.graph.label v).1 ≤ 1 |
| 24 | |
| 25 | def RegularBranch {A : RankedSet} (G : FiniteSystem A 0) (B : System A 0) : Prop := |
| 26 | Unary (ofSetSystem B.val) ∧ Nonempty (FiniteMorphisms.Morphism (ofSetSystem B.val) G) |
| 27 | |
| 28 | def HasAutomatonProperty {A : RankedSet} (L : Algebras.Language A) (E : SyntacticAlgebra L) : Prop := |
| 29 | (∀ k (_hk : 1 ≤ k) (a : Carrier (Accepting L) k), ExtendedContexts.ExtremalElement L E a → |
| 30 | E.algebra.eval k (DirectionProjections.parallel (DirectionProjections.direction E.algebra a)) = a ∧ |
| 31 | ∀ i, ExtendedContexts.ExtremalElement L E (DirectionProjections.direction E.algebra a i)) ∧ |
| 32 | (∀ G : FiniteSystem (Carrier (Accepting L)) 0, Unary G → G.graph.root = ∅ → Reachable G → |
| 33 | (∀ v, (G.graph.label v).1 = 1 → ∃ w, G.graph.edge v 0 (.inl w)) → |
| 34 | (∀ v (h : (G.graph.label v).1 = 1), |
| 35 | ExtendedContexts.ExtremalElement L E (h ▸ (G.graph.label v).2)) → |
| 36 | (AcceptingClass (Accepting L) (E.algebra.eval 0 G) ↔ |
| 37 | ∀ B, RegularBranch G B → AcceptingClass (Accepting L) (E.algebra.eval 0 (ofSetSystem B.val)))) |
| 38 | |
| 39 | axiom path_criterion {A : RankedSet} (L : Algebras.Language A) |
| 40 | (hL : Algebras.UnfoldInvariantLanguage L) (hrec : Algebras.Recognizable L) |
| 41 | (E : SyntacticAlgebra L) (G : FiniteSystem (Carrier (Accepting L)) 0) |
| 42 | (hu : Unary G) (hr : G.graph.root = ∅) (hreach : Reachable G) |
| 43 | (ht : ∀ v, (G.graph.label v).1 = 1 → ∃ w, G.graph.edge v 0 (.inl w)) |
| 44 | (hs : ∀ v (h : (G.graph.label v).1 = 1), |
| 45 | ExtendedContexts.ExtremalElement L E (h ▸ (G.graph.label v).2)) : |
| 46 | AcceptingClass (Accepting L) (E.algebra.eval 0 G) ↔ |
| 47 | ∀ B : System (Carrier (Accepting L)) 0, Unary (ofSetSystem B.val) → |
| 48 | Nonempty (FiniteMorphisms.Morphism (ofSetSystem B.val) G) → |
| 49 | AcceptingClass (Accepting L) (E.algebra.eval 0 (ofSetSystem B.val)) |
| 50 | |
| 51 | axiom selected_path_criterion {A : RankedSet} (L : Algebras.Language A) |
| 52 | (hL : Algebras.UnfoldInvariantLanguage L) (hrec : Algebras.Recognizable L) |
| 53 | (E : SyntacticAlgebra L) (G : FiniteSystem (Carrier (Accepting L)) 0) |
| 54 | (hu : Unary G) (hr : G.graph.root = ∅) (hreach : Reachable G) |
| 55 | (ht : ∀ v, (G.graph.label v).1 = 1 → ∃ w, G.graph.edge v 0 (.inl w)) |
| 56 | (hs : ∀ v (h : (G.graph.label v).1 = 1), |
| 57 | ExtremalUnaryTypes.Selected L E (h ▸ (G.graph.label v).2)) : |
| 58 | AcceptingClass (Accepting L) (E.algebra.eval 0 G) ↔ |
| 59 | ∀ B : System (Carrier (Accepting L)) 0, Unary (ofSetSystem B.val) → |
| 60 | Nonempty (FiniteMorphisms.Morphism (ofSetSystem B.val) G) → |
| 61 | AcceptingClass (Accepting L) (E.algebra.eval 0 (ofSetSystem B.val)) |
| 62 | |
| 63 | axiom syntactic_automaton_property {A : RankedSet} (L : Algebras.Language A) |
| 64 | (hL : Algebras.UnfoldInvariantLanguage L) (hrec : Algebras.Recognizable L) |
| 65 | (E : SyntacticAlgebra L) : HasAutomatonProperty L E |
| 66 | |
| 67 | end Lax369799.ExtremalPaths |
| 68 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments