Lyndon words versus inverse Lyndon words: queries on suffixes and bordered words
| Autor: | Rosalba Zizza, Clelia De Felice, Paola Bonizzoni, Rocco Zaccagnino |
|---|---|
| Přispěvatelé: | Bonizzoni, P, De Felice, C, Zaccagnino, R, Zizza, R |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
050101 languages & linguistics Formal Languages and Automata Theory (cs.FL) 05 social sciences String (computer science) Combinatorial algorithms on words Inverse Computer Science - Formal Languages and Automata Theory 02 engineering and technology Lyndon words Article Combinatorics Factorization Lyndon factorization 0202 electrical engineering electronic engineering information engineering FOS: Mathematics Mathematics - Combinatorics 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Combinatorics (math.CO) Time complexity Word (group theory) Mathematics |
| Zdroj: | Language and Automata Theory and Applications Language and Automata Theory and Applications ISBN: 9783030406073 LATA |
| DOI: | 10.48550/arxiv.1911.01851 |
| Popis: | Lyndon words have been largely investigated and showned to be a useful tool to prove interesting combinatorial properties of words. In this paper we state new properties of both Lyndon and inverse Lyndon factorizations of a word $w$, with the aim of exploring their use in some classical queries on $w$. The main property we prove is related to a classical query on words. We prove that there are relations between the length of the longest common extension (or longest common prefix) $lcp(x,y)$ of two different suffixes $x,y$ of a word $w$ and the maximum length $\mathcal{M}$ of two consecutive factors of the inverse Lyndon factorization of $w$. More precisely, $\mathcal{M}$ is an upper bound on the length of $lcp(x,y)$. This result is in some sense stronger than the compatibility property, proved by Mantaci, Restivo, Rosone and Sciortino for the Lyndon factorization and here for the inverse Lyndon factorization. Roughly, the compatibility property allows us to extend the mutual order between local suffixes of (inverse) Lyndon factors to the suffixes of the whole word. A main tool used in the proof of the above results is a property that we state for factors $m_i$ with nonempty borders in an inverse Lyndon factorization: a nonempty border of $m_i$ cannot be a prefix of the next factor $m_{i+1}$. The last property we prove shows that if two words share a common overlap, then their Lyndon factorizations can be used to capture the common overlap of the two words. The above results open to the study of new applications of Lyndon words and inverse Lyndon words in the field of string comparison. Comment: arXiv admin note: text overlap with arXiv:1705.10277 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|