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,\ldots,a_k\}\$, with \$a_1 < a_2 < \ldots <a_k\$, such that \$bwt(w)\$ is of the form \$a_k^{n_k} a_{k-1}^{n_{k-1}} \cdots a_2^{n_2}a_1^{n_1}\$, for some non-negative integers \$n_1, n_2, \ldots, n_k\$. A characterization of these words in the case \$|A|=2\$ has been given in~\cite{MaReSc}, 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^{n_k} a_{k-1}^{n_{k-1}} \cdots a_2^{n_2}a_1^{n_1}\$ is strongly rich, i.~e. the word \$w^2\$ contains the maximum number of different palindromic factors.

Restivo, A., Rosone, G. (2009). Burrows-Wheeler transform and palindromic richness. THEORETICAL COMPUTER SCIENCE, 410(30-32), 3018-3026 [doi:10.1016/j.tcs.2009.03.008].

### Burrows-Wheeler transform and palindromic richness

#### Abstract

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,\ldots,a_k\}\$, with \$a_1 < a_2 < \ldots
##### Scheda breve Scheda completa Scheda completa (DC)
2009
Settore INF/01 - Informatica
Restivo, A., Rosone, G. (2009). Burrows-Wheeler transform and palindromic richness. THEORETICAL COMPUTER SCIENCE, 410(30-32), 3018-3026 [doi:10.1016/j.tcs.2009.03.008].
File in questo prodotto:
File
RR_TCS_2009.pdf

Solo gestori archvio

Dimensione 558.46 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/10447/40128`