CLR cover

Additional Problem 3: Attractors on Fibonacci Words

\( \newcommand{\Att}{\mathrm{Att}} \)

The notion of 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 Fibonacci words. The Fibonacci word $\fib_k$ is $\phi^k(\sa{a})$, $k\geq 0$, where the morphism $\phi$ is defined by $\phi(\sa{a})=\sa{ab}$ and $\phi(\sa{b})=\sa{a}$. The length of $\fib_k$ is the Fibonacci number $F_{k+2}$.

Find two essentially distinct attractors of size $2$ for each Fibonacci word $\fib_k$, $k\geq 2$.

References