The algebraic condition on infinite branch words
Lax369799.AlgebraicOmegaWords · concepts/Lax369799/AlgebraicOmegaWords.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Section 6.3 accepts an infinite unary word when it belongs to V_a(V_e)^ω for a linked pair (a,e) whose lasso evaluates to an accepting nullary value. For a finite unary sort this language is recognized by a finite deterministic parity word automaton.
Concept map
Evidence
This concept declares 2 statements. Each proof establishes one of them relative to its assumptions.
1 recurrent_factorization proven
2 regular proven
Lean source view on GitHub
| 1 | import Lax369799.UnaryFactorization |
| 2 | import Lax369799.OmegaProducts |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: The algebraic condition on infinite branch words |
| 7 | type: theorem |
| 8 | --- |
| 9 | Section 6.3 accepts an infinite unary word when it belongs to V_a(V_e)^ω |
| 10 | for a linked pair (a,e) whose lasso evaluates to an accepting nullary |
| 11 | value. For a finite unary sort this language is recognized by a finite |
| 12 | deterministic parity word automaton. |
| 13 | -/ |
| 14 | |
| 15 | namespace Lax369799.AlgebraicOmegaWords |
| 16 | open RankedSystems (RankedSet) |
| 17 | open FiniteSyntacticAlgebra UnaryComposition UnaryFactorization UnfoldAutomata |
| 18 | |
| 19 | def Accepts {A : RankedSet} (E : Algebra A) (F : Set (A 0)) (w : ℕ → A 1) : Prop := |
| 20 | ∃ (a e : A 1) (cut : ℕ → ℕ), E.eval 0 (lasso a e) ∈ F ∧ |
| 21 | product E e e = e ∧ product E a e = a ∧ StrictMono cut ∧ 0 < cut 0 ∧ |
| 22 | block E w 0 (cut 0) = a ∧ ∀ i, block E w (cut i) (cut (i + 1)) = e |
| 23 | |
| 24 | axiom regular {A : RankedSet} (E : Algebra A) (F : Set (A 0)) [Fintype (A 1)] {z : ℕ} : |
| 25 | ∃ D : WordCondition (Fintype.card (A 1)) z, ∀ w, D.AcceptsInfinite w ↔ |
| 26 | Accepts E F (fun n => (Fintype.equivFin (A 1)).symm (w n)) |
| 27 | |
| 28 | axiom recurrent_factorization {A : RankedSet} (E : Algebra A) (F : Set (A 0)) |
| 29 | {V : Type} [Finite V] (w : ℕ → A 1) (v : ℕ → V) (h : Accepts E F w) : |
| 30 | ∃ (a e : A 1) (c : ℕ → ℕ) (r : V), E.eval 0 (lasso a e) ∈ F ∧ |
| 31 | product E e e = e ∧ product E a e = a ∧ StrictMono c ∧ 0 < c 0 ∧ |
| 32 | (∀ i, v (c i) = r) ∧ (∀ i, block E w 0 (c i) = a) ∧ |
| 33 | (∀ i j, i < j → block E w (c i) (c j) = e) |
| 34 | |
| 35 | end Lax369799.AlgebraicOmegaWords |
| 36 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments