CLR cover

Problem 95: BW Transform of Balanced Words

The Burrows-Wheeler operation maps a word $w$ to the word $\BWT(w)$ composed of the last letters of the sorted conjugates of $w$. The goal of the problem is to characterise primitive words $w\in \{\sa{a},\sa{b}\}^+$ for which $\BWT(w)\in\sa{b}^+\sa{a}^+$. Such a word $w$ can then be compressed to a word of length $\log|w|$ by representing the exponents of $\sa{a}$ and of $\sa{b}$.

The characterisation is based on the notion of balanced words. The density (or weight) of a word $u\in \{\sa{a},\sa{b}\}^+$ is the number of occurrences of letter $\sa{a}$ in it, that is, $|u|_{\sa{a}}$. A word $w$ is said to be balanced if any two factors of $w$, $u$ and $v$ of the same length, have almost the same density. More formally factors satisfy $$|u|=|v| \Longrightarrow -1\leq |u|_{\sa{a}}-|v|_{\sa{a}} \leq 1.$$ We also say the word $w$ is circularly balanced if $w^2$ is balanced.

For a primitive word $w\in\{\sa{a},\sa{b}\}^+$, show that $w$ is circularly balanced if and only if $\BWT(w)\in\sa{b}^+\sa{a}^+$.

Show that $\BWT(\fib_n)\in\sa{b}^+\sa{a}^+$ for $n\gt 0$.

References

  • J. Berstel and A. de Luca. Sturmian words, Lyndon words and trees. Theor. Comput. Sci., 178(1-2):171-203, 1997.
  • J. Berstel, A. Lauve, C. Reutenauer, and F. Saliola. Combinatorics on Words, volume 27 of CRM Monograph Series. Université de Montréal et American Mathematical Society, Dec. 2008.
  • M. Lothaire. Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002.
  • S. Mantaci, A. Restivo, and M. Sciortino. Burrows-Wheeler transform and Sturmian words. Inf. Process. Lett., 86(5):241-246, 2003.
  • C. Reutenauer. From Christoffel Words to Markov Numbers. Oxford University Press, 2018.