The Smallest String Attractors of Fibonacci and Period-Doubling Words

Banbara, Mutsunori; Bannai, Hideo; Guo, Peaker; Köppl, Dominik; Mieno, Takuya; Okamoto, Yoshio

doi:10.4230/LIPIcs.CPM.2026.33

The Smallest String Attractors of Fibonacci and Period-Doubling Words

Mutsunori Banbara

Graduate School of Informatics, Nagoya University, Japan Hideo Bannai

M&D Data Science Center, Institute of Integrated Research, Institute of Science Tokyo, Japan Peaker Guo

M&D Data Science Center, Institute of Integrated Research, Institute of Science Tokyo, Japan Dominik Köppl

Department of Computer Science and Engineering, University of Yamanashi, Kofu, Japan Takuya Mieno

Graduate School of Informatics and Engineering, University of Electro-Communications, Chofu, Japan Yoshio Okamoto

Graduate School of Informatics and Engineering, University of Electro-Communications, Chofu, Japan

Abstract

A string attractor of a string $T[1..|T|]$ is a set of positions $\Gamma$ of $T$ such that any substring $w$ of $T$ has an occurrence that crosses a position in $\Gamma$ , i.e., there is a position $i$ such that $w=T[i..i+|w|-1]$ and the intersection $[i,i+|w|-1]\cap\Gamma$ is nonempty. The size of the smallest string attractor of Fibonacci words is known to be $2$ . We completely characterize the set of all smallest string attractors of Fibonacci words, and show a recursive formula describing the $2^{n-4}+2^{\lceil n/2\rceil-2}$ distinct position pairs that are the smallest string attractors of the $n$ th Fibonacci word for $n\geq 7$ . Similarly, the size of the smallest string attractor of period-doubling words is known to be $2$ . We also completely characterize the set of all smallest string attractors of period-doubling words, and show a formula describing the two distinct position pairs that are the smallest string attractors of the $n$ th period-doubling word for $n\geq 2$ . Our results show that strings with the same smallest attractor size can have a drastically different number of distinct smallest attractors.

Keywords and phrases:

String attractors, Fibonacci words, Period-doubling words, Combinatorics on words

Funding:

Hideo Bannai: JSPS KAKENHI Grant Number JP24K02899.

Dominik Köppl: JSPS KAKENHI Grant Number JP25K21150.

Takuya Mieno: JSPS KAKENHI Grant Number JP24K20734.

Yoshio Okamoto: JSPS KAKENHI Grant Number JP23K10982.

Copyright and License:

© Mutsunori Banbara, Hideo Bannai, Peaker Guo, Dominik Köppl, Takuya Mieno, and
Yoshio Okamoto; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Combinatorics on words

Editors:

Philip Bille and Nicola Prezza

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

For any string $T$ , a set $\Gamma$ of positions is a string attractor (or simply attractor) of $T$ , if any substring of $T$ has an occurrence that crosses (i.e., contains) a position in $\Gamma$ . String attractors [5] are an important combinatorial notion that captures the repetitiveness (compressiveness) of the string in the sense that dictionary compression algorithms can be viewed as algorithms that compute string attractors. It is known that the size of the smallest string attractor of $T$ , denoted by $\gamma(T)$ , bounds all dictionary compression measures from below, and is NP-hard to compute [5].

The study of string attractors on well-known families of strings has attracted much attention. Mantaci et al. [10, 11] initiated the study of string attractors on standard Sturmian words (which include the Fibonacci words), and Thue–Morse words. For any standard Sturmian word $T$ , they showed that at least one of the sets $\Gamma_{1}=\{\eta+1,\eta+2\}$ or $\Gamma_{2}=\{|T|-\eta-3,|T|-\eta-2\}$ is a smallest string attractor of $T$ , where $\eta$ is the length of the longest proper palindromic prefix of $T[1..|T|-2]$ . For de Bruijn words of length $n$ , they showed that the smallest attractor size asymptotically approaches $n/\log n$ . They also showed an attractor of size $\Theta(\log|\mathcal{T}_{n}|)$ for the $n$ th Thue–Morse word $\mathcal{T}_{n}$ . Later, Kutsukake et al. [7] showed that $\gamma(\mathcal{T}_{n})=4$ for all $n\geq 4$ . In a more general setting, Schaeffer and Shallit [14] discussed string attractors of all prefixes of automatic sequences, including the period-doubling words, Thue–Morse words, and Tribonacci words. In particular, they showed that the size of the smallest attractor of any prefix of the period-doubling word longer than one is $2$ , using the Walnut theorem prover [13].

For the Fibonacci words, defined as $F_{0}=\texttt{b}$ , $F_{1}=\texttt{a}$ , $F_{n}=F_{n-1}F_{n-2}$ , it holds that $\eta=f_{n-1}-2$ (where $f_{n-1}=|F_{n-1}|$ ), and the above result of Mantaci et al. translates to the sets $\Gamma_{1}=\{f_{n-1}-1,f_{n-1}\}$ or $\Gamma_{2}=\{f_{n-2}-1,f_{n-2}\}$ . Since $\Gamma_{2}$ cannot be an attractor (it can be shown that the length $f_{n-1}$ suffix of $F_{n}$ occurs uniquely and does not have an occurrence crossing a position in $\Gamma_{2}$ ), it follows that $\Gamma_{1}$ is an attractor of $F_{n}$ . Hence, this gives an explicit pair of positions to be a smallest attractor of Fibonacci words. However, in general, a given string can have multiple smallest string attractors. For example, any single position of a unary string is an attractor. For a more interesting example, the set of all smallest string attractors of $F_{8}$ is shown in Figure 1. See also Figure 13 for more examples.

In this paper, we take a deeper look into the combinatorial aspects of string attractors of Fibonacci words and period-doubling words, and give a complete characterization of their smallest string attractors. Our characterization for Fibonacci words is based on occurrences of singular words [15] in the Fibonacci word. We show a recursive formula describing the set of all $2^{n-4}+2^{\lceil n/2\rceil-2}$ smallest string attractors of the $n$ th Fibonacci word for all $n\geq 7$ . For the $n$ th period-doubling word $D_{n}$ defined as $D_{0}=\texttt{a}$ and $D_{n}=\phi(D_{n-1})$ for the morphism $\phi(\texttt{a})=\texttt{ab}$ and $\phi(\texttt{b})=\texttt{aa}$ , we show that the position pairs $\{3\cdot 2^{n-3},6\cdot 2^{n-3}\}$ and $\{4\cdot 2^{n-3},6\cdot 2^{n-3}\}$ characterize the smallest attractors for $n\geq 3$ . To the best of our knowledge, this is the first work which shows a complete characterization of the set of smallest string attractors for non-trivial families of strings.

It is also worth noting that, although the smallest attractor size for both the Fibonacci and period-doubling words is two, our results show that the number of smallest attractors can differ drastically, namely, from exponential in the length to constant. We do not yet have a clear interpretation of what this quantity captures, and its understanding remains an open and interesting question, as it may allow us to consider more fine-grained types of repetitiveness. Other related open problems are listed in Section 5.

Related Work

Mieno et al. [12] gave a complete characterization of smallest straight-line programs (SLPs) of Fibonacci words, showing that an SLP of a Fibonacci word is a smallest SLP if and only if it can be obtained by some implementation of the RePair algorithm [8], i.e., the recursive pairing of a most frequent adjacent symbol pair. The number of distinct smallest SLPs for $F_{n}$ was shown to be $2\lfloor(n+1)/2\rfloor-2$ for $n\geq 3$ .

We note that for the strings we have considered, the approach of Schaeffer and Shallit [14] and the software Walnut [13] can be applied, and it is possible to compute a finite state automaton for symbols in $(\{0,1\}\times\{0,1\}\times\{0,1\})^{*}$ , such that accepting paths spell out a representation of the two attractor positions and the length of a prefix of the string. While the correctness of our claims can, in principle, be verified by analyzing and characterizing these paths, this would not seem to give us much insight into why the statements hold. This approach is discussed briefly in Appendix A.

Schaeffer and Shallit [14] and Cassaigne et al. [1] have studied another related attractor-based parameter $\mathit{span}(w)$ , defined as the smallest distance between the leftmost and rightmost positions in an attractor of $w$ .

Figure 1: For

n=8

. Left: all smallest attractors of

F_{n}

, where each pair of horizontally aligned dots represents an attractor. Right: characterization of these attractors according to Theorem 23; the three dotted boxes (top to bottom) correspond to Lemmas 25, 26, and 27. (See Figure 18 in Appendix B for the case

n=9

.)

2 Preliminaries

Let $\Sigma=\{\texttt{a},\texttt{b}\}$ be a binary alphabet. An element of $\Sigma$ is called a symbol. An element of $\Sigma^{*}$ is called a string. For a string $x$ , let $|x|$ denote its length, and let $\varepsilon$ denote the empty string, i.e., $|\varepsilon|=0$ . For any integer $1\leq i\leq|x|$ , let $x[i]$ denote the $i$ th symbol of $x$ , and for any $1\leq i\leq j\leq|x|$ , let $x[i..j]=x[i]\cdots x[j]$ , and $x[i..j)=x[i..j-1]$ . Let $x^{R}$ denote the reverse of $x$ , i.e., if $x=x[1]x[2]\cdots x[|x|]$ , then $x^{R}=x[|x|]x[|x|-1]\cdots x[1]$ . The complement of a symbol in $\Sigma$ is denoted as $\overline{\texttt{a}}=\texttt{b}$ and $\overline{\texttt{b}}=\texttt{a}$ , and for any string $x\in\Sigma^{*}$ , its complement is $\overline{x}=\overline{x[1]}\cdots\overline{x[|x|]}$ .

For a set $X$ of integers and another integer $i$ , let $i\oplus X=X\oplus i:=\{i+x:x\in X\}$ and $i\ominus X:=\{i-x:x\in X\}$ . For two sets $X$ and $Y$ , let $X\otimes Y:=\{\{x,y\}:(x,y)\in X\times Y\}$ . For a string $T$ and an occurrence $w=T[i..j]$ of a substring $w$ of $T$ , we say that the occurrence of $w$ crosses position $k$ , if $i\leq k\leq j$ . A boundary is a pair of consecutive positions sometimes identified with two strings ending and starting at the respective positions. We say that an occurrence of a string crosses the boundary if it crosses both positions of the boundary.

Definition 1 (String Attractors [5]).

A string attractor, or an attractor for short, of a string $T$ is a set $\Gamma$ of positions of $T$ such that for any substring $u$ of $T$ , there exists an occurrence of $u$ in $T$ that crosses some position in $\Gamma$ . We denote by $\mathcal{A}(T)$ the set of all smallest attractors of $T$ .

It is straightforward that string attractors are invariant under string reversal, meaning that the “mirrored” string attractor is a string attractor of the mirrored string.

Observation 2.

If $\Gamma$ is an attractor of a string $w$ , then $(|w|+1)\ominus\Gamma$ is an attractor of $w^{R}$ .

A string $w$ is a minimal unique substring (MUS) [4] of $T$ if $w$ is a substring of $T$ that has a unique occurrence in $T$ , and any proper substring of $w$ has multiple occurrences in $T$ . The following observation is straightforward.

Observation 3.

Any string attractor must contain at least one position that is crossed by the unique occurrence of a MUS.

3 The Smallest Attractors of Fibonacci Words

3.1 Properties of Fibonacci Words and Singular Words

Definition 4 ( $F_{n}$ and $f_{n}$ ).

For each $n\geq 0$ , the $n$ th Fibonacci word is defined as $F_{0}=\texttt{b},F_{1}=\texttt{a}$ , and $F_{n}=F_{n-1}\ F_{n-2}$ for each $n\geq 2$ . The $n$ th Fibonacci number is defined as $f_{0}=1,f_{1}=1$ , and $f_{n}=f_{n-1}+f_{n-2}$ for each $n\geq 2$ . Note that $f_{n}=|F_{n}|$ .

Definition 5 ( $G_{n}$ , $\Delta_{n}$ ).

For $n\geq 2$ , let $G_{n}=F_{n}[1..f_{n}-2]$ and $F_{n}=G_{n}\Delta_{n}$ . For convenience, let $\Delta_{0}=\texttt{ab}$ and $\Delta_{1}=\texttt{ba}$ .

Below are known or simple observations concerning Fibonacci words.

Observation 6 (e.g. [2, 6, 9]).

The following propositions hold.

1.

For $i\geq 2$ , $\Delta_{i}=\Delta_{i\bmod 2}$ .
2.

For $i\geq 2$ , $G_{i}$ is a palindrome (by $G_{i}=G_{i-2}\Delta_{i-2}G_{i-3}\Delta_{i-3}G_{i-2}$ and induction).
3.

For $i\geq 3$ , $F_{i}=F_{i-1}F_{i-2}=F_{i-2}G_{i-1}\Delta_{i}$ .
4.

For $i\geq 5$ ,

$\displaystyle F_{i}$ $\displaystyle=G_{i}\Delta_{i}=F_{i-1}G_{i-2}\Delta_{i}=G_{i-2}\Delta_{i-2}G_{i% -3}\Delta_{i-3}G_{i-2}\Delta_{i}=G_{i-2}(F_{i-3})^{R}(F_{i-2})^{R}\Delta_{i}$

$\displaystyle=G_{i-2}(F_{i-1})^{R}\Delta_{i}.$

Definition 7 (Singular Words).

Let $S_{-1}=\varepsilon$ , $S_{0}=\texttt{a}$ , $S_{1}=\texttt{b}$ , and $S_{n}=S_{n-2}S_{n-3}S_{n-2}$ for $n\geq 2$ .

Notice that $|F_{n}|=|S_{n}|$ , and all singular words are palindromes. In the literature [15, 3], these words have been defined to be $S_{n}=F_{n}[f_{n}-1]F_{n}[1..f_{n}-1]=F_{n}[f_{n}-1]G_{n}F_{n}[f_{n}-1]$ . However, we start from the above definition (Property 2 (4) in [15]) to simplify the presentation. The next lemma summarizes results shown in [15] that we utilize.

Lemma 8 ([15]).

For any $n\geq 0$ , the following propositions hold.

(1)

$S_{n}=S_{n\bmod 2}\left(\prod_{i=0}^{n-2}S_{i}\right)$ . (Property 2 (12) in [15])
(2)

$S_{n}$ is not a substring of $S_{n+1}$ nor of $\prod_{i=0}^{n-1}S_{i}$ . (Properties 2 (2) and (13) in [15])
(3)

Let $S_{n}S_{n+1}=u_{1}u_{2}u_{3}$ where $u_{1}$ is a non-empty proper prefix of $S_{n}$ and $u_{3}$ is a non-empty proper suffix of $S_{n+1}$ . Then, $u_{2}\neq S_{i}$ for any $i\geq 0$ . (Lemma 3 in [15])

The following lemma is essentially the same as what has been shown by Wen and Wen (Theorem 1 in [15]) for the infinite Fibonacci string.

Lemma 9.

For any $n\geq 1$ , $F_{n}=\left(\prod_{i=0}^{n-2}S_{i}\right)S_{(n-1)\bmod 2}$ .

Proof.

Induction on $n$ . The equation holds for $n=1$ . Suppose it holds for all $n\leq k$ . Then,

\displaystyle F_{k+1}=F_{k}F_{k-1}=\left(\prod_{i=0}^{k-2}S_{i}\right)S_{(k-1)% \bmod 2}\left(\prod_{i=0}^{k-3}S_{i}\right)S_{(k-2)\bmod 2}=\left(\prod_{i=0}^% {k-1}S_{i}\right)S_{k\bmod 2}

where the last equation uses $S_{(k-1)\bmod 2}\left(\prod_{i=0}^{k-3}S_{i}\right)=S_{k-1}$ by Lemma 8 (1). Therefore, the equation holds for $n=k+1$ . $\hfill\blacktriangleleft$

Corollary 10.

For any $k\geq 0$ , $S_{k}$ occurs uniquely in $S_{0}\cdots S_{k}$ and the first (leftmost) occurrence of $S_{k}$ in $F_{\infty}$ spans the range $[f_{k+1}..f_{k+2}-1]$ .

Proof.

$S_{k}$ cannot occur in $\prod_{i=0}^{k-1}S_{i}$ nor contain $S_{k-1}$ (Lemma 8 (2)), nor cross the boundary of $S_{k-1}S_{k}$ (Lemma 8 (3)). The range follows from $|S_{k}|=f_{k}$ and $\sum_{i=0}^{k-1}f_{i}=f_{k+1}-1$ . $\hfill\blacktriangleleft$

Lemma 11.

For any $n\geq 5$ , $S_{n-3}$ and $S_{n-2}$ are the (only) MUSs of $F_{n}$ .

Proof.

$S_{n-3}$ occurs uniquely in $F_{n}=\left(\prod_{i=0}^{n-2}S_{i}\right)S_{(n-1)\bmod 2}$ ; It cannot occur after its first occurrence (characterized by Corollary 10) since it cannot occur in $S_{n-2}$ (Lemma 8 (2)) nor cross the boundary of $S_{n-3}S_{n-2}$ as well as the boundary of $S_{n-2}S_{n-1}$ (Lemma 8 (3)). The latter also implies the uniqueness of $S_{n-2}$ in $F_{n}$ . We have $S_{n-3}=F_{n}[f_{n-2}..f_{n-1}-1]$ , $S_{n-2}=F_{n}[f_{n-1}..f_{n}-1]$ from Corollary 10, and any substring containing them are unique. Since $F_{n}=G_{n-1}\Delta_{n-1}F_{n-2}=F_{n-2}G_{n-1}\Delta_{n}$ by Observation 6, it holds that $F_{n}[1..f_{n-1}-2]=F_{n}[f_{n-2}+1..f_{n}-2]=G_{n-1}$ and $F_{n}[f_{n-1}+1..f_{n}]=F_{n-2}$ are repeating substrings. These are the maximal substrings of $F_{n}$ not containing $S_{n-3}$ nor $S_{n-2}$ . All substrings of these maximal substrings are repeating as well, and include all proper substrings of $S_{n-3}$ and $S_{n-2}$ . Therefore $S_{n-3}$ and $S_{n-2}$ are MUSs. Also, since a substring containing a MUS must be unique, there can be no other MUSs in $F_{n}$ . $\hfill\blacktriangleleft$

Definition 12 ( $U_{n}$ and $V_{n}$ ).

For each $n\geq 5$ , define $U_{n}=[f_{n-2}..f_{n-1}-1]$ and $V_{n}=[f_{n-1}..f_{n}-1]$ , i.e., the ranges of positions crossed by the MUSs $S_{n-3}$ and $S_{n-2}$ , respectively.

Proposition 13 ([10, Thm. 5]).

The size of the smallest string attractor of $F_{n}$ is $2$ for $n\geq 2$ .

For any $n\geq 5$ , a Fibonacci word has exactly two MUSs and the ranges of positions crossed by their occurrence are disjoint (Corollary 10, Lemma 11, Definition 12). Since an occurrence of a unique substring must contain an attractor position (Observation 3) and from Proposition 13, the smallest attractor must consist of one position from each of the two MUS ranges.

Observation 14.

For $n\geq 5$ , $\mathcal{A}(F_{n})\subseteq U_{n}\otimes V_{n}$ .

In Section 3.2, we first characterize a subset of position pairs in $U_{n}\otimes V_{n}$ that cannot be an attractor of $F_{n}$ by arguments based on the occurrence of singular words in $F_{n}$ . We then prove in Section 3.3 that all other position pairs are attractors of $F_{n}$ .

3.2 Invalid Attractor Position Pairs

Here, we characterize position pairs in $U_{n}\otimes V_{n}$ that cannot be attractors of $F_{n}$ by using occurrences of singular words in $F_{n}$ . We first show that all occurrences of singular words $S_{i}$ in $F_{n}$ can be captured by their occurrences in our recursive definition (Definition 7). We interpret the recursion as a grammar rule, and show that each occurrence of singular words in $F_{n}$ corresponds to a node in the parse tree of this grammar, where a node in the parse tree is considered to span exactly the interval of positions corresponding to the substring it derives. See Figure 2 for a concrete example.

Figure 2: Illustration of Lemma 15 and Definition 18. Top:

F_{9}

. Bottom: the parse tree of

F_{9}

based on singular words. For

2\leq k\leq 7

: the gray blocks are descendants of the center child

S_{k-3}

in the parse tree for

S_{k}

, i.e.

S_{k}=S_{k-2}S_{k-3}S_{k-2}

. The green and blue blocks correspond to positions in

L_{k}

and

R_{k}

, respectively. (Notice that these positions are not crossed by any center child in the parse tree for

S_{k}

.) The positions corresponding to

L^{\prime}_{k}

are highlighted directly in orange.

Lemma 15.

Consider the equations of Lemma 9 and Definition 7 as grammar rules that derive $F_{n}$ for $n\geq 1$ , i.e., $\{F_{n}\rightarrow\left(\prod_{i=0}^{n-2}S_{i}\right)S_{(n-1)\bmod 2},S_{-1}% \rightarrow\varepsilon,S_{0}\rightarrow\texttt{a}$ , $S_{1}\rightarrow\texttt{b}\}\cup\{S_{i}\rightarrow S_{i-2}S_{i-3}S_{i-2}\mid i% =2,\ldots,n-2\}$ . Then, for any $i\geq 0$ , every occurrence of $S_{i}$ in $F_{n}$ corresponds to a node in the parse tree of this grammar.

Proof.

Due to Corollary 10, there is no occurrence of $S_{i}$ in $F_{n}$ before its first (leftmost) occurrence in a node of the parse tree. Suppose there is a later occurrence of $S_{i}$ that does not correspond to a node in the parse tree of the grammar, and consider the lowest common ancestor (LCA) in the parse tree of the leftmost position and rightmost position of the occurrence. From the above observation, if the LCA is $F_{n}$ , this implies that an occurrence of $S_{i}$ crosses a boundary of $S_{k}S_{k+1}$ for some $k\geq i$ which violates Lemma 8 (3). Therefore, the LCA must be $S_{k}$ for some $k>i$ . Furthermore, since $S_{i}$ does not occur in $S_{i+1}$ (Lemma 8 (2)), the LCA must be $S_{k}$ for some $k>i+1$ , thus, $i\leq k-2$ . By definition, $S_{k}=S_{k-2}\cdot S_{k-3}\cdot S_{k-2}$ . Therefore, $S_{i}$ must have an occurrence in $S_{k}$ (i) crossing both boundaries between $S_{k-2}$ and $S_{k-3}$ , and between $S_{k-3}$ and $S_{k-2}$ (only when $i=k-2$ ), (ii) crossing only the boundary of $S_{k-2}$ and $S_{k-3}$ , or (iii) crossing only the boundary of $S_{k-3}$ and $S_{k-2}$ . Case (i) cannot happen since $S_{k-3}$ is not a substring of $S_{k-2}$ (Lemma 8 (2)). Case (ii) directly violates Lemma 8 (3) and Case (iii) also violates Lemma 8 (3) due to the fact that $S_{i}$ is a palindrome and the statement of Lemma 8 (3) holds for $S_{k}S_{k-1}$ as well. $\hfill\blacktriangleleft$ In the parse tree of $F_{n}$ based on the grammar defined in the statement of Lemma 15, we say that the occurrence of $S_{i}$ is a center child of $S_{i+3}$ if it is derived by the rule $S_{i+3}\rightarrow S_{i+1}S_{i}S_{i+1}$ . Note that $S_{2}\rightarrow S_{0}S_{0}$ has no (or an empty) center child. We say a position $p$ is crossed by a node in the parse tree if the occurrence of the string derived by the node crosses $p$ .

Lemma 16.

Let $n\geq 5$ and $\{u,v\}\in U_{n}\otimes V_{n}$ . If $u$ or $v$ is crossed by a center child in the parse tree of some $S_{i}$ , then $\{u,v\}$ is not an attractor of $F_{n}$ .

Proof.

See Figure 3. $U_{n}$ and $V_{n}$ correspond to the ranges of positions crossed by the MUSs $S_{n-3}$ and $S_{n-2}$ of $F_{n}$ , respectively (Definition 12). Therefore, an attractor of size $2$ of $F_{n}$ must contain exactly one position from each of the ranges. By definition, $S_{n-3}=S_{n-5}S_{n-6}S_{n-5}$ and $S_{n-2}=S_{n-4}S_{n-5}S_{n-4}$ . Here, $S_{n-4}$ only occurs twice as children of $S_{n-2}$ , and does not occur elsewhere in the strings $S_{n-3}$ and $S_{n-2}$ (Lemma 15). Therefore, an attractor position must be crossed by one of the two occurrences of $S_{n-4}$ , and any position crossed by the center child $S_{n-5}$ of $S_{n-2}$ cannot be chosen as an attractor position, since it would not be crossed by $S_{n-4}$ . Similarly, there are three occurrences of $S_{n-5}$ ; two as children of $S_{n-3}$ and one as a center child of $S_{n-2}$ . However, since we cannot choose an attractor position in the center child of $S_{n-2}$ , an attractor position in $S_{n-3}$ must be crossed by one of the two occurrences of $S_{n-5}$ . Therefore, a position crossed by the center child $S_{n-6}$ of $S_{n-3}$ cannot be chosen as an attractor position. The argument can be repeated recursively; For $j=1,\cdots,\lceil n/2\rceil-2$ , given that the attractor positions must be crossed by occurrences of $S_{n-2j-1}=S_{n-2j-3}S_{n-2j-4}S_{n-2j-3}$ and $S_{n-2j}=S_{n-2j-2}S_{n-2j-3}S_{n-2j-2}$ that were not center children in the sub-tree of the parse tree respectively of $S_{n-3}$ and $S_{n-2}$ , attractor positions in the respective center children $S_{n-2j-4}$ and $S_{n-2j-3}$ cannot be chosen. $\hfill\blacktriangleleft$

Figure 3: Illustration of the proof of Lemma 16 for

n=11

. Circles and crosses at the top mark valid and invalid attractor positions, respectively. A cross highlighted in a given color indicates that the position is invalid because it fails to be crossed by the substring shown in the same color. (Note that some combinations of the positions marked by circles in

S_{n-3}

and

S_{n-2}

are still invalid; these are characterized in Lemma 17.)

Lemma 17.

Let $n\geq 7$ and $\{u,v\}\in U_{n}\otimes V_{n}$ . If $u\in U_{n}\setminus\{\min U_{n},\min U_{n}+1\}$ and $v\in V_{n}$ is in the right child of the first occurrence of $S_{n-2}$ , then $\{u,v\}$ is not an attractor of $F_{n}$ .

Proof.

See Figure 4. Consider the occurrences of $S_{n-4}(S_{n-3}[1..2])$ in $F_{n}$ . Due to Lemma 15, $S_{n-4}$ has only three occurrences in $S_{n-4}S_{n-3}S_{n-2}S_{(n-1)\bmod 2}$ , and thus in $F_{n}$ , two of which are the left and right child of $S_{n-2}=S_{n-4}S_{n-5}S_{n-4}$ . Since the last occurrence is only followed by a single symbol $S_{(n-1)\bmod 2}$ , it follows that there can only be two occurrences of $S_{n-4}(S_{n-3}[1..2])$ in $F_{n}$ . Therefore, for an attractor position to be crossed by $S_{n-4}(S_{n-3}[1..2])$ , if one of the first two positions in $U_{n}$ (corresponding to the first two positions of $S_{n-3}$ ) is not chosen as an attractor position, then, we cannot choose a position in the right child of $S_{n-2}$ for the other attractor position. Here, notice that we require $n\geq 7$ , since otherwise, the second occurrence of $S_{n-4}(S_{n-3}[1..2])$ crosses the boundary of the center and right children of $S_{n-2}$ . $\hfill\blacktriangleleft$

Figure 4: Illustration of the proof of Lemma 17 for

n=9

, where

P=S_{n-3}[1..2]

and

\alpha=S_{(n-1)\bmod 2}

. Circles (resp. squares) at the top mark positions in

U_{n}

(resp.

V_{n}

) that are not ruled out by Lemma 16. A circle-square pair in

U_{n}\otimes V_{n}

is invalid if they are both in a red region since they fail to be crossed by

S_{n-4}\ P

. (All other circle-square pairs are indeed valid, which we prove in Section 3.3.)

3.3 Valid Attractor Position Pairs

In this subsection, we show that the position pairs in $U_{n}\otimes V_{n}$ that are not invalidated by Lemma 16 nor Lemma 17 are indeed attractors of $F_{n}$ .

Definition 18 ( $L_{k}$ , $R_{k}$ , and $L^{\prime}_{k}$ ).

For $k\geq 2$ , we define three subsets of positions within the first occurrence of $S_{k}$ ; let $u_{k}$ be the node in the parse tree corresponding to this occurrence. Let $L_{k}$ be the set of positions in the left child of $u_{k}$ that are not crossed by any center child. Similarly, let $R_{k}$ be the set of positions in the right child of $u_{k}$ that are not crossed by any center child. Further, let $L^{\prime}_{k}$ be the set of positions corresponding to the occurrence of $S_{2-(k\bmod 2)}$ in the leftmost path in the parse tree rooted at $u_{k}$ ( $u_{k}$ itself when $u_{k}=S_{2}$ ).

For example, $L_{6}=\{21,22,24,25\}$ , $R_{6}=\{29,30,32,33\}$ , $L^{\prime}_{6}=\{21,22\}$ . See Figure 2.

Observation 19.

$L_{2}=\{3\}$ , $R_{2}=\{4\}$ , $L^{\prime}_{2}=\{3,4\}$ , $L_{3}=\{5\}$ , $R_{3}=\{7\}$ , $L^{\prime}_{3}=\{5\}$ , and

$\displaystyle L_{k}$	$\displaystyle=(L_{k-2}\cup R_{k-2})\oplus f_{k},$	(1)
$\displaystyle R_{k}$	$\displaystyle=(L_{k-2}\cup R_{k-2})\oplus f_{k+1}=L_{k}\oplus f_{k-1},$	(2)
$\displaystyle L^{\prime}_{k}$	$\displaystyle=L^{\prime}_{k-2}\oplus f_{k}.$	(3)

for $k\geq 4$ . For $k\geq 2$ ,

\displaystyle L^{\prime}_{k}=\begin{cases}\{f_{k+1},f_{k+1}+1\}&\text{\nobreak% \ if $k$ is even},\\ \{f_{k+1}\}&\text{\nobreak\ if $k$ is odd}.\end{cases}

(4)

Proof.

Equations (1) and (3) hold because, by Lemma 9, in the factorization $F_{n}=S_{0}S_{1}\cdots\underline{S_{k-2}}S_{k-1}\underline{S_{k}}\cdots S_{n-2% }S_{(n-1)\bmod 2}$ , the offset between the starting positions of the first occurrences of $S_{k-2}$ and $S_{k}$ is $|S_{k-2}S_{k-1}|=f_{k}$ . Equation 4 follows directly from Equation 3. Equation 2 holds because, in $S_{k}=S_{k-2}S_{k-3}S_{k-2}$ , the offset between the starting positions of the two occurrences of $S_{k-2}$ is $|S_{k-2}S_{k-3}|=f_{k-1}$ . $\hfill\blacktriangleleft$

The following is straightforward from the definitions and the above observation.

Observation 20.

For $k\geq 2$ , $\min L_{k}=f_{k+1}$ , $\max L_{k}=2f_{k}-1$ , $\min R_{k}=f_{k+1}+f_{k-1}$ , and $\max R_{k}=f_{k+2}-1$ .

The following holds since all singular words are palindromes and thus the parse tree rooted at each singular word is symmetric, implying that for any $k\geq 2$ , $L_{k}$ and $R_{k}$ are a “mirrored” image of the other with respect to some mid-point.

Observation 21.

For any $k\geq 2$ , $R_{k}=(f_{k+3}-1)\ominus L_{k}$ , $L_{k+2}=(f_{k+4}-1)\ominus(L_{k}\cup R_{k})$ .

Using the sets of Definition 18, the results of Section 3.2 can be summarized as follows.

Corollary 22.

For $n\geq 7$ , $\mathcal{A}(F_{n})\subseteq((L_{n-3}\cup R_{n-3})\otimes L_{n-2})\cup(L^{% \prime}_{n-3}\otimes R_{n-2})$ .

Proof.

Lemma 16 implies that an attractor position pair must be in $(L_{n-3}\cup R_{n-3})\otimes(L_{n-2}\cup R_{n-2})$ , where $L_{n-3}\cup R_{n-3}\subseteq U_{n}$ and $L_{n-2}\cup R_{n-2}\subseteq V_{n}$ . Furthermore, Lemma 17 implies that if one of the attractor positions is in $R_{n-2}$ , then the other position must be in the set $\{\min U_{n},\min U_{n}+1\}=\{f_{n-2},f_{n-2}+1\}$ . If $n-3$ is even, this set is exactly $L^{\prime}_{n-3}$ . If $n-3$ is odd, $L^{\prime}_{n-3}$ only includes $f_{n-2}$ , but then $f_{n-2}+1$ is a center child and cannot be an attractor position by Lemma 16. Therefore, the other position will be in $L^{\prime}_{n-3}$ . These imply that $\mathcal{A}(F_{n})\subseteq((L_{n-3}\cup R_{n-3})\otimes L_{n-2})\cup(L^{% \prime}_{n-3}\otimes R_{n-2})$ . $\hfill\blacktriangleleft$ Below, we show that all position pairs in this set are actually attractors of $F_{n}$ .

Theorem 23.

For any $n\geq 7$ , $\mathcal{A}(F_{n})=((L_{n-3}\cup R_{n-3})\otimes L_{n-2})\cup(L^{\prime}_{n-3}% \otimes R_{n-2})$ .

$\blacktriangleright$ Note 24.

Since $L^{\prime}_{n-3}\subseteq L_{n-3}$ for $n\geq 6$ , Theorem 23 implies $L^{\prime}_{n-3}\otimes(L_{n-2}\cup R_{n-2})\subseteq\mathcal{A}(F_{n})$ .

Since Corollary 22 establishes $\mathcal{A}(F_{n})\subseteq((L_{n-3}\cup R_{n-3})\otimes L_{n-2})\cup(L^{% \prime}_{n-3}\otimes R_{n-2})$ , we prove $\mathcal{A}(F_{n})\supseteq((L_{n-3}\cup R_{n-3})\otimes L_{n-2})\cup(L^{% \prime}_{n-3}\otimes R_{n-2})$ using the following three lemmas.

Lemma 25.

For $n\geq 8$ , if $(L_{n-4}\cup R_{n-4})\otimes L_{n-3}\subseteq\mathcal{A}(F_{n-1})$ , then $R_{n-3}\otimes L_{n-2}\subseteq\mathcal{A}(F_{n})$ .

Proof.

See Figure 5. For any $\{q,p\}\in(L_{n-4}\cup R_{n-4})\otimes L_{n-3}\subseteq\mathcal{A}(F_{n-1})$ with $q<p$ , let $p^{\prime}=f_{n}-p-1$ and $q^{\prime}=f_{n}-q-1$ . Since $p\in L_{n-3}$ and $q\in L_{n-4}\cup R_{n-4}$ , $p^{\prime}=(f_{n}-1)-p\in R_{n-3}$ and $q^{\prime}=(f_{n}-1)-q\in L_{n-2}$ by Observation 21. Thus, $\{p^{\prime},q^{\prime}\}\in R_{n-3}\otimes L_{n-2}$ . Since the mapping $\{p,q\}\mapsto\{p^{\prime},q^{\prime}\}$ is bijective, it suffices to show that $\{p^{\prime},q^{\prime}\}\in\mathcal{A}(F_{n})$ .

From Observation 6, $G_{n}=F_{n-1}G_{n-2}=G_{n-2}(F_{n-1})^{R}$ is a prefix of $F_{n}$ . Essentially, $p^{\prime},q^{\prime}$ are positions in $F_{n}$ that correspond to the positions $p, q$ in $F_{n-1}$ , mapped to the occurrence of $(F_{n-1})^{R}$ , i.e., $p^{\prime}=|G_{n}|-p+1=f_{n}-2-p+1=f_{n}-p-1$ and $q^{\prime}=|G_{n}|-q+1=f_{n}-2-q+1=f_{n}-q-1$ . Thus, by Observation 2, all substrings of $(F_{n-1})^{R}$ must have an occurrence that crosses $p^{\prime}$ or $q^{\prime}$ . In order to prove that $\{p^{\prime},q^{\prime}\}$ is an attractor of $F_{n}$ , consider any substring $u=F_{n}[i..j]$ that does not cross $p^{\prime}$ nor $q^{\prime}$ . Notice that since $p\geq\min L_{n-3}=f_{n-2}$ , we have $p^{\prime}\leq f_{n}-f_{n-2}-1=f_{n-1}-1$ . Also, since $q\leq\max R_{n-4}=f_{n-2}-1$ , we have $q^{\prime}\geq f_{n}-(f_{n-2}-1)-1=f_{n-1}$ .

1.

If $j<p^{\prime}$ , then $j\leq f_{n-1}-2$ , so $u$ is a substring of $G_{n-1}$ , which is a substring of $(F_{n-1})^{R}$ .
2.

If $p^{\prime}<i\leq j<q^{\prime}$ , then $u$ is trivially a substring of $(F_{n-1})^{R}$ .
3.

If $q^{\prime}<i$ , then $i\geq f_{n-1}+1$ so $u$ is a substring of $F_{n-2}$ , which is a substring of $(F_{n-1})^{R}$ because $(F_{n-1})^{R}=(\Delta_{n-1})^{R}G_{n-1}=(\Delta_{n-1})^{R}F_{n-2}G_{n-3}$ .

In all these cases, $u$ is a substring of $(F_{n-1})^{R}$ , which means $u$ has an occurrence that crosses $p^{\prime}$ or $q^{\prime}$ . Therefore, $\{p^{\prime},q^{\prime}\}$ is an attractor of $F_{n}$ . $\hfill\blacktriangleleft$

Figure 5: Illustration of Lemma 25 for

n=10

. White and black markers at the top denote positions in

\mathcal{A}(F_{n-1})

and

\mathcal{A}(F_{n})

, respectively. Highlighted markers, together with the highlighted occurrences of

F_{n-1}

and

(F_{n-1})^{R}

, illustrate the mapping described in the proof. Pink and orange squiggly arrows illustrate Case 1 and Case 3, respectively. (Note that

\Delta_{n-1}=\overline{\Delta_{n}}

and

(\Delta_{n-1})^{R}=\Delta_{n}

.)

Lemma 26.

For $n\geq 7$ , if $R_{n-3}\otimes L_{n-2}\subseteq\mathcal{A}(F_{n})$ , then $L_{n-3}\otimes L_{n-2}\subseteq\mathcal{A}(F_{n})$ .

Proof.

See Figure 6. For any $\{p,q\}\in R_{n-3}\otimes L_{n-2}\subseteq\mathcal{A}(F_{n})$ with $p<q$ , let $p^{\prime}=p-f_{n-4}$ . We have $\{p^{\prime},q\}\in L_{n-3}\otimes L_{n-2}$ since $R_{n-3}=L_{n-3}\oplus f_{n-4}$ (Equation 2). Since the mapping $\{p,q\}\mapsto\{p^{\prime},q\}$ is bijective, it suffices to show that $\{p^{\prime},q\}\in\mathcal{A}(F_{n})$ .

Since $\{p,q\}$ is an attractor of $F_{n}$ , all substrings of $F_{n}$ have an occurrence crossing $p$ or $q$ . Consider substrings of $F_{n}$ that have occurrences crossing $p$ but not $q$ nor $p^{\prime}$ . Since $\min L_{n-3}=f_{n-2}\leq p^{\prime}<p<q\leq\max L_{n-2}=2f_{n-2}-1$ and $F_{n}=\underbrace{\overbrace{F_{n-2}}^{f_{n-2}}G_{n-2}}_{2f_{n-2}-2}\Delta_{n}% G_{n-3}\Delta_{n}$ , all such occurrences are in a substring of $G_{n-2}$ . Furthermore, they have an occurrence crossing $p^{\prime}=p-f_{n-4}$ , since $F_{n}=F_{n-1}F_{n-2}=F_{n-3}G_{n-2}\Delta_{n-1}F_{n-2}$ and $G_{n-2}$ also occurs $f_{n-4}=f_{n-2}-f_{n-3}$ positions to the left. Thus, all substrings of $F_{n}$ have an occurrence crossing $p^{\prime}$ or $q$ , and therefore, $\{p^{\prime},q\}$ is an attractor of $F_{n}$ . $\hfill\blacktriangleleft$

