2024/04/27 by Paola Bonizzoni, Clelia De Felice, Bonizzoni, Paola +5
Engineering · #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · pdf · doi:10.48550/arxiv.2404.17969
openalex publication_date 2024/04/27 · openalex created_date 2024/05/11 · openalex updated_date 2026/07/28
The notion of inverse Lyndon word is related to the classical notion of Lyndon word. More precisely, inverse Lyndon words are all and only the nonempty prefixes of the powers of the anti-Lyndon words, where an anti-Lyndon word with respect to a lexicographical 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 \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 \CFLin with respect to the inverse 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 via the notion of grouping. This result naturally opens new insights in the investigation of the relationship between \ICFL and other notions, e.g., variants of Burrows Wheeler Transform, as already done for the Lyndon factorization.