Variable exits of unary systems
Lax369799.UnarySystems · concepts/Lax369799/UnarySystems.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A deterministic system whose labels have rank at most one follows a single path from its initial vertex. Consequently all its variable exits use the same variable. This is the path property used in the characterization of deterministic algebra elements in Section 5.1.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.Morphisms |
| 2 | import Mathlib.Data.Fintype.Prod |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Variable exits of unary systems |
| 7 | type: theorem |
| 8 | --- |
| 9 | A deterministic system whose labels have rank at most one follows a single |
| 10 | path from its initial vertex. Consequently all its variable exits use the |
| 11 | same variable. This is the path property used in the characterization of |
| 12 | deterministic algebra elements in Section 5.1. |
| 13 | -/ |
| 14 | namespace Lax369799.UnarySystems |
| 15 | open RankedSystems Morphisms |
| 16 | |
| 17 | axiom unique_exit {A : RankedSet} {n : ℕ} (S : System A n) |
| 18 | (hS : ∀ v, (S.val.graph.label v).1 ≤ 1) |
| 19 | {v w : S.val.Vertex} {d e : ℕ} {i j : Fin n} |
| 20 | (hi : S.val.graph.edge v d (.inr i)) (hj : S.val.graph.edge w e (.inr j)) : i = j |
| 21 | |
| 22 | /-- One copy for each variable, retaining only exits to that variable. -/ |
| 23 | def variablePieces {A : RankedSet} {n : ℕ} {V : Type} (G : Presentation A n V) : |
| 24 | Presentation A n (Fin n × V) where |
| 25 | label := fun v => G.label v.2 |
| 26 | initial := fun v => G.initial v.2 |
| 27 | root := fun v => G.root v.2 |
| 28 | edge := fun v d t => ∃ s, G.edge v.2 d s ∧ |
| 29 | (∀ i, s = .inr i → i = v.1) ∧ t = Sum.map (fun w => (v.1, w)) id s |
| 30 | direction_valid := by rintro v d t ⟨s, hs, _, _⟩; exact G.direction_valid _ _ _ hs |
| 31 | |
| 32 | axiom variable_decomposition {A : RankedSet} {n : ℕ} (hn : 0 < n) |
| 33 | {V : Type} [Fintype V] (G : Presentation A n V) |
| 34 | (hG : ∀ v, (G.label v).1 ≤ 1) : |
| 35 | YieldEquivalent (trim G) (trim (variablePieces G)) |
| 36 | |
| 37 | end Lax369799.UnarySystems |
| 38 |
Builds on
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments