Journal
THEORETICAL COMPUTER SCIENCE
Volume 410, Issue 30-32, Pages 3018-3026Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2009.03.008
Keywords
Combinatorics on words; Burrows-Wheeler transform; Palindromes; Rich words
Categories
Ask authors/readers for more resources
The investigation of the extremal case of the Burrows-Wheeler transform leads to study the words w over an ordered alphabet A = {a(1), a(2), ..., a(k)}, with a(1) < a(2) <... < a(k), such that bwt(w) is of the form a(k)(nk) a(k-1)(nk-1) ... a(2)(n2)a(1)(n1), for some non-negative integers n(1), n(2), ..., n(k). 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 a(k)(nk) a(k-1)(nk-1) ... a(2)(n2) a(1)(n1) is strongly rich, i.e. the word w(2) contains the maximum number of different palindromic factors. (C) 2009 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available