Advertisement
Published in:
2020 | OriginalPaper | Chapter
Lyndon Words versus Inverse Lyndon Words: Queries on Suffixes and Bordered Words
Authors : Paola Bonizzoni, Clelia De Felice, Rocco Zaccagnino, Rosalba Zizza
Published in: Language and Automata Theory and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
The Lyndon factorization of a word has been extensively studied in different contexts and several variants of it have been proposed. In particular, the canonical inverse Lyndon factorization \(\mathrm {ICFL}\), introduced in [5], maintains the main properties of the Lyndon factorization since it can be computed in linear time and it is uniquely determined. In this paper we investigate new properties of this factorization with the purpose of exploring its use in string queries.
As a main result, we 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 \(\mathrm {ICFL}(w)\). A tool used in the proof is a property that we state for factors with nonempty borders in \(\mathrm {ICFL}(w)\): a nonempty border of a factor \(m_i\) cannot be a prefix of the next factor \(m_{i+1}\). Another interesting result relates sorting of global suffixes, i.e., suffixes of a word w, and sorting of local suffixes, i.e., suffixes of the factors in \(\mathrm {ICFL}(w)\).
Finally, given a word w and a factor x of w, we prove that their Lyndon factorizations share factors, except for the first and last term of the Lyndon factorization of x. This property suggests that, given two words sharing a common overlap, their Lyndon factorizations could be used to capture the common overlap of these two words.