Algorithms for computing abelian periods of words

DOI10.1016/J.DAM.2013.08.021MaRDI QIDQ496544zbMATH OpenOpenAlexFDO

Authors Gabriele Fici, Thierry Lecroq, A. Lefebvre, Élise Prieur-Gaston

Publication date 22 September 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.5389

zbMATH Keywords

combinatorics on wordsabelian perioddesign of algorithmstext algorithmsweak repetitionabelian repetition

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: 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}imessigma)$ using $O(nimessigma)$ 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$.

Recommendations

• A note on easy and efficient computation of full abelian periods of a word
• Fast computation of abelian runs
• Identifying all abelian periods of a string in quadratic time and relevant problems
• Online computation of abelian runs
• Fast algorithms for abelian periods in words and greatest common divisor queries

Cites work

• scientific article; zbMATH DE number 5605094 (Why is no real title available?)
• scientific article; zbMATH DE number 1052825 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Abelian repetitions in Sturmian words
• Algorithms for jumbled pattern matching in strings
• Binary jumbled string matching for highly run-length compressible texts
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Indexing permutations for binary strings
• New algorithms for binary jumbled pattern matching
• On approximate jumbled pattern matching in strings
• Sub-quadratic time and linear space data structures for permutation matching in binary strings

Cited in

(19)

• Abelian periods of factors of Sturmian words
• On highly palindromic words: the \(n\)-ary case
• Dyck Words, Lattice Paths, and Abelian Borders
• Computing regularities in strings: a survey
• Fast computation of abelian runs
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Abelian repetitions in Sturmian words
• A note on efficient computation of all abelian periods in a string
• String Periods in the Order-Preserving Model
• Abelian-primitive partial words
• Abelian borders in binary words
• A note on easy and efficient computation of full abelian periods of a word
• Identifying all abelian periods of a string in quadratic time and relevant problems
• Abelian periods, partial words, and an extension of a theorem of Fine and Wilf
• Online computation of abelian runs
• Fast algorithms for abelian periods in words and greatest common divisor queries
• scientific article; zbMATH DE number 4197990 (Why is no real title available?)
• Dyck words, lattice paths, and abelian borders
• String periods in the order-preserving model

This page was built for publication: Algorithms for computing abelian periods of words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496544)