Figure 6: Illustration of Lemma 26 for

n=10

. Black markers at the top denote positions in

\mathcal{A}(F_{n})

. Relevant attractor positions and occurrences of

G_{n-2}

are highlighted.

Lemma 27.

For $n\geq 9$ , if $L^{\prime}_{n-5}\otimes(L_{n-4}\cup R_{n-4})\subseteq\mathcal{A}(F_{n-2})$ , then $L^{\prime}_{n-3}\otimes R_{n-2}\subseteq\mathcal{A}(F_{n})$ .

Proof.

See Figure 7. For any $\{p,q\}\in L^{\prime}_{n-5}\otimes(L_{n-4}\cup R_{n-4})\subseteq\mathcal{A}(F_% {n-2})$ with $p\in L^{\prime}_{n-5}$ and $q\in L_{n-4}\cup R_{n-4}$ , let $p^{\prime}=p+f_{n-1}$ , $q^{\prime}=q+f_{n-1}$ , and $p^{\prime\prime}=p+f_{n-3}=p^{\prime}-f_{n-2}$ . Notice that $f_{n-2}\leq p^{\prime\prime}\leq f_{n-2}+1$ , $p^{\prime}\leq 2f_{n-2}+1$ , and $q^{\prime}\leq f_{n}-1$ can be seen from Equation 4 and Observation 20. It can be also seen that $p^{\prime\prime}\in L^{\prime}_{n-5}\oplus f_{n-3}=L^{\prime}_{n-3}$ (Equation 3), and $q^{\prime}\in(L_{n-4}\cup R_{n-4})\oplus f_{n-1}=R_{n-2}$ (Equation 2). Thus, $\{p^{\prime\prime},q^{\prime}\}\in L^{\prime}_{n-3}\otimes R_{n-2}$ . Since the mapping $\{p,q\}\mapsto\{p^{\prime\prime},q^{\prime}\}$ is bijective, it suffices to show that $\{p^{\prime\prime},q^{\prime}\}\in\mathcal{A}(F_{n})$ .

Consider any substring $u=F_{n}[i..j]$ that does not cross $p^{\prime\prime}$ nor $q^{\prime}$ and the following cases.

1.

If $j<p^{\prime\prime}$ , then $u$ is a substring of $F_{n-2}$ since $p^{\prime\prime}\leq f_{n-2}+1$ .
2.

If $p^{\prime\prime}<i\leq j<p^{\prime}$ , then $u$ is a substring of $F_{n-2}$ since $f_{n-2}\leq p^{\prime\prime}<p^{\prime}\leq 2f_{n-2}+1$ , and $(F_{n-2})^{2}$ is a prefix of $F_{n}=F_{n-1}F_{n-2}=F_{n-2}F_{n-3}F_{n-4}F_{n-5}F_{n-4}=(F_{n-2})^{2}F_{n-5}F% _{n-4}$ .
3.

If $p^{\prime\prime}<i<p^{\prime}<j<q^{\prime}$ , then $u$ is a substring of $G_{n-1}$ which crosses $p^{\prime}$ , since $f_{n-2}\leq p^{\prime\prime}<q^{\prime}\leq f_{n}-1$ and $F_{n}=F_{n-2}G_{n-1}\Delta_{n}$ .
4.

If $p^{\prime}<i$ , then $u$ is a substring of $F_{n-2}$ , since $F_{n}=F_{n-1}F_{n-2}$ and $p^{\prime}\geq 2f_{n-2}+1>f_{n-1}$ .

For Case 3, $u$ has an occurrence that crosses $p^{\prime\prime}$ , since $p^{\prime\prime}=p^{\prime}-f_{n-2}$ , and there is an occurrence of $G_{n-1}$ , $f_{n-2}$ positions to the left (as a prefix of $F_{n}$ ). It remains to show that all substrings of $F_{n-2}$ have an occurrence crossing $p^{\prime\prime}$ or $q^{\prime}$ . Since $\{p,q\}$ is an attractor of $F_{n-2}$ , $F_{n}=F_{n-1}F_{n-2}=F_{n-2}F_{n-3}F_{n-2}$ , and $\{p^{\prime},q^{\prime}\}=\{p,q\}\oplus f_{n-1}$ , all substrings of $F_{n-2}$ have an occurrence that crosses $p^{\prime}$ or $q^{\prime}$ . Furthermore, as was the case for Case 3, any substring of $F_{n-2}$ crossing $p^{\prime}$ but not crossing $q^{\prime}$ is a substring of $G_{n-1}$ , and has an occurrence crossing $p^{\prime\prime}$ . Therefore, any substring will cross $p^{\prime\prime}$ or $q^{\prime}$ , and $\{p^{\prime\prime},q^{\prime}\}$ is an attractor of $F_{n}$ . $\hfill\blacktriangleleft$

Figure 7: Illustration of Lemma 27 for

n=10

. White and black markers at the top denote positions in

\mathcal{A}(F_{n-2})

and

\mathcal{A}(F_{n})

, respectively.

Proof of Theorem 23.

