Lyndon words versus inverse Lyndon words: queries on suffixes and bordered words (Q782596)

The paper deals with the Lyndon factorization (CFL) and the canonical inverse Lyndon factorization (ICFL) of words. A Lyndon word is one which is primitive (not a power) and the smallest one in its conjugacy class (obtained by cyclic shift) for the lexicographic order. The Lyndon factorization is a factorization of a word into a sequence of Lyndon words in non-increasing lexicographic order. Such a factorization always exists and is unique. For an inverse Lyndon word (which is strictly greater than each of its proper suffixes) a new factorization, called inverse Lyndon factorization, was introduced by the authors in [Adv. Appl. Math. 101, 281--319 (2018; Zbl 1402.68143)]. A canonical inverse Lyndon factorization is one which uses inverse words as factors. As the main result of the paper (Proposition 6), the authors ``prove an upper bound on the length of the longest common extension (or longest common prefix) for two factors of a word \(w\). This bound is at most the maximum length of two consecutive factors of \(\operatorname{ICFL}(w)\).'' Apart from this result, among others, the paper states ``a property showing that substrings of the same word could share common factors of the Lyndon factorization (Lemma 5). This property could be extended to two words that share a common overlap to capture the suffix-prefix relationship between them. It is an open problem if Lemma 5 extends to \(\operatorname{ICFL}(w)\).'' For the entire collection see [Zbl 1435.68034].