Splitting outgoing choices in cyclic unary contexts
Lax369799.ContextChoices · concepts/Lax369799/ContextChoices.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Restrict the outgoing edges of the hole to a set of target vertices. For a selected unary value, acceptance for a union of targets is equivalent to acceptance for both restrictions. The context may contain feedback, roots, and a self-loop at the hole; every vertex is retained.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.ExtremalUnaryTypes |
| 2 | import Lax369799.FiniteMarkUnion |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Splitting outgoing choices in cyclic unary contexts |
| 7 | type: theorem |
| 8 | --- |
| 9 | Restrict the outgoing edges of the hole to a set of target vertices. |
| 10 | For a selected unary value, acceptance for a union of targets is |
| 11 | equivalent to acceptance for both restrictions. The context may contain |
| 12 | feedback, roots, and a self-loop at the hole; every vertex is retained. |
| 13 | -/ |
| 14 | namespace Lax369799.ContextChoices |
| 15 | open RankedSystems (RankedSet) |
| 16 | open FinitePresentations FiniteContexts FiniteContextualOrder FiniteAcceptance |
| 17 | open FiniteDecomposition FiniteSyntacticAlgebra ExpandedSyntacticAlgebra |
| 18 | |
| 19 | noncomputable def restrict {A : RankedSet} {k : ℕ} (C : Context A k 0) |
| 20 | (p : Set C.system.Vertex) : Context A k 0 where |
| 21 | system := { |
| 22 | size := C.system.size |
| 23 | graph := { C.system.graph with |
| 24 | edge := fun v d t => C.system.graph.edge v d t ∧ |
| 25 | (v = holeVertex C → match t with | .inl w => p w | .inr _ => False) |
| 26 | direction_valid := fun v d t h => C.system.graph.direction_valid v d t h.1 } } |
| 27 | one_hole := C.one_hole |
| 28 | |
| 29 | axiom accepting_union {A : RankedSet} (L : Algebras.Language A) |
| 30 | (E : SyntacticAlgebra L) (b : Carrier (Accepting L) 1) |
| 31 | (hb : ExtremalUnaryTypes.Selected L E b) |
| 32 | (C : Context (Carrier (Accepting L)) 1 0) (p q : Set C.system.Vertex) : |
| 33 | AcceptingClass (Accepting L) (E.algebra.eval 0 (plug (restrict C (p ∪ q)) (atomic b))) ↔ |
| 34 | AcceptingClass (Accepting L) (E.algebra.eval 0 (plug (restrict C p) (atomic b))) ∧ |
| 35 | AcceptingClass (Accepting L) (E.algebra.eval 0 (plug (restrict C q) (atomic b))) |
| 36 | |
| 37 | axiom accepting_finite {A : RankedSet} (L : Algebras.Language A) |
| 38 | (E : SyntacticAlgebra L) (b : Carrier (Accepting L) 1) |
| 39 | (hb : ExtremalUnaryTypes.Selected L E b) |
| 40 | (C : Context (Carrier (Accepting L)) 1 0) (s : Finset C.system.Vertex) (hs : s.Nonempty) : |
| 41 | AcceptingClass (Accepting L) (E.algebra.eval 0 (plug (restrict C (↑s)) (atomic b))) ↔ |
| 42 | ∀ v ∈ s, AcceptingClass (Accepting L) |
| 43 | (E.algebra.eval 0 (plug (restrict C {v}) (atomic b))) |
| 44 | |
| 45 | axiom accepting_all_choices {A : RankedSet} (L : Algebras.Language A) |
| 46 | (E : SyntacticAlgebra L) (b : Carrier (Accepting L) 1) |
| 47 | (hb : ExtremalUnaryTypes.Selected L E b) |
| 48 | (C : Context (Carrier (Accepting L)) 1 0) : |
| 49 | AcceptingClass (Accepting L) (E.algebra.eval 0 (plug C (atomic b))) ↔ |
| 50 | ∀ v : C.system.Vertex, AcceptingClass (Accepting L) |
| 51 | (E.algebra.eval 0 (plug (restrict C {v}) (atomic b))) |
| 52 | |
| 53 | end Lax369799.ContextChoices |
| 54 |
Used by
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments