Reference. Generalized Lyndon Factorizations of Infinite Words
A generalized lexicographic order on words is a lexicographic order where the total order of the alphabet depends on the position of the comparison. A generalized Lyndon word is a finite word which is strictly smallest among its class of rotations with respect to a generalized lexicographic order. This notion can be extended to infinite words: an infinite generalized Lyndon word is an infinite word which is strictly smallest among its class of suffixes. We prove a conjecture of Dolce, Restivo, and Reutenauer: every infinite word has a unique nonincreasing factorization into finite and infinite generalized Lyndon words. When this factorization has finitely many terms, we characterize the last term of the factorization. Our methods also show that the infinite generalized Lyndon words are precisely the words with infinitely many generalized Lyndon prefixes.
Cite
Cites 19 works (0 here)
External (19)
- ω-Lyndon words (2020)
- Generalized Lyndon Factorizations of Infinite Words (WORDS 2019) (2019)
- New Results on Nyldon Words Derived Using an Algorithm from Hall Set Theory (2019)
- Some variations on Lyndon words (2019)
- On generalized Lyndon words (2018)
- Nyldon words (2018)
- Inverse Lyndon words and Inverse Lyndon factorizations of words (2017)
- Transfinite Lyndon Words (2015)
- Words (Handbook of Enumerative Combinatorics chapter) (2015)
- Numeration and enumeration (2012)
- Mots de Lyndon généralisés (2006)
- Algebraic Combinatorics on Words (2002)
- Combinatorics on Words (1997)
- Combinatorial and Asymptotic Methods in Algebra (1995)
- Infinite Lyndon Words (1994)
- The equation $a^M=b^Nc^P$ in a free group (1962)
- Free Differential Calculus, IV. The Quotient Groups of the Lower Central Series (1958)
- On Burnside’s problem (1954)
- Subalgebras of free Lie algebras (1953)