Stable factorization of algebraic branch words
Lax369799.UnaryFactorization · concepts/Lax369799/UnaryFactorization.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
An infinite word of unary values of a finite algebra has a stable factorization. The prefix value absorbs an idempotent block value, and the cuts may simultaneously visit one fixed vertex of any finite graph through which the word runs. The associated two-vertex lasso evaluates the regular word formed from these two values.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.UnaryComposition |
| 2 | import Lax369799.SemigroupFactorization |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Stable factorization of algebraic branch words |
| 7 | type: theorem |
| 8 | --- |
| 9 | An infinite word of unary values of a finite algebra has a stable |
| 10 | factorization. The prefix value absorbs an idempotent block value, and |
| 11 | the cuts may simultaneously visit one fixed vertex of any finite graph |
| 12 | through which the word runs. The associated two-vertex lasso evaluates |
| 13 | the regular word formed from these two values. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.UnaryFactorization |
| 17 | open RankedSystems (RankedSet) |
| 18 | open FinitePresentations FiniteSyntacticAlgebra UnaryComposition |
| 19 | |
| 20 | def block {A : RankedSet} (E : Algebra A) (w : ℕ → A 1) (i j : ℕ) : A 1 := |
| 21 | ((List.range' (i + 1) (j - i - 1)).map w).foldl (product E) (w i) |
| 22 | |
| 23 | def lasso {A : RankedSet} (a e : A 1) : FiniteSystem A 0 where |
| 24 | size := 2 |
| 25 | graph := { |
| 26 | label := Fin.cases ⟨1, a⟩ (fun _ => ⟨1, e⟩) |
| 27 | initial := {0} |
| 28 | root := ∅ |
| 29 | edge := fun _ d t => d = 0 ∧ t = .inl 1 |
| 30 | direction_valid := by |
| 31 | rintro v d t ⟨rfl, _⟩ |
| 32 | exact Fin.cases Nat.zero_lt_one (fun _ => Nat.zero_lt_one) v } |
| 33 | |
| 34 | axiom stable_factorization {A : RankedSet} (E : Algebra A) [Finite (A 1)] |
| 35 | {V : Type} [Finite V] (w : ℕ → A 1) (v : ℕ → V) : |
| 36 | ∃ (cut : ℕ → ℕ) (a e : A 1) (r : V), StrictMono cut ∧ 0 < cut 0 ∧ |
| 37 | product E e e = e ∧ product E a e = a ∧ (∀ i, v (cut i) = r) ∧ |
| 38 | (∀ i, block E w 0 (cut i) = a) ∧ |
| 39 | (∀ i j, i < j → block E w (cut i) (cut j) = e) |
| 40 | |
| 41 | end Lax369799.UnaryFactorization |
| 42 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments