Burrows-Wheeler transform and palindromic richness

Risultato della ricerca: Article

20 Citazioni (Scopus)

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 <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, EuropeanJournal 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.
Lingua originaleEnglish
pagine (da-a)3018-3026
Numero di pagine9
RivistaTheoretical Computer Science
Volume410
Stato di pubblicazionePublished - 2009

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Entra nei temi di ricerca di 'Burrows-Wheeler transform and palindromic richness'. Insieme formano una fingerprint unica.

Cita questo