Regular infinite products of linked pairs
Lax369799.OmegaProducts · concepts/Lax369799/OmegaProducts.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
For a finite monoid, a union of languages V_a(V_e)^ω over linked pairs ae = a and ee = e is recognized by a deterministic parity word automaton. Here V_a consists of nonempty words of product a. Increasing cut points give the nonempty prefix and the successive nonempty blocks explicitly.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.OmegaDeterminization |
| 2 | import Lax369799.WordFactorization |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Regular infinite products of linked pairs |
| 7 | type: theorem |
| 8 | --- |
| 9 | For a finite monoid, a union of languages V_a(V_e)^ω over linked pairs |
| 10 | ae = a and ee = e is recognized by a deterministic parity word automaton. |
| 11 | Here V_a consists of nonempty words of product a. Increasing cut points |
| 12 | give the nonempty prefix and the successive nonempty blocks explicitly. |
| 13 | -/ |
| 14 | |
| 15 | namespace Lax369799.OmegaProducts |
| 16 | open UnfoldAutomata WordFactorization |
| 17 | |
| 18 | def Accepts {M : Type} [Monoid M] {u : ℕ} (f : Fin u → M) |
| 19 | (P : M → M → Prop) (w : ℕ → Fin u) : Prop := |
| 20 | ∃ (a e : M) (cut : ℕ → ℕ), P a e ∧ e * e = e ∧ a * e = a ∧ |
| 21 | StrictMono cut ∧ 0 < cut 0 ∧ block (f ∘ w) 0 (cut 0) = a ∧ |
| 22 | ∀ i, block (f ∘ w) (cut i) (cut (i + 1)) = e |
| 23 | |
| 24 | axiom regular {M : Type} [Monoid M] [Finite M] {u z : ℕ} |
| 25 | (f : Fin u → M) (P : M → M → Prop) : |
| 26 | ∃ D : WordCondition u z, ∀ w, D.AcceptsInfinite w ↔ Accepts f P w |
| 27 | |
| 28 | end Lax369799.OmegaProducts |
| 29 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments