6533b873fe1ef96bd12d4d08
RESEARCH PRODUCT
Algorithms for Computing Abelian Periods of Words
Gabriele FiciíLise Prieur-gastonArnaud LefebvreThierry Lecroqsubject
FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)Abelian repetitionElementary abelian groupRank of an abelian groupCombinatoricsComputer Science - Data Structures and AlgorithmsFOS: MathematicsDiscrete Mathematics and CombinatoricsMathematics - CombinatoricsData Structures and Algorithms (cs.DS)Abelian groupOnline algorithmMathematicsArithmetic of abelian varietiesDiscrete mathematicsCombinatorics on wordsApplied MathematicsAbelian periodText algorithmWeak repetitionPrefixCombinatorics on wordsDesign of algorithmCombinatorics (math.CO)AlgorithmWord (computer architecture)Computer Science::Formal Languages and Automata TheoryComputer Science - Discrete Mathematicsdescription
Constantinescu and Ilie (Bulletin EATCS 89, 167--170, 2006) introduced the notion of an \emph{Abelian period} of a word. A word of length $n$ over an alphabet of size $\sigma$ can have $\Theta(n^{2})$ distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time $O(n^2 \times \sigma)$ using $O(n \times \sigma)$ space. We present an off-line algorithm based on a $\sel$ function having the same worst-case theoretical complexity as the Brute-Force one, but outperforming it in practice. We then present on-line algorithms that also enable to compute all the Abelian periods of all the prefixes of $w$.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2012-11-22 |