Functional restrictions of selected unary graphs
Lax369799.GraphChoices · concepts/Lax369799/GraphChoices.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
In a finite unary/nullary presentation, selected unary labels allow each outgoing target set to be split independently. Acceptance is equivalent to acceptance of all functional restrictions, including in the presence of cycles. Restrictions retain all vertices and all initial/root marks.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.ContextChoices |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Functional restrictions of selected unary graphs |
| 6 | type: theorem |
| 7 | --- |
| 8 | In a finite unary/nullary presentation, selected unary labels allow each |
| 9 | outgoing target set to be split independently. Acceptance is equivalent |
| 10 | to acceptance of all functional restrictions, including in the presence |
| 11 | of cycles. Restrictions retain all vertices and all initial/root marks. |
| 12 | -/ |
| 13 | namespace Lax369799.GraphChoices |
| 14 | open RankedSystems (RankedSet) |
| 15 | open FinitePresentations FiniteContexts FiniteContextualOrder FiniteAcceptance |
| 16 | open FiniteSyntacticAlgebra ExpandedSyntacticAlgebra |
| 17 | |
| 18 | noncomputable def restrictRow {A : RankedSet} (P : FiniteSystem A 0) |
| 19 | (v : P.Vertex) (p : Set P.Vertex) : FiniteSystem A 0 where |
| 20 | size := P.size |
| 21 | graph := { P.graph with |
| 22 | edge := fun w d t => P.graph.edge w d t ∧ |
| 23 | (w = v → match t with | .inl u => p u | .inr _ => False) |
| 24 | direction_valid := fun w d t h => P.graph.direction_valid w d t h.1 } |
| 25 | |
| 26 | |
| 27 | noncomputable def chooseRows {A : RankedSet} (P : FiniteSystem A 0) |
| 28 | (s : Finset P.Vertex) (f : P.Vertex → P.Vertex) : FiniteSystem A 0 where |
| 29 | size := P.size |
| 30 | graph := { P.graph with |
| 31 | edge := fun v d t => P.graph.edge v d t ∧ (v ∈ s → t = .inl (f v)) |
| 32 | direction_valid := fun v d t h => P.graph.direction_valid v d t h.1 } |
| 33 | |
| 34 | |
| 35 | axiom row_choices {A : RankedSet} (L : Algebras.Language A) |
| 36 | (E : SyntacticAlgebra L) (P : FiniteSystem (Carrier (Accepting L)) 0) |
| 37 | (v : P.Vertex) (hv : (P.graph.label v).1 = 1) |
| 38 | (hs : ExtremalUnaryTypes.Selected L E (hv ▸ (P.graph.label v).2)) : |
| 39 | AcceptingClass (Accepting L) (E.algebra.eval 0 P) ↔ |
| 40 | ∀ w : P.Vertex, AcceptingClass (Accepting L) |
| 41 | (E.algebra.eval 0 (restrictRow P v {w})) |
| 42 | |
| 43 | axiom finite_choices {A : RankedSet} (L : Algebras.Language A) |
| 44 | (E : SyntacticAlgebra L) (P : FiniteSystem (Carrier (Accepting L)) 0) |
| 45 | (hu : ∀ v, (P.graph.label v).1 ≤ 1) |
| 46 | (hs : ∀ v (h : (P.graph.label v).1 = 1), |
| 47 | ExtremalUnaryTypes.Selected L E (h ▸ (P.graph.label v).2)) |
| 48 | (s : Finset P.Vertex) : |
| 49 | AcceptingClass (Accepting L) (E.algebra.eval 0 P) ↔ |
| 50 | ∀ f : P.Vertex → P.Vertex, AcceptingClass (Accepting L) (E.algebra.eval 0 (chooseRows P s f)) |
| 51 | |
| 52 | axiom chosen_functional {A : RankedSet} (P : FiniteSystem A 0) |
| 53 | (f : P.Vertex → P.Vertex) (v : P.Vertex) (d : ℕ) (t u : P.Vertex ⊕ Fin 0) |
| 54 | (ht : (chooseRows P Finset.univ f).graph.edge v d t) |
| 55 | (hu : (chooseRows P Finset.univ f).graph.edge v d u) : t = u |
| 56 | |
| 57 | def Admissible {A : RankedSet} (P : FiniteSystem A 0) (f : P.Vertex → P.Vertex) : Prop := |
| 58 | ∀ v, (∃ d w, P.graph.edge v d (.inl w)) → ∃ d, P.graph.edge v d (.inl (f v)) |
| 59 | |
| 60 | |
| 61 | axiom admissible_test {A : RankedSet} (L : Algebras.Language A) |
| 62 | (E : SyntacticAlgebra L) (P : FiniteSystem (Carrier (Accepting L)) 0) |
| 63 | (hu : ∀ v, (P.graph.label v).1 ≤ 1) |
| 64 | (hs : ∀ v (h : (P.graph.label v).1 = 1), |
| 65 | ExtremalUnaryTypes.Selected L E (h ▸ (P.graph.label v).2)) : |
| 66 | AcceptingClass (Accepting L) (E.algebra.eval 0 P) ↔ |
| 67 | ∀ f : P.Vertex → P.Vertex, Admissible P f → |
| 68 | AcceptingClass (Accepting L) (E.algebra.eval 0 (chooseRows P Finset.univ f)) |
| 69 | |
| 70 | end Lax369799.GraphChoices |
| 71 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments