
arXiv: 1705.10277
handle: 10281/206213 , 11386/4714941
Motivated by applications to string processing, we introduce variants of the Lyndon factorization called inverse Lyndon factorizations. Their factors, named inverse Lyndon words, are in a class that strictly contains anti-Lyndon words, that is Lyndon words with respect to the inverse lexicographic order. The Lyndon factorization of a nonempty word w is unique but w may have several inverse Lyndon factorizations. We prove that any nonempty word w admits a canonical inverse Lyndon factorization, named ICFL(w), that maintains the main properties of the Lyndon factorization of w: it can be computed in linear time, it is uniquely determined, it preserves a compatibility property for sorting suffixes. In particular, the compatibility property of ICFL(w) is a consequence of another result: any factor in ICFL(w) is a concatenation of consecutive factors of the Lyndon factorization of w with respect to the inverse lexicographic order.
FOS: Computer and information sciences, Combinatorics on words, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, G.2.1, Lyndon words, DNA sequences, 68R15, Protein sequences, DNA sequences, Algorithms on strings, G.2.1; F.4.3, Lyndon factorization, Lyndon words; Lyndon factorization; Combinatorial algorithms on words, Computer Science - Data Structures and Algorithms, F.4.3, Combinatorial algorithms on words; DNA sequences; Lyndon factorization; Lyndon words; Applied Mathematics, Data Structures and Algorithms (cs.DS), Combinatorial algorithms on words; DNA sequences; Lyndon factorization; Lyndon words;, combinatorial algorithms on words, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Combinatorics on words, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, G.2.1, Lyndon words, DNA sequences, 68R15, Protein sequences, DNA sequences, Algorithms on strings, G.2.1; F.4.3, Lyndon factorization, Lyndon words; Lyndon factorization; Combinatorial algorithms on words, Computer Science - Data Structures and Algorithms, F.4.3, Combinatorial algorithms on words; DNA sequences; Lyndon factorization; Lyndon words; Applied Mathematics, Data Structures and Algorithms (cs.DS), Combinatorial algorithms on words; DNA sequences; Lyndon factorization; Lyndon words;, combinatorial algorithms on words, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 20 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
