Burrows-Wheeler transform and palindromic richness

Research output: Contribution to journalArticlepeer-review

20 Citations (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.
Original languageEnglish
Pages (from-to)3018-3026
Number of pages9
JournalTheoretical Computer Science
Volume410
Publication statusPublished - 2009

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Burrows-Wheeler transform and palindromic richness'. Together they form a unique fingerprint.

Cite this