The proof is by induction. $\mathcal{A}(F_{7})$ and $\mathcal{A}(F_{8})$ can be confirmed by brute force computation:

	$\displaystyle\mathcal{A}(F_{7})$	$\displaystyle=((L_{4}\cup R_{4})\otimes L_{5})\cup(L^{\prime}_{4}\otimes R_{5})$
		$\displaystyle=((\{8,9\}\cup\{11,12\})\otimes\{13,15\})\cup(\{8,9\}\otimes\{18,% 20\})$
		$\displaystyle=\{\{8,13\},\{8,15\},\{8,18\},\{8,20\},\{9,13\},\{9,15\},\{9,18\}% ,\{9,20\},$
		$\displaystyle\phantom{=\{,}\{11,13\},\{11,15\},\{12,13\},\{12,15\}\},\text{ and}$
	$\displaystyle\mathcal{A}(F_{8})$	$\displaystyle=((L_{5}\cup R_{5})\otimes L_{6})\cup(L^{\prime}_{5}\otimes R_{6})$
		$\displaystyle=((\{13,15\}\cup\{18,20\})\otimes\{21,22,24,25\})\cup(\{13\}% \otimes\{29,30,32,33\})$
		$\displaystyle=\{\{13,21\},\{13,22\},\{13,24\},\{13,25\},\{13,29\},\{13,30\},\{% 13,32\},\{13,33\},$
		$\displaystyle\phantom{=\{,}\{15,21\},\{15,22\},\{15,24\},\{15,25\},\{18,21\},% \{18,22\},\{18,24\},\{18,25\},$
		$\displaystyle\phantom{=\{,}\{20,21\},\{20,22\},\{20,24\},\{20,25\}\}.$

Under the induction hypothesis and Note 24, the conditions of Lemmas 25, 26, and 27 hold for $n\geq 9$ , and thus, together with Corollary 22 and the above base cases, the theorem holds. $\hfill\blacktriangleleft$

Corollary 28.

For $k\geq 4$ , $|\mathcal{A}(F_{2k-1})|=(2^{k-3}+1)2^{k-2}$ and $|\mathcal{A}(F_{2k})|=(2^{k-2}+1)2^{k-2}$ .

Proof.

It is clear that $|L_{2}|=|R_{2}|=|L_{3}|=|R_{3}|=1$ , and $|L_{i}|=|R_{i}|=2|L_{i-2}|=2|R_{i-2}|$ for $i\geq 4$ . Therefore, $|L_{2k-1}|=|R_{2k-1}|=2^{k-2}$ and $|L_{2k}|=|R_{2k}|=2^{k-1}$ . Since $|L^{\prime}_{2k-1}|=1$ and $|L^{\prime}_{2k}|=2$ , we have from Theorem 23 that $|\mathcal{A}(F_{2k-1})|=|((L_{2k-4}\cup R_{2k-4})\otimes L_{2k-3})\cup(L^{% \prime}_{2k-4}\otimes R_{2k-3})|=(2\cdot 2^{k-3}\cdot 2^{k-3})+2\cdot 2^{k-3}=% (2^{k-3}+1)2^{k-2}$ and $|\mathcal{A}(F_{2k})|=|((L_{2k-3}\cup R_{2k-3})\otimes L_{2k-2})\cup(L^{\prime% }_{2k-3}\otimes R_{2k-2})|=(2\cdot 2^{k-3}\cdot 2^{k-2})+2^{k-2}=(2^{k-2}+1)2^% {k-2}$ . $\hfill\blacktriangleleft$

4 The Smallest Attractors of Period-Doubling Words

Definition 29 ( $D_{n}$ ).

For each $n\geq 0$ , the $n$ th period-doubling word is defined as $D_{0}=\texttt{a}$ , and $D_{n}=\phi(D_{n-1})$ where $\phi$ is a morphism defined by $\phi(\texttt{a})=\texttt{ab}$ and $\phi(\texttt{b})=\texttt{aa}$ . Note that $|D_{n}|=2^{n}$ .

Theorem 30.

$\mathcal{A}(D_{2})=\{\{2,3\},\{2,4\}\}$ . For $n\geq 3$ , $\mathcal{A}(D_{n})=\{\{p_{n},r_{n}\},$ $\{q_{n},r_{n}\}\}$ , where $p_{n}=3\cdot 2^{n-3}$ , $q_{n}=2^{n-1}$ , and $r_{n}=3\cdot 2^{n-2}$ .

Schaeffer and Shallit [14] showed that for arbitrary prefixes of length at least $6$ of the infinite period-doubling sequence, $\{p_{n},r_{n}\}$ is a smallest attractor when the length is in $[2^{n},3\cdot 2^{n-1})$ , and $\{q_{n},q_{n+1}\}$ , when the length is in $[3\cdot 2^{n-1},2^{n+1})$ . We consider only the length $2^{n}$ prefixes, but characterize all smallest string attractors.

Observation 31.

Since any occurrence of b in $D_{n}$ must have come from an occurrence of a in $D_{n-1}$ by $\phi(\texttt{a})=\texttt{ab}$ , an occurrence of b in $D_{n}$ is always at an even position. Hence, bb cannot occur. This implies that an occurrence of aa starting at an odd position must be followed (provided it is not the end of the string) and preceded by ab, since it could only have come from $\phi(\texttt{aba})$ .

Furthermore, the above implies the following corollary.

Corollary 32.

Any occurrence of a substring $x$ in $D_{n}$ with $|x|\geq 3$ has the same parity, i.e., $|\{i\bmod 2\mid D_{n}[i..i+|x|)=x\}|=1$ .

Observation 33.

The following are known or easily verifiable properties of period-doubling words.

(1)

For $n\geq 1$ , $(D_{n-1})^{2}=D^{\prime}_{n}\overline{c}$ where $D^{\prime}_{n}=D_{n}[1..2^{n})$ and $c=D_{n}[|D_{n}|]$ .
(2)

For $n\geq 2$ , $D_{n}=D_{n-1}(D_{n-2})^{2}=D^{\prime}_{n-1}cD^{\prime}_{n-1}\overline{c}$ , where $c=D_{n-1}[|D_{n-1}|]$ .
(3)

For any $i$ such that $0\leq n-2i<n$ , $(D_{n-2i})^{2}$ is a suffix of $D_{n}$ , and for any $0\leq i<n$ , $D_{i}$ is a prefix of $D_{n}$ .

We first show that the two position pairs are indeed attractors of $D_{n}$ .

Lemma 34.

For $n\geq 3$ , $\{\{p_{n},r_{n}\},\{q_{n},r_{n}\}\}\subseteq\mathcal{A}(D_{n})$

Proof.

The statement can be verified by brute force for $n=3$ and $4$ . Suppose the statement holds for all $3\leq n<k$ . Let $X=D_{k}[i..j]\nobreak\ (1\leq i\leq j\leq 2^{k})$ be an arbitrary substring of $D_{k}$ , and let $Y$ be the shortest even-length substring of $D_{k}$ that contains the occurrence of $X$ , starting at an odd position, and ending at an even position, i.e., $Y=D_{k}[2i^{\prime}-1..2j^{\prime}]$ where $i^{\prime}=\lceil\frac{i}{2}\rceil$ , $j^{\prime}=\lceil\frac{j}{2}\rceil$ . It holds that $Y=\phi(Y^{\prime})$ where $Y^{\prime}=D_{k-1}[i^{\prime}..j^{\prime}]$ . Since $\{p_{k-1},r_{k-1}\}$ (resp. $\{q_{k-1},r_{k-1}\}$ ) are attractors of $D_{k-1}$ , $Y^{\prime}$ has an occurrence $D_{k-1}[i^{\prime\prime}..j^{\prime\prime}]=Y^{\prime}$ crossing $p_{k-1}$ (resp. $q_{k-1}$ ) or $r_{k-1}$ , i.e., $i^{\prime\prime}\leq s_{k-1}\leq j^{\prime\prime}$ for some $s_{k-1}\in\{p_{k-1},q_{k-1},r_{k-1}\}$ . Then, since $2i^{\prime\prime}-1<2s_{k-1}=s_{k}\leq 2j^{\prime\prime}$ , $Y[2..|Y|]$ in the corresponding occurrence of $Y=D_{k}[2i^{\prime\prime}-1..2j^{\prime\prime}]$ will cross $s_{k}$ . Since $Y[2..|Y|-1]$ is a substring of $X$ , $X$ has an occurrence crossing $s_{k}$ or ending just before $s_{k}$ . See Figure 8. Thus, to prove that $\{p_{k},r_{k}\}$ and $\{q_{k},r_{k}\}$ are attractors of $D_{k}$ , it remains to show that any substring $X$ ending just before $p_{k}$ (resp. $q_{k}$ ) or $r_{k}$ will have an occurrence crossing $p_{k}$ (resp. $q_{k}$ ) or $r_{k}$ .

Since $p_{k}=|D_{k-2}D_{k-3}|$ , $q_{k}=|D_{k-1}|$ , and $D_{k}=D^{\prime}_{k-1}cD^{\prime}_{k-1}\overline{c}$ (Observation 33 (2)), any substring $X$ ending just before $p_{k}$ (resp. $q_{k}$ ) has an occurrence ending just before $p_{k}+2^{k-1}=|D_{k-1}D_{k-2}D_{k-3}|$ (resp. $q_{k}+2^{k-1}=|D_{k}|$ ). Since $D_{k}=D_{k-1}(D_{k-2})^{2}=D_{k-1}D_{k-2}D_{k-3}(D_{k-4})^{2}$ and $r_{k}=|D_{k-1}D_{k-2}|$ , any such $X$ not crossing $r_{k}$ must be a suffix of $D^{\prime}_{k-3}$ (resp. $D^{\prime}_{k-2}$ ), having an occurrence ending just before $r_{k}$ . See Figure 9.

Finally, we claim that any substring $X$ ending just before $r_{k}$ will have occurrences crossing both $p_{k}$ and $q_{k}$ , or $r_{k}$ . We consider the following $O(k)$ disjoint cases depending on $|X|$ .

1.

$|X|>|D_{k-3}D^{\prime}_{k-2}|$ . See Figure 10 (a). Since the starting position of $X$ is $r_{k}-|X|<r_{k}-|D_{k-3}D^{\prime}_{k-2}|=3\cdot 2^{k-2}-2^{k-3}-2^{k-2}+1\leq p% _{k}+1$ , $X$ crosses both $p_{k}$ and $q_{k}$ .
2.

$|D_{k-3}D^{\prime}_{k-2}|\geq|X|\geq|(D_{k-4})^{2}|$ . See Figure 10 (a) and Figure 11. Since $D_{k-3}D^{\prime}_{k-2}=D_{k}[p_{k}+1..r_{k}-1]=D_{k}[p_{k}+1-|D_{k-3}|..r_{k}% -1-|D_{k-3}|]$ , it follows that $D_{k-3}D_{k-3}D^{\prime}_{k-2}$ has a period of $|D_{k-3}|$ . Since $|X|\geq|(D_{k-4})^{2}|>|D^{\prime}_{k-3}|$ , $X$ starts with a suffix of $D_{k-3}$ and therefore will have occurrences crossing $p_{k}$ and $q_{k}$ .
3.

$|(D_{k-2i})^{2}|>|X|\geq|D_{k-2i}|=|(D_{k-2i-1})^{2}|$ for $i\geq 2,k-2i-1\geq 0$ . See Figure 10 (b) and Figure 12. Due to Observation 33 (3), there is an occurrence of $(D_{k-2i})^{2}$ centered at (i.e., the first copy ending at) both $r^{\prime}=r_{k}-|(D_{k-2i})|$ and $r_{k}$ . Since $X$ is a suffix of $D_{k-2i}D^{\prime}_{k-2i}$ and crosses $r^{\prime}$ , it also has an occurrence crossing $r_{k}$ .
4.

$|(D_{k-2i-1})^{2}|>|D^{\prime}_{k-2i}|\geq|X|\geq|D_{k-2i-1}|=|(D_{k-2i-2})^{2}|$ for $i\geq 2,k-2i-2\geq 0$ . See Figure 10 (b) and (c), and Figure 12. $X$ is a suffix of $D^{\prime}_{k-2i}$ . There is an occurrence of $(D_{k-3})^{2}$ centered at both $p_{k}$ and $q_{k}$ . Due to Observation 33 (3), there must be an occurrence of $(D_{k-2i-1})^{2}$ also centered at $p_{k}$ and $q_{k}$ , and thus an occurrence of $D^{\prime}_{k-2i}$ (Observation 33 (1)) of which $X$ is a suffix. Since $|X|\geq|D_{k-2i-1}|>|D^{\prime}_{k-2i-1}|$ , $X$ has occurrences that cross $p_{k}$ as well as $q_{k}$ .
5.

$|X|=1$ . $D_{3}[p_{3}]=D_{3}[q_{3}]=\texttt{a}$ and $D_{3}[r_{3}]=\texttt{b}$ . It is easy to see that $D_{k}[p_{k}]=D_{k}[q_{k}]=c$ and $D_{k}[r_{k}]=\overline{c}$ from the definition of $\phi$ , so $X$ will cross both $p_{k}$ and $q_{k}$ , or $r_{k}$ .

Thus, $\{\{p_{k},r_{k}\},\{q_{k},r_{k}\}\}\subseteq\mathcal{A}(D_{k})$ , proving the lemma. $\hfill\blacktriangleleft$

Figure 8: Illustration of the first paragraph of the proof of Lemma 34. Left:

X=Y[2..|Y|]

and

i^{\prime\prime}=s_{k-1}

. Right:

X=[1..|Y|-1]

and

j^{\prime\prime}=s_{k-1}

. (Note that if

X=Y

,

X=Y[2..|Y|]

, or

X=[1..|Y|-1]

and

j^{\prime\prime}<s_{k-1}

, then

X

has an occurrence crossing

s_{k}

.)

Figure 9: Illustration of the second paragraph of the proof of Lemma 34. Blue and green blocks represent substrings that have an occurrence ending just before

p_{k}

and

q_{k}

, respectively, but do not have an occurrence crossing

r_{k}

when considering its occurrence in the second half of the string via

D^{\prime}_{k-1}

. Such substrings have occurrences ending just before

r_{k}

.

Figure 10: Illustration of the proof of Lemma 34. There are 4 main cases depending on the length of

X

which is a suffix of

D_{k}[1..r_{k})

and shown in gray (except for Case 1, which already crosses both

p_{k}

and

q_{k}

), and the occurrence crossing both

p_{k}

and

q_{k}

, or

r_{k}

is shown in orange.

Figure 11: Illustration of Case 2 in the proof of Lemma 34.

Figure 12: Illustration of Cases 3–4 in the proof of Lemma 34 for

i=2

and

i=3

. The highlighted substrings follow the same color pattern in (b) and (c) of Figure 10.

Next, we will show that no other position pairs can be attractors of $D_{n}$ with the help of the following lemma.

Lemma 35.

For $n\geq 4$ , let $\{p,q\}\in\mathcal{A}(D_{n})$ and $D_{n}[p]=\texttt{a}$ and $D_{n}[q]=\texttt{b}$ . Then, $p, q$ are both even and $\{p^{\prime},q^{\prime}\}=\{p/2,q/2\}\in\mathcal{A}(D_{n-1})$ .

Proof.

The strings aaa, aab, baa, bab, abab, aabaa, aabab, babab, babaa, ababab are all substrings of $D_{n}$ for $n\geq 4$ . It is clear that $q$ is even from Observation 31.

We first claim that $D_{n}[p+1]\neq\texttt{b}$ . Suppose to the contrary that $D_{n}[p+1]=\texttt{b}$ . Then, for aaa to have an occurrence crossing $p$ , $D_{n}[p-2..p+1]=\texttt{aa\lx@text@underline{a}b}$ , where the underlined a corresponds to position $p$ . From Observation 31, we have $D_{n}[q-1..q]=\texttt{a\lx@text@underline{b}}$ , where the underlined b corresponds to position $q$ . In order for the substrings baa and bab to have an occurrence crossing one of these positions, $D_{n}[q-3..q+4]=\texttt{{a}ba\lx@text@underline{b}aa{ab}}$ , where the bold a and ab are due to Observation 31. Next, in order for the substrings aabaa and aabab to have an occurrence crossing $p$ or $q$ , $D_{n}[p-2..p+3]=\texttt{aa\lx@text@underline{a}baa}$ and $D_{n}[q-5..q+4]=\texttt{{a}aaba\lx@text@underline{b}aaab}$ . However, then, there cannot be an occurrence of ababab that crosses $p$ or $q$ contradicting that they are an attractor.

Next, we claim that $p$ is even. If it is odd, then, from the above arguments, $D_{n}[p..p+3]=\texttt{\lx@text@underline{a}aab}$ . We also have $D_{n}[q-1..q]=\texttt{a\lx@text@underline{b}}$ . For aab and abab to cross $p$ or $q$ , $D_{n}[q-3..q+2]=\texttt{{a}aa\lx@text@underline{b}ab}$ . Furthermore, for aabaa to cross $p$ or $q$ , $D_{n}[p-3..p+3]=\texttt{aab\lx@text@underline{a}aab}$ . However, then at least one of babab and babaa cannot cross $p$ or $q$ .

Finally, consider any substring $X^{\prime}$ of $D_{n-1}$ . If $|X^{\prime}|=1$ , then, from the above arguments, $D_{n-1}[p^{\prime}]=\texttt{b}$ since $D_{n}[p]=\texttt{a}$ could not have been derived by $\phi(\texttt{a})$ , and $D_{n-1}[q^{\prime}]=\texttt{a}$ since $D_{n}[q]=\texttt{b}$ must have been derived by $\phi(\texttt{a})$ . Hence, $X^{\prime}$ crosses $p^{\prime}$ or $q^{\prime}$ . If $|X^{\prime}|\geq 2$ , consider the corresponding substring $X=\phi(X^{\prime})$ in $D_{n}$ . Since $\{p,q\}$ is an attractor of $D_{n}$ , $X$ has an occurrence crossing $p$ or $q$ . Furthermore, since $|X|\geq 4$ and the parity of its occurrences is determined uniquely (Corollary 32), an occurrence of $X$ at position $k$ in $D_{n}$ crossing $p$ or $q$ implies an occurrence of $X^{\prime}$ at position $\lceil k/2\rceil$ in $D_{n-1}$ crossing $p^{\prime}$ or $q^{\prime}$ . $\hfill\blacktriangleleft$

Proof of Theorem 30.

Assume the statement of Theorem 30 holds for all $3\leq n<k$ . Lemma 35 implies that any element other than $\{p_{k},r_{k}\}$ or $\{q_{k},r_{k}\}$ in $\mathcal{A}(D_{k})$ would imply an element in $\mathcal{A}(D_{k-1})$ not in $\{\{p_{k-1},r_{k-1}\},\{q_{k-1},r_{k-1}\}\}$ contradicting the induction hypothesis. Together with Lemma 34, this completes the proof. $\hfill\blacktriangleleft$

While we studied in earlier sections the smallest attractors of Fibonacci words and period-doubling words of higher orders ( $F_{n}$ for $n\geq 7$ and $D_{n}$ for $n\geq 3$ ), for completeness, we list the smallest attractors of lower orders in Figure 13.

Figure 13: Smallest attractors of period-doubling words

D_{n}

for

n=1,2,3

and Fibonacci words

F_{n}

for

n=3,4,5,6,7

. The visualization pattern follows that of Figure 1.

5 Discussion

Some natural related open problems are:

$\blacksquare$

Characterization of all smallest bidirectional macro schemes (BMS) for the same family of strings considered.
$\blacksquare$

Characterization of all smallest string attractors and BMS for arbitrary prefixes of the considered infinite sequence.

References

[1] Julien Cassaigne, France Gheeraert, Antonio Restivo, Giuseppe Romana, Marinella Sciortino, and Manon Stipulanti. New string attractor-based complexities for infinite words. J. Comb. Theory, Ser. A, 208:105936, 2024. doi:10.1016/J.JCTA.2024.105936.
[2] Aldo de Luca. A combinatorial property of the Fibonacci words. Inf. Process. Lett., 12(4):193–195, 1981. doi:10.1016/0020-0190(81)90099-5.
[3] Gabriele Fici. Factorizations of the Fibonacci infinite word. J. Integer Seq., 18(9):15.9.3, 2015. URL: https://cs.uwaterloo.ca/journals/JIS/VOL18/Fici/fici5.html.
[4] Lucian Ilie and William F. Smyth. Minimum unique substrings and maximum repeats. Fundam. Informaticae, 110(1-4):183–195, 2011. doi:10.3233/FI-2011-536.
[5] Dominik Kempa and Nicola Prezza. At the roots of dictionary compression: string attractors. In Ilias Diakonikolas, David Kempe, and Monika 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. doi:10.1145/3188745.3188814.
[6] Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323–350, 1977. doi:10.1137/0206024.
[7] Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. On repetitiveness measures of Thue–Morse words. In Christina Boucher and Sharma 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. doi:10.1007/978-3-030-59212-7_15.
[8] N. Jesper Larsson and Alistair Moffat. Offline dictionary-based compression. In Data Compression Conference, DCC 1999, Snowbird, Utah, USA, March 29-31, 1999, pages 296–305. IEEE Computer Society, 1999. doi:10.1109/DCC.1999.755679.
[9] M. Lothaire. Sturmian Words, volume 90 of Encyclopedia of Mathematics and its Applications, pages 45–110. Cambridge University Press, 2002.
[10] Sabrina Mantaci, Antonio Restivo, Giuseppe Romana, Giovanna Rosone, and Marinella Sciortino. String attractors and combinatorics on words. In Alessandra Cherubini, Nicoletta Sabadini, and Simone Tini, editors, Proceedings of the 20th Italian Conference on Theoretical Computer Science, ICTCS 2019, Como, Italy, September 9-11, 2019, volume 2504 of CEUR Workshop Proceedings, pages 57–71. CEUR-WS.org, 2019. URL: https://ceur-ws.org/Vol-2504/paper8.pdf.
[11] Sabrina Mantaci, Antonio Restivo, Giuseppe Romana, Giovanna Rosone, and Marinella Sciortino. A combinatorial view on string attractors. Theor. Comput. Sci., 850:236–248, 2021. doi:10.1016/J.TCS.2020.11.006.
[12] Takuya Mieno, Shunsuke Inenaga, and Takashi Horiyama. RePair grammars are the smallest grammars for Fibonacci words. In Hideo Bannai and Jan Holub, editors, 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, Prague, Czech Republic, June 27-29, 2022, volume 223 of LIPIcs, pages 26:1–26:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.CPM.2022.26.
[13] Hamoon Mousavi. Automatic theorem proving in Walnut, 2021. arXiv:1603.06017.
[14] Luke Schaeffer and Jeffrey Shallit. String attractors for automatic sequences, 2024. arXiv:2012.06840.
[15] Zhi-Xiong Wen and Zhi-Ying Wen. Some properties of the singular words of the Fibonacci word. Eur. J. Comb., 15(6):587–598, 1994. doi:10.1006/EUJC.1994.1060.

Appendix A Using Walnut to Characterize the Smallest Attractors

Using the approach by Schaeffer and Shallit [14], we can characterize the smallest attractors of period-doubling and Fibonacci words using the following Walnut program. Below, we only introduce the connection and do not give rigorous arguments.

def pdfaceq "k+i>=j & A u,v (u>=i & u<=j & v+j=u+k) => PD[u]=PD[v]":
def pdsa2 "(i1<n) & (i2<n) & Ak,l (k<=l & l<n) => (Er,s r<=s & s<n &
 (s+k=r+l) & $pdfaceq(k,l,s) & ((r<=i1 & i1<=s) | (r<=i2 & i2<=s)))":
def pdfa1 "An (n>=2) => Ei1,i2 $pdsa2(i1,i2,n)":
def pdfa2 "$pdsa2(i1,i2,n) & i1 < i2":

def fibfaceq "?msd_fib k+i>=j & A u,v (u>=i & u<=j & v+j=u+k) => F[u]=F[v]":
def fibsa2 "?msd_fib (i1<n) & (i2<n) & Ak,l (k<=l & l<n) =>
 (Er,s r<=s & s<n & (s+k=r+l) & $fibfaceq(k,l,s)
 & ((r<=i1 & i1<=s) | (r<=i2 & i2<=s)))":
def fibfa1 "?msd_fib An (n>=2) => Ei1,i2 $fibsa2(i1,i2,n)":
def fibfa2 "?msd_fib $fibsa2(i1,i2,n) & i1 < i2":

The code for the automaton pdfa2 for period-doubling words is taken from [14]. The code for fibfa2 only changes PD (period-doubling words) to F (Fibonacci words), and specifies the numeration system the corresponding automaton is defined for.

See Figures 14 and 15. While these automata characterize the set of all smallest string attractors of arbitrary prefixes of the period-doubling words or Fibonacci words, their interpretation is not straightforward. To limit the lengths of prefixes to the words we consider, we can modify the above to:

reg pow2 msd_2 "10*":
def pdsapow2 "(i1<n) & (i2<n) & (i1<i2) & $pow2(n) & Ak,l (k<=l & l<n) =>
 (Er,s r<=s & s<n & (s+k=r+l) & $pdfaceq(k,l,s)
 & ((r<=i1 & i1<=s) | (r<=i2 & i2<=s)))":

reg fibpow msd_fib "10*":
def fibsaf "?msd_fib (i1<n) & (i2<n) & (i1<i2) & $fibpow(n) &
 Ak,l (k<=l & l<n) => (Er,s r<=s & s<n & (s+k=r+l) & $fibfaceq(k,l,s)
 & ((r<=i1 & i1<=s) | (r<=i2 & i2<=s)))":

Figure 16 shows the sub-automaton pdsapow2 of pdfa2 for paths corresponding to prefixes of $D_{\infty}$ of lengths $2^{k}$ , and can be used to verify the results of Theorem 30. For Fibonacci words, Figure 17 shows a sub-automaton fibsaf of fibfa2 containing only the accepting paths for prefixes of length $f_{k}$ , which can be used to verify the results of Theorem 23.

Figure 14: The automaton pdfa2 accepting a sequence

s\in(\{0,1\}\times\{0,1\}\times\{0,1\})^{*}

if and only if

s[i]=(\mathsf{p}[i],\mathsf{q}[i],\mathsf{n}[i])

where

\mathsf{p},\mathsf{q},\mathsf{n}

are respectively the binary representation of integers

p-1

,

q-1

,

n

, satisfying

\{p,q\}\in\mathcal{A}(D_{\infty}[1..n])

and

p<q

. Here, the

-1

is due to the difference in the start index used for strings. By analyzing accepting paths for which

\mathsf{n}=10^{k}

implying

n=2^{k}

we can verify the statement of Theorem 30. See also Figure 16.

Figure 15: The automaton fibsa2 accepting a sequence

s\in(\{0,1\}\times\{0,1\}\times\{0,1\})^{*}

if and only if

s[i]=(\mathsf{p}[i],\mathsf{q}[i],\mathsf{n}[i])

where

\mathsf{p},\mathsf{q},\mathsf{n}

are respectively the bit representation, in Fibonacci numeration (Zeckendorf bit representation), of integers

p-1

,

q-1

,

n

satisfying

\{p,q\}\in\mathcal{A}(F_{\infty}[1..n])

and

p, q

. Here, the

-1

is due to the difference in the start index used for strings. The accepting paths for which

\mathsf{n}=10^{k}

implies

n=f_{k+1}

and the values

p

and

q

implied from

\mathsf{p}

and

\mathsf{q}

should correspond to the statement of Theorem 23. See Figure 17 for a simplified automaton containing only such paths.

Figure 16: The automaton pdsapow2 obtained by removing, from the automaton in Figure 14, all edges and nodes that are not part of accepting paths with

\mathsf{n}=10^{k}

implying

n=2^{k}

. We can see that For

k=2

,

\mathsf{p}=001

implying

p=2

and

\mathsf{q}=010\mbox{ or }011

implying

q=3\mbox{ or }4

, i.e.,

\mathcal{A}(D_{k})=\{\{2,3\},\{2,4\}\}

. For

k\geq 3

,

\mathsf{p}=00101^{k-3}\mbox{ or }00111^{k-3}

implying

p=3\cdot 2^{k-3}\mbox{ or }2^{k-1}

, and

\mathsf{q}=01011^{k-3}

implying

q=3\cdot 2^{k-2}

, i.e.,

\mathcal{A}(D_{k})=\{\{3\cdot 2^{k-3},3\cdot 2^{k-2}\},\{2^{k-1},3\cdot 2^{k-2% }\}\}

, verifying the statement of Theorem 30.

Figure 17: The automaton fibsaf obtained by removing, from the automaton in Figure 15, all edges and nodes that are not part of accepting paths with

\mathsf{n}=10^{k}

representing

f_{k+1}

in the Fibonacci numeration. Each accepting path of length

n

starting with

[0,0,1]

represents a position pair in

\mathcal{A}(F_{n})

, and the automaton can be used to verify Theorem 23 (in principle).

Appendix B Additional Figures

Figure 18: Extended version of Figure 1 for the case

n=9

. For each of

F_{n}

(bottom),

F_{n-1}

(top left), and

F_{n-2}

(top right), all of their smallest attractors are indicated as pairs of horizontally aligned dots. Characterization of the attractors of

F_{n}

via Theorem 23 is illustrated by colors: the blue and yellow dots illustrate the mapping via the occurrences of

F_{n-1}

and

(F_{n-1})^{R}

in Lemma 25; the pink dots illustrate the offset in Lemma 26; while the green dots illustrate Lemma 27.

[bib.bib1] [1] Julien Cassaigne, France Gheeraert, Antonio Restivo, Giuseppe Romana, Marinella Sciortino, and Manon Stipulanti. New string attractor-based complexities for infinite words. J. Comb. Theory, Ser. A, 208:105936, 2024. doi:10.1016/J.JCTA.2024.105936.

[bib.bib2] [2] Aldo de Luca. A combinatorial property of the Fibonacci words. Inf. Process. Lett., 12(4):193–195, 1981. doi:10.1016/0020-0190(81)90099-5.

[bib.bib3] [3] Gabriele Fici. Factorizations of the Fibonacci infinite word. J. Integer Seq., 18(9):15.9.3, 2015. URL: https://cs.uwaterloo.ca/journals/JIS/VOL18/Fici/fici5.html.

[bib.bib4] [4] Lucian Ilie and William F. Smyth. Minimum unique substrings and maximum repeats. Fundam. Informaticae, 110(1-4):183–195, 2011. doi:10.3233/FI-2011-536.

[bib.bib5] [5] Dominik Kempa and Nicola Prezza. At the roots of dictionary compression: string attractors. In Ilias Diakonikolas, David Kempe, and Monika 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. doi:10.1145/3188745.3188814.

[bib.bib6] [6] Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323–350, 1977. doi:10.1137/0206024.

[bib.bib7] [7] Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. On repetitiveness measures of Thue–Morse words. In Christina Boucher and Sharma 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. doi:10.1007/978-3-030-59212-7_15.

[bib.bib8] [8] N. Jesper Larsson and Alistair Moffat. Offline dictionary-based compression. In Data Compression Conference, DCC 1999, Snowbird, Utah, USA, March 29-31, 1999, pages 296–305. IEEE Computer Society, 1999. doi:10.1109/DCC.1999.755679.

[bib.bib9] [9] M. Lothaire. Sturmian Words, volume 90 of Encyclopedia of Mathematics and its Applications, pages 45–110. Cambridge University Press, 2002.

[bib.bib10] [10] Sabrina Mantaci, Antonio Restivo, Giuseppe Romana, Giovanna Rosone, and Marinella Sciortino. String attractors and combinatorics on words. In Alessandra Cherubini, Nicoletta Sabadini, and Simone Tini, editors, Proceedings of the 20th Italian Conference on Theoretical Computer Science, ICTCS 2019, Como, Italy, September 9-11, 2019, volume 2504 of CEUR Workshop Proceedings, pages 57–71. CEUR-WS.org, 2019. URL: https://ceur-ws.org/Vol-2504/paper8.pdf.

[bib.bib11] [11] Sabrina Mantaci, Antonio Restivo, Giuseppe Romana, Giovanna Rosone, and Marinella Sciortino. A combinatorial view on string attractors. Theor. Comput. Sci., 850:236–248, 2021. doi:10.1016/J.TCS.2020.11.006.

[bib.bib12] [12] Takuya Mieno, Shunsuke Inenaga, and Takashi Horiyama. RePair grammars are the smallest grammars for Fibonacci words. In Hideo Bannai and Jan Holub, editors, 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, Prague, Czech Republic, June 27-29, 2022, volume 223 of LIPIcs, pages 26:1–26:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.CPM.2022.26.

[bib.bib13] [13] Hamoon Mousavi. Automatic theorem proving in Walnut, 2021. arXiv:1603.06017.

[bib.bib14] [14] Luke Schaeffer and Jeffrey Shallit. String attractors for automatic sequences, 2024. arXiv:2012.06840.

[bib.bib15] [15] Zhi-Xiong Wen and Zhi-Ying Wen. Some properties of the singular words of the Fibonacci word. Eur. J. Comb., 15(6):587–598, 1994. doi:10.1006/EUJC.1994.1060.

	$\displaystyle F_{i}$	$\displaystyle=G_{i}\Delta_{i}=F_{i-1}G_{i-2}\Delta_{i}=G_{i-2}\Delta_{i-2}G_{i% -3}\Delta_{i-3}G_{i-2}\Delta_{i}=G_{i-2}(F_{i-3})^{R}(F_{i-2})^{R}\Delta_{i}$
		$\displaystyle=G_{i-2}(F_{i-1})^{R}\Delta_{i}.$

The Smallest String Attractors of Fibonacci and Period-Doubling Words

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Related Work

2 Preliminaries

Definition 1 (String Attractors [5]).

Observation 2.

Observation 3.

3 The Smallest Attractors of Fibonacci Words

3.1 Properties of Fibonacci Words and Singular Words

Definition 4 (Fn and fn).

Definition 5 (Gn, Δn).

Observation 6 (e.g. [2, 6, 9]).

Definition 7 (Singular Words).

Lemma 8 ([15]).

Lemma 9.

Proof.

Corollary 10.

Proof.

Lemma 11.

Proof.

Definition 12 (Un and Vn).

Proposition 13 ([10, Thm. 5]).

Observation 14.

3.2 Invalid Attractor Position Pairs

Lemma 15.

Proof.

Lemma 16.

Proof.

Lemma 17.

Proof.

3.3 Valid Attractor Position Pairs

Definition 18 (Lk, Rk, and Lk′).

Observation 19.

Proof.

Observation 20.

Observation 21.

Corollary 22.

Proof.

Theorem 23.

▶ Note 24.

Lemma 25.

Proof.

Lemma 26.

Proof.

Lemma 27.

Proof.

Proof of Theorem 23.

Corollary 28.

Proof.

4 The Smallest Attractors of Period-Doubling Words

Definition 29 (Dn).

Theorem 30.

Observation 31.

Corollary 32.

Observation 33.

Lemma 34.

Proof.

Lemma 35.

Proof.

Proof of Theorem 30.

5 Discussion

References

Appendix A Using Walnut to Characterize the Smallest Attractors

Appendix B Additional Figures

Definition 4 ( $F_{n}$ and $f_{n}$ ).

Definition 5 ( $G_{n}$ , $\Delta_{n}$ ).

Definition 12 ( $U_{n}$ and $V_{n}$ ).

Definition 18 ( $L_{k}$ , $R_{k}$ , and $L^{\prime}_{k}$ ).

$\blacktriangleright$ Note 24.

Definition 29 ( $D_{n}$ ).