Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\BWT{\mathit{BW}} \def\fib{\mathit{fib}} $

Fibonacci words are typical examples of circularly balanced words. Below is the graph showing the cycle to recover a conjugate of $\fib_4$ (length $F_6=8$ and density $F_5=5$), from $\sa{b}^3\sa{a}^5$. Following the cycle from the top left letter, letters of $\sa{aabaabab}$ are those met successively on the bottom line. Starting from another letter gives another conjugate of $\fib_4=\sa{abaababa}$, which itself is obtained by starting from the first occurrence of $\sa{a}$ on the top line. In fact, any word of length $|\fib_n|$ and density $|\fib_{n-1}|$ is circularly balanced if and only if it is a conjugate of $\fib_n$.

$\BWT(\fib_1)=\BWT(\sa{ab})=\sa{ba}$, $\BWT(\fib_2)=\BWT(\sa{aba})=\sa{baa}$ and $\BWT(\fib_3)=\BWT(\sa{abaab})=\sa{bbaaa}$.

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.

125 Problems in Text Algorithms

Example

Problem 95: BW Transform of Balanced Words

References