Generalized Lyndon factorizations of infinite words (Q6830342)

A generalized lexicographic order on words is a lexicographic order where the total order of the (possibly infinite) alphabet \(A\) depends on the position of the comparison. For instance, one can use two different total orders on \(A\) when comparing letters in odd and even positions of two finite or infinite words. A finite (infinite) word is said to be a generalized Lyndon word if it is strictly smaller than any of its proper cyclic conjugates (respectively, any of its proper suffixes) with respect to a generalized lexicographic order. The authors show that every infinite word has a unique factorization into a nonincreasing product of finite and infinite generalized Lyndon words (Theorem 19). This result solves an open problem from [\textit{F. Dolce} et al., Theor. Comput. Sci. 777, 232--242 (2019; Zbl 1426.68229)]. \N\NReviewer's remark. The same problem has been solved by \textit{M. Postic} and \textit{L. Q. Zamboni} [ibid. 809, 39--44 (2020; Zbl 1458.68153)].