\( \omega \)-Lyndon words (Q2290620): Difference between revisions

Let \(A^\mathbb{N}\) stand for the set of all right infinite words over a finite alphabet \(A\), and for \(n\in\mathbb{N}\), let \(A^n\) denote the set of all words of length \(n\) over \(A\). The authors consider total orders \(\preceq\) on \(A^\mathbb{N}\) satisfying the following condition: (*) for each \(n\in\mathbb{N}\) and \(u,v\in A^n\), if \(u^\omega\prec v^\omega\), then \(ux\prec vy\) for any \(x,y\in A^\mathbb{N}\). This class of total orders strictly contains the class of so-called generalized lexicographic orders introduced by \textit{F. Dolce} et al. [Theor. Comput. Sci. 777, 232--242 (2019; Zbl 1426.68229)]. A total order \(\preceq\) satisfying (*) being fixed, a word \(x\in A^\mathbb{N}\) is said to be \(\omega\)-Lyndon if \(x\prec y\) for every proper suffix \(y\) of \(x\), and a finite word \(w\in A^+\) is called \(\omega\)-Lyndon if \(w^\omega\prec v^\omega\) for every proper suffix \(v\) of \(w\). A word \(x\in A^\mathbb{N}\) is said to admit an infinite \(\omega\)-Lyndon factorisation if \(x=\prod_{i=1}^\infty v_i\) where each \(v_i\) is a finite \(\omega\)-Lyndon word and \(v_1^\omega\succeq v_2^\omega\succeq \dots\succeq v_i^\omega\succeq\cdots\). It admits a finite \(\omega\)-Lyndon factorisation if \(x=v_1\cdots v_ky\) where each \(v_i\) is a finite \(\omega\)-Lyndon word, \(y\) is an infinite \(\omega\)-Lyndon word, and \(v_1^\omega\succeq v_2^\omega\succeq \dots\succeq v_k^\omega\succeq y\). The authors show that every infinite word has a unique \(\omega\)-Lyndon factorization. This result implies a solution to an open problem from [loc. cit]. Reviewer's remark. The same problem has been solved by \textit{A. Burcroff} and \textit{E. Winsor} [ibid. 809, 30--38 (2020; Zbl 1458.68149)].