Extracting powers and periods in a word from its runs structure (Q389938)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Extracting powers and periods in a word from its runs structure |
scientific article; zbMATH DE number 6248965
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Extracting powers and periods in a word from its runs structure |
scientific article; zbMATH DE number 6248965 |
Statements
Extracting powers and periods in a word from its runs structure (English)
0 references
22 January 2014
0 references
run in a word
0 references
powers of a word
0 references
primitive word
0 references
local period
0 references
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. NEWLINENEWLINE\end{itemize}} Efficient algorithms for testing primitivity of subwords and computing primitive roots are given too.
0 references
