From the Lyndon factorization to the canonical inverse Lyndon factorization: Back and forth

The notion of inverse Lyndon word is related to the classical notion of Lyndon word. More precisely, inverse Lyndon words are exactly the nonempty prefixes of the powers of the anti-Lyndon words, where an anti-Lyndon word with respect to a lexicographic order is a classical Lyndon word with respect to the inverse lexicographic order. Each word w admits a factorization in inverse Lyndon words, named the canonical inverse Lyndon factorization and denoted by ICFL ( w ) , which maintains the main properties of the Lyndon factorization of w . Although there is a huge literature on the Lyndon factorization, the relation between the Lyndon factorization ACFL with respect to the inverse lexicographic order and the canonical inverse Lyndon factorization ICFL has not been thoroughly investigated. In this paper, we address this question, and we show how to obtain one factorization from the other using the previously defined notion on grouping. This result naturally opens new insights into the investigation of the relationship between ICFL and other notions, as already done for the Lyndon factorization.