Example
\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\newcommand{\fib}{\mathrm{fib}}
\)
It can be checked directly that $\{4,7\}$ and $\{6,7\}$ are both attractors
on $\fib_5$.
$i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
| 11 | 12 |
$\fib_5[i]$ | $\sa{a}$ | $\sa{b}$ | $\sa{a}$ | $\sa{a}$ | $\sa{b}$ | $\sa{a}$ | $\sa{b}$ | $\sa{a}$
| $\sa{a}$ | $\sa{b}$ | $\sa{a}$ | $\sa{a}$ | $\sa{b}$ |
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
-
D. Kempa and N. Prezza,
At the roots of dictionary compression: string attractors,
In I. Diakonikolas, D. Kempe, and M. Henzinger, editors,
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory
of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018,
pages 827-840. ACM, 2018.
-
K. Kutsukake, T. Matsumoto, Y. Nakashima, S. Inenaga, H. Bannai,
and M. Takeda,
On repetitiveness measures of Thue-Morse words,
In C. Boucher and S. V. Thankachan, editors, String Processing and Information
Retrieval - 27th International Symposium, SPIRE 2020, Orlando,
FL, USA, October 13-15, 2020, Proceedings, volume 12303 of Lecture
Notes in Computer Science, pages 213-220. Springer, 2020.