# An S-adic characterization of minimal subshifts with first difference of complexity $1 \le p(n+1) - p(n) \le 2$

Julien Leroy

► To cite this version:

Julien Leroy. An S-adic characterization of minimal subshifts with first difference of complexity $1 \le p(n+1) - p(n) \le 2$. Discrete Mathematics and Theoretical Computer Science, 2014, Vol. 16 no. 1 (1), pp.233-286. 10.46298/dmtcs.1249. hal-01179422

HAL Id: hal-01179422

https://inria.hal.science/hal-01179422

Submitted on 22 Jul 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
An S-adic characterization of minimal
subshifts with first difference of complexity

$$
1 \le p(n + 1) - p(n) \le 2
$$

Julien Leroy

Mathematics Research Unit, FSTC, University of Luxembourg, Luxembourg

received 3rd June 2013, accepted 11th Mar. 2014.

In [Ergodic Theory Dynam. System, 16 (1996) 663–682], S. Ferenczi proved that any minimal subshift with first difference of complexity bounded by 2 is S -adic with Card(S) ≤ 3$^{27}$. In this paper, we improve this result by giving an S -adic characterization of these subshifts with a set S of 5 morphisms, solving by this way the S -adic conjecture for this particular case.

Keywords: S-adic subshift, S-adic conjecture, Rauzy graph, factor complexity, special factor

1 Introduction

A classical tool in the study of sequences (or infinite words) with values in an alphabet A is the complexity function p that counts the number p(n) of words of length n that appear in the sequence. Thus this function allows to measure the regularity in the sequence. For example, it allows to describe all ultimately periodic sequences as exactly being those for which p(n) ≤ n for some length n [MH40]. By extension, this function can obviously be defined for any language or any symbolic dynamical system (or subshift). For surveys over the complexity function, see [All94, Fer99] or [BR10, Chapter 4].

The complexity function can also be used to define the class of Sturmian sequences : it is the family of aperiodic sequences with minimal complexity p(n) = n + 1 for all lengths n . Those sequences are therefore defined over a binary alphabet (because p (1) = 2) and a large literature is devoted to them (see [Lot02, Chapter 1] and [Fog02, Chapter 6] for surveys). In particular, these sequences admit sev- eral equivalent definitions such as natural codings of rotations with irrational angle or aperiodic balanced sequences. Moreover, it is well known [MH40] that the subshifts they generate can be obtained by suc- cessive iterations of two morphisms (or substitutions) R 0 and R 1 defined (when the alphabet A is { 0 , 1 } ) by R 0 (0) = 0 , R 0 (1) = 10 , R 1 (0) = 01 and R 1 (1) = 1 . To generate not all Sturmian subshifts but all sturmian sequences it is necessary [MS93, BHZ06] to consider two additional morphisms L 0 and L 1 defined by L 0 (0) = 0 , L 0 (1) = 01 , L 1 (0) = 10 and L 1 (1) = 1 . In general, a sequence (or subshift) obtained by such a method, that is, obtained by successive iterations of morphisms belonging to a set S ,
is called an *S-adic sequence* (or subshift), accordingly to the terminology of adic systems introduced by A. M. Vershik [VL92].

Beside Sturmian sequences, many other families of sequences are usually studied in the literature. Among them one can find generalizations of Sturmian sequences, such as codings of rotations [Did98, Rot94] or of interval exchanges [Rau79, FZ08], Arnoux-Rauzy sequences [AR91] and episturmian sequences [GJ09]. One can also think about automatic sequences [AS03] linked to automata theory and morphisms.

An interesting point is that all of these mentioned sequences have a linear complexity, i.e., there exists a constant *D* such that for all positive integers *n*, *p(n) ≤ Dn*. In addition, we can usually associate a (generally finite) set *S* of morphisms to these sequences in such a way that they are *S*-adic. It is then natural to ask whether there is a connection between the fact of being *S*-adic and the fact of having a linear complexity. Both notions cannot be equivalent since, thanks to Pansiot's work [Pan84], there exist purely morphic sequences with a quadratic complexity. However, we can imagine a stronger notion of *S*-adicity that would be equivalent to having a linear complexity. In other words, we would like to find a condition *C* such that *a sequence has linear complexity if and only if it is S-adic satisfying the condition C*. This problem is called the *S-adic conjecture* and is due to B. Host. Up to now, we have no idea about the nature of the condition *C*. It may be a condition on the set *S* of morphisms, or a condition on the way in which they must occur in the sequence of morphisms. There exist examples [DLR13] supporting the idea that the answer should be a combination of both, supporting the difficulty of the conjecture.

Another difficulty of the conjecture is that all known *S*-adic representations of families of sequences strongly depend on the nature of these sequences which makes general properties difficult to extract. In addition, the characterization of everywhere growing purely morphic sequences with linear complexity (obtained by Pansiot) can only be generalized into a sufficient condition for *S*-adic sequences [Dur00, Dur03] and many (*a priori* natural) conditions over *S*-adic sequences are even not sufficient to guarantee a linear complexity [DLR13]. Nevertheless, S. Ferenczi [Fer96] provided a general method that, given any uniformly recurrent sequence with linear complexity, produces an *S*-adic representation with a finite set *S* of morphisms and such that all images of letters under the product of morphisms have length growing to infinity. By a refinement of Ferenczi's proof, the author [Ler12b] managed to highlight a few more necessary conditions of these *S*-adic representations, but which unfortunately were not sufficient to ensure linear complexity. A different (although closely linked) proof of that result can also be obtained using a generalization of return words [LR13], a tool that has been helpful to find an *S*-adic characterization of the family of linearly recurrent sequences [Dur00, Dur03] (that includes the primitive substitutive sequences [Dur98, DHS99]).

In Ferenczi's proof, the algorithm that produces the morphisms is based on an extensive use of *Rauzy graphs*. These graphs first appeared in [Rau83] and are powerful tools to study combinatorial properties of sequences or subshifts. For example, they are at the basis of a deep result due to J. Cassaigne [Cas96] stating that a sequence has linear complexity if and only if the first difference of its complexity *p(n + 1) - p(n)* is bounded. They also allowed T. Monteil [BR10, Chapter 7], [Mon05, Chapter 5] to improve a result due to M. Boshernitzan [Bos85] by giving a better bound on the number of ergodic invariant measures of a subshift. However, these graphs are usually difficult to compute as soon as the complexity exceeds a very low level. For this reason, the extraction of properties of the *S*-adic representation from these graphs is usually hard. Anyway, applying these methods to subshifts for which the difference of complexity *p(n+1) - p(n)* is no more than 2 for every *n*, Ferenczi succeeded to prove that the number of morphisms built in such a way is less than $3^{27}$.
In this paper, we strongly improve this bound and show the existence of a set $\mathcal{S}$ of 5 morphisms such that any minimal subshift with first difference of complexity bounded by 2 is $\mathcal{S}$-adic. Furthermore, we give necessary and sufficient conditions on sequences in $\mathcal{S}^\mathbb{N}$ to be an $\mathcal{S}$-adic representation of such a subshift. In other words, we solve the $\mathcal{S}$-adic conjecture for this particular case. This characterization contains the Sturmian subshifts, the Arnoux-Rauzy subshifts, the three-interval-exchange subshifts and the subshifts with complexity $2n$, some of which were studied by G. Rote [Rot94].

As a corollary, the obtained $\mathcal{S}$-adic representations provide Bratteli-Vershik representations of the concerned subshifts. Historically, O. Bratteli [Bra72] introduced infinite graphs (subsequently called *Bratteli diagrams*) partitioned into levels in order to approximate $C^*$-algebras. With other motivations, Vershik [Ver82] associated dynamics (*adic transformations*) to these diagrams by introducing a lexicographic ordering on the infinite paths of the diagrams. This ordering is induced by a partial order on the edges between two consecutive levels, it can then be defined by an adjacency matrix between the two considered levels and thus by a morphism. For more details, see [BR10, Chapter 6] and see [War02] for the link between Bratteli diagrams and $\mathcal{S}$-adic systems.

By a refinement of Vershik's constructions, the authors of [HPS92] have proved that any minimal Cantor system is topologically isomorphic to a Bratteli-Vershik system (Vershik already obtained this result in [Ver82] in a measure theoretical context). These Bratteli-Vershik representations are helpful in dynamics, mainly with problems about recurrence. But, being given a minimal Cantor system, it is generally difficult to find a "canonical" Bratteli-Vershik representation (see [DHS99] for examples). However, Ferenczi proved that for minimal subshifts with linear complexity, the number of morphisms read on the associated Bratteli diagram (in a measure theoretical context) is finite [Fer96]. In particular, he obtained an upper bound on the rank of these systems and proved that they cannot be strongly mixing. In addition, Durand showed that, in the case of linearly recurrent subshifts, the morphisms appearing in the $\mathcal{S}$-adic representation are exactly those read on the Bratteli diagram. Furthermore, unlike in Ferenczi's result, the subshift is topologically conjugated to the Bratteli-Vershik system. Similarly to that last case, the $\mathcal{S}$-adic representations obtained in this paper are exactly those that can be read on a Bratteli-Vershik system which is topologically conjugated to the $\mathcal{S}$-adic subshift [DL12].

The paper is organized as follows. Section 2 contains all needed definitions and backgrounds. Section 3 concerns $\mathcal{S}$-adic representations of minimal subshift. We define the tools that are needed for the announced $\mathcal{S}$-adic characterization in a more general case. In Section 4, we start a detailed description of Rauzy graphs corresponding to minimal subshifts with first difference of complexity bounded by 2. This allows us to explicitly compute all needed morphisms. In Section 5, we improve the results obtained in Section 4 by studying even more the sequences of possible evolutions of Rauzy graphs. This allows us to obtain an $\mathcal{S}$-adic characterization, hence the condition $C$ of the conjecture for this particular case. Observe that due to the length of some computation, not all development are presented here. The interested reader can find some help (figures representing evolutions, list of corresponding morphisms, etc.) in [Ler13].

# 2 Backgrounds

## 2.1 Words, sequences and languages

We assume that readers are familiar with combinatorics on words; for basic (possibly omitted) definitions we follow [Lot97, Lot02, BR10].

Given an *alphabet* $A$, that is a finite set of symbols called *letters*, we denote by $A^*$ the set of all finite words over $A$ (that is the set of all finite sequences of elements of $A$). As usual, the *concatenation* of two
words $u$ and $v$ is simply denoted $uv$. It is well known that the set $A^*$ embedded with the concatenation
operation is a free monoid with neutral element $\varepsilon$, the empty word.

For a word $u = u_1 \cdots u_\ell$ of length $|u| = \ell$, we write $u[i, j] = u_i \cdots u_j$ for $1 \le i \le j \le \ell$. A word $v$
is a factor of a word $u$ (or occurs at position $i$ in $u$) if $u[i, j] = v$ for some integers $i$ and $j$. It is a prefix
 resp. suffix) if $i=1$ (resp. $j=|u|$). The language of $u$ is the set Fac($u$) of all factors of $u$;

A two-sided sequence (resp. one-sided sequence) is an element of $A^{\mathbb{Z}}$ (resp. $A^{\mathbb{N}}$); sequences will be
denoted by bold letters. When no information are given, sequence means two-sided sequence. With the
product topology of the discrete topology over $A$, $A^{\mathbb{Z}}$ and $A^{\mathbb{N}}$ are compact metric spaces.

We extend the notions of factor, prefix and suffix to two-sided sequences (resp. one-sided sequences)
putting $i, j \in \mathbb{Z}$ (resp. $i, j \in \mathbb{N}$), $i \le j$, $i = -\infty$ (resp. $i = 0$) for prefixes and $j = +\infty$ for suffixes.

Let $u$ be a non-empty finite word over $A$. We let $u^\omega$ (resp. $u^\infty$) denote the one-sided sequence $uuu\cdots$ (resp. two-sided sequence $\cdots uuu.uuu\cdots$) composed of consecutive copies of $u$. A one-sided sequence (resp. two-sided sequence) $w$ is periodic if there is a word $u$ such that $w = u^\omega$ (resp. $w = u^\infty$).

A sequence $w$ is recurrent if every factor occurs infinitely often. It is uniformly recurrent if it is
recurrent and every factor occurs with bounded gaps, i.e., if $w$ is a factor of $w$, there is a constant $K$ such
that for any integers $i, j$ such that $w[i, i + |u| - 1]$ and $w[j, j + |u| - 1]$ are two consecutive occurrences
of $u$ in $w$, then $|i - j| \le K$.

## 2.2 Subshifts and minimality

A subshift over $A$ is a couple $(X, T|_X)$ (or simply $(X, T)$) where $X$ is a closed $T$-invariant $(T(X) = X)$
subset of $A^{\mathbb{Z}}$ and $T$ is the shift transformation $T: A^{\mathbb{Z}} \to A^{\mathbb{Z}}$, $(w_i)_{i \in \mathbb{Z}} \mapsto (w_{i+1})_{i \in \mathbb{Z}}$.

The language of a subshift $X$ is the union of the languages of its elements and we denote it by $\text{Fac}(X)$.

Let $w$ be a sequence (or a one-sided sequence) over $A$. We denote by $X_w$ the set $\{\mathbf{x} \in A^{\mathbb{Z}} \mid \mathbf{x}[i, j] \in \text{Fac}(w) \text{ for all } i, j \in \mathbb{Z}, i \le j\}$. Then, $(X_w, T)$ is a subshift called the subshift generated by $w$. For $w \in A^{\mathbb{Z}}$, we have $X_w = \{T^n(\mathbf{w}) \mid n \in \mathbb{Z}\}$, where $\mathbb{Y}$ denotes the topological closure of $Y \subset A^{\mathbb{Z}}$.

A subshift $(X, T)$ is periodic whenever $X$ is finite. Observe that in this case, $X$ contains only periodic
sequences. It is minimal if the only closed $T$-invariant subsets of $X$ are $X$ and $\emptyset$, or, equivalently, if for all
$w \in X$, we have $X = X_w$. We also have that $(X_w, T)$ is minimal if and only if $w$ is uniformly recurrent.

In the sequel, we will mostly consider minimal subshifts.

## 2.3 Factor complexity and special factors

The factor complexity of a subshift $X$ is the function $p_X: \mathbb{N} \to \mathbb{N}$ that counts the number of words of each
length that occur in elements of $X$, i.e., $p_X(n) = \text{Card}(\text{Fac}_n(X))$, where $\text{Fac}_n(X) = \text{Fac}(X) \cap A^n$.

The first difference of complexity $s(n) = p(n+1) - p(n)$ is closely related to special factors [Cas97].
A word $u$ in Fac($X$) is a right special factor (resp. a left special factor) if there are two letters $a$ and $b$ in
$A$ such that $ua$ and $ub$ (resp. $au$ and $bu$) belong to Fac($X$). For $u$ in Fac($X$), if $\delta^+u$ (resp. $\delta^-u$) denotes
the number of letters $a$ in $A$ such that $ua$ (resp. $au$) is in Fac($X$) we have

$$p_X(n+1) - p_X(n) = \sum_{\substack{u \in \text{Fac}_n(X) \\ u \text{ right special}}} \underbrace{(\delta^+ u - 1)}_{\ge 1} \quad (1)$$

$$= \sum_{\substack{u \in \text{Fac}_n(X) \\ u \text{ left special}}} \underbrace{(\delta^- u - 1)}_{\ge 1} \quad (2)$$
It is well known [MH40] that a subshift is aperiodic if and only if $p_X(n) \ge n + 1$ for all $n$, or, equivalently, if there is at least one right (resp. left) special factor of each length.

The second difference of complexity $s(n+1) - s(n)$ is related to *bispecial factors*, i.e., to factors that are both left and right special. Indeed, if $u$ is a bispecial factor in $\mathrm{Fac}(X)$, its *bilateral order* is $m(u) = \mathrm{Card}(\mathrm{Fac}(X) \cap \mathrm{AuA}) - \delta^+u - \delta^-u + 1$ and we have$^{(i)}$

$$s_X(n+1) - s_X(n) = \sum_{u \in \mathrm{Fac}_n(X)} m(u).$$

A bispecial factor $u$ is said to be *weak* (resp. *neutral*, *strong*) whenever $m(u) < 0$ (resp. $m(u) = 0$, $m(u) > 0$).

## 2.4 Morphisms and S-adicity

Given two alphabets $A$ and $B$, a free monoid morphism, or simply *morphism* $\sigma$, is a map from $A^*$ to $B^*$ such that $\sigma(uv) = \sigma(u)\sigma(v)$ for all words $u$ and $v$ over $A$ (note this implies $\sigma(\varepsilon) = \varepsilon$). It is well known that a morphism is completely determined by the images of letters.

When a morphism is not *erasing*, that is the images of letters are never the empty word, the notion of morphism extends naturally to one-sided and two-sided sequences. Furthermore, if $A = B$ and if there is a letter $a \in A$ such that $\sigma(a) \in aA^*$, then $\sigma^\omega(a) = \lim_{n \to +\infty} \sigma^n(a^\omega)$ is a one-sided sequence which is a fixed point of $\sigma$. If there is also a letter $b$ such that $\sigma(b) \in A^*b$, then the two-sided sequence $\sigma^\omega(b.a^\omega) = \lim_{n \to +\infty} \sigma^n(\cdots bbb.aaa\cdots)$ is also a fixed point of $\sigma$.

Let $w$ be a sequence over $A$. An *adic representation* of $w$ is given by a sequence $(\sigma_n : A_{n+1}^* \to A_n^*)_{n \in \mathbb{N}}$ of morphisms and a sequence $(a_n)_{n \in \mathbb{N}}$ of letters, $a_i \in A_i$ for all $i$, such that the alphabet $A_0$ is equal to $A$, $\lim_{n \to +\infty} |\sigma_0\sigma_1\cdots\sigma_n(a_{n+1})| = +\infty$ and

$$\mathbf{w} = \lim_{n \to +\infty} \sigma_0 \sigma_1 \cdots \sigma_n (a_{n+1}^\infty).$$

The sequence $(\sigma_n)_{n \in \mathbb{N}}$ is the *directive word* of the representation. Let $S$ be a set of morphisms. We say that $\mathbf{w}$ is *S-adic* (or that $\mathbf{w}$ is *directed by* $(\sigma_n)_{n \in \mathbb{N}}$) if $(\sigma_n)_{n \in \mathbb{N}} \in S^\mathbb{N}$. In the sequel, we will say that a sequence $\mathbf{w}$ is *S-adic* whenever there is a set $S$ of morphisms for which $\mathbf{w}$ admits an *S-adic representation*. We say that a subshift $(X, T)$ is *S-adic* if it is the subshift generated by an *S-adic sequence*.

Let $(\sigma_n)_{n \in \mathbb{N}}$ be a sequence of morphisms. The sequence of morphisms $(\tau_n : B_{n+1}^* \to B_n^*)_{n \in \mathbb{N}}$ is a *contraction* of $(\sigma_n : A_{n+1}^* \to A_n^*)_{n \in \mathbb{N}}$ if there is an increasing sequence of integers $(i_n)_{n \in \mathbb{N}}$ such that for all $n \in \mathbb{N}$, $B_n = A_{i_n}$ and

$$\tau_n = \sigma_{i_n} \sigma_{i_{n+1}} \cdots \sigma_{i_{n+1}-1}.$$

A sequence $(\sigma_n)_{n \in \mathbb{N}}$ of morphisms is said to be *weakly primitive* if for all $r \in \mathbb{N}$, there exists $s > r$ such that for all letters $a \in A_r$ and $b \in A_{s+1}$, the letter $a$ occurs in $\sigma_r \cdots \sigma_s(b)$. A sequence $(\sigma_n)_{n \in \mathbb{N}}$ of morphisms is said to be *primitive* if there exists $k \in \mathbb{N}$ such that for all $r \in \mathbb{N}$ and for all letters $a \in A_r$ and $b \in A_{r+k+1}$, the letter $a$ occurs in $\sigma_r \cdots \sigma_{r+k}(b)$.

<footnote>(i) Observe that for non-bispecial factors $u$, we have $m(u) = 0$.</footnote>
## 2.5 Rauzy graphs

Let $(X, T)$ be a subshift over an alphabet $A$.

**Definition 2.1** The Rauzy graph of order $n$ of $(X, T)$ (also called graph of words of length $n$), denoted by $G_n(X)$ (or simply $G_n$), is the labelled directed graph whose set of vertices is $\text{Fac}_n(X)$ and there is an edge from $u$ to $v$ if there exist some letters $a$ and $b$ in $A$ such that $ub = av \in \text{Fac}_{n+1}(X)$; this edge is labelled$^{(ii)}$ by $ub$ and is denoted by $(u, (a, b), v)$.

Let us introduce some notation: for an edge $e = (u, (a, b), v)$, we write $o(e) = u$ (o for out), $i(e) = v$ (i for in) and we call $\lambda_L(e) = a$ its left label, $\lambda_R(e) = b$ its right label and $\lambda(e) = ub = av$ its full label. Same definitions hold for labels of paths where we naturally extend these maps as follows: if $p$ is the path $(u_0, (a_1, b_1), u_1)(u_1, (a_2, b_2), u_2) \cdots (u_{\ell-1}, (a_\ell, b_\ell), u_\ell)$, then $\lambda_L(p) = a_1 \cdots a_\ell$, $\lambda_R(p) = b_1 \cdots b_\ell$ and $\lambda(p) = u_0\lambda_R(p) = \lambda_L(p)u_\ell$. Thus left and right labels are words of same length as the considered path. In this paper we will mostly consider right labels.

**Example 2.2** Let $(X_\varphi, T)$ be the subshift generated by the Fibonacci sequence $\varphi^\omega(0)$ where $\varphi$ is the morphism defined by $\varphi(0) = 01$, $\varphi(1) = 0$. Figure 2.1 represents the three first Rauzy graphs of $(X_\varphi, T)$ (with full labels on the edges).

<figure><img src="image_2.png" /><figcaption>Figure 2.1: First Rauzy graphs of the Fibonacci sequence</figcaption></figure>

**Remark 2.3** Any minimal subshift has only strongly connected Rauzy graphs (that is, for all vertices $u$ and $v$ of $G_n$ there is a path from $u$ to $v$).

We say that a vertex $v$ is right special (resp. left special, bispecial) if it corresponds to a right special (resp. left special, bispecial) factor.

By definition of Rauzy graphs, any word $u \in \text{Fac}(X)$ is the full label of a path in $G_n(X)$ for $n < |u|$. Figure 12.1.2 shows that the converse is not true: the word 000 is the full label of a path of length 2 but does not belong to $\text{Fac}(X_\varphi)$. Hence a path $p$ is said to be allowed if $\lambda(p) \in \text{Fac}(X)$. The next proposition follows immediately from definitions.

**Proposition 2.4** Let $G_n$ be a Rauzy graph of order $n$. For all paths $p$ of length $\ell \le n$ in $G_n$, the left (resp. right) label of $p$ is a prefix (resp. a suffix) of $o(p)$ (resp. of $i(p)$).

<footnote>(ii) In the literature, there are different ways of labelling the edges: they are sometimes labelled by the letter $a$, by the letter $b$, by the ordered pair $(a, b)$ or by the word $av$.</footnote>
**Definition 2.5** The reduced Rauzy graph of order $n$ of $(X, T)$ is the directed graph $g_n(X)$ such that the vertices are the special vertices of $G_n(X)$ and there is an edge from $u$ to $v$ if there is a path $p$ in $G_n(X)$ from $u$ to $v$ such that all interior vertices of $p$ are not special.

The (left, right and full) labels of an edge in $g_n(X)$ are the (left, right and full) labels of the corresponding path in $G_n(X)$. To avoid any confusion, edges of reduced Rauzy graphs are represented by double lines. Figure 2.2 represents the reduced Rauzy graph $g_\phi(2)$ with full labels on the edges.

<figure><img src="image_3.png" /><figcaption>Figure 2.2: $g_2(X_\phi)$</figcaption></figure>

# 3 Adicity of minimal subshifts using Rauzy graphs

Let $(X, T)$ be a minimal subshift over an alphabet $A$. In this section we prove the following theorem.

**Theorem 3.1** An aperiodic subshift $(X, T)$ is minimal if and only if it is primitive and proper S-adic. Moreover, if $X$ does not have linear complexity, then $S$ is infinite.

The construction of the S-adic representation is based on the evolution of Rauzy graphs. Similar construction can be found in [Ler12b] (see also [Fer96]) where we give a method to build an S-adic representation of any uniformly recurrent sequence with a linear complexity. In that paper, the construction is based on the $n$-segments although here we work with the $n$-circuits (see Section 3.2 below for the definition). However the techniques are the same.

## 3.1 $n$-circuits

For $n \in \mathbb{N}$, an $n$-circuit is a non-empty path $p$ in $G_n(X)$ such that $o(p) = i(p)$ is a right special vertex and no interior vertex of $p$ is $o(p)$.

**Remark 3.2** An $n$-circuit is not necessarily an allowed path of $G_n(X)$. Indeed, consider the subshift $X_\mu$ generated by the Thue-Morse sequence $\mu^\omega(0)$ where $\mu$ is the Thue-Morse morphism defined by $\mu(0) = 01$ and $\mu(1) = 10$. The path

$$010 \to (101 \to 011 \to 110 \to 101)^3 \to 010$$

in Figure 3.1 is a 3-circuit and its full label contains the word $(101)^3$ which is not a factor of $\mu^\omega(0)$ since the Thue-Morse sequence is cube-free [Thu06, Thu12].
<figure><img src="image_4.png" /><figcaption>Figure 3.1: Rauzy graph of order 3 (with right labels on the edges) of $X_μ$.</figcaption></figure>

**Remark 3.3** The notion of n-circuit is closely related to the notion of return word. Let us recall that if $u \in \mathrm{Fac}(X)$, a return word to $u$ in $X$ is a non-empty word $v$ such that $uv \in \mathrm{Fac}(X)$ and that contains exactly two occurrences of $u$, one as a prefix and one as a suffix. If $u$ is a right special vertex in $G_n(X)$, then $\{\lambda_R(v) | v \text{ allowed n-circuit starting from } u\}$ is exactly the set of return words to $u$.

**Fact 3.4** A subshift is minimal if and only if for all $n$, the number of its allowed $n$-circuits is finite.

The next lemma is also well known.

**Lemma 3.5** Let $(X, T)$ be a minimal and aperiodic subshift. Then

$$ \lim_{n \to +\infty} \min\{|\lambda_R(p)| \mid p \text{ allowed n-circuit}\} = +\infty. $$

## 3.2 Definition of the morphisms of the adic representation

The adic representation that we will compute is based on the behaviour of $n$-circuits when $n$ increases. To this aim we define a map $\psi_n$ on the set of paths of $G_{n+1}(X)$ in the following way. For each path $p$ in $G_{n+1}(X)$ with right label $\lambda_R(p) = u$, $\psi_n(p)$ is the unique path $q$ in $G_n(X)$ whose right label is $\lambda_R(q) = u$ and such that $o(q)$ is suffix of $o(p)$ respectively. The next lemma is obvious.

**Lemma 3.6** Let $(X, T)$ be a subshift. If $u \in \mathrm{Fac}_{n+1}(X)$ is a right special factor, then for all allowed $(n+1)$-circuit $p$ starting from $u$, there exist some allowed $n$-circuits $q_1, q_2, \dots, q_k$ starting from the right special factor $u[2, n+1] \in \mathrm{Fac}_n(X)$ such that $\psi_n(p) = q_1q_2\cdots q_k$. Moreover, if $G_n(X)$ does not contain any bispecial vertex, then $\psi_n$ is a bijective map such that for every allowed $(n+1)$-circuit $p$, $\psi_n(p)$ is an allowed $n$-circuit.

Lemma 3.6 allows to define some morphisms coding how the $n$-circuits can be concatenated to create the $(n+1)$-circuits. However we can see in this lemma that we can only put in relations the $n$-circuits and $(n+1)$-circuits that are starting in vertices with the same suffix of length $n$. Lemma 3.7 below allows to choose some particular vertices; it comes from aperiodicity and from the observation that any suffix of a right special factor is also right special.

**Lemma 3.7** Let $(X, T)$ be an aperiodic subshift on an alphabet $A$. There exists an infinite sequence $(U_n \in \mathrm{Fac}_n(X))_{n \in \mathbb{N}}$ such that for all $n$, $U_n$ is a right special factor and is a suffix of $U_{n+1}$.

**Definition 3.8** Let $(X, T)$ be a minimal and aperiodic subshift and let $(U_n)_{n \in \mathbb{N}}$ be a sequence as in Lemma 3.7. For each non-negative integer $n$, we let $A_n$ denote the set of allowed $n$-circuits starting from $U_n$. Now define the alphabet $^{(iii)}$ $A_n = \{0, 1, \dots, \mathrm{Card}(A_n) - 1\}$ and consider a bijection $\theta_n : A_n \to A_n$.

<footnote>(iii) $A_n$ is finite due to Fact 3.4.</footnote>
We can extend $\theta_n$ to an isomorphism by putting $\theta_n(ab) = \theta_n(a)\theta_n(b)$ for all letters a, b in $A_n$ (observe that $\theta_n(a)\theta_n(b)$ might not be a path in $G_n(X)$). Then, for all $n$ we define the morphism $\gamma_n : A_{n+1}^* \to A_n^*$ as the unique morphism satisfying

$$ \theta_n \gamma_n = \psi_n \theta_{n+1}. $$

**Remark 3.9** Let $(i_n)_{n \in \mathbb{N}}$ be the increasing sequence of non-negative integers such that there is a bispecial factor in $\mathrm{Fac}_k(X)$ if and only if $k = i_n$ for some $n$. It is a direct consequence of Lemma 3.6 that if $k \notin \{i_n | n \in \mathbb{N}\}$, then the morphism $\gamma_k$ is simply a bijective and letter-to-letter morphism. This morphism only depends on the differences that could exist between $\theta_k$ and $\theta_{k+1}$. In that case, we can suppose without loss of generality that $\theta_k$ and $\theta_{k+1}$ satisfy $\psi_k \theta_{k+1}(i) = \theta_k(i)$ for all letters $i$ in $A_{k+1}$ so that $\gamma_k$ is the identity morphism. As a consequence, to build an adic representation of a subshift, it would suffice to consider the subsequence $(\gamma_{i_n})_{n \in \mathbb{N}}$ of $(\gamma_n)_{n \in \mathbb{N}}$. Depending on the context, we will sometimes consider the sequence $(\gamma_n)_{n \in \mathbb{N}}$ or the subsequence $(\gamma_{i_n})_{n \in \mathbb{N}}$.

**Remark 3.10** If the alphabet of $(X, T)$ is $A = \{0, \dots, k\}$, the Rauzy graph $G_0(X)$ is as in Figure 3.2 so we have $\lambda_R(A_0) = A$. We can suppose that $\theta_0$ is such that $\lambda_R \theta_0(a) = a$ for all $a \in A_0$.

<figure><img src="image_5.png" /><figcaption>Figure 3.2: Rauzy graph $G_0$ of any subshift over $\{0, \dots, k\}$</figcaption></figure>

### 3.2.1 An example

Consider a graph as represented in Figure 3.3 and let us give all possible evolutions from it. The letters $a$ and $b$ (resp. $\alpha$ and $\beta$) represent the right (resp. left) extending letters of $U_n$.

<figure><img src="image_6.png" /><figcaption>Figure 3.3: Reduced Rauzy graph $g_n$ with some additional labels</figcaption></figure>

By the definition of Rauzy graphs, the words $\alpha U_n$, $\beta U_n$, $U_n a$ and $U_n b$ are vertices of $G_{n+1}$. Since the subshifts we are considering satisfy $p(n+1) - p(n) \ge 1$ for all $n$, at least one of the vertices $\alpha U_n$ and $\beta U_n$ is right special and at least one of the vertices $U_n a$ and $U_n b$ is left special. Moreover, by the definition of reduced Rauzy graphs, the two loops of $g_n$ become edges respectively from $U_n a$ to $\alpha U_n$ and from $U_n b$ to $\beta U_n$. Thus, the only missing information are which edges are starting from $\alpha U_n$ and $\beta U_n$ and which edges are arriving to $U_n a$ and $U_n b$. By minimality, $G_{n+1}$ has to be strongly connected so
we have only three possibilities (2 of them being symmetric). The possible evolutions are represented at Figure 3.4.

<figure><img src="image_7.png" /><figcaption>Figure 3.4: Possible evolutions of the graph represented in Figure 3.3</figcaption></figure>

Suppose that the bijection $\theta_n$ maps 0 to the $n$-circuit starting with letter $a$ and 1 to the $n$-circuit starting with letter $b$. Consider the same definition of $\theta_{n+1}$ for the first two evolutions (since $\text{Card}(A_{n+1}) = 2$). For the third one, suppose that $\text{Card}(A_{n+1}) = r+1$ ($1 \le r < +\infty$) and that if $U_{n+1} = \alpha U_n$ (resp. $\beta U_n$), $\theta_{n+1}(0)$ is the loop starting with the edge from $\alpha U_n$ to $U_n a$ (resp. $\beta U_n$ to $U_n b$) and let $k_1, \dots, k_r$ be integers such that $\theta_{n+1}(i)$ is the path going to $U_n b$ (resp. to $U_n a$) and going $k_i$ times through the loop $U_n b \to \beta U_n \to U_n b$ (resp. $U_n a \to \alpha U_n \to U_n a$) before coming back to $\alpha U_n$ (resp. $\beta U_n$).

Then for the first two possible evolutions, the morphisms coding them are respectively

$$ \begin{cases} 0 \mapsto 0 \\ 1 \mapsto 10 \end{cases} \quad \text{and} \quad \begin{cases} 0 \mapsto 1 \\ 1 \mapsto 01 \end{cases} \qquad (3) $$

and the morphism coding the third evolution is one of the following, depending on the choice of $U_{n+1}$:

$$ \left\{ \begin{array}{l} 0 \mapsto 0 \\ 1 \mapsto 1^{k_1} 0 \\ 2 \mapsto 1^{k_2} 0 \\ \vdots \\ r \mapsto 1^{k_r} 0 \end{array} \right. \qquad \left\{ \begin{array}{l} 0 \mapsto 1 \\ 1 \mapsto 0^{k_1} 1 \\ 2 \mapsto 0^{k_2} 1 \\ \vdots \\ r \mapsto 0^{k_r} 1 \end{array} \right. \qquad (4) $$

### 3.3 Adic representation of $\text{Fac}(X)$

The next two results show a *posteriori* that this makes sense to build an *S*-adic representation using *n*-circuits: they state that when considering a sequence $(U_n)_{n \in \mathbb{N}}$ as in Lemma 3.7, the labels of *n*-circuits starting from $U_n$ provide the entire language of $X$ when *n* goes to infinity.
**Lemma 3.11** Let $(X, T)$ be a minimal and aperiodic subshift. If $(U_n \in \text{Fac}_n(X))_{n \in \mathbb{N}}$ is a sequence of right special vertices such that $U_n$ is suffix of $U_{n+1}$, then for all $n$

$$ \text{Fac}(\{\lambda_R(p) \mid p \text{ allowed } (n+1)\text{-circuit starting from } U_{n+1}\}^*) \subseteq \text{Fac}(\{\lambda_R(p) \mid p \text{ allowed } n\text{-circuit starting from } U_n\}^*) \quad (5) $$

and

$$ \bigcap_{n \in \mathbb{N}} \text{Fac}(\{\lambda_R(p) \mid p \text{ allowed } n\text{-circuit starting from } U_n\}^*) = \text{Fac}(X). \quad (6) $$

Furthermore, for all non-negative integers $\ell$, there is a non-negative integer $N_\ell$ such that

$$ \text{Fac}_{\le \ell}(\{\lambda_R(p) \mid p \text{ allowed } N_\ell\text{-circuit starting from } U_n\}^*) = \text{Fac}_{\le \ell}(X), \quad (7) $$

where $\text{Fac}_{\le \ell}(X)$ stands for $\bigcup_{0 \le n \le \ell} \text{Fac}_n(X)$.

**Proof:** Indeed, (5) directly follows from Lemma 3.6 and (6) and (7) are consequences of the minimality.

<figure><img src="image_8.png" /></figure>

The next result is just a reformulation of Lemma 3.5 and of Lemma 3.11.

**Corollary 3.12** Let $(X, T)$ be a minimal and aperiodic subshift and let $(\gamma_n)_{n \in \mathbb{N}}$ be the sequence of morphisms as in Definition 3.8. We have

$$ \min_{n \to +\infty} \min_{a \in A_{n+1}} |\gamma_0 \cdots \gamma_n(a)| = +\infty $$

and for all sequences of letters $(a_n \in A_n)_{n \in \mathbb{N}}$,

$$ \bigcap_{n \in \mathbb{N}} \text{Fac}(\gamma_0 \cdots \gamma_n(a_{n+1})) = \text{Fac}(X). $$

## 3.4 Adic representation of X

In this section we prove that, up to a little change, the directive word $(\gamma_n)_{n \in \mathbb{N}}$ introduced in Definition 3.8 is an adic representation of a sequence in $X$, i.e., we provide a slightly different directive word $(\tau_n : B_{n+1}^* \to B_n^*)_{n \in \mathbb{N}}$ such that $(\tau_0 \cdots \tau_n(a_{n+1}^\infty))_{n \in \mathbb{N}}$ converges in $A^Z$ to $w \in X$. The proof of Theorem 3.1 follows immediately from Lemma 3.16 and Proposition 3.17.

The next result shows that there is a contraction $(\gamma'_n : A_{n+1}^{\prime*} \to A_n^{\prime*})_{n \in \mathbb{N}}$ of $(\gamma_n)_{n \in \mathbb{N}}$ such that every morphism $\gamma'_n$ is right proper, i.e., there is a letter $a \in A'_n$ such that $\gamma'_n(A_{n+1}'') \subset A_n'^*a$.

**Lemma 3.13** Let $(X, T)$ be a minimal subshift and let $(\gamma_n)_{n \in \mathbb{N}}$ be the sequence of morphisms defined in Definition 3.8. For all non-negative integers $r$ there is an integer $s \ge r$ and a letter $a$ in $A_r$ such that $\gamma_r \cdots \gamma_s(A_{s+1}) \subset A_r^*a$.

**Proof:** Let $(U_n)_{n \in \mathbb{N}}$ be a sequence as defined in Lemma 3.7 and let $(\gamma_n)_{n \in \mathbb{N}}$ be the sequence of morphisms as in Definition 3.8. Let $r$ be a non-negative integer. By definition, for all integers $j > r$, $U_j$ is a word in $\text{Fac}(X)$ that admits $U_r$ as a suffix. Consequently, we can associate to $U_j$ a path $p_j$ of length $j-r$ in $G_r$ such that $\lambda(p_j) = U_j$ and $i(p_j) = U_r$. As $(X, T)$ is minimal, there is an integer $\ell$ such that $U_r$ is
a factor of every word in $\mathrm{Fac}_\ell(X)$. Thus, there is an integer $k > r$ for which $p_k$ is an allowed $r$-circuit starting in $U_r$. Thus $U_k \in (U_r A^+ \cap A^+ U_r) \setminus (A^+ U_r A^+)$. Let us prove that there is an integer $s > r$ such that $\gamma_r \cdots \gamma_{s-1}(A_s) \subset A_r^* a$ with $a = \theta_r^{-1}(p_k)$.

By Lemma 3.5, there is an integer $s \ge k$ such that all $s$-circuits starting from $U_s$ have length at least $k+r$. Let $c$ be such an $s$-circuit. We deduce from Proposition 2.4 that $\lambda_R(c) \in A^{\ge r} U_k$. Let $q$ be the suffix of $c$ of length $k-r$. By construction, we have $o(q) \in A^+ U_r$, $i(q) = U_s \in A^+ U_r$ and $\lambda_R(q) = \lambda_R(p_k)$. Consequently we get $\psi_r \psi_{r+1} \cdots \psi_{s-1}(q) = p_k$, meaning that $\gamma_r \cdots \gamma_{s-1}(A_s) \subset A_r^* a$. $\square$

The following trick allows us to define the directive word $(\tau_n)_{n \in \mathbb{N}}$ mentioned above. If $\sigma : A^* \to B^*$ is a right proper morphism with ending letter $r \in B$, then its left conjugate is the morphism $\sigma^{(L)} : A^* \to B^*$ defined by $\sigma^{(L)}(a) = ru$ whenever $\sigma(a) = ur$. Thus, it is a left proper morphism, i.e., there is a letter $a \in B$ such that $\sigma(A) \subset aB^*$ (in our case, $a = r$).

**Lemma 3.14** If $\sigma : A^* \to B^*$ is a right proper morphism and if $w$ is a sequence in $A^\mathbb{Z}$, then we have $T(\sigma^{(L)}(w)) = \sigma(w)$. In particular, $\mathrm{Fac}(\sigma^{(L)}(w)) = \mathrm{Fac}(\sigma(w))$.

**Fact 3.15** Let $(\gamma'_n)_{n \in \mathbb{N}}$ be a contraction of $(\gamma_n)_{n \in \mathbb{N}}$ such that all morphisms $\gamma'_n$ are right proper. Every morphism $\tau_n = \gamma'_{2n} \gamma'^{(L)}_{2n+1}$ is proper, i.e., is both left and right proper.

**Lemma 3.16** The directive word $(\tau_n : B^*_{n+1} \to B^*_{n})_{n \in \mathbb{N}}$ is proper and weakly primitive and such that $(\tau_0 \cdots \tau_n(b_{n+1}))_{n \in \mathbb{N}}$ converges in $A^\mathbb{Z}$ to $w \in X$ for all sequences $(b_n \in B_n)_{n \in \mathbb{N}}$.

**Proof:** The convergence is ensured by the fact that all morphisms are left and right proper. The fact that the limit $w$ belongs to $X$ follows from Corollary 3.12 and Lemma 3.14. The weak primitiveness comes from the minimality of $(X, T)$. $\square$

**Proposition 3.17 (Durand [Dur00, Dur03])** If $(X, T)$ is a primitive $S$-adic subshift with $S$ finite, then $X$ has linear complexity.

## 4 $S$-adicity of minimal subshifts satisfying $1 \le p(n+1) - p(n) \le 2$

In this chapter we present Theorem 4.1 which is an improvement of Theorem 3.1 for the particular case of minimal subshifts with first difference of complexity bounded by 2. For this class of complexity, Ferenczi [Fer96] proved that the amount of morphisms needed for the $S$-adic representations is less than $3^{27}$. Here, we significantly improve this bound by giving the set $S$ of 5 morphisms that are actually needed. To avoid unnecessary repetitions, we only sketch the proof of Theorem 4.1 on an example. We will later prove Theorem 5.25 which is an improvement of the former. In all this chapter, the set $S$ is the set of morphisms $\{G, D, M, E_{01}, E_{12}\}$ where

$$ G: \begin{cases} 0 \mapsto 10 \\ 1 \mapsto 1 \\ 2 \mapsto 2 \end{cases} \quad D: \begin{cases} 0 \mapsto 01 \\ 1 \mapsto 1 \\ 2 \mapsto 2 \end{cases} \quad M: \begin{cases} 0 \mapsto 0 \\ 1 \mapsto 1 \\ 2 \mapsto 1 \end{cases} $$

$$ E_{01}: \begin{cases} 0 \mapsto 1 \\ 1 \mapsto 0 \\ 2 \mapsto 2 \end{cases} \quad E_{12}: \begin{cases} 0 \mapsto 0 \\ 1 \mapsto 2 \\ 2 \mapsto 1 \end{cases} $$
**Theorem 4.1** Let $\mathcal{G}$ be the graph represented in Figure 4.5. There is a non-trivial way to label the edges of $\mathcal{G}$ with morphisms in $\mathcal{S}^*$ such that for any minimal subshift $(X, T)$ satisfying $1 \le p_X(n+1) - p_X(n) \le 2$ for all $n$, there is an infinite path $p$ in $\mathcal{G}$ whose label $(\sigma_n)_{n \in \mathbb{N}} \in \mathcal{S}^\mathbb{N}$ is a directive word of $(X, T)$. Furthermore, $(\sigma_n)_{n \in \mathbb{N}}$ is weakly primitive and admits a contraction that contains only proper morphisms.

This result is based on a detailed description of all possible Rauzy graphs of minimal subshifts with the considered complexity. The Rauzy graphs of such subshifts can have only 10 different shapes. These shapes correspond to vertices of $\mathcal{G}$. The edges of $\mathcal{G}$ are given by the possible evolutions of these graphs and are labelled by morphisms coding these evolutions (see Section 3.2.1). The theorem is obtained by showing that these labels belong to $\mathcal{S}^*$. In the next section, we will study even more the evolutions of Rauzy graphs in order to obtain an $\mathcal{S}$-adic characterization of the considered subshifts.

From now on, $(X, T)$ satisfies the conditions of Theorem 4.1, i.e., it is minimal and is such that $1 \le p_X(n+1) - p_X(n) \le 2$ for all $n$. Consequently, we have $p_X(n) \le 2n$ for all $n \ge 1$ when $\text{Card}(A) = 2$ and $p_X(n) \le 2n+1$ for all $n$ when $\text{Card}(A) = 3$.

We also consider notation introduced in Definition 3.8 and Remark 3.9, i.e., for every $n$, the morphism $\gamma_n$ describes the evolution from $G_n$ to $G_{n+1}$ and $(i_n)_{n \in \mathbb{N}}$ is the sequence of integers such that there is a bispecial factor in $\text{Fac}_k(X)$ if and only if $k \in \{i_n \mid n \in \mathbb{N}\}$.

## 4.1 10 shapes of Rauzy graphs

In this section we describe the possible shapes of Rauzy graphs for the considered class of complexity.

From Equation (1) (page 236) the hypothesis on the complexity implies that for all integers $n$, either there is one right special factor $u$ of length $n$ with $\delta^+(u) \in \{2, 3\}$ or there are two right special factors $v_1$ and $v_2$ with $\delta^+(v_1) = \delta^+(v_2) = 2$. From Equation (2) we can make a similar observation for left special factors. Hence for all integers $n$, we have the following possibilities:

1. there is one right special factor $r$ and one left special factor $l$ of length $n$ with $\delta^+(r) = \delta^-(l) \in \{2, 3\}$ (Figure 4.1);

2. there is one right special factor $r$ and two left special factors $l_1$ and $l_2$ of length $n$ with $\delta^+(r) = 3$ and $\delta^-(l_1) = \delta^-(l_2) = 2$ (Figure 4.2.1);

3. there are two right special factors $r_1$ and $r_2$ and one left special factor $l$ of length $n$ with $\delta^+(r_1) = \delta^+(r_2) = 2$ and $\delta^-(l) = 3$ (Figure 4.2.2);

4. there are two right special factors $r_1$ and $r_2$ and two left special factors $l_1$ and $l_2$ of length $n$ with $\delta^+(r_1) = \delta^+(r_2) = \delta^-(l_1) = \delta^-(l_2) = 2$ (Figure 4.3).

From these possibilities we can deduce that for all $n$, $g_n(X)$ only has eight possible shapes: those represented from Figure 4.1 to Figure 4.3. Reduced Rauzy graphs in Figure 4.1 are well-known: they correspond to reduced Rauzy graphs of Sturmian subshifts (Figure 4.1.1) or of Arnoux-Rauzy subshifts (Figure 4.1.2). Reduced Rauzy graphs in Figure 4.3 have also been studied by Rote [Rot94]. Observe that in these figures, the edges represented by dots may have length 0. In this case, the two vertices they link are merged to one bispecial vertex.

From Remark 3.9, it is enough to consider Rauzy graphs of order $i_n$, $n \in \mathbb{N}$. To this aim, we have to merge the vertices that are linked by dots in Figure 4.1 to Figure 4.3. Observe that both Figure 4.3.1 and Figure 4.3.2 give rise to two different graphs: one with one bispecial vertex and one right special vertex
<figure><img src="image_9.png" /><figcaption>Figure 4.1: Reduced Rauzy graphs with one left special factor and one right special factor.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 4.2: Reduced Rauzy graphs with different numbers of left and right special factors.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 4.3: Reduced Rauzy graphs with two left and two right special factors.</figcaption></figure>
and one with two bispecial vertices. This gives rise to 10 different types of graphs. They are represented in Figure 4.4.

**Remark 4.2** In the sequel, we sometimes talk about the type of a reduced Rauzy graph $g_k$ with $k \notin \{i_n | n \in \mathbb{N}\}$. In that case, the type of that graph is simply the type of $g_{\min\{i_n | i_n \ge k\}}$. This makes no confusions since if $R$ is a right special vertex in a Rauzy graph, the circuits starting from it have the same right labels (and full labels) of those starting from the smallest bispecial vertex (in a Rauzy graph of larger order) containing $R$ as a suffix. We also sometimes talk about the type of a Rauzy graph (and not reduced Rauzy graph). This simply corresponds to the type of the corresponding reduced Rauzy graph.

### 4.1.1 Graph of graphs

Now that we have defined all types of graphs, we can check which evolutions are available, i.e., which type of graphs can evolve to which type of graphs. It is clear that a given Rauzy graph cannot evolve to any type of Rauzy graphs. For example, if $G_n$ is a graph of type 4, both right special vertices can be extended by only two letters. Since for any word $u$ and for any suffix $v$ of $u$, we have $\delta^+(v) \ge \delta^+(u)$, the graph $G_n$ will never evolve to a graph of type 2 or 3. Section 3.2.1 shows that a graph of type 1 can evolve to graphs of type 1, 7 or 8.

By computing all available evolutions, we can define the graph of graphs as the directed graph with 10 vertices (one for each type of Rauzy graph) such that there is an edge from $i$ to $j$ if a Rauzy graph of type $i$ can evolve to a Rauzy graph of type $j$. This edge will be labeled by morphisms coding the evolution of Rauzy graphs. The graph of graphs is represented in Figure 4.5. A detailed computation of evolutions is available [Ler13, Appendix A].

## 4.2 A critical result

Now that we know all possible Rauzy graphs we have to deal with, we can define the bijections $\theta_n$ of Definition 3.8. A first necessary condition to need only a finite set of morphisms is that the alphabets $A_n$ have bounded cardinality. In this section we prove that when the first difference of complexity is bounded by 2, they always contain 2 or 3 letters. This result seems to be inherent to that class of complexity [DLR13]. We need two technical lemmas to simplify the proof that $\text{Card}(A_n) \in \{2, 3\}$ for all $n$.

**Lemma 4.3** Let $A$ be an alphabet. If $(X, T)$ is a minimal subshift over $A$ satisfying $p(n+1) - p(n) \le 2$ for all $n$ and if $B$ is a strong bispecial factor of $X$, then any right special factor of length $\ell > |B|$ admits $B$ as a suffix.

**Proof:** Indeed, $B$ being supposed to be strong bispecial, its bilateral order $m(B)$ is positive. Observe that, by definition, $m(B) > 0$ is equivalent to the inequality

$$ \sum_{aB \in \text{Fac}(X)} (\delta^+(aB) - 1) > \delta^+(B) - 1, $$

which is true only if there are at least two letters $a$ and $b$ in $A$ such that $aB$ and $bB$ are right special (since $\delta^+(aB) \le \delta^+(B)$). As there can exist at most 2 right special factors of each length (because $p(n+1) - p(n) \le 2$) and as any suffix of a right special factor is still a right special factor, the result holds. □

The following result is a direct consequence of Lemma 4.3.
<figure><img src="image_12.png" /><figcaption>Figure 4.4: Reduced Rauzy graphs with at least one bispecial vertex.</figcaption></figure>
An S-adic characterization of minimal subshifts with $1 \le p(n+1) - p(n) \le 2$

<figure><img src="image_13.png" /><figcaption>Figure 4.5: Graph of graphs.</figcaption></figure>
**Corollary 4.4** Let $(X, T)$ be a minimal subshift satisfying $1 \le p(n+1) - p(n) \le 2$ for all $n$ and let $(U_n)_{n \in \mathbb{N}}$ be a sequence of right special factors of $X$ fulfilling the conditions of Lemma 3.7. For any strong bispecial factor $B$ of length $n$ of $X$, we have $B = U_n$. In particular, if there are infinitely many strong bispecial factors in $\mathrm{Fac}(X)$, the sequence $(U_n)_{n \in \mathbb{N}}$ of Lemma 3.7 is unique.

**Lemma 4.5** Let $G_n$ be a Rauzy graph. If there is a right special vertex $R$ in $G_n$ with $\delta^+(R) = 2$, an $n$-circuit $q$ starting from $R$, two paths $p$ and $s$ in $G_n$ and two integers $k_1$ and $k_2$, $k_1 < k_2 - 1$, such that

1. $i(p) = o(s) = R$;

2. $p$ is not a suffix of $q$;

3. $q$ is not a suffix of $p$;

4. the first edge of $s$ is not the first edge of $q$;

5. both paths $pq^{k_1}s$ and $pq^{k_2}s$ are allowed;

then there is a strong bispecial factor $B$ that admits $R$ as a suffix.

**Proof:** Since $i(p) = o(q) = R$ but $p$ and $q$ are not suffix of each other, there is a left special vertex $L$ in $G_n$ and two edges $e_1$ in $p$ and $e_2$ in $q$ such that $p$ and $q$ agree on a path $q'$ from $L$ to $R$ and $i(e_1) = i(e_2) = L$. Let $\alpha$ and $\beta$ be the respective left labels of $e_1$ and $e_2$. Let also $a$ and $b$ respectively denote the right labels of the first edge of $q$ and of $s$. By hypothesis we have $a \neq b$.

Now let us prove that the word $\lambda(q'q^{k_1})$ is strong bispecial. As the paths $pq^{k_1}s$ and $pq^{k_2}s$ are allowed, the four words $\alpha\lambda(q'q^{k_1})a$, $\alpha\lambda(q'q^{k_1})b$, $\beta\lambda(q'q^{k_1})a$ and $\beta\lambda(q'q^{k_1})b$ belong to $\mathrm{Fac}(X)$. Consequently we have

$$ \delta^+(\alpha\lambda(q'q^{k_1})) + \delta^+(\beta\lambda(q'q^{k_1})) = 4. $$

Moreover, as the word $\lambda(q'q^{k_1})$ admits $R$ as a suffix, we have $\delta^+(\lambda(q'q^{k_1})) \le \delta^+(R) = 2$ which implies that $m(\lambda(q'q^{k_1})) > 0$. $\square$

**Proposition 4.6** Let $(X, T)$ be a minimal subshift satisfying $1 \le p(n+1) - p(n) \le 2$ for all $n$ and let $(U_n)_{n \ge N}$ be a sequence of right special factors fulfilling the conditions of Lemma 3.7. Then for all right special factors $U_n$, there are at most 3 allowed $n$-circuits starting from $U_n$.

**Proof:** Suppose that there exist 4 allowed $n$-circuits starting from the vertex $U_n$ in the graph $G_n(X)$ and let us have a look at all possible reduced Rauzy graphs in Figure 4.1 to Figure 4.3. We see that this is possible only if there exist two right special factors of length $n$. More precisely, this is only possible if $U_n$ corresponds to the leftmost right special vertex in Figures 4.2.2, 4.3.3 and 4.3.4 or to any right special vertex in Figures 4.3.1 and 4.3.2 (as these two graphs present a kind of “symmetry”). We will show that for each of these graphs, the existence of 4 $n$-circuits starting from the described vertices implies that the other right special factor $R$ of length $n$ is a suffix of a strong bispecial factor $B$ of length $m \ge n$ in $\mathrm{Fac}(X)$. Then, due to Corollary 4.4, $U_m = B$ so $U_n$ is not a suffix of $U_m$ which contradicts the hypothesis.

The result clearly holds for graphs as represented in Figure 4.3.1 and it is a direct consequence of Lemma 4.5 for graphs as represented at Figure 4.3.2 (since the existence of 4 $n$-circuits implies that 3 of them goes through the loop respectively $k_1, k_2$ and $k_3$ times, $k_1 < k_2 < k_3$).
For graphs as represented in Figure 4.3.3, we have to consider several cases. To be clearer, Figure 4.6 represents the same graph with some labels. The letters $\alpha$ and $\beta$ are the left extending letters of $L_1$ in $\mathrm{Fac}(X)$ and the letters $a$ and $b$ are the right extending letters of $R_2$ in $\mathrm{Fac}(X)$. If there are three $n$-circuits starting from $R_1$, going through a same simple path from $R_1$ to $L_1$ and going through the loop $p = L_2 \to R_2 \to L_2$ respectively $k_1, k_2$, and $k_3$ times, $k_1 < k_2 < k_3$, then we can conclude using Lemma 4.5. Otherwise, for both simple paths from $R_1$ to $L_1$, there are two $n$-circuits going through it. Let $k_{\alpha,1}$ and $k_{\alpha,2}$, $k_{\alpha,1} < k_{\alpha,2}$ (resp. $k_{\beta,1}$ and $k_{\beta,2}$, $k_{\beta,1} < k_{\beta,2}$) be the number of times that the two circuits going through the edge with left label $\alpha$ (resp. $\beta$) can go through the loop $p$. If $k_{\alpha,1} < k_{\alpha,2} - 1$ or if $k_{\beta,1} < k_{\beta,2} - 1$ or if $k_{\alpha,1} \neq k_{\beta,1}$, we conclude using Lemma 4.5. Otherwise, we have $k_{\alpha,1} = k_{\beta,1}$ and $k_{\alpha,2} = k_{\beta,2} = k_{\alpha,1} + 1$ and we can easily check that the full label of the path $q = L_1 (\to L_2 \to R_2)^{k_{\alpha,1}}$ is a strong bispecial factor.

<figure><img src="image_14.png" /><figcaption>Figure 4.6: Graph as in Figure 4.3.3 with some labels.</figcaption></figure>

The cases of graphs as represented at Figures 4.2.2 and 4.3.4 can be treated in a similar way. $\square$

<figure><img src="image_15.png" /></figure>

Proposition 4.6 cannot be extended to the general case. Indeed, there exist [DLR13] minimal subshifts with linear complexity and such that the number of allowed $n$-circuits to any factor of length $n$ increases with $n$.

## 4.3 A procedure to assign letters to circuits

Now let us explicitly determine the bijections $\theta_{i_n}$. We would like to define them for each graph represented at Figure 4.4 in such a way that two Rauzy graphs of same type provide the same bijection $\theta_n$. In that case, a given evolution (from $G_{i_n}$ to $G_{i_{n+1}}$) would always provide the same morphism $\gamma_{i_n}$ (which is equal to $\gamma_{i_n} \cdots \gamma_{i_{n+1}-1}$) of Definition 3.8. However, we will see that it is sometimes impossible to give enough details about $\theta_{i_n}$ so that the morphisms are sometimes defined up to permutations of the letters.

From Lemma 4.6 we know that $\mathrm{Card}(A_{i_n}) \in \{2, 3\}$ for all $n$ (1 is not enough since the number of $i_n$-circuits is at least $\delta^+(U_{i_n}) \ge 2$). From Definition 3.8 we then have $A_{i_n} \in \{\{0, 1\}, \{0, 1, 2\}\}$ depending on $n$.

Observe that, in the description of the bijections $\theta_{i_n}$ below, we sometimes express some restrictions on the number of times that some circuits can go through a loop in the considered type of Rauzy graph. The reason for this is that if the circuits do not satisfy those restrictions, the right special factor that is not $U_{i_n}$ is a suffix of a strong bispecial factor (by Lemma 4.5) which contradicts Corollary 4.4.

If $G_n$ is a Rauzy graph, then an $n$-segment is a path that starts in a right special vertex and ends in a right special vertex and that does not go through any other right special vertex.

1. **Type 1:** there exists only one right special vertex and the two possible circuits are the two loops.
One is $\theta_{i_n}(0)$ and the other is $\theta_{i_n}(1)$ and we cannot be more precise (like we are for graphs of type 2 or 3 below).

2. **Type 2 and 3:** also here there exists only one right special vertex and the three possible circuits are the three possible loops $\theta_{i_n}(0)$, $\theta_{i_n}(1)$ and $\theta_{i_n}(2)$. However, as shown by Figure 4.5, the only graphs that can evolve to a graph of type 2 (resp. of type 3) are the graphs of type 2 (resp. of type 2 and 3). Moreover after such an evolution, the right labels of the three loops start with the same letter as before the evolution. Consequently we suppose that for all $i \in \{0, 1, 2\}$, $i$ is prefix of $\lambda_R \circ \theta_{i_n}(i)$.

3. **Type 4:** first consider $U_{i_n} = R$. There exist two segments from $R$ to $B$. Consequently, there exist at least two circuits $\theta_{i_n}(0)$ and $\theta_{i_n}(1)$, each of them going through one of the two segments and looping respectively $k$ and $\ell$ times, $k+\ell \ge 1$, in the loop $B \to B$ before coming back to $R$. If there exists a third circuit, then we suppose it starts with the same segment as the circuit $\theta_{i_n}(0)$ does, and then goes through the loop exactly $k-1$ times. In this case, we must have $\ell \le k$. If the third circuit does not exist, then we suppose that $k \ge \ell$ so we have $k \ge \ell \ge 0$ and $k+\ell \ge 1$.

Now consider $U_{i_n} = B$. There exist exactly three circuits: the circuit that does not go through the vertex $R$ is denoted by $\theta_{i_n}(0)$ and the two others, $\theta_{i_n}(1)$ and $\theta_{i_n}(2)$, are going to the vertex $R$ and then are coming back to $B$ with one of the two segments from $R$ to $B$.

4. **Type 5 and 6:** as a consequence of Remark 4.2, the circuits are the same whatever the type of graphs is. Moreover, from the symmetry of these graphs, it is useless to make a distinction between the two right special vertices. Suppose $U_{i_n} = R$ for a graph of type 5. There exist four possible circuits (but Proposition 4.6 implies that only three among them are allowed) and we only impose some restrictions on their labels: the circuits $\theta_{i_n}(0)$ and $\theta_{i_n}(1)$ must go through two different segments from $R$ to $B$ and through two different segments from $B$ to $R$. If the third circuit $\theta_{i_n}(2)$ exists, then it goes through the same segment from $R$ to $B$ as $\theta_{i_n}(0)$ does and through the same segment from $B$ to $R$ as $\theta_{i_n}(1)$ does.

5. **Type 7 and 8:** like for graphs of type 5 or 6, the starting vertex and the type of the graph does not change anything to the definition of the circuits. Suppose $U_{i_n} = R$ for a graph of type 7. We consider that $\theta_{i_n}(0)$ is the circuit that does not go through the vertex $B$. The circuit $\theta_{i_n}(1)$ goes to $B$, then goes through the loop $B \to B$ $k$ times, $k \ge 1$, and eventually comes back to $R$. The circuit $\theta_{i_n}(2)$, if it exists, is the same as $\theta_{i_n}(1)$ but goes $k-1$ times through the loop $B \to B$ instead of $k$ times.

6. **Type 9:** suppose $U_{i_n} = R$. Like for graphs of type 4, we consider the two circuits $\theta_{i_n}(0)$ and $\theta_{i_n}(1)$, each of them going through different segments from $R$ to $B$ and looping respectively $k$ and $\ell$ times in the loop $B \to B$, $k+\ell \ge 1$, before coming back to $R$. However for these graphs, $k$ and $\ell$ must satisfy $|k-\ell| \le 1$ otherwise the vertex $B$ would become strong bispecial (see Lemma 4.5). Moreover, if the third circuit $\theta_{i_n}(2)$ exists, we suppose it starts like $\theta_{i_n}(0)$ does and goes through the loop exactly $k-1$ times. In this case, the circuit $\theta_{i_n}(1)$ cannot go through the loop $k+1$ times otherwise $B$ would again become strong bispecial. Hence we always suppose $k \ge \ell$. Consequently, $\ell$ can only take the values $k-1$ and $k$ even if the circuit $\theta_{i_n}(2)$ does not exist.

Now suppose $U_{i_n} = B$. There exist exactly three circuits: the circuit that does not go through the vertex $R$ is $\theta_{i_n}(0)$ and the two other circuits, $\theta_{i_n}(1)$ and $\theta_{i_n}(2)$, are going to the vertex $R$ and then are coming back to $B$ with one of the two segments from $R$ to $B$.
7. **Type 10:** suppose $U_{i_n} = R$. Let $x$ denote the segment from $R$ to $B$ that goes only through non-left-special vertices; $y$ is the other segment from $R$ to $B$. We consider that $\theta_{i_n}(0)$ (resp. $\theta_{i_n}(1)$) is the circuit that starts with $y$ (resp. with $x$), goes $k$ times (resp. $\ell$ times) through the loop $B \to B$, $k+\ell \ge 1$, and then comes back to $R$. If the third circuit $\theta_{i_n}(2)$ exists, then it starts with $x$ or $y$ and loops respectively $k-1$ or $\ell-1$ times before coming back to $R$. Moreover, if $\theta_{i_n}(2)$ starts with $x$, then we must have $k \le \ell-1$ and if $\theta_{i_n}(2)$ starts with $y$, then we must have $\ell \le k$ (because of Lemma 4.5).

Now suppose $U_{i_n} = B$. There are exactly three circuits. The loop $B \to B$ is $\theta_{i_n}(0)$, the circuit going through the segment $y$ is $\theta_{i_n}(1)$ and the circuit going through $x$ is $\theta_{i_n}(2)$.

## 4.4 Computation of the morphisms $\gamma_n$

Now that we know the bijections $\theta_{i_n}$, we can compute the morphisms $\gamma_{i_n}$ of Definition 3.8 (knowing $\gamma_{i_n}$ is enough since we have supposed that for all $k \notin \{i_n \mid n \in \mathbb{N}\}, \gamma_k = id$). As announced at the beginning of the section, we only present the method on the example of Section 3.2.1. The entire list of morphisms is available [Ler13, Appendix A] and can be computed in the same way so it is left to the reader. However, not all morphisms in that list will be needed to get the S-adic characterization of Section 5. At each step, we will provide the concerned morphisms.

Suppose $G_{i_n}$ is a graph of type 1 as in Figure 3.3 (on page 241). By definition of $\theta_{i_n}$ for this type of graphs, $\theta_{i_n}(0)$ and $\theta_{i_n}(1)$ are the two loops of the graph. Suppose that $\theta_{i_n}$ maps 0 to the $i_n$-circuit starting with the letter $a$ and 1 to the $i_n$-circuit starting with the letter $b$. For the first two evolutions (Figure 3.4.1 and 3.4.2), $G_{i_{n+1}}$ is again of type 1. By definition of $\theta_{i_{n+1}}$ for this type of graphs, we therefore have two possibilities for each evolution. Indeed, in Figure 3.4.1 we have either

$$ (\psi_{i_n} \circ \theta_{i_{n+1}}(0), \psi_{i_n} \circ \theta_{i_{n+1}}(1)) = (\theta_{i_n}(0), \theta_{i_n}(10)) $$

or

$$ (\psi_{i_n} \circ \theta_{i_{n+1}}(0), \psi_{i_n} \circ \theta_{i_{n+1}}(1)) = (\theta_{i_n}(10), \theta_{i_n}(0)) $$

and in Figure 3.4.2 we have either

$$ (\psi_{i_n} \circ \theta_{i_{n+1}}(0), \psi_{i_n} \circ \theta_{i_{n+1}}(1)) = (\theta_{i_n}(01), \theta_{i_n}(1)) $$

or

$$ (\psi_{i_n} \circ \theta_{i_{n+1}}(0), \psi_{i_n} \circ \theta_{i_{n+1}}(1)) = (\theta_{i_n}(1), \theta_{i_n}(01)) $$

The four morphisms labelling the edge from 1 to 1 in the graph of graphs are therefore

$$ \left\{ \begin{array}{l} 0 \mapsto 0 \\ 1 \mapsto 10 \end{array} \quad \begin{array}{l} 0 \mapsto 10 \\ 1 \mapsto 0 \end{array} \right. \qquad (8) \\ \left\{ \begin{array}{l} 0 \mapsto 01 \\ 1 \mapsto 1 \end{array} \quad \begin{array}{l} 0 \mapsto 1 \\ 1 \mapsto 01 \end{array} \right. $$

For the third evolution (Figure 3.4.3), the bijection $\theta_{i_{n+1}}$ (hence $\theta_{i_{n+1}}$) depends on $U_{i_{n+1}}$. If $U_{i_{n+1}} = \alpha B$ we have

$$ (\psi_{i_n} \theta_{i_{n+1}}(0), \psi_{i_n} \theta_{i_{n+1}}(1), \psi_{i_n} \theta_{i_{n+1}}(2)) = (\theta_{i_n}(0), \theta_{i_n}(1^k 0), \theta_{i_n}(1^{k-1} 0)) $$
for an integer $k \ge 2$ (remember that the circuit $\theta_{i_n+1}(2)$ might not exist). Similarly, if $U_{i_n+1} = \beta B$ we have

$$ (\psi_{i_n} \theta_{i_n+1}(0), \psi_{i_n} \theta_{i_n+1}(1), \psi_{i_n} \theta_{i_n+1}(2)) = (\theta_{i_n}(1), \theta_{i_n}(0^k 1), \theta_{i_n}(0^{k-1} 1)) $$

for an integer $k \ge 2$. Consequently, there are infinitely many morphisms labelling the edges from 1 to 7 and from 1 to 8 (one for each $k \ge 2$) but they all have one of the following two shapes:

$$ \left\{ \begin{array}{l} 0 \to 0 \\ 1 \to 1^k 0 \\ 2 \to 1^{k-1} 0 \end{array} \right. \quad \text{and} \quad \left\{ \begin{array}{l} 0 \to 1 \\ 1 \to 0^k 1 \\ 2 \to 0^{k-1} 1 \end{array} \right. . \qquad (9) $$

## 4.5 Sketch of proof of Theorem 4.1

Let us briefly recall the way the proof can be obtained. Section 4.1 describes how to build the graph of graphs $G$ (Figure 4.5). Then, Section 4.2 states that the morphisms $\gamma_{i_n}$ of Definition 3.8 are defined over alphabets of 2 of 3 letters. Section 4.3 and Section 4.4 explicitly compute the morphisms.

Due to Lemma 3.13, Lemma 3.14, Fact 3.15 and Lemma 3.16, the sequence $(\gamma_{i_n})_{n \in \mathbb{N}}$ can be slightly modified into a weakly primitive and proper directive word of $(X, T)$ (by contracting it and considering some left conjugates of the obtained morphisms). Therefore, what remains to show is that the morphisms $\gamma_{i_n}$ are compositions of morphisms in $S$ as well as the left conjugates of the contracted morphisms.

Let us keep on considering the example of Section 3.2.1. The morphisms in Equation (8) clearly belong to $S^*$ as well as their respective left conjugates. Those in Equation (9) and their respective left conjugates also admit a decomposition: we define the morphisms of $S^*$

$$ D_{12} : \left\{ \begin{array}{l} 0 \to 0 \\ 1 \to 12 \\ 2 \to 2 \end{array} \right. \quad D_{20} : \left\{ \begin{array}{l} 0 \to 0 \\ 1 \to 1 \\ 2 \to 20 \end{array} \right. \quad G_{21} : \left\{ \begin{array}{l} 0 \to 0 \\ 1 \to 1 \\ 2 \to 12 \end{array} \right. $$

and obtain

$$ MG_{21}^{k-2} D_{20} D_{12} = \left\{ \begin{array}{l} 0 \to 0 \\ 1 \to 1^k 0 \\ 2 \to 1^{k-1} 0 \end{array} \right. \quad E_{01} MG_{21}^{k-2} D_{20} D_{12} = \left\{ \begin{array}{l} 0 \to 1 \\ 1 \to 0^k 1 \\ 2 \to 0^{k-1} 1 \end{array} \right. . $$

For the left conjugates, we simply have to replace $D_{12}$ and $D_{20}$ respectively by

$$ G_{12} : \left\{ \begin{array}{l} 0 \to 0 \\ 1 \to 21 \\ 2 \to 2 \end{array} \right. \quad \text{and} \quad G_{20} : \left\{ \begin{array}{l} 0 \to 0 \\ 1 \to 1 \\ 2 \to 02 \end{array} \right. . $$

On that example, we see that the result holds, i.e., both $\gamma_{i_n}$ and $\gamma_{i_n}^{(L)}$ belong to $S^*$. It is actually always true that $\gamma_{i_n}$ belongs to $S^*$. But, not all morphisms $\gamma_{i_n}$ are right proper, making $\gamma_{i_n}^{(L)}$ undefined. However, one can always find a composition $\Gamma = \gamma_{i_n} \cdots \gamma_{i_{n+m}}$ such that $\Gamma$ is right proper and $\Gamma^{(L)}$ belongs to $S^*$. This will be explained with more details in Theorem 5.25.
**Remark 4.7** In what follows we will consider finite or infinite paths in $\mathcal{G}$ and we will deal with their labels. However, as we have observed in Section 4.4, a given edge in $\mathcal{G}$ may be labeled not by a morphism but by a (possibly infinite) set of morphisms. When talking about the label of a path $p$ in $\mathcal{G}$, we understand a sequence of morphisms $(\gamma_n)_{n \in \mathbb{N}}$ such that for all $n$, $\gamma_n$ belongs to the set of labels of the $(n+1)$th edge of $p$.

**Remark 4.8** Observe that the number of morphisms labelling an edge is not only due to a lack of precision in the definition of the bijections $\theta_{i_n}$ but also to the number of possibilities that exist for a given Rauzy graph to evolve to a given type of Rauzy graph. For example, consider a graph of type 8 as in Figure 4.7.

<figure><img src="image_16.png" /><figcaption>Figure 4.7: Rauzy graph of type 8 with some labels.</figcaption></figure>

This graph can evolve to a graph of type 7 or 8 (depending on the length of some paths) in two different ways:

- either one of the bispecial factors $B_1$ and $B_2$ is a strong bispecial factor and the other one is a weak bispecial factor;

- or both of them are neutral bispecial factors and the two new right special factors are $\alpha B_1$ and $\delta B_2$.

For the other cases, either they make the subshift leave the considered class of complexity (two weak bispecial factors or two strong bispecial factor are not compatible with $1 \le p(n+1) - p(n) \le 2$), or, the Rauzy graph evolve to a Rauzy graph not of type 7 or 8.

The Rauzy graphs obtained in both available cases are represented at Figure 4.8. They are of type 7 or 8 depending on the respective length of the paths $B_1b \to \alpha B_1$ and $B_1a \to \beta B_1$ for Figure 4.8.1 and on the respective length of the paths $B_1b \to \alpha B_1$ and $B_2c \to \delta B_2$ for Figure 4.8.2. These two possibilities of evolution to a same type of graphs imply that the edges $8 \to 7$ and $8 \to 8$ in $\mathcal{G}$ are labelled by several morphisms.

# 5 S-adic characterization

Theorem 4.1 states that any minimal and aperiodic subshift $(X, T)$ with first difference of complexity bounded by two admits a directive word $(\sigma_n)_{n \in \mathbb{N}} \in S^\mathbb{N}$ which is linked to a path in $\mathcal{G}$. However, the converse is false (see Section 5.1). A possible way to get an S-adic characterization of the considered subshifts would be to describe exactly all infinite paths in $\mathcal{G}$ that really correspond to the sequences of evolutions of Rauzy graphs of such subshifts. By achieving this, we would determine the condition $C$ of the S-adic conjecture for this particular case. This is the aim of this section and this will lead to Theorem 5.25.
<figure><img src="image_17.png" /><figcaption>Figure 4.8: Evolutions from 8 to 7 or 8.</figcaption></figure>
In the sequel, to alleviate notations we let $[u, v, w]$ denote the morphism

$$ \begin{cases} 0 \mapsto u \\ 1 \mapsto v \\ 2 \mapsto w \end{cases} $$

and when some letters are not completely determined (that is if some circuits can play the same role), we use the letters $x, y$ and $z$.

For example, the morphisms in Equation (9) will be denoted by $[x, y^{k_1}x, y^{k_1-1}x]$ and it is understood that $\{x, y\} = \{0, 1\}$. Observe that $x$ and $y$ depend on the type of graphs we come from. Indeed, when coding the evolution of a graph of type 1, we cannot have $\{x, y\} = \{0, 2\}$ by definition of $\theta_{i_n}$ for such graphs. Moreover, if for example the letters 0, $x$ and $y$ occur in an image, it is understood that 0, $x$, and $y$ are pairwise distinct.

We also need to introduce the following notation. For $x, y \in \{0, 1, 2\}, x \neq y$, the morphisms $D_{x,y}$ and $E_{x,y}$ are respectively defined by

$$ D_{x,y} : \begin{cases} x \mapsto xy \\ y \mapsto y \\ z \mapsto z \end{cases} $$

and

$$ E_{x,y} : \begin{cases} x \mapsto y \\ y \mapsto x \\ z \mapsto z \end{cases} $$

## 5.1 Valid paths

The first step to get the S-adic characterization is to understand how we can describe the “good labelled paths” in $\mathcal{G}$, hence the good sequences of evolutions. To this aim, we introduce the notions of valid directive word and of valid path.

**Definition 5.1** An infinite and labelled path $p$ in $\mathcal{G}$ is valid if there is a minimal subshift with first difference of complexity bounded by 2 for which the sequence $(\gamma_{i_n})_{n \in \mathbb{N}}$ of Definition 3.8 (and Remark 3.9) labels $p$.

We extend the notion of validity to prefix and suffixes of $p$, i.e., a path is a valid prefix (resp. valid suffix) if it is a prefix (resp. suffix) of a valid path. We also extend it to sequences of morphisms in $S^*$, i.e., a sequence of morphisms is valid if it is the label of a valid path (or valid prefix or valid suffix).

There exist several reasons for which a given labelled path in $\mathcal{G}$ is not valid: two conditions (due to Theorem 4.1) are that its label has to be weakly primitive and must admit a contraction that contains only right$^{(iv)}$ proper morphisms. Example 5.2 and Example 5.3 below show two sequences of evolutions which are forbidden because their respective directive words do not satisfy the weak primitiveness.

**Example 5.2** Sturmian subshifts have Rauzy graphs of type 1 for all $n$. Thus, for all $n$, $\gamma_{i_n}$ is one of the morphisms given in Equation (8). However if, for instance, we consider that for all $n$, the morphism $\gamma_{i_n}$ is $[0, 10]$, the directive word is not weakly primitive and the sequence of Rauzy graphs $(G_{i_n})_{n \in \mathbb{N}}$ is such that for all $n$, $i_n = n$ and $\lambda_R(\theta_n(0)) = 0$ and $\lambda_R(\theta_n(1)) = 10^n$ (the reduced Rauzy graph $g_n$ is represented in Figure 5.1). It actually corresponds to the subshift generated by the sequence $w = \cdots 000.1000\cdots$ which has complexity $p(n) = n+1$ for all $n$ but which is not minimal.

<footnote>(iv) In the definition of valid directive word, we did not consider left conjugates of morphisms so the property of being proper becomes being right proper.</footnote>
<figure><img src="image_18.png" /><figcaption>Figure 5.1: Reduced Rauzy graph $g_n$ of ... 000.1000 ...</figcaption></figure>

**Example 5.3** Let us consider a path in $G$ that ultimately stays in the vertex 9. Figure 5.2 represents the only way for a Rauzy graph $G_{i_n}$ of type 9 to evolve to a Rauzy graph of type 9. We can see that in this evolution, the $i_n$-circuit $\theta_{i_n}(0)$ starting from the vertex B (i.e., the loop that does not go through the vertex R) "stays unchanged" in $G_{i_n+1}$, i.e., $\psi_{i_n}(\theta_{i_n+1}(0)) = \theta_{i_n}(0)$. Consequently, we have $\lim_{n \to +\infty} |\theta_{i_n}(0)| < +\infty$: a contradiction with Lemma 3.5 (the circuit is trivially allowed). One can also check that for all morphisms $\gamma_{i_n}$ coding such an evolution, we have $\gamma_{i_n}(0) = 0$. As there is no other evolution from a Rauzy graph of type 9 to a Rauzy graph of type 9, the directive word cannot be weakly primitive.

<figure><img src="image_19.png" /><figcaption>5.2.1 Before evolution</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>5.2.2 After evolution</figcaption></figure>

Figure 5.2: Evolution of a graph of type 9 to a graph of type 9.

The two previously given conditions (being weak primitive and proper) are not sufficient to be a valid
directive word: there is also a "local condition" that has to be satisfied. Indeed, Example 5.4 below shows
that for some prefixes $\gamma_{i_0} \cdots \gamma_{i_k}$ labelling a finite path $p$ in $G$, not every edge starting from $i(p)$ is allowed.

**Example 5.4** Consider a graph $G_{i_n}$ of type 1 that evolves to a graph as in Figure 3.4.3 (Page 242), hence to a graph of type 7 or 8. We write $R_1 = \alpha B$ and $R_2 = \beta B$ and suppose that $U_{i_n+1} = R_1$. The morphism coding this evolution is $[x, y^k x, y^{k-1} x]$ for some integer $k \ge 2$. If we suppose $k \ge 3$, this means that the circuits $\theta_{i_n+1}(1)$ and $\theta_{i_n+1}(2)$ respectively go through $k-1$ and $k-2$ times in the loop $R_2 \to R_2$. By construction of the Rauzy graphs, this means that the shortest bispecial factor $B'$ admitting $R_2$ as a suffix is a neutral bispecial factor. Let $m > n$ be an integer such that $B'$ is a bispecial vertex in $G_{i_m}$. Since $B'$ is neutral bispecial, there is a right special factor $R'$ of length $i_m + 1$ that admits $B'$ as a suffix. Moreover, since $U_{i_m}$ is not $B'$ (as $R_1$ has to be a suffix of $U_{i_m}$), the right special factor $U_{i_m+1}$ is not $R'$. Consequently there are two right special factors in $G_{i_m+1}$ so $G_{i_m+1}$ is not of type 1.
To be a valid labelled path in $\mathcal{G}$ the three previous examples show that a given path $p$ must necessary satisfy at least two conditions: a local one about its prefixes (Example 5.4) and a global one about weak primitiveness (Example 5.2 and Example 5.4). The next result states that the converse is true.

**Proposition 5.5** An infinite and labelled path $p$ in $\mathcal{G}$ is valid if and only if both following conditions are satisfied.

1. All prefixes of $p$ are valid(v);

2. its label is weakly primitive and a contraction of it contains only right proper morphisms(vi).

**Proof:** The first condition is obviously necessary and the second condition comes from Theorem 4.1. For the sufficient part, if all prefixes of $p$ are valid, it implies that we can build a sequence of Rauzy graphs $(G_n)_{n \in \mathbb{N}}$ such that for all $n$, $G_n$ is as represented in Figure 4.1 to Figure 4.3 and evolves to $G_{n+1}$. To these Rauzy graphs we can associate a sequence of languages $(L(G_n))_{n \in \mathbb{N}}$ defined as the set of finite words labelling paths in $G_n$. By construction we obviously have $L(G_{n+1}) \subset L(G_n)$ and the language

$$L = \bigcap_{n \in \mathbb{N}} L(G_n)$$

is factorial(vii), prolongable(viii) and such that $1 \le p_L(n+1) - p_L(n) \le 2$ for all $n$ (where $p_L$ is the complexity function of the language). Thus, it defines a subshift $(X, T)$ whose language is $L$, which, by construction, is such that the sequence $(\gamma_{i_n})_{n \in \mathbb{N}}$ of Definition 3.8 labels $p$ and which is minimal by weak primitiveness. $\square$

## 5.2 Decomposition of the problem

Our aim is now to describe exactly the set of all valid paths in $\mathcal{G}$. The idea is to modify the graph of graphs $\mathcal{G}$ in such a way that the “local condition” to be a valid path (the first point of Proposition 5.5) is treated by the graph. In other words, we would like to modify $\mathcal{G}$ in such a way that all finite paths are valid. We also would like that for any minimal subshift with $p(n+1) - p(n) \le 2$, a contraction of $(\gamma_{i_n})_{n \in \mathbb{N}}$ that contains infinitely many right proper morphisms labels a path in $\mathcal{G}$ (to be able to consider left conjugates). In that case, we will only have to take care of the weak primitiveness, which is rather easy to check. But, we actually will see that modifying the graph $\mathcal{G}$ as wanted will not be possible. There will still remain some vertices $v$ such that for some finite paths arriving in $v$, some edges $e$ starting from $v$ make the path $pe$ not valid. However, we will manage to describe the local condition for these vertices so this will still provides an S-adic characterization. The computations in the next section are sometimes a little bit heavy to check. The reader can find some help (figures with evolutions of graphs, list of morphisms coding these evolutions, decomposition of them into $S^*$, etc.) in [Ler13].

The graph of graphs $\mathcal{G}$ contains 4 strongly connected components:

$$C_1 = \{1, 5, 6, 7, 8, 9, 10\}, C_2 = \{2\}, C_3 = \{3\}, C_4 = \{4\}.$$

<footnote>(v) a local condition</footnote>

<footnote>(vi) a global condition</footnote>

<footnote>(vii) For every word $u$ in $L$, $\text{Fac}(u) \subset L$.</footnote>

<footnote>(viii) For every word $u$ in $L$, there are some letters $a$ and $b$ such that $au$ and $ub$ are in $L$.</footnote>
Any infinite path in $\mathcal{G}$ ends in one component $C_i$ and is valid if and only if the prefix leading to $C_i$ is valid and if the infinite suffix staying in $C_i$ is valid and fit with the prefix. Thus, to describe all valid paths in $\mathcal{G}$, we can separately describe the valid suffixes in each component and then study how the components are linked to each other.

**Remark 5.6** By hypothesis on $p(1) - p(0)$, a valid path $p$ in $\mathcal{G}$ always starts from the vertex 1 or from the vertex 2 (depending on the size of the alphabet: 2 or 3). Therefore, when studying the validity of a path in the component $C_1$, $C_3$ or $C_4$, we only study the validity of its suffix that always stays in that component. By contrary, studying the validity of the suffix of a path ultimately staying in $C_2$ is the same as studying the validity of the entire path.

**Remark 5.7** Due to the symmetry between Rauzy graphs of type 3 and 4, one could think that the description of valid suffixes of paths ultimately staying in components $C_3$ and $C_4$ will be similar. We will actually see that this is not the case. The reason is that, as we are dealing with right labels of n-circuits, the right special vertices do not play the same role at all as the left special vertices.

## 5.3 Valid paths in $C_2$

This component corresponds to the well-known class of Arnoux-Rauzy subshifts [AR91]. The morphisms $\gamma_{i_n}$ that code an evolution in that component are right proper and are easily seen to belong to $S^*$, as well as their respective left conjugates.

$$ \forall n, \quad \gamma_{i_n} \in \{[0, 10, 20], [01, 1, 21], [02, 12, 2]\} $$

$$ \forall n, \quad \gamma_{i_n}^{(L)} \in \{[0, 01, 02], [10, 1, 12], [20, 21, 2]\} $$

Arnoux and Rauzy [AR91] gave an $S$-adic description of the so-called Arnoux-Rauzy subshifts by considering the morphisms $[0, 10, 20]$, $[01, 1, 21]$ and $[02, 12, 2]$. They proved the following result.

**Proposition 5.8 (Arnoux and Rauzy [AR91])** A labelled path $p$ in $\mathcal{G}$ is valid and corresponds to an Arnoux-Rauzy subshift if and only if it goes only through vertex 2 and the three morphisms $[0, 10, 20]$, $[01, 1, 21]$ and $[02, 12, 2]$ occur infinitely often in the label of $p$.

## 5.4 Valid paths in $C_3$

This component contains only the vertex 3 of $\mathcal{G}$ and the morphisms $\gamma_{i_n}$ that code an evolution in this component are the following

$$ [0, 10, 20], [01, 1, 21], [02, 12, 2], [0, 10, 2], [01, 1, 2], [02, 1, 2], [0, 1, 20], [0, 1, 21], [0, 12, 2]; $$

they belong to $S^*$.

Observe that not all these morphisms are right proper and we could even find an infinite sequence of them that would not admit a contraction with only right proper morphisms (for instance, $[0, 10, 2]^\omega$). The reason is that not all finite composition of these morphisms correspond to a valid finite sequence of evolution of Rauzy graphs. The next lemma describes this fact.

**Lemma 5.9** Let $(X, T)$ be a minimal and aperiodic subshift with first difference of complexity bounded by 2. Let $(\gamma_{i_n})_{n \in \mathbb{N}}$ be the directive word of Definition 3.8. Suppose that both $\gamma_{i_n}$ and $\gamma_{i_{n+1}}$ are coding an evolution from a graph of type 3 to a graph of type 3. Then if $\gamma_{i_n}$ is equal to

$$ D_{y,x}D_{z,x} \quad (\text{resp. } D_{x,y}) $$
for $\{x, y, z\} = \{0, 1, 2\}$, then $\gamma_{i_{n+1}}$ can only be one of the three following morphisms

$$D_{y,x}D_{z,x}, D_{x,y}, D_{x,z} \text{ (resp. } D_{y,z}D_{x,z}, D_{z,y}, D_{z,x})$$

**Proof:** We only have to look at the behaviour of the Rauzy graph when it evolves. Figure 5.3 shows the two possibilities for a graph of type 3 to evolve to a graph of type 3. When computing the morphisms coding these evolutions, we see that what is important to know is which letter corresponds to the top loop in Figure 5.3.1. Indeed, if $\theta_{i_n}(x)$ corresponds to the top loop in Figure 5.3.1, the three available morphisms are (the second must be counted twice since $y$ can be replaced by $z$)

$$\left\{ \begin{array}{l} x \mapsto x \\ y \mapsto yx \\ z \mapsto zx \end{array} \right. \quad \text{and} \quad \left\{ \begin{array}{l} x \mapsto xy \\ y \mapsto y \\ z \mapsto z \end{array} \right. .$$

The evolution represented in Figure 5.3.2 is coded by the first morphism and the evolution represented in Figure 5.3.3 is coded by the second one (where $\theta_{i_n}(y)$ is the leftmost loop in Figure 5.3.1).

After the first evolution, the graph becomes again a graph as in Figure 5.3.1 where the circuit $\theta_{i_{n+1}}(x)$ still corresponds to the top loop. The available morphisms are therefore the same as before the evolution.

After the second evolution, the graph becomes again a graph as in Figure 5.3.1 but the top loop is the circuit $\theta_{i_{n+1}}(z)$. The available morphisms are therefore the same as before the evolution but with $x$ and $z$ exchanged.

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /><figcaption>Figure 5.3: Evolutions of a graph of type 3 to a graph of type 3.</figcaption></figure>

<figure><img src="image_24.png" /></figure>

Thanks to the previous lemma, if $\gamma_{i_k} \gamma_{i_{k+1}} \gamma_{i_{k+2}} \cdots$ labels a valid suffix that stays in component $C_3$, then for all $n \ge k$, $\gamma_{i_n} \gamma_{i_{n+1}}$ is a right proper morphism. Consequently, we obtain the following result. We let the reader check that all involved morphisms (as well as their respective left conjugates when they exist) belongs to $S^*$.

**Proposition 5.10** An infinite path $p$ in $\mathcal{G}$ labelled by $(\gamma_{i_n})_{n \ge N}$ is a valid suffix that always stays in vertex 3 if and only if there is a contraction $(\alpha_n)_{n \ge N}$ of $(\gamma_{i_n})_{n \ge N}$ such that

1. $(\alpha_n)_{n \ge N}$ labels an infinite path in the graph represented in Figure 5.4 with
(a) for all $x \in \{0, 1, 2\}$, the loop on $V_x$ is labelled by morphisms in

$$F_x = \{D_{y,x}D_{z,x}, D_{x,y}D_{z,y} \mid \{x, y, z\} = \{0, 1, 2\}\};$$

(b) for all $x, y \in \{0, 1, 2\}$, $x \neq y$, the edge from $V_x$ to $V_y$ is labelled by morphisms in

$$F_{x \to y} = \{D_{x,z}, D_{x,y}D_{z,x} \mid z \notin \{x, y\}\};$$

2. $(\alpha_n)_{n \ge N}$ contains infinitely many right proper morphisms;

3. for all $x \in \{0, 1, 2\}$, there are infinitely many integers $n \ge N$ such that $D_{y,x}$ is a factor of $\alpha_n$ for some $y \in \{0, 1, 2\}$.

<figure><img src="image_25.png" /><figcaption>Figure 5.4: Graph corresponding to component $C_3$ in $G$.</figcaption></figure>

**Proof:** Our aim is to describe valid suffix in $G$ that stay in vertex 3, accordingly to Proposition 5.5.

Let us start with Condition 1 (i.e., the local one). The morphisms that code an evolution from a graph of type 3 to a graph of type 3 are listed at the beginning of Section 5.4. However, Lemma 5.9 shows that they cannot be composed in every way. When computing the morphisms coding the different evolutions (see Figure 5.3), we see that what is important is which letter corresponds to the top loop in Figure 5.3.1. Consequently, we can “split” the vertex 3 in $G$ into 3 vertices $V_0$, $V_1$ and $V_2$, each $V_x$ corresponding to the fact that the circuit $\theta_{i_n}(x)$ only goes through non-left special vertices (i.e., corresponds to the top loop in Figure 5.3.1) and we put some edges between these vertices if the corresponding evolution is available. Then we label the graph as follows: for all $x, y \in \{0, 1, 2\}$ such that $x \neq y$, we let $F_x$ denote the set of morphisms labelling the loop on $V_x$ and we let $F_{x \to y}$ denote the set of morphisms labelling the edge from $V_x$ to $V_y$. Of course, $F_x$ and $F_{x \to y}$ contain the morphism corresponding to the evolution, i.e., $F_x$ contains
the morphism $D_{y,x}D_{z,x}$ and $F_{x \to y}$ contains the morphism $D_{x,z}$. Defining $F_x$ and $F_{x \to y}$ this way ensures that the local condition is satisfied.

Before considering the second condition of Proposition 5.5, let us modify the sets $F_x$ and $F_{x \to y}$ accordingly to what we explained in Section 5.2, i.e., in such a way that a contraction $(\alpha_n)_{n \ge N}$ of $(\gamma_{i_n})_{n \ge N}$ contains infinitely many right proper morphisms and labels a path in Figure 5.4. As all non-right proper morphisms belong to some set $F_{x \to y}$, this can easily be done as follows: for all $x, y, z \in \{0, 1, 2\}, x \ne y, y \ne z$, one can check that the morphism $D_{x,z}D_{y,x} \in F_{x \to y}F_{y \to z}$ is right proper and labels a finite path from $V_x$ to $V_z$. Consequently, for all $x$ and all $y, z$ such that $\{x, y, z\} = \{0, 1, 2\}$ we can add in $F_x$ the morphism $D_{x,z}D_{y,z}$ and we add in $F_{x \to z}$ the morphism $D_{x,z}D_{y,x}$. By doing this, the existence of $(\alpha_n)_{n \ge N}$ is ensured.

Now let us describe all labelled paths in Figure 5.4 with weakly primitive label (Condition 2 of Proposition 5.5). The morphisms in $F_x$ and in $F_{x \to y}$, $x, y \in \{0, 1, 2\}$, are composed of morphisms $D_{u,v}$ for some $u, v \in \{0, 1, 2\}$. Let us prove that the label $(\alpha_n)_{n \ge N}$ of a path in Figure 5.4 is weakly primitive if and only if for all $x \in \{0, 1, 2\}$, there are infinitely many integers such that $D_{y,x}$ is a factor of $\alpha_n$ for some $y \in \{0, 1, 2\}, y \ne x$. The condition is trivially necessary since if for all $y, D_{y,x}$ is not a factor of $\alpha_n$ for $n$ not smaller than some integer $m \ge N$, then $x$ does not belong to $\alpha_m \cdots \alpha_{m+k}(z)$ for all $z \ne x$ and all integers $k \ge 0$. It is also sufficient. Indeed, it is clear that if, for $\{x, y, z\} = \{0, 1, 2\}$, the three morphisms $D_{x,y}, D_{y,z}$ and $D_{z,x}$ occur infinitely often as factors of $(\alpha_n)_{n \ge m}$, then the directive word is weakly primitive. Thus, to satisfy the condition without inducing the weak primitiveness, the set of morphisms that occur infinitely often as factors of $(\alpha_n)_{n \ge m}$ has to be included in $\{D_{x,y}, D_{y,z}, D_{y,x}, D_{x,z}\}$. This is in contradiction with the way the morphisms have to be composed (governed by Figure 5.4). $\square$

## 5.5 Preliminary lemmas for $C_4$ and $C_1$

In both types of graph of component $C_2$ and $C_3$, there is only one right special vertex. This makes the computation of valid paths easier to compute than when there are two right special factors. Indeed, if $R_1$ and $R_2$ are two bispecial factors in a Rauzy graph $G_{i_n}$, the circuits starting from $R_1$ impose some restrictions on the behaviour of $R_2$, i.e., on the way it will make the graph evolve when it will become bispecial (see Example 5.4 where the burst of the bispecial vertex $B'$ is governed by $\theta_{i_n}(1)$ and $\theta_{i_n}(2)$). Such a thing cannot happen for graphs of type 2 and 3, i.e., the local condition of Proposition 5.5 can be easily expressed. In this section, we introduce some notations and we give some lemmas that will be helpful to study valid paths in components $C_4$ and $C_1$.

First, let us briefly explain what we will mean when talking about the *burst* of a bispecial factor. Roughly speaking, “burst” describes the behaviour of a bispecial vertex when the Rauzy graph evolves. These vertices are of a particular interest since those are the only ones that can change the shape of a graph (hence they are the only ones that determine the morphisms $\gamma_{i_n}$ since they depend on the shape of the graphs).

Indeed, let us consider a non-special vertex $V$ in a Rauzy graph $G_{i_n}$. Since $V$ is not special, there are exactly two vertices $V_p$ and $V_s$ in $G_{i_n+1}$ such that $V$ is prefix of $V_p$ and suffix of $V_s$ and there is an edge from $V_p$ to $V_s$. Consequently, the behaviour of $V$ when $G_{i_n}$ evolves does not change the shape of $G_{i_n}$. One can make a similar observation for left (but not right) special vertices and for right (but not left) special vertices. The difference is that, for left special vertices (resp. for right special vertices), there are several vertices $V_p^{(1)}, \dots, V_p^{(k)}$ with $k = \delta^{-}V > 1$ (resp. $V_s^{(1)}, \dots, V_s^{(k)}$ with $k = \delta^{+}V > 1$) that admit $V$ as a prefix (resp. as a suffix) and for all $i, 1 \le i \le k$, there is an edge from $V_p^{(i)}$ to $V_s$ (resp. from $V_p$ to $V_s$).
$V_s^{(i)}$). Consequently, the behaviour of $V$ when $G_{i_n}$ evolves does not change the shape of $G_{i_n}$ either.

For bispecial vertices $V$, this is not true anymore. Indeed, in the graph $G_{i_n+1}$ there are several vertices $V_p^{(1)}, \dots, V_p^{(k)}$ with $k = \delta^{-}V > 1$ and several vertices $V_s^{(1)}, \dots, V_s^{(\ell)}$ with $\ell = \delta^{+}V > 1$ that respectively admit $V$ as a prefix and as a suffix. Moreover, the number of edges between $\{V_p^{(1)}, \dots, V_p^{(k)}\}$ and $\{V_s^{(1)}, \dots, V_s^{(\ell)}\}$ depends on the bilateral order of $V$. Therefore the behaviour of $V$ when $G_{i_n}$ evolves can strongly change the shape of $G_{i_n}$ (by increasing or decreasing the number of special vertices for example).

The next lemma gives a method to build a sequence $(\eta_{j_n})_{n \in \mathbb{N}}$ of morphisms which is a little bit different from $(\gamma_{i_n})_{n \in \mathbb{N}}$ and that will help us to describe the valid paths in $C_4$ and $C_1$.

**Lemma 5.11** Let $(X, T)$ be a minimal subshift with first difference of complexity satisfying $1 \le p(n + 1) - p(n) \le 2$ for all $n$ and let $(i_n)_{n \in \mathbb{N}}$ be the increasing sequence of integers such that $\text{Frac}_k(X)$ contains a bispecial factor of $X$ if and only if $k \in \{i_n \mid n \in \mathbb{N}\}$. There is a non-decreasing sequence $(j_n)_{n \in \mathbb{N}}$ of integers such that $j_n \le i_n$ for all $n$ and a sequence $(\eta_n)_{n \in \mathbb{N}}$ of morphisms in $S^*$ such that or all $n$, $\eta_n$ codes the burst of a unique bispecial factor of length $j_n$ in $G_{j_n}(X)$.

**Proof:** First it is obvious that if a Rauzy graph $G_{i_n}$ contains two bispecial vertices, making them burst at the same time or separately produces the same graph $G_{i_n+1}$ (hence $G_{i_{n+1}}$). Consequently, since $\gamma_{i_n}$ describes how a graph evolves to the next one, we can decompose it into two morphisms $\gamma_{i_n}^{(1)}$ and $\gamma_{i_n}^{(2)}$ such that $\gamma_{i_n} = \gamma_{i_n}^{(1)}\gamma_{i_n}^{(2)}$, each one describing the burst of one of the two bispecial vertices. Then it suffices to show that we can decompose $\gamma_{i_n}^{(1)}$ and $\gamma_{i_n}^{(2)}$ into morphisms of $S$. This is actually obvious. Indeed, if there are two bispecial vertices, the graph can only be of type 6 or of type 8. Then, making only one bispecial vertex burst corresponds to considering that it is actually respectively of type 5 or 7 and we know that these morphisms belong to $S^*$. However, we have to make it carefully: if $B_1$ and $B_2$ are the two bispecial vertices in $G_{i_n}$ and if, for instance, $B_1$ is strong, we have to make $B_2$ burst before $B_1$ otherwise the burst of $B_1$ would provide a graph with 3 right special vertices and this does not correspond to any type of graphs as considered in Figure 4.4. In other words, $\gamma_{i_n}^{(1)}$ has to correspond to the burst of $B_2$ and $\gamma_{i_n}^{(2)}$ has to correspond to the burst of $B_1$.

To conclude the proof, it suffices to build the sequences $(j_n)_{n \in \mathbb{N}}$ and $(\eta_n)_{n \in \mathbb{N}}$. From what precedes, the first one is simply the sequence $(i_n)_{n \in \mathbb{N}}$ but such that when $G_{i_n}$ contains two bispecial factors, then $i_n$ occurs twice in a row in $(j_n)_{n \in \mathbb{N}}$. The second one is the sequence $(\gamma_{i_n})_{n \in \mathbb{N}}$ but such that when $G_{i_n}$ contains two bispecial vertices, we split $\gamma_{i_n}$ into $\gamma_{i_n}^{(1)}$ and $\gamma_{i_n}^{(2)}$. $\square$

**Example 5.12** Let us consider a path $p$ in $\mathcal{G}$ that ultimately stays in the set of vertices $\{7, 8\}$. When the Rauzy graph $G_{i_n}$ is of type 7, there is a unique bispecial factor so the morphism $\gamma_{i_n}$ satisfies the conditions of the lemma, i.e., it corresponds to a morphism in $(\eta_m)_{m \in \mathbb{N}}$. On the other hand, when $G_{i_n}$ is of type 8, its two possible evolutions are represented at Figures 4.8.1 and 4.8.2 on page 256. Suppose that the starting vertex $U_{i_n}$ corresponds to the vertex $B_1$ in Figure 4.7 (page 255) and suppose that $G_{i_n}$ evolves as in Figure 4.8.1 with $U_{i_n+1}$ equals to $\alpha B_1$; the others cases are analogous. We have $\gamma_{i_n} = [0, 1^k, 0, (1^{k-1}0)]$. To decompose it as announced in Lemma 5.11, it suffices to consider that $G_{i_n}$ is of type 7 with $B_2$ as bispecial vertex. We make this bispecial vertex burst like it is supposed to do (i.e. like a weak bispecial factor). This makes the graph evolve to a graph $G'_{i_n}$ of type 1 (whose bispecial vertex is
$B_1$) and we consider that the morphism coding this evolution is $\eta_m = [0, 1]$. Now it suffices to make this new graph $G'_{i_n}$ evolve to a graph of type 7 or 8 with the morphism $\eta_{m+1} = [0, 1^k0, (1^{k-1}0)]$. We then have $\gamma_{i_n} = \eta_m\eta_{m+1}$ and these new morphisms satisfy the condition 2 in Lemma 5.11. They can easily be decomposed by morphisms in $S$ since $\eta_m = \text{id}$ and $\eta_{m+1} = \gamma_{i_n}$.

**Definition 5.13** Let $(j_n)_{n \in \mathbb{N}}$ and $(\eta_n)_{n \in \mathbb{N}}$ be as in Lemma 5.11. For all $n$ we let $B_{j_n}$ denote the bispecial factor of length $j_n$ whose burst is coded by $\eta_n$.

The following result directly follows from the definition of the morphisms $\eta_n$.

**Lemma 5.14** Let $(j_n)_{n \in \mathbb{N}}$ and $(\eta_n)_{n \in \mathbb{N}}$ be as in Lemma 5.11. The morphism $\eta_n$ is a letter-to-letter morphism if and only if $B_{j_n} \neq U_{j_n}$ (where $(U_n)_{n \in \mathbb{N}}$ is the sequence of starting vertices of the circuits).

**Remark 5.15** Observe that, as illustrated by Example 5.4, when $B_{j_n} \neq U_{j_n}$, the evolution of $G_{j_n}$ is influenced by the last morphism $\eta_k$, $k < n$, such that $B_{j_k} = U_{j_k}$. Indeed, as we have seen in Section 4.3, the circuits starting from $U_{j_k}$ may depend on some parameters (the number of loops they contain for instance) and there exist some restrictions to these parameters$^{(ix)}$. Actually, considering a particular morphism $\eta_k$ corresponds to determining these parameters. Since some of these circuits go through the other right special vertex in $G_{j_k}$ (if it exists), these parameters influence the behaviour of this right special vertex.

On the other hand, when $B_{j_n} = U_{j_n}$, there are no restrictions on the possibilities for $\eta_n$ since we do not have any information on the circuits starting from the right special vertex that is not $U_{j_n}$. Also, for graphs in components $C_4$ and $C_1$ there are no restrictions on the labels of the circuits like there are for Rauzy graphs of type$^{(x)}$ 2 or 3. Consequently, all possible morphisms are allowed. However, some of these morphisms are only locally allowed, i.e., even if a morphism is allowed, some "infinite choices" containing it may be forbidden. Indeed, Example 5.3 shows that a graph of type 9 can evolve to a graph of type 9 (so there is an allowed evolution) but it cannot ultimately keep being a graph of type 9 otherwise $(\gamma_{i_n})_{n \in \mathbb{N}}$ would not be everywhere growing. To be clearer, the circuits starting in the right special vertex that is not $U_{j_n}$ also depend on some parameters and, as for the circuits starting from $U_{j_n}$, there are some restrictions on them. Those parameters are partially determined by the morphism $\eta_n$. For instance let us consider the evolution of a graph of type 9 as in Figure 5.2 (Page 258) such that $U_{j_n}$ corresponds to the vertex B in Figure 5.2.1. This evolution implies that all circuits starting from the vertex R in Figure 5.2.1 go through the loop $B \to B$ at least once.

## 5.6 Valid paths in $C_4$

This component only contains the vertex 4 in $\mathcal{G}$ and this type of graphs contains two right special vertices. Moreover, these two right special vertices cannot be bispecial at the same time since there is only one left special factor of each length. Consequently, we have $j_n = i_n$ and $\eta_n = \gamma_{i_n}$ for all $n$ and, as explained in Remark 5.15, we can locally choose any morphism we want when $U_{i_n} = B_{i_n}$ and we have to be careful when $U_{i_n} \neq B_{i_n}$. In other words, when $U_{i_n}$ is the vertex R in Figure 5.5, the choice of the morphism $\gamma_{i_n}$ is restrained by the latest morphism $\gamma_{i_{m}}$, $m < n$, such that $U_{i_m}$ is the vertex B. We let the reader check that this morphism $\gamma_{i_m}$ is either

$$[0x^k y, x^\ell y, (0x^{k-1} y)] \text{ or } [x^k y, 0x^\ell y, (x^{k-1} y)]$$

<footnote>(ix) For instance, when there are two parameters $k$ and $\ell$, one of them can sometimes not be greater than the other one.</footnote>

<footnote>(x) For those graphs, the right label of $\theta_{i_n}(x)$ always starts with $x$.</footnote>
with $\{x, y\} = \{1, 2\}, k \ge 1 \text{ and } k \ge \ell \ge 0$.

<figure><img src="image_26.png" /><figcaption>Figure 5.5: Rauzy graph of type 4.</figcaption></figure>

Lemma 5.16 below expresses the consequences of this morphism $\gamma_{i_m}$.

**Lemma 5.16** Let $m \in \mathbb{N}$ and $G_{i_m}$ be a Rauzy graph of type 4.

Suppose that $U_{i_m} = R$ and that the two $i_m$-circuits $\theta_{i_m}(0)$ and $\theta_{i_m}(1)$ go through the loop $k$ and $\ell$ times respectively, with $k \ge 1$ and $k \ge \ell \ge 0$.

If the circuit $\theta_{i_m}(2)$ exists:

i. if $\ell = k$, the Rauzy graph will evolve to a graph $G_{i_n}$, $n > m$ of type 10 such that $U_{i_n}$ corresponds to the vertex $B$ in Figure 4.4.10 (page 248) and the evolution from $G_{i_m}$ to $G_{i_n}$ is coded by the morphism $[1, 0, 2]$;

ii. if $\ell = k - 1$, the Rauzy graph will evolve to a graph $G_{i_n}$, $n > m$ of type 4 such that $U_{i_n}$ corresponds to the vertex $B$ in Figure 5.5 just above and the evolution from $G_{i_m}$ to $G_{i_n}$ is coded by a morphism in $\{[1, 0, 2], [1, 2, 0]\}$;

iii. if $\ell < k - 1$, the Rauzy graph will evolve to a graph $G_{i_n}$, $n > m$ of type 7 or 8 such that $U_{i_n}$ corresponds to one of the vertices $R$ and $B$ in Figure 4.4.7 and to one of the vertices $B_1$ and $B_2$ in Figure 4.4.8. The evolution from $G_{i_m}$ to $G_{i_n}$ is coded by the morphism $[1, 0, 2]$ and the $i_n$-circuit $\theta_{i_n}(1)$ goes through the loop $k - \ell - 1$ times.

If the circuit $\theta_{i_m}(2)$ does not exist:

i. if $\ell = k$ or $\ell = k - 1$, the graph will evolve to a graph $G_{i_n}$, $n > m$ of type 1 such that $U_{i_n}$ corresponds to the vertex $B$ in Figure 4.4.1 and the evolution from $G_{i_m}$ to $G_{i_n}$ is coded by a morphism in $\{[0, 1], [1, 0]\}$;

ii. if $\ell < k - 1$, the graph will evolve to a graph $G_{i_n}$, $n > m$ of type 7 or 8 such that $U_{i_n}$ corresponds to one of the vertices $R$ and $B$ in Figure 4.4.7 and to one of the vertices $B_1$ and $B_2$ in Figure 4.4.8. The evolution from $G_{i_m}$ to $G_{i_n}$ is coded by the morphism $[1, 0]$ and the $i_n$-circuit $\theta_{i_n}(1)$ goes through the loop $k - \ell - 1$ times.

**Proof:** It suffices to see how the graph evolves. Indeed, when the vertex $B$ bursts, we have eight possibilities represented at Figure 5.6 and Figure 5.7. The main thing to notice is that if both circuits$^{(xi)}$ $\theta_{i_m}(0)$ and $\theta_{i_m}(1)$ can go through the loop $B \to B$ respectively $k$ and $\ell$ times with $k$ and $\ell$ greater than 1 (observe that in this case, the circuit $\theta_{i_m}(2)$ goes through that loop $k-1$ times), the graph will evolve as in Figure 5.6.1 and the new circuits $\theta_{i_{m+1}}(0)$ and $\theta_{i_{m+1}}(1)$ will go through the loop respectively $k-1$ and $\ell-1$ times (so $k-2$ times for $\theta_{i_{m+1}}(2)$). The computation of the morphisms is left to the reader. $\square$

Now we can determine the valid suffixes in component $C_4$. Moreover, in $\mathcal{G}$ we can rename the vertex 4 by $4B$, meaning that we always have $U_{i_n} = B$.

<footnote>(xi) The reader is invited to check the definition of $\theta_{i_m}$ for such graphs on page 252.</footnote>
<figure><img src="image_27.png" /><figcaption>Figure 5.6: Evolutions of a graph of type 4 with 3 circuits starting from $R$.</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>Figure 5.7: Evolutions of a graph of type 4 with 2 circuits starting from $R$.</figcaption></figure>
**Proposition 5.17** An infinite path $p$ in $\mathcal{G}$ labelled by $(\gamma_{i_n})_{n \ge N}$ is a valid suffix that always stays in vertex 4 and that is such that $U_{i_N}$ is bispecial if and only if there is a contraction $(\alpha_n)_{n \ge N}$ of $(\gamma_{i_n})_{n \ge N}$ such that

1. for all $n \ge N$,

$$ \alpha_n \in \{[0, 10, 20], [0, 20, 10], [x^{k-1}y, 0x^k y, 0x^{k-1}y], [x^{k-1}y, 0x^{k-1}y, 0x^k y], \\ [0x^{k-1}y, x^k y, x^{k-1}y], [0x^{k-1}y, x^{k-1}y, x^k y] \mid k \ge 1\} $$

$$ \text{with } \{x, y\} = \{1, 2\}; $$

2. for all $r \ge N$,

$$ (\alpha_n)_{n \ge r} \notin \{[0, 10, 20], [0, 20, 10]\}^{\omega} $$

and

$$ (\alpha_n)_{n \ge r} \notin \{[0x^{k-1}y, x^k y, x^{k-1}y], [0x^{k-1}y, x^{k-1}y, x^k y] \mid k \ge 1\}^{\omega} $$

**Proof:** Our aim is to describe the valid suffixes in $\mathcal{G}$ that stay in vertex 4, accordingly to Proposition 5.5.

Let us start with Condition 1. Given a graph $G_{i_n}$ of type 4 with $U_{i_n} = B$, the morphism $\gamma_{i_n}$ coding the evolution to a graph of type 4 and such that

(a) $U_{i_{n+1}} = B$ are $[0, 10, 20]$ and $[0, 20, 10]$;

(b) $U_{i_{n+1}} = R$ are $[0x^k y, x^l y, 0x^{k-1} y]$ and $[x^k y, 0x^l y, x^{k-1} y]$.

Let $(k_n)_{n \ge N}$ be the subsequence of $(i_n)_{n \ge N}$ such that $U_{i_n}$ is bispecial if and only if $i_n \in \{k_n \mid n \ge N\}$ and let $(\alpha_n)_{n \ge N}$ be the contraction of $(\gamma_{i_n})_{n \ge N}$ defined by $\alpha_n = \gamma_{k_n} \gamma_{k_{n+1}} \cdots \gamma_{k_{n+1}-1}$. Using Lemma 5.16, we obtain that $(\gamma_{i_n})_{n \ge N}$ has valid prefixes if and only if all morphisms $\alpha_n$ belong to

$$ \{[0, 10, 20], [0, 20, 10], [x^{k-1}y, 0x^k y, 0x^{k-1}y], [x^{k-1}y, 0x^{k-1}y, 0x^k y], \\ [0x^{k-1}y, x^k y, x^{k-1}y], [0x^{k-1}y, x^{k-1}y, x^k y] \mid k \ge 1\}. $$

Indeed, the exponent $k$ (resp. $\ell$) in the morphisms given above (in (b)) corresponds to the number of times the circuit $\theta_{i_{n+1}}(0)$ (resp. $\theta_{i_{n+1}}(0)$) goes through the loop $B \to B$. Consequently, we must have $\ell = k-1$.

Now let us consider Condition 2. All morphisms $\alpha_n$ are right proper so we only have to take care of the weak primitiveness and it is easily seen that $(\alpha_n)_{n \ge N}$ is weakly primitive if and only if for all $r \ge N$,

$$ (\alpha_n)_{n \ge r} \notin \{[0, 10, 20], [0, 20, 10]\}^{\omega} $$

and

$$ (\alpha_n)_{n \ge r} \notin \{[0x^{k-1}y, x^k y, x^{k-1}y], [0x^{k-1}y, x^{k-1}y, x^k y] \mid k \ge 1\}^{\omega} $$

$$ \text{with } \{x, y\} = \{1, 2\}. \quad \square $$
## 5.7 Valid paths in $C_1$

This component of $\mathcal{G}$ contains the vertices 1, 5, 6, 7, 8, 9 and 10. This component contains all subshifts with complexity $2n$ that have been studied by Rote [Rot94]. Any three-interval-exchange subshift also describes a path in $\mathcal{G}$ that eventually ends up in this component [FHZ03].

As for component $C_4$, we need some lemmas to determine the consequences of some morphisms $\gamma_{i_n}$ on the sequence $(\gamma_{i_k})_{k \ge n+1}$. The difficulty in determining the valid paths in this component lies in the fact that we have to take care of the length of some paths in the Rauzy graphs to know which morphisms are allowed. Indeed, the morphisms that code the evolutions to Rauzy graphs of type 5 or 6 (and 7 or 8) are the same and the precise type depends on the lengths of the path $p_1$ and $p_2$ in Figure 5.8.1 (and of the lengths of the paths $u_1, u_2, v_1$ and $v_2$ in Figure 5.8.2. When the Rauzy graph $G_{i_n}$ is of type 6 or 8 (i.e., when $|p_1| = |p_2|$ or when $|u_1| = |u_2|$), we know from Lemma 5.11 that we can decompose the morphism $\gamma_{i_n}$ into two morphisms, each one corresponding to the burst of one bispecial vertex. On the other hand, if for example $|u_1|$ is much larger than $|u_2| + |v_2|$ in Figure 5.8.2 and if we denote by $B_1(1), B_1(2), \dots$ (resp. $B_2(1), B_2(2), \dots$) the bispecial vertices (ordered by increasing length) in the Rauzy graphs of larger order that admit $R_1$ (resp. $R_2$) as a suffix, we will see that many vertices $B_1(i)$ will burst before that $B_2(1)$ bursts. Consequently not all morphisms are allowed.

<figure><img src="image_29.png" /><figcaption>Figure 5.8: The next evolutions of these graphs depend on the length of the paths $u_i, v_i$ and $p_i$.</figcaption></figure>

First, the following result will be helpful to characterize valid paths that goes infinitely often through the vertex 1 in the graph of graphs. Its proof is left to the reader, but can be found in [Ler13].

**Fact 5.18** We can suppose without loss of generality that the evolution of a Rauzy graph of type 1 to a Rauzy graph of type 1 is coded by $[0, 10]$ or by $[01, 1]$.

Next, Lemma 5.19 implies that we can merge the vertices 5 and 6 to one vertex denoted by $5/6$ in $\mathcal{G}$ and that the outgoing edges of that vertex are the same as the outgoing edges of the vertex 6 in $\mathcal{G}$. However, we have to take care of the lengths of $p_1$ and $p_2$ in Figure 5.8.1 to know which morphism in the labels of the edges can be applied.

**Lemma 5.19** Let $G_k$ be a Rauzy graph as in Figure 5.8.1 and let $i_n$ be the smallest integer in $(i_n)_{n \in \mathbb{N}}$ such that $i_n \ge k$. We have

$$ \{\text{Type of } G_{i_{n+1}} \mid G_{i_n} \text{ is of type 6}\} = \{\text{Type of } G_{i_{n+2}} \mid G_{i_n} \text{ is of type 5 and } U_{i_n} \text{ is not strong bispecial}\} $$
and

$$ \{\gamma_{i_n} | G_{i_n} \text{ is of type } 6\} = \{\gamma_{i_n} \circ \gamma_{i_{n+1}} | G_{i_n} \text{ is of type } 5 \text{ and } U_{i_n} \text{ is not strong bispecial}\}. $$

**Proof:** The first equality can be easily checked on the graph of graphs (Figure 4.5 on page 249) and the second one is deduced from the computation of morphisms coding the needed evolutions and is left to the reader (see also [Ler13]). □

**Remark 5.20** In order to describe all valid paths in the component $C_1$, we sometimes have to know the precise type of a graph corresponding to the vertex 5/6. Indeed, when going to that vertex in the modified component (suppose the label of the edge is $\gamma_{i_n}$ and that $U_{i_{n+1}}$ corresponds to the vertex $R_1$ in Figure 5.8.1), we may want to leave it using the morphism $\gamma_{i_{n+1}} = [x, y^k x, (y^{k-1}x)]$. However, the evolution corresponding to that morphism is such that the smallest bispecial factor that admits $U_{i_{n+1}}$ as a suffix is strong (the other right special vertex is therefore suffix of a weak bispecial factor). Consequently, we can leave the vertex 5/6 with that morphism only if $U_{i_{n+1}}$ is not bispecial, i.e., the other right special vertex becomes bispecial before $U_{i_{n+1}}$. In other words, we must have $|p_1| \ge |p_2|$ in Figure 5.8.1.

Next lemma deals with the same kind of stuffs as in Lemma 5.19 but for Rauzy graphs of type 7 and 8. As for graphs of type 5 and 6, it allows us to merge the vertices 7 and 8 to one vertex denoted 7/8 in $\mathcal{G}$. It also allows us to delete the vertex 9 in $\mathcal{G}$ because it does not have any incoming edge anymore. Though its proof is not really difficult, it is a bit long. The interested reader is invited to check it in [Ler13].

**Lemma 5.21** Let $G_t$ be a Rauzy graph as in Figure 5.8.2 and let $i_n$ be the smallest integer in $(i_m)_{m \in \mathbb{N}}$ such that $i_n \ge t$. Suppose that $U_t$ is the vertex $R_1$ and that $\theta_t(1)$ goes $k$ times through the loop $v_2u_2$. Let $\ell \in \mathbb{Z}$ such that

$$ |u_1| + (\ell - 1)(|u_1| + |v_1|) < |u_2| + (k - 1)(|u_2| + |v_2|) \le |u_1| + \ell(|u_1| + |v_1|). \quad (10) $$

Then, the graph can evolve to a graph of type

i. 1 and the composition of morphisms coding this evolution is in

$$ \{[0, 10]^h \{[01, 1], [1, 01]\} | h \in \mathbb{N}\} \cup \{[0, 10]^h[x, y] | \{x, y\} = \{0, 1\}, h \ge \max\{0, \ell\}\} $$

ii. 5 or 6 as in Figure 5.8.1 and the composition of morphisms coding this evolution is in

$$ \{[0, 10, 20]^h \{[0x, y, (0y)], [x, 0y, (y)]\} | \{x, y\} = \{1, 2\}, h \in \mathbb{N}\}. $$

The last type of graph that has not been treated yet is the type 10. The next lemma does it.

**Lemma 5.22** Let $G_{i_n}$ be a Rauzy graph of type 10. Suppose that $U_{i_n}$ corresponds to the vertex $R$ in Figure 4.4.10 and that the two $i_n$-circuits $\theta_{i_n}(0)$ and $\theta_{i_n}(1)$ respectively go through the loop $k$ and $\ell$ times with $k, \ell \ge 0$ and $k + \ell \ge 1$.

If the circuit $\theta_{i_n}(2)$ exists and starts like $\theta_{i_n}(0)$ does (recall that $\ell \le k$ in this case), then

i. if $\ell = k$, $G_{i_n}$ will evolve to a Rauzy graph $G_{i_m}$, $m > n$, of type 10 such that $U_{i_m}$ corresponds to the vertex $B$ in Figure 4.4.10. This evolution is coded by the morphism $[1, 0, 2]$;
ii. if $\ell < k$, $G_{i_n}$ will evolve to a Rauzy graph $G_{i_m}$, $m > n$, of type 7 or 8 such that the $i_m$-circuit $\theta_{i_m}(1)$ starting from $U_{i_m}$ goes through the loop $k - \ell$ times. This evolution is also coded by the morphism $[1, 0, 2]$.

If the circuit $\theta_{i_n}(2)$ exists and starts like $\theta_{i_n}(1)$ does (recall that $k \le \ell - 1$ in this case), then

i. if $k = \ell - 1$, $G_{i_n}$ will evolve to a Rauzy graph $G_{i_m}$, $m > n$, of type 10 such that $U_{i_m}$ corresponds to the vertex B in Figure 4.4.10. This evolution is coded by the morphism $[0, 1, 2]$;

ii. if $k < \ell - 1$, $G_{i_n}$ will evolve to a Rauzy graph $G_{i_m}$, $m > n$, of type 7 or 8 such that the $i_m$-circuit $\theta_{i_m}(1)$ starting from $U_{i_m}$ goes through the loop $\ell - k - 1$ times. This evolution is again coded by the morphism $[0, 1, 2]$.

If the circuit $\theta_{i_n}(2)$ does not exist, then

i. if $\ell \in \{k, k+1\}$, $G_{i_n}$ will evolve to a Rauzy graph $G_{i_m}$, $m > n$, of type 1. This evolution is coded by a morphism in $\{[0, 1], [1, 0]\}$;

ii. if $\ell < k$, $G_{i_n}$ will evolve to a Rauzy graph $G_{i_m}$, $m > n$, of type 7 or 8 such that the $i_m$-circuit $\theta_{i_m}(1)$ starting from $U_{i_m}$ goes through the loop $k - \ell$ times. This evolution is coded by the morphism $[1, 0]$.

iii. if $\ell > k + 1$, $G_{i_n}$ will evolve to a Rauzy graph $G_{i_m}$, $m > n$, of type 7 or 8 such that the $i_m$-circuit $\theta_{i_m}(1)$ starting from $U_{i_m}$ goes through the loop $\ell - k - 1$ times. This evolution is coded by the morphism $[0, 1]$.

**Proof:** Indeed, if the vertex B in Figure 4.4.10 bursts as in Figure 5.9.1, the new graph is still of type 10. This evolution is coded by the morphism $[1, 0, (2)]$. Moreover, if for all $n$ we denote by $k_{i_n}(0)$ (resp. $k_{i_n}(1)$, $k_{i_n}(2)$) the number of times that the $i_n$-circuit $\theta_{i_n}(0)$ (resp. $\theta_{i_n}(1)$, $\theta_{i_n}(2)$) goes through the loop, then we have $k_{i_{n+1}}(0) = k_{i_n}(1) - 1$ and $k_{i_{n+1}}(1) = k_{i_n}(0)$. We also have $k_{i_{n+1}}(2) = k_{i_n}(2)$ if the $i_n$-circuit $\theta_{i_n}(2)$ starts like $\theta_{i_n}(0)$ does and $k_{i_{n+1}}(2) = k_{i_n}(2) - 1$ if the $i_n$-circuit $\theta_{i_n}(2)$ starts like $\theta_{i_n}(1)$ does. Consequently, this evolution is repeated until either $k_{i_n'}(1) = 0$ or $k_{i_n'}(0) = 0$ and $k_{i_n'}(1) = 1$ for some $n' \ge n$. Then the graph $G_{i_{n'}}$ evolves to a Rauzy graph of type 1, 7, 8 or 9 depending on $k_{i_{n'}}(0)$, $k_{i_{n'}}(1)$ and $k_{i_{n'}}(2)$ (if the circuit $\theta_{i_n}(2)$ exists). The computation of the morphism coding this last evolution is left to the reader. $\square$

### 5.7.1 Modification of Component $C_1$

Now we can modify the component $C_1$ of $G$.

First let us modify the vertices. Lemmas 5.19 and 5.21 allow to merge the vertices 5 and 6 to one vertex 5/6 and the vertices 7 and 8 to one vertex 7/8. As already mentioned, the vertex 9 can also be deleted (thanks to Lemma 5.21). Finally, Lemma 5.22 describes the sequence of evolutions while $U_{i_n}$ corresponds to the vertex R in a graph of type 10. Consequently, if a graph evolves to a graph of type 10 such that $U_{i_n} = R$, there is only one possible finite sequence of evolutions, the one given by Lemma 5.22. Consequently, we can simply treat these evolutions by modifying the edges in $C_1$ as explained just below and we rename vertex 10 by $10B$, meaning that the vertex $U_{i_n}$ always corresponds to the vertex B in Figure 4.4.10.

Now let us modify the edges and/or their labels. All modifications are direct consequences of Fact 5.18, Lemma 5.19, Lemma 5.21 and Lemma 5.22:
<figure><img src="image_30.png" /><figcaption>Figure 5.9: Evolutions of a graph of type 10 with 3 circuits starting from $R$.</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>Figure 5.10: Evolutions of a graph of type 10 with 2 circuits starting from $R$.</figcaption></figure>
* Fact 5.18 implies that we can consider only two morphisms to label the loop on vertex 1.

* Lemma 5.19 implies that the edges starting from 5/6 are the same as those starting from 6 in $\mathcal{G}$.

* By Lemma 5.22, we can replace each morphism $\gamma_{i_n}$ labelling an edge coming to 10 in $\mathcal{G}$ such that $U_{i_{n+1}} = R$ by the corresponding behaviour given in that lemma. For instance, in $\mathcal{G}$, the morphism $\gamma_{i_n} = [12^k 0, 2^\ell 0, 12^{k-1} 0]$ labels an edge from 6 to 10. By Lemma 5.22, this morphism makes the graph of type 10 evolve to a graph of type 7 or 8 or 10 depending on $k$ and $\ell$. Consequently, we delete this morphism and add two morphisms: the morphism $\gamma_{i_n} \circ [1, 0, 2]$ from 5/6 to 10B with $k = \ell$ (case i.) and the morphism $\gamma_{i_n} \circ [1, 0, 2]$ from 5/6 to 7/8 with $\ell < k$.

* In Lemma 5.21, as the behaviours depend on some lengths in Rauzy graphs, we simply consider the needed outgoing edges of the vertex 7/8 to be able to follow all described behaviours and put some restrictions on the choices in Proposition 5.23.

We then obtain the modified component $C_1$ represented in Figure 5.11 with labels as given in Table 5.1; those are trivially compositions of morphisms of $\mathcal{S}$.

As in the previous cases, we would like to ensure that any valid path in Figure 5.11 can be chosen in such a way that its label contains infinitely many right proper morphisms, which is currently not the case. For instance, any path oscillating between 5/6 and 7/8 such that the edge from 5/6 to 7/8 is labelled by $[1, 0^k 2, 0^{k-1} 2]$ does not contain any right proper morphism but can be a suffix of a valid path (Lemma 5.19 and Lemma 5.21 ensure that the local condition of Proposition 5.5 is satisfied). Thus, we have to modify Figure 5.11 in such a way that a contraction of such a sequence of morphisms labels another path and contains infinitely many right proper morphisms.

As proved in Proposition 5.23, this kind of problem can be solved by adding two edges in Figure 5.11 labelled by the morphisms given in Table 5.2. We then obtain the modified component as represented in Figure 5.12.

**Proposition 5.23** An infinite path $p$ in $\mathcal{G}$ labelled by $(\gamma_{i_n})_{n \ge N}$ is a valid suffix that always stays in component $C_1$ and that is such that $U_{i_N}$ is bispecial if and only if there is a contraction $(\alpha_n)_{n \ge N}$ of $(\gamma_{i_n})_{n \ge N}$ such that

1. there are infinitely many right proper morphisms in $(\alpha_n)_{n \ge N}$;

2. $(\alpha_n)_{n \ge N}$ labels an infinite path $p$ in the graph represented in Figure 5.12 (whose labels are given in Table 5.1 and Table 5.2) such that

(A) if for some integer $n \ge N$, $\alpha_n$ labels an edge to 5/6, then $\alpha_{n+1}$ can be in $\{[x, y^k x, (y^{k-1} x)] \mid \{x, y\} = \{0, 1\}, k \ge 2\}$ only if $|p_1| \ge |p_2|$, where $p_1$ and $p_2$ are the path represented in Figure 5.8.1 and the right special factor corresponding to $\alpha_{n+1}$ is $R_1$;

(B) if for some integer $n \ge N$, $\alpha_n$ labels an edge to 7/8 but not from 7/8 (so it is equal to $[w_1, w_2 w_3^\ell w_4, w_2 w_3^{\ell-1} w_4]$ for some words $w_1, w_2, w_3$ and $w_4$ and for an integer $\ell \ge 1$ which corresponds to the greatest number of times that a circuit goes through the loop $v_2 u_2$ in Figure 5.8.2), if $h$ is the greatest integer such that $\alpha_{n+i} = [0, 10, 20]$ for all $i = 1, \dots, h$, then $h$ is finite and $\alpha_{n+h+1}$ can be in $\{[0, 1], [1, 0]\}$ if and only if $|u_1| + h(|u_1| + |v_1|) \ge |u_2| + (\ell - 1)(|u_2| + |v_2|)$;
<figure><img src="image_32.png" /><figcaption>Figure 5.11: First attempt to modify the component $C_1$ in $\mathcal{G}$.</figcaption></figure>

<table><caption>Table 5.1: Labels of edges in Figure 5.11</caption><thead><tr><th>From</th><th>to</th><th>Labels</th><th>Conditions</th></tr></thead><tbody><tr><td rowspan="2">1</td><td>1</td><td>[0, 10], [01, 1]</td><td></td></tr><tr><td>7/8</td><td>[x, y<sup>k</sup>x, (y<sup>k-1</sup>x)]</td><td>k ≥ 2</td></tr><tr><td rowspan="10">5/6</td><td rowspan="2">1</td><td>[x, yx], [yx, x]</td><td></td></tr><tr><td>[12<sup>k</sup>0, 2<sup>k</sup>0], [2<sup>k</sup>0, 12<sup>k</sup>0]</td><td>k ≥ 1</td></tr><tr><td rowspan="4">7/8</td><td>[12<sup>k</sup>0, 2<sup>k+1</sup>0], [2<sup>k+1</sup>0, 12<sup>k</sup>0]</td><td>k ≥ 0</td></tr><tr><td>[1, 0<sup>k</sup>2, (0<sup>k-1</sup>2)]</td><td>k ≥ 1</td></tr><tr><td>[x, y<sup>k</sup>x, (y<sup>k-1</sup>x)]</td><td>k ≥ 2</td></tr><tr><td>[2<sup>l</sup>0, 12<sup>k</sup>0, (12<sup>k-1</sup>0)]</td><td>k > l ≥ 0</td></tr><tr><td rowspan="4">10B</td><td>[12<sup>k</sup>0, 2<sup>l</sup>0, (2<sup>l-1</sup>0)]</td><td>l > k + 1 ≥ 1</td></tr><tr><td>[1, 01, 2]</td><td></td></tr><tr><td>[2<sup>k</sup>0, 12<sup>k</sup>0, 12<sup>k-1</sup>0]</td><td>k ≥ 1</td></tr><tr><td>[12<sup>k</sup>0, 2<sup>k+1</sup>0, 2<sup>k</sup>0]</td><td>k ≥ 0</td></tr><tr><td rowspan="3">7/8</td><td>1</td><td>[01, 1], [1, 01], [x, y]</td><td></td></tr><tr><td>5/6</td><td>[0x, y, (0y)], [x, 0y, (y)]</td><td></td></tr><tr><td>7/8</td><td>[0, 10, (20)]</td><td></td></tr><tr><td rowspan="10">10B</td><td rowspan="2">1</td><td>[01<sup>k</sup>2, 1<sup>k</sup>2], [1<sup>k</sup>2, 01<sup>k</sup>2]</td><td>k ≥ 1</td></tr><tr><td>[01<sup>k</sup>2, 1<sup>k+1</sup>2], [1<sup>k+1</sup>2, 01<sup>k</sup>2]</td><td>k ≥ 0</td></tr><tr><td rowspan="3">7/8</td><td>[0, 2<sup>k</sup>1, 2<sup>k-1</sup>1]</td><td>k ≥ 1</td></tr><tr><td>[1<sup>l</sup>2, 01<sup>k</sup>2, (01<sup>k-1</sup>2)]</td><td>k > l ≥ 0</td></tr><tr><td>[01<sup>k</sup>2, 1<sup>l</sup>2, (1<sup>l-1</sup>2)]</td><td>l > k + 1 ≥ 1</td></tr><tr><td rowspan="3">10B</td><td>[0, 20, 1]</td><td></td></tr><tr><td>[1<sup>k</sup>2, 01<sup>k</sup>2, 01<sup>k-1</sup>2]</td><td>k ≥ 1</td></tr><tr><td>[01<sup>k</sup>2, 1<sup>k+1</sup>2, 1<sup>k</sup>2]</td><td>k ≥ 0</td></tr></tbody></table>
<figure><img src="image_33.png" /><figcaption>Figure 5.12: Graph corresponding to the component $C_1$ in $\mathcal{G}$.</figcaption></figure>

<table><caption>Table 5.2: Labels of the two additional edges in Figure 5.12</caption><thead><tr><th>From</th><th>To</th><th>Labels</th><th>Conditions</th></tr></thead><tbody><tr><td>5/6</td><td>5/6</td><td>[10<sup>k</sup>2, 0<sup>k-1</sup>2, 10<sup>k-1</sup>2]<br>[10<sup>k-1</sup>2, 0<sup>k</sup>2, 10<sup>k</sup>2]<br>[0<sup>k</sup>2, 10<sup>k-1</sup>2, 0<sup>k-1</sup>2]<br>[0<sup>k-1</sup>2, 10<sup>k</sup>2, 0<sup>k</sup>2]</td><td>k ≥ 1</td></tr><tr><td>10B</td><td>5/6</td><td>[02<sup>k</sup>1, 2<sup>k-1</sup>1, 02<sup>k-1</sup>1]<br>[02<sup>k-1</sup>1, 2<sup>k</sup>1, 02<sup>k</sup>1]<br>[2<sup>k</sup>1, 02<sup>k-1</sup>1, 2<sup>k-1</sup>1]<br>[2<sup>k-1</sup>1, 02<sup>k</sup>1, 2<sup>k</sup>1]</td><td>k ≥ 1</td></tr></tbody></table>
and such that one of the following conditions is satisfied

(i) $p$ ultimately stays in vertex 1 and both morphisms $[0, 10]$ and $[01, 1]$ occur infinitely often in $(\alpha_n)_{n \ge N}$;

(ii) $p$ ultimately stays in the subgraph $\{1, 7/8\}$, goes through both vertices infinitely often and for all suffixes $p'$ of $p$ starting in vertex 7/8, the label of $p'$ is not only composed of finite sub-sequences of morphisms in

$$([0, 10]^*[0, 1][0, 10]^*\{[0, 1^k 0] \mid k \ge 2\}) \cup ([0, 10]^*[1, 0][01, 1]^*\{[1, 0^k 1] \mid k \ge 2\});$$

(iii) $p$ contains infinitely many occurrences of sub-paths $q$ that start in vertex 1 and end in vertex 5/6.

(iv) $p$ ultimately stays in the subgraph $\{5/6, 7/8, 10B\}$ and does not ultimately correspond to one of the following three configurations:

(a) the path ultimately stays in vertex 7/8;

(b) $\bullet$ the loop over 5/6 is always labelled by in $[02, 12, 2]$ or $[102, 2, 12]$;

$\bullet$ the edge from 5/6 to 7/8 is always labelled by $[1, 02, 2]$;

• the edge from 5/6 to 10B is always labelled by $[1, 01, 2]$;

• the edge from 7/8 to 5/6 is always labelled by $[1, 02, 2]$ or by $[01, 2, 02]$;

• for all sub-paths $q$ uniquely composed of loops over 10B, the label of $q$ contains only occurrences of morphisms in

$$\{[0, 20, 1]^{2n}, [02, 12, 2] \mid n \in \mathbb{N}\};$$

• for all finite sub-paths $q$ composed of loops over 10B and followed by the edge from 10B to 5/6, the label of $q$ is in

$$\{[0, 20, 1]^{2n}, [02, 12, 2] \mid n \in \mathbb{N}\}^*[0, 20, 1]\{[21, 01, 1], [021, 1, 01]\};$$

(c) $\bullet$ the paths does not go through the loop over the vertex 7/8;

• the loop over the vertex 5/6 is always labelled by $[0^k 2, 10^{k-1} 2, 0^{k-1} 2]$ or by $[0^{k-1} 2, 10^k 2, 0^k 2]$ for some integer $k \ge 1$;

• the loop over the vertex 10B is always labelled by $[12^k 0, 2^{k+1} 0, 2^k 0]$ for some integer $k \ge 0$;

• the edge from 5/6 to 7/8 is always labelled either by $[1, 0^k 2, 0^{k-1} 2]$ for some integer $k \ge 1$ or by $[12^k 0, 2^\ell 0, 2^{\ell-1} 0]$ for some integers $k$ and $\ell$ such that $\ell > k + 1 \ge 1$;

• the edge from 7/8 to 5/6 is always labelled by $[1, 02, 2]$ or by $[2, 01, 1]$;

• the edge from 10B to 5/6 is always labelled by morphism $[2^k 1, 02^{k-1} 1, 2^{k-1} 1]$ or $[2^{k-1} 1, 02^k 1, 2^k 1]$ for some integer $k \ge 1$;

• the edge from 10B to 7/8 is always labelled by $[0, 2^k 1, 2^{k-1} 1]$ for some integer $k \ge 1$.
**Proof:** Our aim is to describe the valid suffixes in $\mathcal{G}$ that stay in component $C_1$, accordingly to Proposition 5.5. The first step is to ensure that to any valid path $p$ in $\mathcal{G}$, there is a contraction $(\alpha_n)_{n \ge N}$ of its label that labels a path in Figure 5.12 and that contains infinitely many right proper morphisms. Up to know, the results in Section 5.7 state that such a contraction labels a path in Figure 5.11, but some of them can contain only finitely many right proper morphisms. One can check that all of them label paths in Figure 5.13 where

1. the edge from 5/6 to 10B is labelled by $[1, 01, 2]$;

2. the edge from 5/6 to 7/8 is labelled by $[1, 0^k 2, 0^{k-1} 2]$;

3. the edge from 7/8 to 5/6 is labelled by $[0x, y, 0y]$ and $[x, 0y, x]$;

4. the edge from 10B to 7/8 is labelled by $[0, 2^k 1, 2^{k-1} 1]$;

5. the loop on 10B is labelled by $[0, 20, 1]$.

<figure><img src="image_34.png" /><figcaption>Figure 5.13: Part of Figure 5.11 where there might be some valid labelled path with only non-right proper morphisms as labels.</figcaption></figure>

It is easily seen that the labelled paths in Figure 5.13 that ultimately stay in vertex 10B are not valid. Moreover, the labels of the path of length 2 from 5/6 to 5/6 (hence going through 7/8) are right proper and equal to

$$ 
\begin{align*}
[1, 0^k 2, 0^{k-1} 2] \circ [01, 2, 02] &= [10^k 2, 0^{k-1} 2, 10^{k-1} 2] \\
[1, 0^k 2, 0^{k-1} 2] \circ [02, 1, 01] &= [10^{k-1} 2, 0^k 2, 10^k 2] \\
[1, 0^k 2, 0^{k-1} 2] \circ [1, 02, 2] &= [0^k 2, 10^{k-1} 2, 0^{k-1} 2] \\
[1, 0^k 2, 0^{k-1} 2] \circ [2, 01, 1] &= [0^{k-1} 2, 10^k 2, 0^k 2]
\end{align*}
$$

Similarly, the labels of the path of length 2 from 10B to 5/6 (hence going through 7/8) are right proper and equal to

$$ 
\begin{align*}
[0, 2^k 1, 2^{k-1} 1] \circ [01, 2, 02] &= [02^k 1, 2^{k-1} 1, 02^{k-1} 1] \\
[0, 2^k 1, 2^{k-1} 1] \circ [02, 1, 01] &= [02^{k-1} 1, 2^k 1, 02^k 1] \\
[0, 2^k 1, 2^{k-1} 1] \circ [1, 02, 2] &= [2^k 1, 02^{k-1} 1, 2^{k-1} 1] \\
[0, 2^k 1, 2^{k-1} 1] \circ [2, 01, 1] &= [2^{k-1} 1, 02^k 1, 2^k 1]
\end{align*}
$$
To our aim, it suffices therefore to add two edges in Figure 5.11: one loop over 5/6 labelled by the first four morphisms above and one edge from 10B to 5/6 labelled by the last four morphisms above, which corresponds to Table 5.2.

With that modification of Figure 5.11, the proper condition of Proposition 5.5 is equivalent to the condition 1 of the result. For the first condition of Proposition 5.5 (the local one), it is a direct consequence of all previous lemmas and of the modifications applied to $C_1$:

1. any finite path going only through the vertex 1 is trivially valid;

2. the condition 2A of the result summarizes what is allowed according to Lemma 5.19 for vertex 5/6;

3. the condition 2B summarizes what is allowed with vertex 7/8 according to Lemma 5.21;

4. the edges going to vertex 10 in Figure 4.5 (page 249) have been modified according to Lemma 5.22.

It remains therefore to check the weakly primitive property. It is easily seen that conditions 2i to 2iv are sufficient for the sequence of morphisms to be weakly primitive. The proof of the necessary part is rather long so, once again, can be found in [Ler13, Appendix B]. □

## 5.8 Links between components

Now that we know how the suffixes of valid paths in each component must behave, it remains to describe all links between them. To this aim, it suffices to look at the graph of graphs $\mathcal{G}$ (Figure 4.5 page 249) and, like we did in each component, to study the consequences of a given morphism $\gamma_{i_n}$ on the sequel in the directive word. For instance, in $\mathcal{G}$ there is an edge from 2 to 4 which is labelled by morphisms $\gamma_{i_n}$ depending on some exponents $k$ and $\ell$ and that are such that $U_{i_{n+1}}$ corresponds to the vertex $R$ in Figure 4.4.4. Then, Lemma 5.16 (page 266) states that, depending on $k$ and $\ell$, the graph will evolve to a graph of type 1, 4, 7 or 8 and 10 (with $U_{i_m} = B$) and it provides the morphism $\tau$ coding this evolution. Consequently, we add edges (if necessary) from 2 to $\{1, 4B, 7/8, 10B\}$ labelled by $\gamma_{i_n} \circ \tau$. This yields to the *modified graph of graphs $\mathcal{G}'$* represented in Figure 5.14 (gray edges are simply those inner components). Labels of black edges are given below. In Table 5.3, Table 5.4 and Table 5.5, we express in the column “Through” if the morphism is the result of a contraction like just explained. In the previous example, we would write $4R$ in the column “Through”, meaning that the morphisms is a composition of $\gamma_{i_n}$ and $\tau$ and that $\gamma_{i_n}$ codes an evolution to a Rauzy graph of type 4 such that $U_{i_{n+1}}$ corresponds to the vertex $R$ in Figure 4.4.4.

Observe that, since black edges can only occur in a finite prefix of any valid path in $\mathcal{G}'$, we do not need to compute the left conjugates of their labels.

**Remark 5.24** It is important to notice that the exponents $k$ and $\ell$ in morphisms $\gamma_{i_n}$ do not always correspond to the integers $k$ and $\ell$ in Lemma 5.16, Lemma 5.21 and Lemma 5.22. Indeed, if for instance we consider the evolution of a Rauzy graph of type 2 to a Rauzy graph of type 4 as represented in Figure 5.15. The morphism coding this evolution is either $[yz^kx, z^\ell x, yz^{k-1}x]$ or $[z^kx, yz^\ell x, z^{k-1}x]$ for some integers $k$ and $\ell$. But, the circuits $\theta_{i_{n+1}}(0)$ and $\theta_{i_{n+1}}(1)$ respectively go $k-1$ and $\ell-1$ times through the loop.
<figure><img src="image_35.png" /><figcaption>Figure 5.14: Modified graph of graphs.</figcaption></figure>
<table><caption>Table 5.3: Morphisms labelling the black edges starting from 2 in $\mathcal{G}'$</caption><thead><tr><th>To</th><th>Through</th><th>Labels</th><th>Conditions</th></tr></thead><tbody><tr><td rowspan="3">1</td><td>/</td><td>[x, yzx], [yzx, x], [xy, zy]<br>[xy, zxy], [zxy, xy]</td><td></td></tr><tr><td>4R</td><td>[yz<sup>k</sup>x, z<sup>k</sup>x], [z<sup>k</sup>x, yz<sup>k</sup>x]<br>[yz<sup>k</sup>x, z<sup>k-1</sup>x], [z<sup>k-1</sup>x, yz<sup>k</sup>x]<br>[yz<sup>k-1</sup>x, z<sup>k</sup>x], [z<sup>k</sup>x, yz<sup>k-1</sup>x]</td><td>k ≥ 2</td></tr><tr><td>10R</td><td>[(xy)<sup>k</sup>z, y(xy)<sup>k</sup>z], [y(xy)<sup>k</sup>z, (xy)<sup>k</sup>z]<br>[(xy)<sup>k</sup>z, y(xy)<sup>k-1</sup>z], [y(xy)<sup>k-1</sup>z, (xy)<sup>k</sup>z]</td><td>k ≥ 1<br>k ≥ 2</td></tr><tr><td rowspan="2">4B</td><td>/</td><td>[x, yx, yzx], [y, yzx, yx]</td><td></td></tr><tr><td>4R</td><td>[y<sup>k-1</sup>z, xy<sup>k</sup>z, xy<sup>k-1</sup>z]<br>[y<sup>k-1</sup>z, xy<sup>k-1</sup>z, xy<sup>k</sup>z]<br>[xy<sup>k-1</sup>z, y<sup>k</sup>z, y<sup>k-1</sup>z]<br>[xy<sup>k-1</sup>z, y<sup>k-1</sup>z, y<sup>k</sup>z]</td><td>k ≥ 2</td></tr><tr><td>V<sub>0</sub></td><td>/</td><td>[0, 120, 20], [0, 10, 210]</td><td></td></tr><tr><td>V<sub>1</sub></td><td>/</td><td>[01, 1, 201], [021, 1, 21]</td><td></td></tr><tr><td>V<sub>2</sub></td><td>/</td><td>[02, 102, 2], [012, 12, 2]</td><td></td></tr><tr><td rowspan="6">7/8</td><td>/</td><td>[x, y<sup>k</sup>zx, (y<sup>k-1</sup>zx)]<br>[x, zy<sup>k</sup>x, (zy<sup>k-1</sup>x)]<br>[x, (yz)<sup>k</sup>x, ((yz)<sup>k-1</sup>x)]<br>[xy, z<sup>k</sup>xy, (z<sup>k-1</sup>xy)]<br>[xy, z<sup>k</sup>y, (z<sup>k-1</sup>y)]<br>[x, (yz)<sup>k</sup>yx, ((yz)<sup>k-1</sup>yx)]</td><td>k ≥ 2</td></tr><tr><td>4R</td><td>[z<sup>l</sup>x, yz<sup>k</sup>x, yz<sup>k-1</sup>x]<br>[yz<sup>l</sup>x, z<sup>k</sup>x, z<sup>k-1</sup>x]</td><td>k - 1 > l ≥ 1</td></tr><tr><td>10R</td><td>[y(xy)<sup>l</sup>z, (xy)<sup>k</sup>z, (xy)<sup>k-1</sup>z]<br>[(xy)<sup>k</sup>z, y(xy)<sup>l</sup>z, y(xy)<sup>l-1</sup>z]</td><td>k - 1 > l ≥ 0<br>l > k ≥ 1</td></tr><tr><td>/</td><td>[xy, zxy, zy]</td><td></td></tr><tr><td>4R</td><td>[z<sup>k</sup>x, yz<sup>k</sup>x, yz<sup>k-1</sup>x]<br>[yz<sup>k</sup>x, z<sup>k</sup>x, z<sup>k-1</sup>x]</td><td>k ≥ 2</td></tr><tr><td>10R</td><td>[y(xy)<sup>k-1</sup>z, (xy)<sup>k</sup>z, (xy)<sup>k-1</sup>z]<br>[(xy)<sup>k</sup>z, y(xy)<sup>k</sup>z, y(xy)<sup>k-1</sup>z]</td><td>k ≥ 2</td></tr></tbody></table>
<figure><img src="image_36.png" /><figcaption>Figure 5.15: Evolution of a graph of type 2 to a graph of type 4.</figcaption></figure>

<table><caption>Table 5.4: Morphisms labelling the black edges starting from $V_i$ in $\mathcal{G}'$</caption><thead><tr><th>To</th><th>Through</th><th>Labels</th><th>Conditions</th></tr></thead><tbody><tr><td rowspan="3">1</td><td>/</td><td>[x, iy], [iy, x], [xi, yi]</td><td></td></tr><tr><td rowspan="2">10R</td><td>[xy<sup>k</sup>i, y<sup>k</sup>i], [y<sup>k</sup>i, xy<sup>k</sup>i]</td><td>k &ge; 1</td></tr><tr><td>[xy<sup>k</sup>i, y<sup>k-1</sup>i], [y<sup>k-1</sup>i, xy<sup>k</sup>i]</td><td>k &ge; 2</td></tr><tr><td rowspan="2">7/8</td><td>/</td><td>[i, xy<sup>k</sup>i, xy<sup>k-1</sup>i]</td><td>k &ge; 1</td></tr><tr><td></td><td>[x, i<sup>k</sup>y, i<sup>k-1</sup>y]</td><td>k &ge; 2</td></tr><tr><td rowspan="2">—</td><td rowspan="2">10R</td><td>[xy<sup>l</sup>i, y<sup>k</sup>i, y<sup>k-1</sup>i]</td><td>k - 1 &gt; l &ge; 0</td></tr><tr><td>[y<sup>k</sup>i, xy<sup>l</sup>i, xy<sup>l-1</sup>i]</td><td>l &gt; k &ge; 1</td></tr><tr><td rowspan="3">10B</td><td>/</td><td>[x, ix, iy]</td><td></td></tr><tr><td rowspan="2">10R</td><td>[xy<sup>k-1</sup>i, y<sup>k</sup>i, y<sup>k-1</sup>i]</td><td>k &ge; 2</td></tr><tr><td>[y<sup>k</sup>i, xy<sup>k</sup>i, xy<sup>k-1</sup>i]</td><td>k &ge; 1</td></tr></tbody></table>
<table><caption>Table 5.5: Morphisms labelling the black edges starting from 4B in $G'$</caption><thead><tr><th>To</th><th>Through</th><th>Labels</th><th>Conditions</th></tr></thead><tbody><tr><td rowspan="2">1</td><td>4R</td><td>[x<sup>k</sup>y, 0x<sup>k</sup>y], [0x<sup>k</sup>y, x<sup>k</sup>y]<br/>[x<sup>k-1</sup>y, 0x<sup>k</sup>y], [0x<sup>k</sup>y, x<sup>k-1</sup>y]<br/>[x<sup>k</sup>y, 0x<sup>k-1</sup>y], [0x<sup>k-1</sup>y, x<sup>k</sup>y]</td><td>k ≥ 1</td></tr><tr><td>10R</td><td>[0(x<sup>0</sup>)<sup>k</sup>y, (x<sup>0</sup>)<sup>k</sup>y], [(x<sup>0</sup>)<sup>k</sup>y, 0(x<sup>0</sup>)<sup>k</sup>y]<br/>[0(x<sup>0</sup>)<sup>k-1</sup>y, (x<sup>0</sup>)<sup>k</sup>y], [(x<sup>0</sup>)<sup>k</sup>y, 0(x<sup>0</sup>)<sup>k-1</sup>y]</td><td>k ≥ 1</td></tr><tr><td rowspan="4">7/8</td><td>/</td><td>[0, x<sup>k</sup>y0, x<sup>k-1</sup>y0]</td><td>k ≥ 1</td></tr><tr><td>4R</td><td>[x<sup>l</sup>y, 0x<sup>k</sup>y, 0x<sup>k-1</sup>y]<br/>[0x<sup>l</sup>y, x<sup>k</sup>y, x<sup>k-1</sup>y]</td><td>k - 1 > l ≥ 0</td></tr><tr><td>10R</td><td>[(x<sup>0</sup>)<sup>l</sup>y, 0(x<sup>0</sup>)<sup>k</sup>y, 0(x<sup>0</sup>)<sup>k-1</sup>y]<br/>[0(x<sup>0</sup>)<sup>k</sup>y, (x<sup>0</sup>)<sup>l</sup>y, (x<sup>0</sup>)<sup>l-1</sup>y]</td><td>k > l ≥ 0<br/>l - 1 > k ≥ 0</td></tr><tr><td>10B</td><td>4R<br/>10R</td><td>[x<sup>k</sup>y, 0x<sup>k</sup>y, 0x<sup>k-1</sup>y]<br/>[0x<sup>k</sup>y, x<sup>k</sup>y, x<sup>k-1</sup>y]<br/>[(x<sup>0</sup>)<sup>k</sup>y, 0(x<sup>0</sup>)<sup>k</sup>y, 0(x<sup>0</sup>)<sup>k-1</sup>y]<br/>[0(x<sup>0</sup>)<sup>k-1</sup>y, (x<sup>0</sup>)<sup>k</sup>y, (x<sup>0</sup>)<sup>k-1</sup>y]</td><td>k ≥ 1<br/>k ≥ 1</td></tr></tbody></table>

## 5.9 Final Result

Now we can give an $S$-adic characterization of minimal and aperiodic subshift with first difference of complexity bounded by 2. It suffices to put together all what we have proved until now.

**Theorem 5.25** Let $(X, T)$ be a subshift over an alphabet $A$ and let

$$S = \{G, D, M, E_{01}, E_{12}\}$$

be the set of 5 morphisms as defined on page 244. Then, $(X, T)$ is minimal and satisfies $1 \le p_X(n+1) - p_X(n) \le 2$ for all $n \in \mathbb{N}$ if and only if $(X, T)$ is $S$-adic such that there exists a contraction $(\Gamma_n)_{n \in \mathbb{N}}$ of its directive word and a sequence of morphisms $(\alpha)_{n \in \mathbb{N}}$ labelling an infinite path $p$ in the graph represented at Figure 5.14 and such that

1. there are infinitely many right proper morphisms in $(\alpha_n)_{n \in \mathbb{N}}$ and for all integers $n \ge 0$, $\Gamma_n$ is either $\alpha_n$ or $\alpha_n^{(L)}$ and there are infinitely many right proper morphisms and infinitely many left proper morphisms in $(\Gamma_n)_{n \in \mathbb{N}}$;

2. if $p$ ultimately stays in component $C_2$ (resp. $C_3$, $C_4$), then the suffix of $p$ that stays in that component satisfies the conditions of Proposition 5.8 (resp. Proposition 5.10, Proposition 5.17);

3. if $p$ ultimately stays in component $C_1$, then the suffix $p'$ of $p$ that stays in that component satisfies the conditions of Proposition 5.23 with the following additional condition: if $p'$ starts in 7/8, if the edge preceding $p'$ in $p$ is labelled by some morphism $\alpha_n = [w_1, w_2w_3^k w_4, w_2w_3^{k-1}w_4]$ such that $k \ge 1$ corresponds to the greatest number of times that a circuit goes through the loop $v_2u_2$ in Figure 5.8.2), if $h$ is the greatest integer such that $\alpha_{n+i} = [0, 10, 20]$ for all $i = 1, \dots, h$, then $h$ is finite and $\alpha_{n+h+1}$ can be in $\{[0, 1], [1, 0]\}$ if and only if $|u_1| + h(|u_1| + |v_1|) \ge |u_2| + (k-1)(|u_2| + |v_2|)$;
**Proof:** The last thing that remains to prove is that all morphisms $\Gamma_n$ belong to $S^*$. To avoid long decompositions, we define the following morphisms of $S^*$. For $x, y \in \{0, 1, 2\}$, $D_{x,y}$ (resp. $G_{x,y}, M_{x,y}$) is the morphism that maps $x$ to $xy$ (resp. to $yx$, to $y$) and let the other letters unchanged. The morphism $E_{x,y}$ exchanges $x$ and $y$.

Now we can compute all decompositions. The morphisms labelling inner edges in components $C_2$ and $C_3$ are easily seen to belong to $S^*$. Hence, we can restrict ourselves to those labelling edges in components $C_1$ and $C_4$ and labelling the black edges in Figure 5.14. Furthermore, the only morphisms that really need some computation are those that depend on some exponents $k$ or $\ell$. Observe that the conditions on $k$ and $\ell$ given below are sometimes not restrictive enough; a given type morphism might label different edges, but the conditions on $k$ and $\ell$ can be different for these edges. The conditions we consider here are taken to be the most general ones.

When having a look at the concerned morphisms in Proposition 5.17, Table 5.1, Table 5.2, Table 5.3, Table 5.4 and Table 5.5, we see that there is an integer $K$ such that all of them can be written under the form $\sigma \circ \tau$, where $\sigma \in S^{\le K}$ and $\tau$ is one of the following morphisms (up to a permutation of the images)

$$ 
\begin{array}{ll}
[x, y^k x, y^{k-1} x], & k \ge 2 \\
[x, y^k z, y^{k-1} z], & k \ge 1 \\
[x, z y^k x, z y^{k-1} x], & k \ge 1 \\
[y^\ell x, z y^k x, z y^{k-1} x], & k > \ell \ge 0 \\
[y^k x, z y^k x, z y^{k-1} x], & k \ge 1 \\
[x y^\ell z, y^k z, y^{k-1} z], & k \ge \ell \ge 0, k + \ell \ge 1
\end{array}
$$

For instance, the morphism $[y(xy)^\ell z, (xy)^k z, (xy)^{k-1} z]$ in Table 5.3 can be written

$$D_{x,y}E_{x,y}[xy^\ell z, y^k z, y^{k-1} z].$$

Thus, all we have to do is to compute the decompositions of the previous morphisms, as well as the decomposition of their respective left conjugates when they exist (except for $[x, yz^k x, yz^{k-1} x]$ that only occurs as label of black edges, where it is useless to consider left conjugates). We obtain

$$ 
\begin{align*}
[x, y^k x, y^{k-1} x] &= M_{z,x} G_{z,y}^{k-1} D_{y,z}[x, y, z] \\
[x, xy^k, xy^{k-1}] &= M_{z,x} D_{z,y}^{k-1} G_{y,z}[x, y, z] \\
[x, y^k z, y^{k-1} z] &= G_{z,y}^{k-1} D_{y,z}[x, y, z] [x, y, z] \\
[x, z y^k x, z y^{k-1} x] &= D_{z,y}^{k-1} G_{y,z} D_{y,x} D_{z,x}[x, y, z] \\
[y^\ell x, z y^k x, z y^{k-1} x] &= D_{z,y}^{k-\ell-1} G_{x,y}^\ell G_{y,z} D_{y,x} D_{z,x}[x, y, z] \\
[x y^\ell, x z y^k, x z y^{k-1}] &= G_{z,x} D_{z,y}^{k-1} D_{x,y}^\ell G_{y,z}[x, y, z] \\
[y^k x, z y^k x, z y^{k-1} x] &= G_{x,y}^{k-1} D_{y,x} G_{x,z} D_{z,y}[y, z, x] \\
[x y^k, x z y^k, x z y^{k-1}] &= G_{z,x} D_{z,y}^{k-1} D_{x,y}^k G_{y,z}[x, y, z] \\
[x y^\ell z, y^k z, y^{k-1} z] &= D_{x,y}^\ell D_{x,z} G_{z,y}^{k-1} D_{y,z}[x, y, z] \\
[z x y^\ell, z y^k, z y^{k-1}] &= G_{x,y}^\ell G_{x,z} D_{z,y}^{k-1} G_{y,z}[x, y, z]
\end{align*}
$$
which concludes the proof.

□

**Remark 5.26** Up to now, Theorem 5.25 is stated in such a way that we have to keep track of the Rauzy graphs to be able to compute the length of some paths $p_1$ and $p_2$ in Figure 5.8.1 and $u_1, u_2, v_1$ and $v_2$ in Figure 5.8.2. This can actually be avoided by expressing these lengths only using the first morphisms of the directive word. Indeed, if $p$ is a valid path in $G'$ (labelled by $(\alpha_n)_{n \in \mathbb{N}}$) and if $p'$ is a prefix of $p$ ending in 5/6 (resp. in 7/8), then the lengths $|p_1|$ and $|p_2|$ (resp. $|u_1|, |u_2|, |v_1|$ and $|v_2|$) can be expressed only with the label $(\alpha_n)_{0 \le n \le N}$ of $p'$. The interested reader can find the calculation in [Ler13, Appendix C].

To obtain the exact complexities $p(n) = 2n$ or $p(n) = 2n + 1$, it suffices to impose respectively that $p(1) = 2$ or $p(1) = 3$ and that for all $n \ge 1$, $p(n+1) - p(n) = 2$. This can be expressed by the fact that Rauzy graphs cannot be of type 1 (because these graphs are such that $p(n+1) - p(n) = 1$). Consequently, one just has to impose that the path $p$ of the theorem does no go through vertex 1 except in some particular cases depending on the lengths $|u_1|, |u_2|, |v_1|, |v_2|, |p_1|$ and $|p_2|$.

**Corollary 5.27** A subshift $(X, T)$ is minimal and has complexity $p(n) = 2n$ (resp. $p(n) = 2n + 1$) for all $n \ge 1$ if and only if it is an $S$-adic subshift satisfying Theorem 5.25 and the following additional conditions:

1. either the path $p$ of Theorem 5.25 starts in vertex 2, or, it starts in vertex 1 and $\alpha_0$ labels the edge to vertex 7/8;

2. in Condition 2B of Proposition 5.23 and in Condition 3 of Theorem 5.25, the inequality

$$|u_1| + h(|u_1| + |v_1|) \ge |u_2| + (\mathfrak{k} - 1)(|u_2| + |v_2|)$$

is replaced by

$$|u_1| + h(|u_1| + |v_1|) = |u_2| + (\mathfrak{k} - 1)(|u_2| + |v_2|)$$

and in that case, $\alpha_{n+h+2}$ must label the edge from 1 to 7/8;

3. in Condition 2B of Proposition 5.23, the inequality $|p_1| \ge |p_2|$ is replaced by $|p_1| = |p_2|$.

# 6 Acknowledgement

I would like to thank Fabien Durand and Gwenaël Richomme for their help and useful comments about this work. This paper was mainly written during the author's PhD thesis [Ler12a] at the University of Picardie. It is also supported by the internal research project F1R-MTH-PUL-12RDO2 of the University of Luxembourg.

# References

[All94] J.-P. Allouche. Sur la complexité des suites infinies. *Bull. Belg. Math. Soc. Simon Stevin*, 1(2):133–143, 1994. Journées Montoises (Mons, 1992).

[AR91] P. Arnoux and G. Rauzy. Représentation géométrique de suites de complexité $2n + 1$. *Bull. Soc. Math. France*, 119:199–215, 1991.

[AS03] J.-P. Allouche and J. Shallit. *Automatic sequences: Theory, applications, generalizations*. Cambridge University Press, Cambridge, 2003.
[BHZ06] V. Berthé, C. Holton, and L. Q. Zamboni. Initial powers of Sturmian sequences. *Acta Arith.*, 122:315–347, 2006.

[Bos85] M. Boshernitzan. A unique ergodicity of minimal symbolic flows with linear block growth. *J. Analyse Math.*, 44:77–96, 1984/85.

[BR10] V. Berthé and M. Rigo, editors. *Combinatorics, Automata and Number Theory*, volume 135 of *Encyclopaedia of Mathematics and its Applications*. Cambridge University Press, Cambridge, 2010.

[Bra72] O. Bratteli. Inductive limits of finite dimensional $C^*$-algebras. *Trans. Amer. Math. Soc.*, 171:195–234, 1972.

[Cas96] J. Cassaigne. Special factors of sequences with linear subword complexity. In *Developments in language theory, II (Magdeburg, 1995)*, pages 25–34. World Sci. Publ., River Edge, NJ, 1996.

[Cas97] J. Cassaigne. Complexité et facteurs spéciaux. *Bull. Belg. Math. Soc. Simon Stevin*, 4:67–88, 1997. Journées Montoises (Mons, 1994).

[DHS99] F. Durand, B. Host, and C. Skau. Substitutional dynamical systems, Bratteli diagrams and dimension groups. *Ergodic Theory Dynam. Systems*, 19:953–993, 1999.

[Did98] G. Didier. Combinatoire des codages de rotations. *Acta Arith.*, 85(2):157–177, 1998.

[DL12] F. Durand and J. Leroy. S-adic conjecture and Bratteli diagrams. *C. R. Math. Acad. Sci. Paris*, 350(21-22):979–983, 2012.

[DLR13] F. Durand, J. Leroy, and G. Richomme. Do the Properties of an S-adic Representation Determine Factor Complexity? *J. Integer Seq.*, 16(2):Art. 13.2.6, 30, 2013.

[Dur98] F. Durand. A characterization of substitutive sequences using return words. *Discrete Math.*, 179:89–101, 1998.

[Dur00] F. Durand. Linearly recurrent subshifts have a finite number of non-periodic subshift factors. *Ergodic Theory Dynam. Systems*, 20:1061–1078, 2000.

[Dur03] F. Durand. Corrigendum and addendum to: "Linearly recurrent subshifts have a finite number of non-periodic subshift factors". *Ergodic Theory Dynam. Systems*, 23:663–669, 2003.

[Fer96] S. Ferenczi. Rank and symbolic complexity. *Ergodic Theory Dynam. Systems*, 16:663–682, 1996.

[Fer99] S. Ferenczi. Complexity of sequences and dynamical systems. *Discrete Math.*, 206(1-3):145–154, 1999. Combinatorics and number theory (Tiruchirappalli, 1996).

[FHZ03] S. Ferenczi, C. Holton, and L. Q. Zamboni. Structure of three-interval exchange transformations. II. A combinatorial description of the trajectories. *J. Anal. Math.*, 89:239–276, 2003.

[Fog02] N. Pytheas Fogg. *Substitutions in dynamics, arithmetics and combinatorics*, volume 1794 of *Lecture Notes in Mathematics*. Springer-Verlag, Berlin, 2002. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel.

[FZ08] S. Ferenczi and L. Q. Zamboni. Languages of k-interval exchange transformations. *Bull. Lond. Math. Soc.*, 40(4):705–714, 2008.

[GJ09] A. Glen and J. Justin. Episturmian words: a survey. *Theor. Inform. Appl.*, 43(3):403–442, 2009.

[HPS92] R. H. Herman, I. F. Putnam, and C. F. Skau. Ordered Bratteli diagrams, dimension groups and topological dynamics. *Internat. J. Math.*, 3(6):827–864, 1992.

[Ler12a] J. Leroy. *Contribution to the resolution of the S-adic conjecture*. PhD thesis, Université de Picardie Jules Verne, 2012.

[Ler12b] J. Leroy. Some improvements of the S-adic conjecture. *Advances in Applied Mathematics*, 48(1):79–98, 2012.
[Ler13] J. Leroy. An S-adic characterization of minimal subshifts with first difference of complexity $1 \le p(n + 1) - p(n) \le 2$. http://arxiv.org/abs/1305.0434, 2013.

[Lot97] M. Lothaire. *Combinatorics on words*. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. Corrected reprint of the 1983 original.

[Lot02] M. Lothaire. *Algebraic combinatorics on words*, volume 90 of *Encyclopedia of Mathematics and its Applications*. Cambridge University Press, Cambridge, 2002.

[LR13] J. Leroy and G. Richomme. A combinatorial proof of S-adicity for sequences with sub-affine complexity. *Integers*, 13, 2013.

[MH40] M. Morse and G. A. Hedlund. Symbolic dynamics II. Sturmian trajectories. *Amer. J. Math.*, 62:1–42, 1940.

[Mon05] T. Monteil. *Illumination in polygonal billiards and symbolic dynamics*. PhD thesis, Université Aix-Marseille II, 2005.

[MS93] F. Mignosi and P. Séébold. Morphismes sturmiens et règles de Rauzy. *J. Théor. Nombres Bordeaux*, 5(2):221–233, 1993.

[Pan84] J.-J. Pansiot. Complexité des facteurs des mots infinis engendrés par morphismes itérés. In *Automata, languages and programming (Antwerp, 1984)*, volume 172 of *Lecture Notes in Comput. Sci.*, pages 380–389. Springer, Berlin, 1984.

[Rau79] G. Rauzy. Échanges d’intervalle et transformations induites. *Acta Arith.*, 34(4):315–328, 1979.

[Rau83] G. Rauzy. Suites à termes dans un alphabet fini. 1983.

[Rot94] G. Rote. Sequences with subword complexity $2n$. *J. Number Theory*, 46:196–213, 1994.

[Thu06] A. Thue.
"Uber unendliche Zeichenreihen. Skrifter udgivne af Videnskabsselskabet i Christiania. 1906. Reprinted in *Selected Mathematical Papers of Axel Thue*, T. Nagell et al., editors, Universitetsforlaget, Oslo, 1977, pp. 139–158.

[Thu12] A. Thue.
"Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Skrifter utg. av Videnskapsselskapet i Kristiania. I, Mat.-naturv. klasse. 1912. Reprinted in *Selected Mathematical Papers of Axel Thue*, T. Nagell et al., editors, Universitetsforlaget, Oslo, 1977, pp. 413–477.

[Ver82] A. M. Vershik. A theorem on Markov periodic approximation in ergodic theory. *Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI)*, 115:72–82, 306, 1982. Boundary value problems of mathematical physics and related questions in the theory of functions, 14.

[VL92] A. M. Vershik and A. N. Livshits. Adic models of ergodic transformations, spectral theory, substitutions, and related topics. In *Representation theory and dynamical systems*, volume 9 of *Adv. Soviet Math.*, pages 185–204. Amer. Math. Soc., Providence, RI, 1992.

[War02] K. Wargan. *S-adic Dynamical Systems and Bratteli Diagrams*. PhD thesis, George Washington University, 2002.