6533b825fe1ef96bd1282a4a

RESEARCH PRODUCT

Burrows-Wheeler transform and palindromic richness

Giovanna RosoneAntonio Restivo

subject

Combinatorics on wordsGeneral Computer ScienceBurrows–Wheeler transformSettore INF/01 - InformaticaRich wordsPalindromeBurrows-Wheeler transformTheoretical Computer ScienceCombinatoricsRich wordBurrows-Wheeler transform; Palindromes; Rich words; Combinatorics on wordsPalindromePalindromesSpecies richnessAlphabetArithmeticBurrows–Wheeler transformComputer Science(all)MathematicsCombinatorics on word

description

AbstractThe investigation of the extremal case of the Burrows–Wheeler transform leads to study the words w over an ordered alphabet A={a1,a2,…,ak}, with a1<a2<⋯<ak, such that bwt(w) is of the form aknkak−1nk−1⋯a2n2a1n1, for some non-negative integers n1,n2,…,nk. A characterization of these words in the case |A|=2 has been given in [Sabrina Mantaci, Antonio Restivo, Marinella Sciortino, Burrows-Wheeler transform and Sturmian words, Information Processing Letters 86 (2003) 241–246], where it is proved that they correspond to the powers of conjugates of standard words. The case |A|=3 has been settled in [Jamie Simpson, Simon J. Puglisi, Words with simple Burrows-Wheeler transforms, Electronic Journal of Combinatorics 15, (2008) article R83], which also contains some partial results for an arbitrary alphabet. In the present paper we show that such words can be described in terms of the notion of “palindromic richness”, recently introduced in [Amy Glen, Jacques Justin, Steve Widmer, Luca Q. Zamboni, Palindromic richness, European Journal of Combinatorics 30 (2) (2009) 510–531]. Our main result indeed states that a word w such that bwt(w) has the form aknkak−1nk−1⋯a2n2a1n1 is strongly rich, i.e. the word w2 contains the maximum number of different palindromic factors.

yearjournalcountryeditionlanguage
2009-08-01
10.1016/j.tcs.2009.03.008http://hdl.handle.net/10447/40128