Extracting powers and periods in a word from its runs structure (Q389938)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Extracting powers and periods in a word from its runs structure
scientific article

    Statements

    Extracting powers and periods in a word from its runs structure (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    22 January 2014
    0 references
    As the authors note in the abstract, the applications of runs (the maximal periodic subwords) in a word are underrepresented in the existing literature, and this paper tries to fill in this gap. The results are related to {\parindent=4mm \begin{itemize}\item[--] the decomposition into pairwise disjoint classes of sets of runs of a given word, based on Lyndon-roots; \item[--] computing and listing in linear time the \(k\)-th powers in a given word; and \item[--] computing by a formula the number of occurrences of a \(k\)-th power in a given word; and \item[--] computing in linear time all local periods of a word. \end{itemize}} Efficient algorithms for testing primitivity of subwords and computing primitive roots are given too.
    0 references
    0 references
    run in a word
    0 references
    powers of a word
    0 references
    primitive word
    0 references
    local period
    0 references

    Identifiers