CLR cover
Previous problem

Problem 94: BW Transform of Thue-Morse Words

Next problem
\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\BWT{\mathit{BW}} \)

The goal of the problem is to show the inductive structure of the Burrows-Wheeler transform of Thue-Morse words. The words are produced by the Thue-Morse morphism $\mu$ from $\{\sa{a},\sa{b}\}^*$ to itself defined by $\mu(\sa{a})=\sa{ab}$ and $\mu(\sa{b})=\sa{ba}$. Iterating $\mu$ from letter $\sa{a}$ gives the $n$th Thue-Morse word $\tau_n=\mu^n(\sa{a})$ of length $2^n$.

The Burrows-Wheeler transform $\BWT(w)$ of $w$ is the word composed of the last letters of the sorted conjugates (rotations) of $w$. The list of Thue-Morse words starts with $\tau_0=\sa{a}$, $\tau_1=\sa{ab}$, $\tau_2=\sa{abba}$ and $\tau_3=\sa{abbabaab}$ and the transforms of the last two are $\BWT(\tau_2)=\sa{baba}$ and $\BWT(\tau_3)=\sa{bbababaa}$.

Below, the bar morphism from $\{\sa{a},\sa{b}\}^*$ to itself is defined by $\overline{\sa{a}}=\sa{b}$ and $\overline{\sa{b}}=\sa{a}$.

Show the Burrows-Wheeler transform $\BWT(\tau_{n+1})$, $n\gt 0$, is the word $\sa{b}^k \cdot \overline{\BWT(\tau_n)} \cdot \sa{a}^k$, where $k={2^{n-1}}$.