Evaluation of unary chains in every sort
Lax369799.UnaryChains · concepts/Lax369799/UnaryChains.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A finite chain of unary letters followed by a value of any rank is evaluated by successive unary application. For a unary final letter this computes the semigroup value of a nonempty word.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.UnaryComposition |
| 2 | import Lax369799.UnaryFactorization |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Evaluation of unary chains in every sort |
| 7 | type: theorem |
| 8 | --- |
| 9 | A finite chain of unary letters followed by a value of any rank is |
| 10 | evaluated by successive unary application. For a unary final letter this |
| 11 | computes the semigroup value of a nonempty word. |
| 12 | -/ |
| 13 | |
| 14 | namespace Lax369799.UnaryChains |
| 15 | open RankedSystems (RankedSet) |
| 16 | open FinitePresentations FiniteSyntacticAlgebra |
| 17 | |
| 18 | def path {A : RankedSet} {k n : ℕ} (w : Fin k → A 1) (a : A n) : FiniteSystem A n where |
| 19 | size := k + 1 |
| 20 | graph := { |
| 21 | label := Fin.lastCases ⟨n, a⟩ (fun i => ⟨1, w i⟩) |
| 22 | initial := {0} |
| 23 | root := ∅ |
| 24 | edge := fun v d t => |
| 25 | (∃ i : Fin k, v = i.castSucc ∧ d = 0 ∧ t = .inl i.succ) ∨ |
| 26 | (v = Fin.last k ∧ ∃ j : Fin n, d = j.val ∧ t = .inr j) |
| 27 | direction_valid := by |
| 28 | rintro v d t (⟨i, rfl, rfl, rfl⟩ | ⟨rfl, j, rfl, _⟩) <;> simp } |
| 29 | |
| 30 | axiom evaluation {A : RankedSet} (E : Algebra A) {k n : ℕ} |
| 31 | (w : Fin k → A 1) (a : A n) : |
| 32 | E.eval n (path w a) = (List.ofFn w).foldr (UnaryComposition.act E) a |
| 33 | |
| 34 | def word {A : RankedSet} (w : ℕ → A 1) (i k : ℕ) : FiniteSystem A 1 := |
| 35 | path (fun t : Fin k => w (i + t.val)) (w (i + k)) |
| 36 | |
| 37 | axiom word_evaluation {A : RankedSet} (E : Algebra A) (w : ℕ → A 1) (i k : ℕ) : |
| 38 | E.eval 1 (word w i k) = UnaryFactorization.block E w i (i + k + 1) |
| 39 | |
| 40 | end Lax369799.UnaryChains |
| 41 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments