×

Burrows-Wheeler transform and palindromic richness. (English) Zbl 1173.68055

Summary: 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},\cdots ,a_k\}\), with \(a_{1}<a_{2}<\cdots <a_k\), such that \(\text{bwt}(w)\) is of the form \(a^{n_k}_ka^{n_{k-1}}_{k-1}\cdots a^{n_2}_2a^{n_1}_1\), for some non-negative integers \(n_{1},n_{2},\cdots ,n_k\). A characterization of these words in the case \(|A|=2\) has been given in [S. Mantaci, A. Restivo, and M. Sciortino, “Burrows-Wheeler transform and Sturmian words”, Inf. Process. Lett. 86, No. 5, 241–246 (2003; Zbl 1162.68511)], where it is proved that they correspond to the powers of conjugates of standard words. The case \(|A|=3\) has been settled in [J. Simpson and S. J. Puglisi, “Words with simple Burrows-Wheeler transforms”, Electron. J. Comb. 15, No. 1, Research Paper R83, 17 p. (2008; Zbl 1183.68446)], 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 [A. Glen, J. Justin, St. Widmer and L. Q. Zamboni, “Palindromic richness”, Eur. J. Comb. 30, No. 2, 510–531 (2009; Zbl 1169.68040)]. Our main result indeed states that a word \(w\) such that \(\text{bwt}(w)\) has the form \(a^{n_k}_ka^{n_{k-1}}_{k-1}\cdots a^{n_2}_2a^{n_1}_1\) is strongly rich, i.e. the word \(w^{2}\) contains the maximum number of different palindromic factors.

MSC:

68R15 Combinatorics on words
Full Text: DOI

References:

[1] Bucci, Michelangelo; De Luca, Alessandro; Glen, Amy; Zamboni, Luca Q., A new characteristic property of rich words, Theoretical Computer Science, 410, 30-32, 2860-2863 (2009) · Zbl 1173.68048
[2] Bucci, Michelangelo; Luca, Alessandro De; Glen, Amy; Zamboni, Luca Q., A connection between palindromic and factor complexity using return words, Advances in Applied Mathematics, 42, 1, 60-74 (2009) · Zbl 1160.68027
[3] Michael Burrows, David J. Wheeler, A block sorting data compression algorithm. Technical Report, DIGITAL System Research Center, 1994; Michael Burrows, David J. Wheeler, A block sorting data compression algorithm. Technical Report, DIGITAL System Research Center, 1994
[4] Choffrut, Christian; Karhumaki, Juhani, Combinatorics of words, (Rozenberg, G.; Salomaa, A., Handbook of Formal Language Theory, vol. 1 (1997), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0964.68119
[5] Droubay, Xavier; Justin, Jacques; Pirillo, Giuseppe, Episturmian words and some constructions of de Luca and Rauzy, Theoretical Computer Science, 255, 1-2, 539-553 (2001) · Zbl 0981.68126
[6] Glen, Amy; Justin, Jacques; Widmer, Steve; Zamboni, Luca Q., Palindromic richness, European Journal of Combinatorics, 3, 2, 510-531 (2009) · Zbl 1169.68040
[7] Lothaire, M., (Combinatorics on Words. Combinatorics on Words, Encyclopedia of Mathematics, vol. 17 (1983), Addison-Wesley: Addison-Wesley Reading, Mass), Reprinted in the Cambridge Mathematical Library, Cambridge University Press, 1997 · Zbl 0514.20045
[8] Lothaire, M., Algebraic Combinatorics on Words (2002), Cambridge University Press · Zbl 1001.68093
[9] Mantaci, Sabrina; Restivo, Antonio; Sciortino, Marinella, Burrows-Wheeler transform and Sturmian words, Information Processing Letters, 86, 241-246 (2003) · Zbl 1162.68511
[10] Simpson, Jamie; Puglisi, Simon J., Words with simple Burrows-Wheeler transforms, Electronic Journal of Combinatorics, 15 (2008), article R83 · Zbl 1183.68446
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.