It can be checked directly that $\{4,6,8,12\}$ and $\{4,8,10,12\}$ are attractors on $\tau_4$.
$i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
$\tau[i]$ | $\sa{a}$ | $\sa{b}$ | $\sa{b}$ | $\sa{a}$ | $\sa{b}$ | $\sa{a}$ | $\sa{a}$ | $\sa{b}$ | $\sa{b}$ | $\sa{a}$ | $\sa{a}$ | $\sa{b}$ | $\sa{a}$ | $\sa{b}$ | $\sa{b}$ | $\sa{a}$ |
The notion of an attractor provides a unifying framework for known dictionary-based compressors. A string attractor for a word $x$ is a subset $\Att$ of positions on $x$ for which each factor $u$ of $x$ has an occurrence covering at least one position in $\Att$. That is, there are positions $i$, $j$ and $t$ satisfying $u=x[i\dd j]$, $t\in\Att$ and $i\leq t\leq j$.
In this problem we concentrate on attractors on Thue-Morse words. Thue-Morse words are defined by the following recurrence: \[\cases{ \tau_0 = \sa{a}, \cr \tau_{k+1} = \tau_k\overline{\tau_k}, & for $k \geq 0$, }\] where the bar morphism is defined by $\overline{\sa{a}}\,=\sa{b}$ and $\overline{\sa{b}}\,=\sa{a}$. Note the length of the $k$th Thue-Morse word is $|\tau_k|=2^k$ and $\overline{\tau_{k+1}} = \overline{\tau_k}\tau_k$.