#  $\mathcal{S}$-adic characterization of minimal dendric shifts

France Gheeraert† and Julien Leroy<EMAIL_ADDRESS><EMAIL_ADDRESS>University of Liège, Dept. of Mathematics, Allée de la
découverte 12 (B37), B-4000 Liège, Belgium

###### Abstract.

Dendric shifts are defined by combinatorial restrictions of the extensions of
the words in their languages. This family generalizes well-known families of
shifts such as Sturmian shifts, Arnoux-Rauzy shifts and codings of interval
exchange transformations. It is known that any minimal dendric shift has a
primitive $\mathcal{S}$-adic representation where the morphisms in
$\mathcal{S}$ are positive tame automorphisms of the free group generated by
the alphabet. In this paper we give an $\mathcal{S}$-adic characterization of
this family by means of two finite graphs. As an application, we are able to
decide whether a shift space generated by a uniformly recurrent morphic word
is (eventually) dendric.

###### Key words and phrases:

Dendric shifts, $S$-adic, substitution, Sturmian shifts, Interval exchange
transformations, Arnoux-Rauzy shifts.

###### 2020 Mathematics Subject Classification:

37B10, 68R15

†Supported by a FNRS fellowship.

##  1\. Introduction

Dendric shifts are defined in terms of extension graphs that describe the left
and right extensions of their factors. Extension graphs are bipartite graphs
that can roughly be described as follows: if $u$ is a word in the language
$\mathcal{L}(X)$ of the shift space $X$, one puts an edge between the left and
right copies of letters $a$ and $b$ such that $aub$ is in $\mathcal{L}(X)$. A
shift space is then said to be dendric if the extension graph of every word of
its language is a tree. These shift spaces were initially defined through
their languages under the name of tree sets [5] and were studied in a series
of papers. They generalize classical families of shift spaces such as Sturmian
shifts [30], Arnoux-Rauzy shifts [2], codings of regular interval exchange
transformations [31, 1] (IET) or else shift spaces arising from the
application of the Cassaigne multidimensional continued fraction algorithm
[13] (MCF).

Minimal dendric shifts exhibit striking combinatorial [8, 10], algebraic [5,
7] and ergodic properties [4]. They for instance have factor complexity
$\\#(\mathcal{L}(X)\cap\mathcal{A}^{n})=(\\#\mathcal{A}-1)n+1$ [5] and
topological rank $\\#\mathcal{A}$ [4], where $\mathcal{A}$ is the alphabet of
the shift space. They also fall into the class of eventually dendric shift
spaces, which are exactly those satisfying the regular bispecial condition
[18]. This implies that the number of their ergodic measures is at most
$\\#\mathcal{A}/2$ [16]. An important property for our work is that the
derived shift of a minimal dendric shift is again a minimal dendric shift on
the same alphabet, where derivation is here understood as derivation by return
words. This allows to give $\mathcal{S}$-adic representations of such shift
spaces [26], i.e., to define a set $\mathcal{S}$ of endomorphisms of the free
monoid $\mathcal{A}^{*}$ and a sequence
${\boldsymbol{\sigma}}=(\sigma_{n})_{n\geq 0}\in\mathcal{S}^{\mathbb{N}}$,
called an $\mathcal{S}$-adic representation, such that

$X=\\{x\in\mathcal{A}^{\mathbb{Z}}\mid u\in\mathcal{L}(x)\Rightarrow\exists
n\in\mathbb{N},a\in\mathcal{A}:u\in\mathcal{L}(\sigma_{0}\sigma_{2}\cdots\sigma_{n}(a))\\}.$

$\mathcal{S}$-adic representations are a classical tool that allows to study
several properties of shift spaces such as the factor complexity [24, 19], the
number of ergodic measures [9, 3, 12], the dimension group and topological
rank [4] or yet the automorphism group [25]. In the case of minimal dendric
shifts, the involved endomorphisms are particular tame automorphisms of the
free group generated by the alphabet [8, 10]. This in particular allows to
prove that minimal dendric shifts have topological rank equal to the
cardinality of the alphabet and that ergodic measures are completely
determined by the measures of the letter cylinders [4, 12].

In the case of the ternary alphabet $\\{1,2,3\\}$, we were able to give an
$\mathcal{S}$-adic characterization of minimal dendric shifts [29]. We
explicitly define an infinite set $\mathcal{S}_{3}$ of positive automorphisms
of the free group $F_{3}$ and a labeled directed graph $\mathcal{G}$ with two
vertices and labels in $\Sigma_{3}\mathcal{S}_{3}\Sigma_{3}$ (where
$\Sigma_{3}$ is the symmetric group of $\\{1,2,3\\}$) such that a shift space
over $\\{1,2,3\\}$ is a minimal dendric shift if and only if it has a
primitive $\Sigma_{3}\mathcal{S}_{3}\Sigma_{3}$-adic representation labelling
an infinite path in $\mathcal{G}$. We were then able to localize in
$\mathcal{G}$ classical families of dendric shifts such as codings of regular
interval exchanges or Arnoux-Rauzy shifts.

In this paper we extend this work to any alphabet as follows.

######  Theorem 1.

Let $\mathcal{S}$ be a family of dendric return morphisms from
$\mathcal{A}^{*}$ to $\mathcal{A}^{*}$ and let $X$ be a shift space having an
$\mathcal{S}$-adic representation ${\boldsymbol{\sigma}}=(\sigma_{n})_{n\geq
0}$. Then $X$ is minimal dendric if and only if ${\boldsymbol{\sigma}}$ is
primitive and labels infinite paths in the graphs
$\mathcal{G}^{L}(\mathcal{S})$ and $\mathcal{G}^{R}(\mathcal{S})$.

Observe that, contrary to the ternary case, we are not able to explicitely
define the set $\mathcal{S}$. We also consider two finite graphs instead of
one. A key argument in the ternary case is that for all $N$, the
$\mathcal{S}$-adic shift $X^{(N)}$ generated by $(\sigma_{n})_{n\geq N}$ is
minimal and dendric, so that $\sigma_{N}$ preserves dendricity from
$X^{(N+1)}$. The finiteness of $\mathcal{G}$ was obtained by defining an
equivalence relation with finite index on the set of dendric shifts such that
two shifts $X,Y$ are equivalent if and only if the same morphisms of
$\Sigma_{3}\mathcal{S}_{3}\Sigma_{3}$ preserve dendricity from $X$ and from
$Y$. The vertices of $\mathcal{G}$ are the two equivalent classes of this
relation.

In the general case, while we are not able to explicitly define $\mathcal{S}$,
we have enough information on the morphisms in $\mathcal{S}$ to similarly
define an equivalence relation characterizing how dendricity is preserved. It
is defined by means of two finite graphs describing the left and right
extensions of infinite special factors of $X$ (see Section 4).

The paper is organized as follows. We start by giving, in Section 2, the basic
definitions for the study of shift spaces. We introduce the notion of
extension graph of a word and of a dendric shift. In Section 3, we recall and
extend some results of [29] about the stability of dendricity when taking the
image under a return morphism.

In Section 4, we introduce new graphs associated with a shift space. They
provide another characterization of dendric shift spaces. We also study the
link with eventual dendricity in Section 5.

After that, in Section 6, we reformulate the results of Section 3 and study
the image under a return morphism using these graphs. We then use these
results to obtain an $S$-adic characterization of dendric shift spaces
(Theorem 1) in Section 7. We illustrate our results by giving an explicit
graph characterizing the minimal dendric shift spaces over four letters having
exactly one right special factor of each length. We also show that (eventual)
dendricity, and the corresponding threshold, is decidable for substitutive
shift spaces.

Finally, in Section 8, we focus on the sub-family of interval exchanges and
provide an $\mathcal{S}$-adic characterization (Theorem 72) using a subgraph
of the graph obtained in the dendric case.

##  2\. Definitions

###  2.1. Words, languages and shift spaces

Let $\mathcal{A}$ be a finite alphabet of cardinality $d\geq 2$. Let us denote
by $\varepsilon$ the empty word of the free monoid $\mathcal{A}^{*}$ (endowed
with concatenation), by $\mathcal{A}^{+}$ the set of non-empty finite words on
$\mathcal{A}$ and by $\mathcal{A}^{\mathbb{Z}}$ the set of bi-infinite words
over $\mathcal{A}$. For a word $w=w_{1}\cdots w_{\ell}\in\mathcal{A}^{\ell}$,
its length is denoted $|w|$ and equals $\ell$. We say that a word $u$ is a
factor of a word $w$ if there exist words $p,s$ such that $w=pus$. If
$p=\varepsilon$ (resp., $s=\varepsilon$) we say that $u$ is a prefix (resp.,
suffix) of $w$. For a word $u\in\mathcal{A}^{*}$ and a word
$w\in\mathcal{A}^{*}\cup\mathcal{A}^{\mathbb{Z}}$, an index $j$ such that
$w_{j}\cdots w_{j+|u|-1}=u$ is called an occurrence of $u$ in $w$. The number
of occurrences of a word $u\in\mathcal{A}^{*}$ in a finite word $w$ is denoted
by $|w|_{u}$.

The set $\mathcal{A}^{\mathbb{Z}}$ endowed with the product topology of the
discrete topology on each copy of $\mathcal{A}$ is topologically a Cantor set.
The shift map $S$ defined by
$S\left((x_{n})_{n\in\mathbb{Z}}\right)=(x_{n+1})_{n\in\mathbb{Z}}$ is a
homeomorphism of $\mathcal{A}^{\mathbb{Z}}$. A shift space is a pair $(X,S)$
where $X$ is a closed shift-invariant subset of some
$\mathcal{A}^{\mathbb{Z}}$. It is thus a topological dynamical system. It is
minimal if the only closed shift-invariant subset $Y\subset X$ are $\emptyset$
and $X$. Equivalently, $(X,S)$ is minimal if and only if the orbit of every
$x\in X$ is dense in $X$. Usually we say that the set $X$ is itself a shift
space.

The language of a sequence $x\in\mathcal{A}^{\mathbb{Z}}$ is its set of
factors and is denoted $\mathcal{L}(x)$. For a shift space $X$, its language
$\mathcal{L}(X)$ is $\bigcup_{x\in X}\mathcal{L}(x)$ and we set
$\mathcal{L}_{n}(X)=\mathcal{L}(X)\cap\mathcal{A}^{n}$, $n\in\mathbb{N}$, and
$\mathcal{L}_{\leq N}(X)=\bigcup_{n\leq N}\mathcal{L}_{n}(X)$. Its factor
complexity is the function $p_{X}:\mathbb{N}\to\mathbb{N}$ defined by
$p_{X}(n)=\operatorname{Card}\mathcal{L}_{n}(X)$. We say that a shift space
$X$ is over $\mathcal{A}$ if $\mathcal{L}_{1}(X)=\mathcal{A}$.

###  2.2. Extension graphs and dendric shifts

Dendric shifts are defined with respect to combinatorial properties of their
language expressed in terms of extension graphs. Let $F$ be a set of finite
words on the alphabet $\mathcal{A}$ which is factorial, i.e., if $u\in F$ and
$v$ is a factor of $u$, then $v\in F$. For $w\in F$, we define the sets of
left, right and bi-extensions of $w$ by

$\displaystyle E_{F}^{L}(w)$ $\displaystyle=\\{a\in\mathcal{A}\mid aw\in
F\\};$ $\displaystyle E_{F}^{R}(w)$ $\displaystyle=\\{b\in\mathcal{A}\mid
wb\in F\\};$ $\displaystyle E_{F}(w)$
$\displaystyle=\\{(a,b)\in\mathcal{A}\times\mathcal{A}\mid awb\in F\\}.$

The elements of $E_{F}^{L}(w)$, $E_{F}^{R}(w)$ and $E_{F}^{L}(w)$ are
respectively called the left extensions, the right extensions and the bi-
extensions of $w$ in $F$. If $X$ is a shift space over $\mathcal{A}$, we will
use the terminology extensions in $X$ instead of extensions in
$\mathcal{L}(X)$ and the index $\mathcal{L}(X)$ will be replaced by $X$ or
even omitted if the context is clear. Observe that as
$X\subset\mathcal{A}^{\mathbb{Z}}$, the set $E_{X}(w)$ completely determines
$E_{X}^{L}(w)$ and $E_{X}^{R}(w)$. A word $w$ is said to be right special
(resp., left special) if $\operatorname{Card}(E^{R}(w))\geq 2$ (resp.,
$\operatorname{Card}(E^{L}(w))\geq 2$). It is bispecial if it is both left and
right special. The factor complexity of a shift space is completely governed
by the extensions of its special factors. In particular, we have the following
result.

######  Proposition 2 (Cassaigne and Nicolas [14]).

Let $X$ be a shift space. For all $n$, we have

$\displaystyle p_{X}(n+1)-p_{X}(n)$
$\displaystyle=\sum_{w\in\mathcal{L}_{n}(X)}(\operatorname{Card}(E^{R}(w))-1)$
$\displaystyle=\sum_{w\in\mathcal{L}_{n}(X)}(\operatorname{Card}(E^{L}(w))-1)$

In addition, if for every bispecial factor $w\in\mathcal{L}(X)$, one has

(1)
$\operatorname{Card}(E(w))-\operatorname{Card}(E^{L}(w))-\operatorname{Card}(E^{R}(w))+1=0,$

then $p_{X}(n)=(p_{X}(1)-1)n+1$ for every $n$.

A classical family of bispecial factors satisfying Equation (1) is made of the
ordinary bispecial factors that are defined by
$E(w)\subset(\\{a\\}\times\mathcal{A})\cup(\mathcal{A}\times\\{b\\})$ for some
$(a,b)\in E(w)$. A larger family of bispecial factors also satisfying Equation
(1) are the dendric bispecial factors defined below.

For a word $w\in F$, we consider the undirected bipartite graph
$\mathcal{E}_{F}(w)$ called its _extension graph_ with respect to $F$ and
defined as follows: its set of vertices is the disjoint union of
$E_{F}^{L}(w)$ and $E_{F}^{R}(w)$ and its edges are the pairs $(a,b)\in
E_{F}^{L}(w)\times E_{F}^{R}(w)$ such that $awb\in F$. For an illustration,
see Example 3 below. Note that a letter $a$ can label a vertex both on the
left and on the right side. To distinguish the two, we will denote the left
vertex $a^{L}$ and the right vertex $a^{R}$. We say that $w$ is dendric if
$\mathcal{E}(w)$ is a tree. We then say that a shift space $X$ is a _dendric
shift_ if all its factors are dendric in $\mathcal{L}(X)$ and it is an
_eventually dendric shift (with threshold $N$)_ if all factors of length at
least $N$ are dendric (where $N$ is chosen minimal).

Note that every non-bispecial word and every ordinary bispecial word is
trivially dendric. In particular, the Arnoux-Rauzy shift spaces are dendric
(recall that Arnoux-Rauzy shift spaces are the minimal shift spaces having
exactly one left special factor $u_{n}$ and one right special factor $v_{n}$
of each length $n$ and such that $E^{L}(u_{n})=\mathcal{A}=E^{R}(v_{n})$; all
bispecial factors of an Arnoux-Rauzy shift are ordinary). By Proposition 2, we
deduce that any dendric shift has factor complexity $p_{X}(n)=(p_{X}(1)-1)n+1$
for every $n$.

######  Example 3.

If $X$ is the Fibonacci shift generated by the Fibonacci word
$0100101001001010\cdots$. We have $\mathcal{L}_{3}(X)=\\{001,010,100,101\\}$.
The extension graphs of the empty word and of the two letters $0$ and $1$ are
represented in Figure 1.

$\mathcal{E}(\varepsilon)$$0$$1$$0$$1$$\mathcal{E}(0)$$0$$1$$0$$1$$\mathcal{E}(1)$$0$$0$
Figure 1. The extension graphs of $\varepsilon$ (on the left), $0$ (in the
center) and $1$ (on the right) are trees.

##  3\. Extension graphs in morphic images

Let $\mathcal{A},\mathcal{B}$ be finite alphabets with cardinality at least 2.
By a morphism $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$, we mean a monoid
homomorphism (also called a _substitution_ when $\mathcal{A}=\mathcal{B}$). We
will always assume that $\mathcal{B}$ is minimal, i.e. each letter appear in
the image of some word. A morphism is said to be non-erasing if the image of
any letter is a non-empty word. We stress the fact that all morphisms are
assumed to be non-erasing in the following. Using concatenation, we extend
$\sigma$ to $\mathcal{A}^{\mathbb{Z}}$. In particular, if $X$ is a shift space
over $\mathcal{A}$, the image of $X$ under $\sigma$ is the shift space

$\sigma\cdot X:=\\{S^{k}\sigma(x)\mid x\in X,0\leq k<|\sigma(x_{0})|\\}.$

In general, it can be difficult to deduce extension graphs of words in
$\mathcal{L}(\sigma\cdot X)$ from those of $\mathcal{L}(X)$. In this paper, we
will restrict ourselves to particular morphisms which offer some nice
recognizability properties. They are defined using the notion of return words.
Let $X$ be a shift space. If $w\in\mathcal{L}(X)$ is non-empty, a _return
word_ to $w$ in $X$ is a non-empty word $r$ such that $rw\in\mathcal{L}(X)$
and $rw$ contains exactly two occurrences of $w$, one as a prefix and one as a
suffix.

######  Definition 4.

A _return morphism for a word_ $w\in\mathcal{B}^{+}$ is an injective morphism
$\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ such that, for all
$a\in\mathcal{A}$, $\sigma(a)w$ contains exactly two occurrences of $w$, one
as a (proper) prefix and one as a (proper) suffix.

In particular, the set $\sigma(\mathcal{A})$ is then a suffix code, i.e.
$\sigma(a)$ is not a suffix of $\sigma(b)$ if $b\neq a$. Hence, injectivity on
the letters is equivalent to injectivity on the words.

######  Example 5.

The morphism $\sigma:0\mapsto 01,1\mapsto 010,2\mapsto 0102$ is a return
morphism for $01$ and it is also a return morphism for $010$.

As we have seen in the previous example, the word $w$ for which $\sigma$ is a
return morphism is not always unique. However, we have the following result.

######  Proposition 6.

Let $\sigma$ be a return morphism for two distinct words $w$ and $w^{\prime}$
and let $X$ be a shift space. If $|w|\leq|w^{\prime}|$, then

  1. (1)

$w$ is a proper prefix of $w^{\prime}$;

  2. (2)

$\sigma$ is a return morphism for all prefixes of $w^{\prime}$ of length at
least $|w|$;

  3. (3)

$w$ is not right special in $\sigma\cdot X$;

  4. (4)

if $w^{\prime}$ is of maximal length, it is right special in $\sigma\cdot X$.

###### Proof.

  1. (1)

Let $a\in\mathcal{A}$. If $|w|\leq|\sigma(a)|$, then $w$ is a prefix of
$\sigma(a)$. As $w^{\prime}$ is also prefix of $\sigma(a)w^{\prime}$ and
$|w|\leq|w^{\prime}|$, $w$ is a proper prefix of $w^{\prime}$. Otherwise,
$|w^{\prime}|\geq|w|>|\sigma(a)|$ and both $w$ and $w^{\prime}$ are of the
form $(\sigma(a))^{n}p$, where $p$ is a prefix of $\sigma(a)$. Thus $w$ is a
proper prefix of $w^{\prime}$.

  2. (2)

Let $wu$ be a prefix of $w^{\prime}$. By definition, it is a prefix and a
suffix of $\sigma(a)wu$ for all $a\in\mathcal{A}$. Moreover, since $w$ only
has two occurrences in $\sigma(a)w$, $wu$ only has two occurrences in
$\sigma(a)wu$ thus $\sigma$ is a return morphism for $wu$.

  3. (3)

Since $\sigma$ is a return morphism for $w$, any occurrence of $w$ in
$\sigma\cdot X$ is as a proper prefix of some $\sigma(a)w$ for
$a\in\mathcal{A}$. However, for all $a\in\mathcal{A}$, $w^{\prime}$ is a
prefix of $\sigma(a)w^{\prime}$ thus $ww^{\prime}_{|w|+1}$ is a prefix of
$\sigma(a)w$. The only right extension of $w$ is then $w^{\prime}_{|w|+1}$.

  4. (4)

Assume that $w^{\prime}$ only has one right extension $b$. Thus $w^{\prime}b$
is a prefix (and a suffix) of each $\sigma(a)w^{\prime}b$, $a\in\mathcal{A}$.
As $w^{\prime}$ only has two occurrences in $\sigma(a)w^{\prime}$, the word
$w^{\prime}b$ only has two occurrences in $\sigma(a)w^{\prime}b$, which proves
that $\sigma$ is a return morphism for $w^{\prime}b$, a contradiction.

∎

We will sometimes talk about a _return morphism_ without specifying the word
$w$ for which it is a return morphism. By default, this $w$ will be chosen of
maximal length. Because of the previous proposition, most results are
independent of this choice (or only depend in a minor way).

We now give a description of the extension graphs in $\sigma\cdot X$ when
$\sigma$ is a return morphism. We first introduce some notations.

######  Definition 7.

Let $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a return morphism for the
word $w\in\mathcal{B}^{+}$. For all $u\in\mathcal{B}^{*}$, we define the sets

$\mathcal{A}^{L}_{\sigma,u}=\\{a\in\mathcal{A}\mid\sigma(a)\in\mathcal{B}^{+}u\\}$

and

$\mathcal{A}^{R}_{\sigma,u}=\\{a\in\mathcal{A}\mid\sigma(a)w\in
u\mathcal{B}^{+}\\}.$

For a shift $X$ over $\mathcal{A}$ and a word $v\in\mathcal{L}(X)$, we then
note
$E_{X,s,p}(v)=E_{X}(v)\cap(\mathcal{A}^{L}_{\sigma,s}\times\mathcal{A}^{R}_{\sigma,p})$.

######  Proposition 8.

Let $X$ be a shift space over $\mathcal{A}$,
$\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ a return morphism for the word $w$
and $Y=\sigma\cdot X$.

  * •

If $u\in\mathcal{L}(Y)$ is such that $|u|_{w}=0$, then

$\mathcal{E}_{Y}(u)=\mathcal{E}_{\mathcal{L}(\sigma)}(u),$

where we define

$\mathcal{L}(\sigma)=\bigcup_{a\in\mathcal{A}}\mathcal{L}(\sigma(a)w).$

  * •

If $u\in\mathcal{L}(Y)$ is such that $|u|_{w}>0$, then there exists a unique
triplet $(s,v,p)\in\mathcal{B}^{*}\times\mathcal{L}(X)\times w\mathcal{B}^{*}$
such that $u=s\sigma(v)p$ and for which the set $E_{X,s,p}(v)$ is not empty.
The bi-extensions of $u$ are then governed by those of $v$ through the
equation

(2)
$E_{Y}(u)=\\{(a^{\prime},b^{\prime})\in\mathcal{B}\times\mathcal{B}\mid\exists(a,b)\in
E_{X,s,p}(v):\sigma(a)\in\mathcal{B}^{*}a^{\prime}s\wedge\sigma(b)w\in
pb^{\prime}\mathcal{B}^{*}\\}.$

###### Proof.

Let us prove the first case. For any $(b,c)\in E_{Y}(u)$, there exist a letter
$a$ and a word $v\in\mathcal{L}(X)$ such that $buc$ is a factor of
$\sigma(a)\sigma(v)$. We can moreover assume that the first occurrence of
$buc$ begins in $\sigma(a)$. Since $w$ is not a factor of $u$ and $\sigma(v)$
is prefix comparable with $w$, i.e. $\sigma(v)$ is either a prefix of $w$ or
has $w$ as a prefix, we deduce that $buc$ is a factor of $\sigma(a)w$. This
proves that $(b,c)\in E_{\mathcal{L}(\sigma)}(u)$. By definition,
$\mathcal{L}(\sigma)$ is included in $\mathcal{L}(Y)$ and we conclude that
$\mathcal{E}_{Y}(u)=\mathcal{E}_{\mathcal{L}(\sigma)}(u)$.

For the second case, the proof is similar to the proof of [29, Proposition
4.1]. ∎

Under the assumptions of the previous result, the words $u$ that do not
contain any occurrence of $w$ are the _$\sigma$ -initial factors_ of $Y$. As
they and their extension graphs only depend on $\sigma$, we will sometimes
talk about _$\sigma$ -initial factors_ without specifying $Y$. Note that a
different convention for the choice of $w$ leads to a smaller set of
$\sigma$-initial factors. However, by Proposition 6, the set of right special
$\sigma$-initial factors is the same.

Whenever $u$ and $v$ are as in the second case of the previous proposition,
$v$ is called the _antecedent_ of $u$ under $\sigma$ and $u$ is said to be an
_extended image_ of $v$.

Thus, any factor of $Y$ is either $\sigma$-initial or an extended image of
some factor in $X$. Using Proposition 8, we directly know when the
$\sigma$-initial factors of $Y$ are dendric. It only depends on $\sigma$ and
not on $X$. We introduce the following definition.

######  Definition 9.

A return morphism $\sigma$ is _dendric_ if every $\sigma$-initial factor is
dendric in $\mathcal{L}(\sigma)$.

Note that, by Proposition 6 and because the proof of Proposition 8 works for
any choice of $w$, the fact that a return morphism for $w$ is dendric is
independent of the choice of $w$.

######  Example 10.

The morphism $\beta:0\mapsto 0,1\mapsto 01,2\mapsto 02,3\mapsto 032$ is a
return morphism for $0$. Its $\beta$-initial factors are $\varepsilon$, $1$,
$2$, $3$ and $32$. Note that the only one which is right special is
$\varepsilon$ and we can easily check that it is dendric thus $\beta$ is a
dendric return morphism.

We will now use the second item of Proposition 8 to characterize the fact that
all the extended images are dendric in $Y$. Equation 2 can also be seen in
terms of extension graphs. To do that, we introduce two types of (partial)
maps.

######  Definition 11.

Let $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a return morphism for the
word $w$. For $s,p\in\mathcal{B}^{*}$, we define the partial maps
$\varphi^{L}_{\sigma,s},\varphi^{R}_{\sigma,p}:\mathcal{A}\to\mathcal{B}$ as
follows:

  1. (1)

for $a\in\mathcal{A}^{L}_{\sigma,s}$, $\varphi^{L}_{\sigma,s}(a)$ is the
letter $a^{\prime}$ such that $\sigma(a)\in\mathcal{B}^{*}a^{\prime}s$;

  2. (2)

for $b\in\mathcal{A}^{R}_{\sigma,p}$, $\varphi^{R}_{\sigma,p}(b)$ is the
letter $b^{\prime}$ such that $\sigma(b)w\in pb^{\prime}\mathcal{B}^{*}$.

We denote by $\mathcal{E}_{X,s,p}(v)$ the subgraph of $\mathcal{E}_{X}(v)$
generated by the edges in $E_{X,s,p}(v)$. Remark that, with this definition,
no vertex is isolated. In particular, the set of vertices might be strictly
included in the disjoint union of $E_{X}^{L}(v)\cap\mathcal{A}_{\sigma,s}^{L}$
and $E_{X}^{R}(v)\cap\mathcal{A}_{\sigma,p}^{R}$.

The following proposition then directly follows from Equation 2.

######  Proposition 12.

Let $X$ be a shift space over $\mathcal{A}$,
$\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ a return morphism for the word $w$,
$Y=\sigma\cdot X$ and $u\in\mathcal{L}(Y)$ such that $|u|_{w}>0$. If $(s,v,p)$
is the triplet given by Proposition 8, then the extension graph of $u$ in $Y$
is the image of the graph $\mathcal{E}_{X,s,p}(v)$ by the morphisms
$\varphi^{L}_{\sigma,s}$ acting on the left vertices and
$\varphi^{R}_{\sigma,p}$ acting on the right vertices.

Remark that, as a consequence,
$E^{L}_{Y}(u)\subset\varphi^{L}_{\sigma,s}(E^{L}_{X}(v))$ and
$E^{R}_{Y}(u)\subset\varphi^{R}_{\sigma,p}(E^{R}_{X}(v))$. In particular, if
$u$ is left (resp., right) special, $v$ is also left (resp., right) special
and there exist two distinct letters $a,b\in\mathcal{A}$ and two distinct
letters $a^{\prime},b^{\prime}\in\mathcal{B}$ such that

$\sigma(a)\in\mathcal{B}^{*}a^{\prime}s,\quad\sigma(b)\in\mathcal{B}^{*}b^{\prime}s$
$\text{(resp., }\sigma(a)w\in pa^{\prime}\mathcal{B}^{*},\quad\sigma(b)w\in
pb^{\prime}\mathcal{B}^{*}\text{)}.$

This observation motivates the following definition.

######  Definition 13.

Let $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a return morphism for the
word $w$. For two distinct letters $a,b\in\mathcal{A}$, we denote by
$s_{\sigma}(a,b)$ the longest common suffix of $\sigma(a)$ and $\sigma(b)$ and
by $p_{\sigma}(a,b)$ the longest common prefix of $\sigma(a)w$ and
$\sigma(b)w$. Finally, we define the two sets

$\mathcal{T}^{L}(\sigma)=\\{s_{\sigma}(a,b)\mid a,b\in\mathcal{A},a\neq b\\}$

and

$\mathcal{T}^{R}(\sigma)=\\{p_{\sigma}(a,b)\mid a,b\in\mathcal{A},a\neq b\\}.$

The following result is [29, Proposition 4.8].

######  Proposition 14.

Let $X$ be a shift space over $\mathcal{A}$,
$\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ a return morphism, $Y=\sigma\cdot
X$ and $v\in\mathcal{L}(X)$ a dendric factor. All the extended images of $v$
under $\sigma$ are dendric in $Y$ if and only if the following conditions are
satisfied

  1. (1)

for every $s\in\mathcal{T}^{L}(\sigma)$, $\mathcal{E}_{X,s,\varepsilon}(v)$ is
connected;

  2. (2)

for every $p\in\mathcal{T}^{R}(\sigma)$, $\mathcal{E}_{X,\varepsilon,p}(v)$ is
connected.

######  Remark 15.

Recall that a word $v\in\mathcal{L}(X)$ is ordinary if there exist
$a,b\in\mathcal{A}$ such that
$E_{X}(v)=(E^{L}_{X}(v)\times\\{b\\})\cup(\\{a\\}\times E^{R}_{X}(v))$. In
this case, for all $s\in\mathcal{T}^{L}(\sigma)$ (resp.,
$p\in\mathcal{T}^{R}(\sigma)$), the graph $\mathcal{E}_{X,s,\varepsilon}(v)$
(resp., $\mathcal{E}_{X,\varepsilon,p}(v)$) is connected (or empty). Thus $v$
only has dendric extended images. In fact, one can see using Proposition 12
that $v$ only has ordinary extended images.

As a direct consequence of Propositions 8 and 14, we can determine when the
image of a dendric shift under a return morphism is dendric.

######  Proposition 16.

Let $X$ be a dendric shift over $\mathcal{A}$ and
$\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a return morphism. The shift
space $Y=\sigma\cdot X$ is dendric if and only if $\sigma$ is dendric and, for
all $v\in\mathcal{L}(X)$, for all $s\in\mathcal{T}^{L}(\sigma)$ and for all
$p\in\mathcal{T}^{R}(\sigma)$, the graphs $\mathcal{E}_{X,s,\varepsilon}(v)$
and $\mathcal{E}_{X,\varepsilon,p}(v)$ are connected.

In particular, by Remark 15, the image of an Arnoux-Rauzy shift under a return
morphism is dendric if and only if the morphism is dendric.

In the case of an eventually dendric shift, we recall the following
characterization.

######  Proposition 17 (Dolce and Perrin [18]).

Let $X$ be a shift space over $\mathcal{A}$. The following properties are
equivalent.

  1. (1)

The shift $X$ is eventually dendric.

  2. (2)

There exists $N\in\mathbb{N}$ such that for any left special word
$v\in\mathcal{L}_{\geq N}(X)$, there exists a unique letter $a\in\mathcal{A}$
such that $va$ is left special. Moreover, $E^{L}_{X}(va)=E^{L}_{X}(v)$.

  3. (3)

There exists $N\in\mathbb{N}$ such that for any right special word
$v\in\mathcal{L}_{\geq N}(X)$, there exists a unique letter $a\in\mathcal{A}$
such that $av$ is right special. Moreover, $E^{R}_{X}(av)=E^{R}_{X}(v)$.

######  Corollary 18.

A shift space $X$ is eventually dendric if and only if any long enough
bispecial factor is ordinary.

Thus, the image of an eventually dendric shift under a return morphism is also
an eventually dendric shift, as stated in the following proposition.

######  Proposition 19.

Let $X$ be an eventually dendric shift over $\mathcal{A}$ and
$\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ a return morphism for $w$. The
shift space $Y=\sigma\cdot X$ is an eventually dendric shift. More precisely,
if $N$ satisfies Proposition 17 for $X$, then $Y$ is eventually dendric of
threshold at most $\max_{a\in\mathcal{A}}|\sigma(a)|(N+1)+|w|-1$.

###### Proof.

Let $K=\max_{a\in\mathcal{A}}|\sigma(a)|$. Every word $u$ in $\mathcal{L}(Y)$
of length at least $K+|w|-1$ contains an occurrence of $w$ and thus, using
Proposition 8, has an antecedent $v\in\mathcal{L}(X)$. Furthermore, since $u$
is of the form $s\sigma(v)p$, if $u$ is of length at least $K(N+1)+|w|-1$,
then $|\sigma(v)|\geq K(N-1)+1$, so the antecedent $v$ of $u$ is of length at
least $N$. By hypothesis on $N$ and by Remark 15, $v$ then only has dendric
extended images thus $u$ is dendric. ∎

##  4\. Other graphs characterizing dendricity

For any shift space, we introduce graphs which describe all the sets of left
or right extensions for factors of length $n$ in the shift space.

######  Definition 20.

Let $X$ be a shift space over $\mathcal{A}$ and $n\geq 0$. The graph
$G^{L}_{n}(X)$ (resp., $G^{R}_{n}(X)$) is the multi-graph with labeled edges
such that

  * •

its vertices are the elements of $\mathcal{A}$,

  * •

for any $v\in\mathcal{L}_{n}(X)$ and any distinct $a,b\in E^{L}_{X}(v)$
(resp., $a,b\in E^{R}_{X}(v)$) there is an (undirected) edge labeled by $v$
between the vertices $a$ and $b$.

######  Example 21.

Let $X$ be the Thue-Morse shift space over $\\{0,1\\}$. The first few graphs
$G^{L}_{n}(X)$ are given in Figure 2.

$G^{L}_{0}(X)$$0$$1$$\varepsilon$$G^{L}_{1}(X)$$0$$1$$1$$0$$G^{L}_{2}(X)$$0$$1$$10$$01$$G^{L}_{3}(X)$$0$$1$$100$$101$$010$$011$
Figure 2. Graphs $G_{n}^{L}(X)$ for $n\in\\{0,\dots,3\\}$.

######  Remark 22.

By definition, the edges are only labeled by left (resp., right) special
factors and the edges with a given label $v$ form a complete subgraph of
$G^{L}_{n}(X)$ (resp., $G^{R}_{n}(X)$). In addition, if $v=v_{1}\cdots v_{n}$
labels an edge between $a$ and $b$ in $G^{L}_{n}(X)$ (resp., $G^{R}_{n}(X)$),
then $v_{1}\cdots v_{k}$ (resp., $v_{n-k+1}\cdots v_{n}$) labels an edge
between $a$ and $b$ in $G^{L}_{k}(X)$ (resp., $G^{R}_{k}(X)$) for all $k\leq
n$.

We now explain the link between the properties of the extension graphs in $X$
and of the graphs $G^{L}_{n}(X)$, $G^{R}_{n}(X)$ regarding both acyclicity and
connectedness. We first need to define a notion of acyclicity for multi-graph
with labeled edges.

######  Definition 23.

A multi-graph with labeled edges $G$ is _acyclic for the labeling_ if any
simple cycle in $G$ only uses edges with the same label.

The following lemma is a direct consequence of the definition of the graphs
$G^{L}_{n+1}(X)$ and $G^{R}_{n+1}(X)$.

######  Lemma 24.

Let $X$ be a shift space and $v\in\mathcal{L}_{n}(X)$. The graph
$\mathcal{E}_{X}(v)$ contains the path
$(a_{1}^{L},b_{1}^{R},a_{2}^{L},\dots,b_{k}^{R},a_{k+1}^{L})$ if and only if
$G^{L}_{n+1}(X)$ contains the path

$a_{1}\xrightarrow{vb_{1}}a_{2}\dots\xrightarrow{vb_{k}}a_{k+1}.$

Symmetrically, the graph $\mathcal{E}_{X}(v)$ contains the path
$(a_{1}^{R},b_{1}^{L},a_{2}^{R},\dots,b_{k}^{L},a_{k+1}^{R})$ if and only if
$G^{R}_{n+1}(X)$ contains the path

$a_{1}\xrightarrow{b_{1}v}a_{2}\dots\xrightarrow{b_{k}v}a_{k+1}.$

######  Proposition 25.

Let $X$ be a shift space and $N\geq 0$. The following properties are
equivalent.

  1. (1)

The graph $\mathcal{E}_{X}(v)$ is acyclic for all $v\in\mathcal{L}_{<N}(X)$.

  2. (2)

The graph $G^{L}_{n}(X)$ (resp. $G^{R}_{n}(X)$) is acyclic for the labeling
for all $n\leq N$.

###### Proof.

Let us show the equivalence with the acyclicity of the graphs $G^{L}_{n}(X)$
by contraposition. The result with the graphs $G^{R}_{n}(X)$ is symmetric. If
$v\in\mathcal{L}_{n}(X)$, $n<N$, is such that $\mathcal{E}_{X}(v)$ contains a
(non-trivial) cycle, then $G^{L}_{n+1}(X)$ contains a cycle by Lemma 24 and
the edges of this cycle do not have the same label. For the converse, assume
that $G^{L}_{n}(X)$, $n\leq N$, contains a simple cycle

$a_{1}\xrightarrow{u^{(1)}}a_{2}\dots\xrightarrow{u^{(k)}}a_{1},$

with at least two distinct labels. Let $v$ be the longest common prefix to all
the $u^{(i)}$, $i\leq k$, and, for all $i\leq k$, let $b_{i}$ be the letter
such that $vb_{i}$ is a prefix of $u^{(i)}$. By Remark 22, the graph
$G^{L}_{|v|+1}(X)$ thus contains the cycle

$a_{1}\xrightarrow{vb_{1}}a_{2}\dots\xrightarrow{vb_{k}}a_{1}.$

By definition of $v$, there exist $i<j$ such that $b_{i}\neq b_{j}$. We may
assume that $b_{1}\neq b_{k}$ because, if $b_{1}=b_{k}$, since the subgraph of
$G^{L}_{|v|+1}(X)$ generated by the edges labeled by $vb_{k}$ is a complete
graph, we can consider the path

$a_{2}\xrightarrow{vb_{2}}a_{3}\dots\xrightarrow{vb_{k}}a_{2}$

instead.

By Lemma 24, the graph $\mathcal{E}_{X}(v)$ contains the cycle
$(a_{1}^{L},b_{1}^{R},a_{2}^{L},\dots,b_{k}^{R},a_{1}^{L})$ which is non-
trivial as $b_{1}\neq b_{k}$. ∎

We now look at the connectedness properties.

######  Proposition 26.

Let $X$ be a shift, $N\geq 0$ and $C\subset\mathcal{A}$. If the graph
$\mathcal{E}_{X}(v)$ is acyclic for all $v\in\mathcal{L}_{<N}(X)$, then the
following properties are equivalent.

  1. (1)

For all $v\in\mathcal{L}_{<N}(X)$ and all $a,b\in E^{L}_{X}(v)\cap C$, $a^{L}$
and $b^{L}$ are connected in $\mathcal{E}_{X}(v)$ by a path avoiding vertices
$c^{L}$, $c\notin C$.

  2. (2)

For all $n\leq N$, the subgraph of $G^{L}_{n}(X)$ generated by the vertices in
$C$ is connected.

  3. (3)

The subgraph of $G^{L}_{N}(X)$ generated by the vertices in $C$ is connected.

Similarly, the following are equivalent.

  1. (1)

For all $v\in\mathcal{L}_{<N}(X)$ and all $a,b\in E^{R}_{X}(v)\cap C$, $a^{R}$
and $b^{R}$ are connected in $\mathcal{E}_{X}(v)$ by a path avoiding vertices
$c^{R}$, $c\notin C$.

  2. (2)

For all $n\leq N$, the subgraph of $G^{R}_{n}(X)$ generated by the vertices in
$C$ is connected.

  3. (3)

The subgraph of $G^{R}_{N}(X)$ generated by the vertices in $C$ is connected.

###### Proof.

Let us show the first set of equivalences. We denote by $H_{n}$ the subgraph
of $G^{L}_{n}(X)$ generated by the vertices in $C$. Assume that the first
property is satisfied. We prove that $H_{n}$ is connected by induction on $n$.
The graph $G^{L}_{0}(X)$ is a complete graph thus any subgraph is connected.
If $H_{n}$ is connected, then, to prove that $H_{n+1}$ is also connected, it
suffices to show that any two vertices $a,b\in C$ that were connected by an
edge in $H_{n}$ are connected by a path in $H_{n+1}$. Let $a,b\in C$ be two
such vertices and $v$ be the label of an edge between them. As $a$ and $b$ are
left extensions of $v$, $a^{L}$ and $b^{L}$ are connected in
$\mathcal{E}_{X}(v)$ by a path avoiding vertices $c^{L}$, $c\notin C$. The
vertices $a$ and $b$ are thus connected by a path in $H_{n+1}$ by Lemma 24.
Notice that the acyclic hypothesis is not needed for this implication.

For the converse, let us proceed by contraposition. Let
$v\in\mathcal{L}_{n}(X)$, $n<N$, be such that there exist two letters $a,b\in
E^{L}_{X}(v)\cap C$ such that the vertices $a^{L}$ and $b^{L}$ are not
connected in $\mathcal{E}_{X}(v)$ by a path avoiding vertices $c^{L}$,
$c\notin C$. By definition, there is an edge labeled by $v$ between $a$ and
$b$ in $G^{L}_{n}(X)$ thus, as this graph is acyclic for the labeling by
Proposition 25, any simple path between $a$ and $b$ in $G^{L}_{n}(X)$ only
uses edges labeled by $v$. By Remark 22, any simple path between $a$ and $b$
in $G^{L}_{n+1}(X)$ uses edges labeled by elements of $v\mathcal{A}$. This is
also true for the paths in $H_{n+1}$. However, using Lemma 24, the existence
of such path in $H_{n+1}$ would imply that $a^{L}$ and $b^{L}$ are connected
in $\mathcal{E}_{X}(v)$ by a path avoiding vertices $c^{L}$, $c\notin C$. Thus
$H_{n+1}$ is not connected.

The equivalence between the second and the third properties follows from
Remark 22 as, with any path in $H_{N}$, we can associate a path in $H_{n}$ for
$n\leq N$. ∎

In particular, when $C=\mathcal{A}$, Proposition 26 can be rewritten as
follows.

######  Proposition 27.

Let $X$ be a shift space and $N\geq 0$. If the graph $\mathcal{E}_{X}(v)$ is
acyclic for all $v\in\mathcal{L}_{<N}(X)$, then the following properties are
equivalent.

  1. (1)

The graph $\mathcal{E}_{X}(v)$ is connected for all $v\in\mathcal{L}_{<N}(X)$.

  2. (2)

The graph $G^{L}_{n}(X)$ (resp., $G^{R}_{n}(X)$) is connected for all $n\leq
N$.

  3. (3)

The graph $G^{L}_{N}(X)$ (resp., $G^{R}_{N}(X)$) is connected.

######  Remark 28.

The result is false if we remove the acyclic hypothesis. Indeed, if $X$ is
such that $\mathcal{L}_{3}(X)=\\{001,010,011,100,110,111\\}$, then the graph
$\mathcal{E}_{X}(0)$ is not connected. However, $G^{L}_{2}(X)$ is and, indeed,
the graph $\mathcal{E}_{X}(\varepsilon)$ contains a cycle (see Figure 3) thus
this does not contradict the previous result.

$\mathcal{E}(0)$$0$$1$$1$$0$$G^{L}_{2}(X)$$0$$1$$10$$11$$\mathcal{E}(\varepsilon)$$0$$1$$0$$1$
Figure 3. The acyclicity of $\mathcal{E}_{X}(v)$ is necessary in Proposition
27.

As a direct consequence of Proposition 25 and Proposition 27, we obtain the
following characterization of dendric shifts.

######  Corollary 29.

A shift space $X$ is dendric if and only if, for all $n\in\mathbb{N}$, the
graph $G^{L}_{n}(X)$ (resp., $G^{R}_{n}(X)$) is acyclic for the labeling and
connected.

##  5\. Stabilization and eventually dendric shifts

In the rest of the paper, we will be interested in whether two edges have the
same label or not more than in the actual label of the edges. We will thus
identify two multi-graphs $G$ and $G^{\prime}$ with edges labeled by elements
of $C$ and $C^{\prime}$ respectively if they both have the same set of
vertices and if there exists a bijection $\varphi:C\to C^{\prime}$ such that
there are $k$ edges labeled by $c\in C$ between $a$ and $b$ in $G$ if and only
if there are $k$ edges labeled by $\varphi(c)$ between $a$ and $b$ in
$G^{\prime}$.

To make the distinction clearer, we will talk about multi-graphs with
_colored_ edges instead of labeled edges. We can naturally extend the notion
of acyclicity for the labeling to acyclicity for the coloring.

Among the multi-graphs with colored edges, we will mainly be interested in
graphs that can correspond to $G^{L}_{n}(X)$ (or $G^{R}_{n}(X)$) for some
shift space $X$. These graphs are exactly the ones that can be constructed as
follows.

######  Definition 30.

A multi-graph $G$ with colored edges and with set of vertices $V$ is _multi-
clique_ if there exist subsets $C_{1},\dots,C_{k}$ of $V$ such that the set of
edges is the union of the sets of colored edges $\left((C_{i}\times
C_{i})\setminus\operatorname{diag}(C_{i})\right)\times\\{c_{i}\\}$, $i\leq k$,
where $c_{i}$ is the color of the edges and $c_{1},\dots,c_{k}$ are distinct
colors. The multi-clique $G$ is then denoted $G(\\{C_{1},\dots,C_{k}\\})$.

######  Example 31.

If $C=\\{0,1,2,3\\}$, $C_{1}=\\{0,1\\}$, $C_{2}=\\{1,2,3\\}$,
$C_{3}=\\{0,3\\}$, the multi-clique $G(\\{C_{1},C_{2},C_{3}\\})$ is
represented in Figure 4. It is not acyclic from the coloring because of the
cycle $0,1,3,0$.

$0$$1$$2$$3$ Figure 4. Multi-clique $G(\\{\\{0,1\\},\\{1,2,3\\},\\{0,3\\}\\})$

With this definition, the colored version of $G^{L}_{n}(X)$ is the graph
$G(\\{E^{L}_{X}(v):v\in\mathcal{L}_{n}(X)\\})$. Remark that if
$\operatorname{Card}(C_{i})\leq 1$, then
$G(\\{C_{1},\dots,C_{k}\\})=G(\\{C_{1},\dots,C_{k}\\}\setminus\\{C_{i}\\})$
and, in particular, this shows once again that it suffices to consider the
left-special factors to build $G^{L}_{n}(X)$.

In the case where the shift space $X$ is eventually dendric, the graphs
$G^{L}_{n}(X)$ (resp., $G^{R}_{n}(X)$) are eventually constant, when seen as
multi-graphs with colored edges. This is stated in the following result.

######  Proposition 32.

Let $X$ be an eventually dendric shift. There exists $N\in\mathbb{N}$ such
that, for all $n\geq N$,

$G(\\{E^{L}_{X}(v)\mid v\in\mathcal{L}_{n}(X)\\})=G(\\{E^{L}_{X}(v)\mid
v\in\mathcal{L}_{N}(X)\\})$ $\text{(resp., }G(\\{E^{R}_{X}(v)\mid
v\in\mathcal{L}_{n}(X)\\})=G(\\{E^{R}_{X}(v)\mid
v\in\mathcal{L}_{N}(X)\\}\text{).}$

###### Proof.

It suffices to take $N$ satisfying condition 2 (resp., condition 3) of
Proposition 17. ∎

The previous result is not an equivalence as there exist non eventually
dendric shift spaces $X$ whose graphs $G^{L}_{n}(X)$ and $G^{R}_{n}(X)$ are
eventually constant, when seen as multi-graphs with colored edges. This is the
case of the following example.

######  Example 33.

The Chacon ternary shift space over $\\{0,1,2\\}$ is generated by the morphism
$\sigma:0\mapsto 0012,1\mapsto 12,2\mapsto 012$. It is of complexity $2n+1$
[28] thus, by Proposition 2, for each length $n$, there is either a unique
left special word with three extensions or two left special words with two
extensions each. The graph $G^{L}_{n}(X)$ then contains three or two edges
respectively. Since the graph $G^{L}_{1}(X)$ only contains two edges between
$0$ and $2$ (labeled by $0$ and $1$), using Remark 22, it will be the case of
$G^{L}_{n}(X)$ for all $n\geq 1$. We can similarly show that the graphs
$G^{R}_{n}(X)$ correspond to the same colored graph for all $n\geq 1$.
However, the Chacon shift space is not eventually dendric [18].

We can however show that, if $X$ is eventually connected, i.e. the extension
graph of any long enough factor is connected, and if the graphs $G^{L}_{n}(X)$
or $G^{R}_{n}(X)$ are eventually constant, then $X$ is eventually dendric.

######  Definition 34.

Let $X$ be an eventually dendric shift. The graph $G^{L}(X)$ (resp.,
$G^{R}(X)$) is the graph $G(\\{E^{L}_{X}(v)\mid v\in\mathcal{L}_{N}(X)\\})$
(resp., $G(\\{E^{R}_{X}(v)\mid v\in\mathcal{L}_{N}(X)\\})$) where $N$ is as in
Proposition 32.

######  Remark 35.

Another way to see the graph $G^{L}(X)$ is to consider the right infinite
words and their left extensions. More precisely, for a right infinite word
$x$, we denote by $E^{L}_{X}(x)$ the set of letters $a$ such that
$\mathcal{L}(ax)\subset\mathcal{L}(X)$. We then have

$G^{L}(X)=G(\\{E^{R}_{X}(x)\mid x\in\mathcal{A}^{\mathbb{N}}\\}).$

This is also related to the notion of asymptotic equivalence. Indeed, each
edge of $G^{L}(X)$ corresponds to a (right) asymptotic pair, i.e. two elements
$x,y\in X$ such that $x_{n}=y_{n}$ for each $n\geq 0$ and $x_{-1}\neq y_{-1}$.

By Corollary 29, if $X$ is a dendric shift, then $G^{L}(X)$ and $G^{R}(X)$ are
acyclic for the coloring and connected. However, the converse is not true, as
can be seen in the following example.

######  Example 36.

Let $\sigma$ be the morphism defined by $\sigma(0)=0110$ and $\sigma(1)=011$.
It is a return morphism for $01$. Let $X$ be the image under $\sigma$ of a
Sturmian shift. It is not a dendric shift space since the graph
$\mathcal{E}_{X}(\varepsilon)$ contains a cycle but, by Remark 15, $X$ is
eventually dendric with threshold at most 4. We can then show that the only
words which are not dendric are $\varepsilon$ and $1$ thus
$G^{L}(X)=G^{L}_{2}(X)$ and $G^{R}(X)=G^{R}_{2}(X)$. These graphs are acyclic
for the coloring and connected since $01$ (resp., $10$) is the only left
(resp., right) special word of length 2.

##  6\. Action of morphisms on $G^{L}(X)$ and $G^{R}(X)$

In this section, we use the graphs $G^{L}(X)$ and $G^{R}(X)$ to study the
action of a return morphism on a dendric shift $X$. We first show that these
graphs contain all the information needed to know whether the image $Y$ of $X$
under a return morphism is dendric. This gives us a simpler formulation for
Proposition 16. We then explain how to use these graphs to obtain $G^{L}(Y)$
and $G^{R}(Y)$.

######  Definition 37.

Let $G$ be a multi-graph (with colored or uncolored edges) with set of
vertices $\mathcal{A}$ and $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a
return morphism for $w$. For all $s\in\mathcal{T}^{L}(\sigma)$, we define the
graph $G^{L}_{\sigma,s}$ as the subgraph of $G$ generated by the vertices in
$\mathcal{A}^{L}_{\sigma,s}$. Similarly, for all
$p\in\mathcal{T}^{R}(\sigma)$, the graph $G^{R}_{\sigma,p}$ is the subgraph of
$G$ generated by the vertices in $\mathcal{A}^{R}_{\sigma,p}$.

If $X$ is an eventually dendric shift over $\mathcal{A}$, we will write
$G^{L}_{\sigma,s}(X)$ instead of $(G^{L}(X))^{L}_{\sigma,s}$ and
$G^{R}_{\sigma,s}(X)$ instead of $(G^{R}(X))^{R}_{\sigma,s}$.

######  Proposition 38.

Let $X$ be a dendric shift space and $\sigma$ a return morphism. The image $Y$
of $X$ under $\sigma$ is dendric if and only if $\sigma$ is dendric and for
all $s\in\mathcal{T}^{L}(\sigma)$ and all $p\in\mathcal{T}^{R}(\sigma)$, the
graphs $G^{L}_{\sigma,s}(X)$ and $G^{R}_{\sigma,p}(X)$ are connected.

###### Proof.

As $G_{n}^{L}(X)=G^{L}(X)$ for all large enough $n$, the graphs
$\mathcal{E}_{X,s,\varepsilon}(v)$ and $\mathcal{E}_{X,\varepsilon,p}(v)$ are
connected for all $v\in\mathcal{L}(X)$ if and only if $G^{L}_{\sigma,s}(X)$
and $G^{R}_{\sigma,p}(X)$ are connected. Indeed, it is a direct consequence of
Proposition 26 with $C=\mathcal{A}^{L}_{\sigma,s}$ and
$C=\mathcal{A}^{R}_{\sigma,p}$ respectively. The conclusion then follows from
Proposition 16. ∎

######  Definition 39.

Let $G$ be the multi-clique $G(\\{C_{1},\dots,C_{k}\\})$ with set of vertices
$\mathcal{A}$ and $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a return
morphism. The _left image_ of $G$ by $\sigma$ is the multi-clique

$\sigma^{L}(G)=G(\\{\varphi^{L}_{\sigma,s}(C_{i})\mid i\leq
k,s\in\mathcal{T}^{L}(\sigma)\\})$

where the set of vertices is $\mathcal{B}$ and the _right image_ of $G$ by
$\sigma$ is the multi-clique

$\sigma^{R}(G)=G(\\{\varphi^{R}_{\sigma,p}(C_{i})\mid i\leq
k,p\in\mathcal{T}^{R}(\sigma)\\})$

where the set of vertices is $\mathcal{B}$.

######  Example 40.

Let $\beta:0\mapsto 0,1\mapsto 01,2\mapsto 02,3\mapsto 032$ be the morphism of
Example 10. We have $\mathcal{T}^{L}(\beta)=\\{\varepsilon,2\\}$ and the
associated partial maps are given by

$\varphi^{L}_{\beta,\varepsilon}:\begin{cases}\;\,0&\\!\\!\\!\mapsto 0\\\
\;\,1&\\!\\!\\!\mapsto 1\\\ 2,3&\\!\\!\\!\mapsto
2\end{cases}\qquad\text{and}\qquad\varphi^{L}_{\beta,2}:\begin{cases}2\mapsto
0\\\ 3\mapsto 3.\end{cases}$

If $G=G(\\{\\{0,1\\},\\{1,2,3\\}\\})$, then we have

$\displaystyle\beta^{L}(G)$
$\displaystyle=G\left(\left\\{\varphi^{L}_{\beta,\varepsilon}(\\{0,1\\}),\varphi^{L}_{\beta,\varepsilon}(\\{1,2,3\\}),\varphi^{L}_{\beta,2}(\\{0,1\\}),\varphi^{L}_{\beta,2}(\\{1,2,3\\})\right\\}\right)$
$\displaystyle=G(\\{\\{0,1\\},\\{1,2\\},\\{0,3\\}\\}).$

The graphs are represented in Figure 5.

$0$$1$$2$$3$$0$$1$$2$$3$ Figure 5. Graphs $G=G(\\{\\{0,1\\},\\{1,2,3\\}\\})$
(on the left) and $\beta^{L}(G)$ (on the right)

######  Proposition 41.

Let $X$ be an eventually dendric shift and $\sigma$ a return morphism for $w$.
If $Y=\sigma\cdot X$, then $G^{L}(Y)=\sigma^{L}(G^{L}(X))$ and
$G^{R}(Y)=\sigma^{R}(G^{R}(X))$.

###### Proof.

Let us prove the link between $G^{L}(X)$ and $G^{L}(Y)$. By Proposition 19,
$Y$ is also eventually dendric. If we write
$m=\max\\{|\sigma(a)|:a\in\mathcal{A}\\}$, let $N\in\mathbb{N}$ (resp.,
$M\in\mathbb{N}$) be large enough so that $N$ (resp., $M-m$) satisfies the
condition 2 of Proposition 17 for the shift $X$ (resp., $Y$). Let us also
assume that the antecedent of any word $u\in\mathcal{L}(Y)$ of length at least
$M$ is of length at least $N$. By Proposition 32, $G^{L}(X)$ (resp.,
$G^{L}(Y)$) is constructed with the left special factors of length $N$ (resp.,
$M$).

We define the application $f$ mapping any left special
$u\in\mathcal{L}_{M}(Y)$ to the pair
$(s_{u},v)\in\mathcal{T}^{L}(\sigma)\times\mathcal{L}_{N}(X)$ where
$(s_{u},v_{u},p_{u})$ is the triplet associated with $u$ by Proposition 8 and
$v$ is the prefix of length $N$ of $v_{u}$.

We will prove that $f$ is a bijection between the left special factors of
length $M$ in $Y$ and the set

$D=\\{(s,v)\in\mathcal{T}^{L}(\sigma)\times\mathcal{L}_{N}(X)\mid\operatorname{Card}(\varphi^{L}_{\sigma,s}(E^{L}_{X}(v)))\geq
2\\}.$

We will also show that, if $(s,v)=f(u)$, then

$E^{L}_{Y}(u)=\varphi^{L}_{\sigma,s}(E^{L}_{X}(v))$

which will allow us to conclude since

$\sigma^{L}(G^{L}(X))=G(\\{\varphi^{L}_{\sigma,s}(E^{L}_{X}(v))\mid(s,v)\in
D\\}).$

Note that, if $f(u)=(s,v)$, then $s\sigma(v)w$ is a prefix of $u$, thus, by
Proposition 8,

$E^{L}_{Y}(u)\subset
E^{L}_{Y}(s\sigma(v)w)=\varphi^{L}_{\sigma,s}(E^{L}_{X}(v))$

and $(s,v)$ is in $D$.

The application $f$ is injective. Indeed, if $f(u)=f(u^{\prime})=(s,v)$, then
$s_{u}=s=s_{u^{\prime}}$ and $v$ is a prefix of both $v_{u}$ and
$v_{u^{\prime}}$. However, as $u$ and $u^{\prime}$ are left special, $v_{u}$
and $v_{u^{\prime}}$ must be left special. As they have a common prefix of
length $N$ and $N$ is chosen large enough, it means that one is prefix of the
other. Let us assume that $v_{u}$ is a prefix of $v_{u^{\prime}}$. Then
$s\sigma(v_{u})w$ is a prefix of both $u$ and $u^{\prime}$. Since $u$ is of
length $M$, $s\sigma(v_{u})w$ is a left special factor of length at least
$M-m$ and, as $M$ is large enough, it is prefix of a unique left special
factor of length $M$. This proves that $u=u^{\prime}$ and that $f$ is
injective.

We now prove the surjectivity. For any $(s,v)\in D$, by definition of $N$,
there exists $v^{\prime}\in v\mathcal{A}^{*}$ left special such that
$|s\sigma(v^{\prime})w|\geq M$ and $E^{L}_{X}(v^{\prime})=E^{L}_{X}(v)$. If
$u$ is the prefix of length $M$ of $s\sigma(v^{\prime})w$, then $s_{u}=s$ and
$v_{u}$ is a prefix of $v^{\prime}$ of length at least $N$. Thus $s\sigma(v)w$
is a prefix of $u$. In addition, by Proposition 12,

$E^{L}_{Y}(u)\supset
E^{L}_{Y}(s\sigma(v^{\prime})w)=\varphi_{\sigma,s}^{L}(E^{L}_{X}(v^{\prime}))=\varphi_{\sigma,s}^{L}(E^{L}_{X}(v)).$

In particular, $u$ is left special and $f(u)=(s,v)$. This proves that $f$ is
surjective. Moreover, we have both inclusions thus
$E^{L}_{Y}(u)=\varphi_{\sigma,s}^{L}(E^{L}_{X}(v))$. ∎

##  7\. $S$-adic characterization of minimal dendric shifts

We recall the notion of $S$-adic representation and provide an $S$-adic
characterization of both the dendric and the eventually dendric minimal shift
spaces.

###  7.1. $S$-adic representations

Let
${\boldsymbol{\sigma}}=(\sigma_{n}:\mathcal{A}_{n+1}^{*}\to\mathcal{A}_{n}^{*})_{n\geq
0}$ be a sequence of morphisms such that
$\max_{a\in\mathcal{A}_{n}}|\sigma_{0}\circ\cdots\circ\sigma_{n-1}(a)|$ goes
to infinity when $n$ increases. For $n<N$, we define the morphism
$\sigma_{[n,N)}=\sigma_{n}\circ\sigma_{n+1}\circ\dots\circ\sigma_{N-1}$. The
_language $\mathcal{L}^{(n)}({{\boldsymbol{\sigma}}})$ of level $n$ associated
with ${\boldsymbol{\sigma}}$_ is defined by

$\mathcal{L}^{(n)}({{\boldsymbol{\sigma}}})=\left\\{w\in\mathcal{A}_{n}^{*}\mid\mbox{$w$
occurs in $\sigma_{[n,N)}(a)$ for some $a\in\mathcal{A}_{N}$ and
$N>n$}\right\\}.$

As $\max_{a\in\mathcal{A}_{N}}|\sigma_{[n,N)}(a)|$ goes to infinity when $N$
increases, $\mathcal{L}^{(n)}({{\boldsymbol{\sigma}}})$ defines a non-empty
shift space $X_{{\boldsymbol{\sigma}}}^{(n)}$. More precisely,
$X_{{\boldsymbol{\sigma}}}^{(n)}$ is the set of points
$x\in\mathcal{A}_{n}^{\mathbb{Z}}$ such that
$\mathcal{L}(x)\subset\mathcal{L}^{(n)}({{\boldsymbol{\sigma}}})$. Note that
it may happen that $\mathcal{L}(X_{{\boldsymbol{\sigma}}}^{(n)})$ is strictly
contained in $\mathcal{L}^{(n)}({{\boldsymbol{\sigma}}})$. Also observe that
for all $n$, $X_{{\boldsymbol{\sigma}}}^{(n)}$ is the image of
$X_{{\boldsymbol{\sigma}}}^{(n+1)}$ under $\sigma_{n}$.

We set $X_{{\boldsymbol{\sigma}}}=X_{{\boldsymbol{\sigma}}}^{(0)}$ and call
${\boldsymbol{\sigma}}$ an $S$-adic representation of
$X_{{\boldsymbol{\sigma}}}$.

We say that the sequence ${\boldsymbol{\sigma}}$ is primitive if, for any $n$,
there exists $N>n$ such that for all
$(a,b)\in\mathcal{A}_{n}\times\mathcal{A}_{N}$, $a$ occurs in
$\sigma_{[n,N)}(b)$. Observe that if ${\boldsymbol{\sigma}}$ is primitive,
then $\min_{a\in\mathcal{A}_{n}}|\sigma_{[0,n)}(a)|$ goes to infinity when $n$
increases,
$\mathcal{L}(X_{{\boldsymbol{\sigma}}}^{(n)})=\mathcal{L}^{(n)}({{\boldsymbol{\sigma}}})$,
and $X_{{\boldsymbol{\sigma}}}^{(n)}$ is a minimal shift space (see for
instance [21, Lemma 7]).

Given a minimal shift space $X$ over the alphabet $\mathcal{A}$, we can build
specific $S$-adic representations using return words. Let $w\in\mathcal{L}(X)$
be a non-empty word. Recall that a return word to $w$ in $X$ is a non-empty
word $r$ such that $rw\in\mathcal{L}(X)$ and $rw$ contains exactly two
occurrences of $w$, one as a prefix and one as a suffix.

We let $\mathcal{R}_{X}(w)$ denote the set of return words to $w$ in $X$ and
we omit the subscript $X$ whenever it is clear from the context. The shift
space $X$ being minimal, $\mathcal{R}(w)$ is always finite thus we write
$R_{X}(w)=\\{1,\dots,\operatorname{Card}(\mathcal{R}_{X}(w))\\}$. A morphism
$\sigma:{R(w)}^{*}\to\mathcal{A}^{*}$ is a coding morphism associated with $w$
if $\sigma(R(w))=\mathcal{R}(w)$. It is trivially a return morphism for $w$.

Let us consider the set
$\mathcal{D}_{w}(X)=\\{x\in{R(w)}^{\mathbb{Z}}\mid\sigma(x)\in X\\}$. It is a
minimal shift space, called the derived shift of $X$ (with respect to $w$). We
now show that derivation of minimal shift spaces allows to build primitive
$\mathcal{S}$-adic representations with return morphisms. We inductively
define the sequences $(w_{n})_{n\geq 0}$, $(R_{n})_{n\geq 0}$, $(X_{n})_{n\geq
0}$ and $(\sigma_{n})_{n\geq 0}$ by

  * •

$X_{0}=X$, $R_{0}=\mathcal{A}$ and
$w_{0}\in\mathcal{L}(X)\setminus\\{\varepsilon\\}$;

  * •

for all $n$, $R_{n+1}=R_{X_{n}}(w_{n})$, $\sigma_{n}:R_{n+1}^{*}\to R_{n}^{*}$
is a coding morphism associated with $w_{n}$,
$X_{n+1}=\mathcal{D}_{w_{n}}(X_{n})$ and
$w_{n+1}\in\mathcal{L}(X_{n+1})\setminus\\{\varepsilon\\}$.

Observe that the sequence $(w_{n})_{n\geq 0}$ is not uniquely defined, as well
as the morphism $\sigma_{n}$ (even if $w_{n}$ is fixed). However, to avoid
heavy considerations when we deal with sequences of morphisms obtained in this
way, we will speak about “the” sequence $(\sigma_{n})_{n\geq 0}$ and it is
understood that we may consider any such sequence.

######  Theorem 42 (Durand [20]).

Let $X$ be a minimal shift space. Using the notation defined above, the
sequence of morphisms ${\boldsymbol{\sigma}}=(\sigma_{n}:R_{n+1}^{*}\to
R_{n}^{*})_{n\geq 0}$ is a primitive $S$-adic representation of $X$ using
return morphisms. In particular, for all $n$, we have
$X_{n}=X_{{\boldsymbol{\sigma}}}^{(n)}$.

In the case of minimal dendric shifts, we have stronger properties for the
$S$-adic representation ${\boldsymbol{\sigma}}$. Recall that if
$F_{\mathcal{A}}$ is the free group generated by $\mathcal{A}$, an
automorphism $\alpha$ of $F_{\mathcal{A}}$ is tame if it belongs to the monoid
generated by the permutations of $\mathcal{A}$ and by the elementary
automorphisms

$\begin{cases}a\mapsto ab,\\\ c\mapsto c,&\text{for }c\neq
a,\end{cases}\qquad\text{and}\qquad\begin{cases}a\mapsto ba,\\\ c\mapsto
c,&\text{for }c\neq a.\end{cases}$

######  Theorem 43 (Berthé et al. [8]).

Let $X$ be a minimal dendric shift over the alphabet
$\mathcal{A}=\\{1,\dots,d\\}$. For any $w\in\mathcal{L}(X)$,
$\mathcal{D}_{w}(X)$ is a minimal dendric shift over $\mathcal{A}$ and the
coding morphism associated with $w$ is a tame automorphism of
$F_{\mathcal{A}}$. As a consequence, if
${\boldsymbol{\sigma}}=(\sigma_{n})_{n\geq 0}$ is the primitive directive
sequence of Theorem 42, then all morphisms $\sigma_{n}$ are tame dendric
return morphisms.

The previous result is true for any sequence ${\boldsymbol{\sigma}}$ build as
above. However, some choices for the words $w_{n}$ give additional properties
to the morphisms $\sigma_{n}$.

In particular, if $w_{n}$ is a letter, the morphism $\sigma_{n}$ is _strongly
left proper_ , i.e. the image of each letter begins with the letter $w_{n}$
which does not appear elsewhere. Moreover, we can assume that $w_{n}$ is a
bispecial letter, as shown in the following results. This implies that
$w_{n}\in\mathcal{T}^{R}(\sigma_{n})$ and
$\varepsilon\in\mathcal{T}^{L}(\sigma_{n})$.

######  Lemma 44.

Let $X$ be a minimal shift space over $\mathcal{A}$. If there exist letters
$a_{1},\dots,a_{k}$ such that $a_{i+1}$ is the only right (resp., left)
extension of $a_{i}$ for all $i<k$, and $a_{1}$ is the only right (resp.,
left) extension of $a_{k}$, then $\mathcal{A}=\\{a_{1},\dots,a_{k}\\}$. In
particular, $X$ does not have any right (resp., left) special letter.

######  Proposition 45.

Any minimal shift space $X$ such that the graph $\mathcal{E}_{X}(\varepsilon)$
is connected has a bispecial letter.

###### Proof.

First, notice that, because $\mathcal{E}_{X}(\varepsilon)$ is connected, there
is always a left and a right special letter. Let $a_{1}$ be a right special
letter. If it is bispecial, we can conclude. Otherwise, let $a_{2}$ be its
unique left extension. Using Lemma 44, we know that $a_{2}\neq a_{1}$. In the
graph $\mathcal{E}_{X}(\varepsilon)$, $a_{2}^{L}$ is then the only neighbour
of the vertex $a_{1}^{R}$ but this graph is connected thus the vertex
$a_{2}^{L}$ is of degree at least two and $a_{2}$ is a right special letter.
Once again, if it is left special, we have found a bispecial letter and
otherwise it has a unique left extension $a_{3}$. By Lemma 44, we must have
$a_{3}\neq a_{1}$ and $a_{3}\neq a_{2}$. We can iterate the process to define
$a_{4},a_{5},\dots$. However, since the alphabet is finite, it stops at some
point, meaning that we have found a bispecial letter. ∎

###  7.2. Characterization via two graphs

Similarly to what was done in the case of a ternary alphabet in [29], using
the results of Section 6, we can give an $S$-adic characterization of the
minimal dendric shifts on an alphabet $\mathcal{A}$. This characterization
uses two graphs corresponding to the left and the right extensions
respectively.

The edges of these graphs are given by the left (resp., right) valid triplets,
as defined below. Note that we only assume that $\sigma$ is a return morphism
and not a dendric return morphism, even if for the $S$-adic characterization
(Theorem 1), we will restrict ourselves to dendric return morphisms.

######  Definition 46.

Let $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a return morphism. The
triplet $(G^{\prime},\sigma,G)$ is _left (resp., right) valid_ if the
following conditions are satisfied

  1. (1)

$G$ is an acyclic for the coloring and connected multi-clique;

  2. (2)

for all $s\in\mathcal{T}^{L}(\sigma)$, $G^{L}_{\sigma,s}$ is connected (resp.,
for all $p\in\mathcal{T}^{R}(\sigma)$, $G^{R}_{\sigma,p}$ is connected);

  3. (3)

$G^{\prime}=\sigma^{L}(G)$ (resp., $G^{\prime}=\sigma^{R}(G)$) is an acyclic
for the coloring and connected multi-clique.

Note that, if $s\in\mathcal{T}^{L}(\sigma)$ (resp.,
$p\in\mathcal{T}^{R}(\sigma)$) is of minimal length, then $G^{L}_{\sigma,s}=G$
(resp., $G^{R}_{\sigma,p}=G$) thus the second item of Definition 46 implies
that $G$ is connected. Remark also that, if $X$ is dendric, then item 1 is
satisfied for $(G^{L}(\sigma\cdot X),\sigma,G^{L}(X))$ and $(G^{R}(\sigma\cdot
X),\sigma,G^{R}(X))$. Moreover, if $\sigma$ is a dendric return morphism, then
$\sigma\cdot X$ is dendric if and only if item 2 is satisfied for both
triplets by Proposition 38, and in that case, item 3 is also satisfied by
Proposition 41.

######  Example 47.

The morphism $\beta$ of Example 40 is a dendric return morphism such that
$\mathcal{T}^{L}(\beta)=\\{\varepsilon,2\\}$ and
$\mathcal{A}^{L}_{\beta,\varepsilon}=\\{0,1,2,3\\}$,
$\mathcal{A}^{L}_{\beta,2}=\\{2,3\\}$. Thus the triplet
$(\beta^{L}(G),\beta,G)$, where $G=G(\\{0,1\\},\\{1,2,3\\})$ is the graph of
Example 40 is left valid since both graphs are acyclic for the coloring and
connected multi-cliques and $G$ contains the edge $(2,3)$

We can deduce that a shift space is minimal dendric if and only if it has a
primitive $S$-adic representation labeling an infinite path in the graphs
built with the left (resp., right) valid triplets for dendric return
morphisms.

We do not go into more details as we will prove that, instead of considering
all the valid triplets, we can restrict ourselves to the case where the graphs
are _colored trees_ , i.e. all the edges have a different color and the
corresponding uncolored graph is a tree. Note that a colored tree is trivially
acyclic for the coloring and connected. We will often say that the colored
graph itself is a tree and assimilate the colored and the uncolored version.

For two multi-graphs $G$ and $G^{\prime}$ with colored edges, we say that $G$
is a subgraph of $G^{\prime}$ if the uncolored version of $G$ is a subgraph of
the uncolored version of $G^{\prime}$ (but the colors might not coincide).

######  Lemma 48.

If the multi-clique $G=G(\\{C_{1},\dots,C_{k}\\})$ is acyclic for the coloring
and connected and if $D,E$ are such that

$D\cup E=C_{1}\quad\text{and}\quad\operatorname{Card}(D\cap E)=1,$

then the multi-clique $G^{\prime}=G(\\{D,E,C_{2},\dots,C_{k}\\})$ is an
acyclic for the coloring and connected subgraph of $G$.

###### Proof.

Let $\\{c\\}=D\cap E$. By construction, $G^{\prime}$ is a subgraph of $G$ and
any lost edge was between a vertex of $D\setminus\\{c\\}$ and a vertex of
$E\setminus\\{c\\}$. Any two such vertices remain connected through $c$ thus
$G^{\prime}$ is connected. Moreover, any simple cycle of $G^{\prime}$
corresponds to cycle of $G$ thus only uses edges corresponding to one of the
$C_{i}$, $i\leq k$, in $G$. Since $c$ is the only vertex with both ingoing
edges corresponding to $D$ and ingoing edges corresponding to $E$, any simple
cycle using edges from $C_{1}=D\cup E$ only uses edges corresponding to $D$ or
edges corresponding to $E$. The conclusion follows. ∎

######  Proposition 49.

Let $(G^{\prime},\sigma,G)$ be a left (resp., right) valid triplet. For any
covering tree $T^{\prime}$ of $G^{\prime}$, there exists a covering tree $T$
of $G$ such that $(T^{\prime},\sigma,T)$ is left (resp., right) valid.

###### Proof.

We prove the result for left valid triplets. Let
$\mathcal{C}=\\{C_{1},\dots,C_{k}\\}$ be such that $G=G(\mathcal{C})$. Because
$(G^{\prime},\sigma,G)$ is left valid, one has
$G^{\prime}=\sigma^{L}(G)=G(\mathcal{C}^{\prime})$, where
$\mathcal{C}^{\prime}=\\{\varphi^{L}_{\sigma,s}(C_{i})\mid i\leq
k,s\in\mathcal{T}^{L}(\sigma)\\}$.

Assume that either $G$ or $G^{\prime}$ is not a tree. Observe that since
$(G^{\prime},\sigma,G)$ is a left valid triplet, $G$ and $G^{\prime}$ are
connected multi-cliques. Thus if one of them is not a tree, it must contain a
cycle. Whichever of $G$ and $G^{\prime}$ is not a tree, we start by
highlighting a word $s\in\mathcal{T}^{L}(\sigma)$, some set
$C_{i}\in\mathcal{C}$ and two distinct vertices
$a,b\in\varphi^{L}_{\sigma,s}(C_{i})$ as follows.

  * •

If $G^{\prime}$ is not a tree, it contains a cycle. Since
$G^{\prime}=G(\mathcal{C}^{\prime})$ is acyclic for the coloring, there exist
$i\leq k$ and $s\in\mathcal{T}^{L}(\sigma)$ such that
$C=\varphi_{\sigma,s}^{L}(C_{i})$ contains at least 3 elements. The subgraph
$T^{\prime\prime}$ of $T^{\prime}$ generated by the vertices of $C$ is
acyclic. Moreover, for any two vertices in $C$, any path connecting them in
$G^{\prime}$ uses edges corresponding to $C$ as $G^{\prime}$ is acyclic for
the coloring. Thus the path connecting them in $T^{\prime}$ is in
$T^{\prime\prime}$ and $T^{\prime\prime}$ is connected. We choose $a\in C$ to
be a vertex of degree 1 in $T^{\prime\prime}$ and let $b$ be its neighbor in
$T^{\prime\prime}$.

  * •

If $G^{\prime}$ is a tree but $G$ is not, then similarly to the first case,
there exists $i\leq k$ such that $C_{i}$ contains at least 3 elements. Let $s$
be the longest common suffix to all the $\sigma(d)$, $d\in C_{i}$; we have
$s\in\mathcal{T}^{L}(\sigma)$. The set $C=\varphi_{\sigma,s}^{L}(C_{i})$
contains exactly two elements. Indeed, it has at least two elements by
definition of $s$ and, $G^{\prime}$ being a tree, it cannot contain more than
2. Let us write $C=\\{a,b\\}$ with $b$ such that

$\operatorname{Card}(\\{d\in C_{i}\mid\varphi_{\sigma,s}^{L}(d)=b\\})\geq 2.$

In both cases, let $c\in C_{i}$ be such that $\varphi_{\sigma,s}^{L}(c)=b$ and
let us note

$D=\\{c\\}\cup\\{d\in C_{i}\mid\varphi_{\sigma,s}^{L}(d)=a\\}$

and

$E=(C_{i}\setminus D)\cup\\{c\\}.$

We now use Lemma 48 to obtain a new left valid triplet
$(H^{\prime},\sigma,H)$, where

  * •

$H$ is a connected subgraph of $G$;

  * •

$T^{\prime}$ is still a covering tree of $H^{\prime}$;

  * •

the total number of edges in $H$ and $H^{\prime}$ is less than in $G$ and
$G^{\prime}$.

This will end the proof by iterating the construction.

If $\mathcal{D}=\\{D,E,C_{1},\dots,C_{k}\\}\setminus\\{C_{i}\\}$, then by
Lemma 48, the multi-clique $H=G(\mathcal{D})$ is an acyclic for the coloring
and connected subgraph of $G$.

Consider now $\mathcal{D}^{\prime}=\\{\varphi^{L}_{\sigma,s^{\prime}}(F)\mid
F\in\mathcal{D},s^{\prime}\in\mathcal{T}^{L}(\sigma)\\}$ and
$H^{\prime}=G(\mathcal{D}^{\prime})$. We show that the triplet
$(H^{\prime},\sigma,H)$ is left valid, i.e., we show item 2 and 3 of
Definition 46. For any $s^{\prime}\in\mathcal{T}^{L}(\sigma)$, we now show
that $H^{L}_{\sigma,s^{\prime}}$ is connected. Moreover, we describe the sets
$\varphi^{L}_{\sigma,s^{\prime}}(D)$ and $\varphi^{L}_{\sigma,s^{\prime}}(E)$.
Observe that for all $s^{\prime}$, $H^{L}_{\sigma,s^{\prime}}$ is a subgraph
of $G^{L}_{\sigma,s^{\prime}}$ obtained by removing the edges between
$D\setminus\\{c\\}$ and $E\setminus\\{c\\}$.

  * •

If $s^{\prime}=s$, then $c\in\mathcal{A}^{L}_{\sigma,s^{\prime}}$. The graph
$H^{L}_{\sigma,s^{\prime}}$ is connected as any pair of vertices is connected
in $G^{L}_{\sigma,s^{\prime}}$ and a path in $H^{L}_{\sigma,s^{\prime}}$ can
be deduced from the one in $G^{L}_{\sigma,s^{\prime}}$ by replacing an edge
$(d,e)\in(D\setminus\\{c\\})\times(E\setminus\\{c\\})$ by the path $d,c,e$. By
definition of $D$ and $E$,

$\varphi^{L}_{\sigma,s^{\prime}}(D)=\\{a,b\\}\quad\text{and}\quad\varphi^{L}_{\sigma,s^{\prime}}(E)=\varphi^{L}_{\sigma,s^{\prime}}(C_{i})\setminus\\{a\\}=C\setminus\\{a\\}.$

  * •

If $s\in\mathcal{A}^{*}ds^{\prime}$ for some letter $d$, then
$H^{L}_{\sigma,s^{\prime}}$ is connected for the same reason and

$\varphi^{L}_{\sigma,s^{\prime}}(D)=\\{d\\}\quad\text{and}\quad\varphi^{L}_{\sigma,s^{\prime}}(E)=\varphi^{L}_{\sigma,s^{\prime}}(C_{i}).$

  * •

If $s^{\prime}\in\mathcal{A}^{*}as$, then
$\mathcal{A}^{L}_{\sigma,s^{\prime}}\cap E=\emptyset$ and
$\mathcal{A}^{L}_{\sigma,s^{\prime}}\cap
C_{i}=\mathcal{A}^{L}_{\sigma,s^{\prime}}\cap D$ thus no edge was lost from
$G^{L}_{\sigma,s^{\prime}}$ to $H^{L}_{\sigma,s^{\prime}}$. In addition,

$\varphi^{L}_{\sigma,s^{\prime}}(D)=\varphi^{L}_{\sigma,s^{\prime}}(C_{i})\quad\text{and}\quad\varphi^{L}_{\sigma,s^{\prime}}(E)=\emptyset.$

  * •

Otherwise, $as$ and $s^{\prime}$ are not suffix comparable thus
$\mathcal{A}^{L}_{\sigma,s^{\prime}}\cap
C_{i}=\mathcal{A}^{L}_{\sigma,s^{\prime}}\cap E$,
$\mathcal{A}^{L}_{\sigma,s^{\prime}}\cap D\subset\\{c\\}$ and no edge was lost
from $G^{L}_{\sigma,s^{\prime}}$ to $H^{L}_{\sigma,s^{\prime}}$. We have

$\varphi^{L}_{\sigma,s^{\prime}}(D)=\varphi^{L}_{\sigma,s^{\prime}}(\\{c\\})\quad\text{and}\quad\varphi^{L}_{\sigma,s^{\prime}}(E)=\varphi^{L}_{\sigma,s^{\prime}}(C_{i}).$

In particular, we have shown that

$G(\mathcal{D}^{\prime})=G\left(\left(\mathcal{C}^{\prime}\setminus\\{C\\}\right)\cup\\{\\{a,b\\},C\setminus\\{a\\}\\}\right)$

thus, using Lemma 48, the graph

$H^{\prime}=G(\mathcal{D}^{\prime})=\sigma^{L}(H)$

is acyclic for the coloring and connected. This proves that the triplet
$(H^{\prime},\sigma,H)$ is left valid.

We finally show that $T^{\prime}$ is still a subtree of $H^{\prime}$ and that
the total number of edges decreased. By what have just seen, $H^{\prime}$ is a
subgraph of $G^{\prime}$ obtained by removing the edges corresponding to $C$
between $a$ and the elements of $C\setminus\\{a,b\\}$. If $G^{\prime}$ is not
a tree, then $H^{\prime}$ is a strict subgraph of $G^{\prime}$ since $C$
contains at least three elements, and $a$ and $b$ where chosen so that
$T^{\prime}$ is a subtree of $H^{\prime}$. If $G^{\prime}$ is a tree, then
$H^{\prime}=G^{\prime}$ and $H$ is a connected strict subgraph of $G$ as $D$
and $E$ both contain at least two elements. Thus we can iterate the process
until both graphs are trees. ∎

We now define formally the graphs that we will use for the $S$-adic
characterization.

######  Definition 50.

Let $\mathcal{S}$ be a set of return morphisms from $\mathcal{A}^{*}$ to
$\mathcal{A}^{*}$. The graph $\mathcal{G}^{L}(\mathcal{S})$ (resp.,
$\mathcal{G}^{R}(\mathcal{S})$) is defined by

  * •

each vertex corresponds to a tree whose vertices are the elements of
$\mathcal{A}$;

  * •

there is an edge from $T^{\prime}$ to $T$ labeled by $\sigma\in\mathcal{S}$ if
$(T^{\prime},\sigma,T)$ is a left (resp., right) valid triplet.

The proof of the main result of this article uses the following lemma.

######  Lemma 51.

Let $X$ be a dendric shift, $\sigma$ a dendric return morphism and
$Y=\sigma\cdot X$. If there exist a left valid triplet $(G^{\prime},\sigma,G)$
and a right valid triplet $(H^{\prime},\sigma,H)$ such that $G$ is a covering
subgraph of $G^{L}(X)$ and $H$ is a covering subgraph of $G^{R}(X)$, then $Y$
is dendric, $G^{\prime}$ is a covering subgraph of $G^{L}(Y)$ and $H^{\prime}$
is a covering subgraph of $G^{R}(Y)$.

###### Proof.

For all $s\in\mathcal{T}^{L}(\sigma)$, the graph $G^{L}_{\sigma,s}$ is a
covering subgraph of $G^{L}_{\sigma,s}(X)$. Since $(G^{\prime},\sigma,G)$ is
left valid, $G^{L}_{\sigma,s}$ is connected and so is $G^{L}_{\sigma,s}(X)$.
The same reasoning proves that $G^{R}_{\sigma,p}(X)$ is connected for all
$p\in\mathcal{T}^{R}(\sigma)$. By Proposition 38, $Y$ is dendric.

Let us prove that $G^{\prime}$ is a covering subgraph of $G^{L}(Y)$. The proof
for $H^{\prime}$ and $G^{R}(Y)$ is similar. First, notice that $G^{L}(Y)$ and
$G^{\prime}=\sigma^{L}(G)$ have the same set of vertices which is the image
alphabet of $\sigma$. Moreover, they are acyclic for the coloring and multi-
clique thus they are simple. Hence, it suffices to prove that if there is an
edge in $G^{\prime}$, it is also an edge in $G^{L}(Y)$.

Let $(a,b)$ be an edge of $G^{\prime}$ and let $G=G(\\{C_{1},\dots,C_{k}\\})$
and $G^{L}(X)=G(\\{C^{\prime}_{1},\dots,C^{\prime}_{l}\\})$. By definition,
$G^{\prime}=\sigma^{L}(G)$ thus there exist $i\leq k$ and
$s\in\mathcal{T}^{L}(\sigma)$ such that $a,b\in\varphi^{L}_{\sigma,s}(C_{i})$.
In other words, there exist $c,d\in C_{i}$ such that
$\varphi^{L}_{\sigma,s}(c)=a$ and $\varphi^{L}_{\sigma,s}(d)=b$. Since $(c,d)$
is an edge of $G$, it is an edge of $G^{L}(X)$ and there exists $j\leq l$ such
that $c,d\in C^{\prime}_{j}$. We then have
$a,b\in\varphi^{L}_{\sigma,s}(C^{\prime}_{j})$ thus there is an edge between
$a$ and $b$ in $\sigma^{L}(G^{L}(X))$, which is exactly $G^{L}(Y)$ by
Proposition 41. We conclude that $G^{\prime}$ is a covering subgraph of
$G^{L}(Y)$. ∎

We can now prove the main result, that we recall here.

See 1

###### Proof.

Assume that $X$ is minimal dendric. The morphisms of $\mathcal{S}$ being
return morphisms, the sequence ${\boldsymbol{\sigma}}$ is as in Theorem 42 and
thus is primitive. Let us show that ${\boldsymbol{\sigma}}$ labels an infinite
path in $\mathcal{G}^{L}(\mathcal{S})$. Similarly, it will label an infinite
path in $\mathcal{G}^{R}(\mathcal{S})$. For all $n\geq 0$, as
$X_{\boldsymbol{\sigma}}^{(n+1)}$ and $X_{\boldsymbol{\sigma}}^{(n)}$ are
dendric and since $X_{\boldsymbol{\sigma}}^{(n)}$ is the image of
$X_{\boldsymbol{\sigma}}^{(n+1)}$ under $\sigma_{n}$, the triplet
$(G^{L}(X_{\boldsymbol{\sigma}}^{(n)}),\sigma_{n},G^{L}(X_{\boldsymbol{\sigma}}^{(n+1)}))$
is left valid by Proposition 38 and Proposition 41. Let $T_{0}$ be a covering
tree of $G^{L}(X)=G^{L}(X_{\sigma}^{(0)})$. By Proposition 49, there exists a
covering tree $T_{1}$ of $G^{L}(X_{\sigma}^{(1)})$ such that the triplet
$(T_{0},\sigma_{0},T_{1})$ is left valid thus $\sigma_{0}$ labels an edge from
$T_{0}$ to $T_{1}$ in $\mathcal{G}^{L}(\mathcal{S})$. We iterate the process
to obtain an infinite path in $\mathcal{G}^{L}(\mathcal{S})$.

Now assume that ${\boldsymbol{\sigma}}$ is primitive and labels a path
$\left(G^{L}_{n}\right)_{n\geq 0}$ in $\mathcal{G}^{L}(\mathcal{S})$ and a
path $\left(G^{R}_{n}\right)_{n\geq 0}$ in $\mathcal{G}^{R}(\mathcal{S})$. The
shift $X_{\boldsymbol{\sigma}}$ is minimal by primitiveness of
${\boldsymbol{\sigma}}$. Let $u\in\mathcal{L}(X_{\boldsymbol{\sigma}})$ be a
factor. If $u$ is a $\sigma_{0}$-initial factor, then it is dendric since
$\sigma_{0}$ is dendric. Otherwise, there exist a unique $k>0$ and a unique
$v\in\mathcal{L}(X_{\boldsymbol{\sigma}}^{(k)})$ $\sigma_{k}$-initial such
that $u$ is an extended image of $v$ by $\sigma_{0}\dots\sigma_{k-1}$ by
Proposition 8. Let $Y$ be an Arnoux-Rauzy shift and let $Z=\sigma_{k}\cdot Y$.
Since $v$ is $\sigma_{k}$-initial,
$\mathcal{E}_{Z}(v)=\mathcal{E}_{X_{\boldsymbol{\sigma}}^{(k)}}(v)$. The graph
$G^{L}(Y)$ (resp., $G^{R}(Y)$) is the complete (simple and monochromatic)
graph on $\mathcal{A}$, thus $G^{L}_{k+1}$ (resp., $G^{R}_{k+1}$) is a
covering subgraph. By Lemma 51 applied $k+1$ times, we obtain that
$\sigma_{0}\dots\sigma_{k-1}\cdot Z$ is dendric thus, starting with the
extension graph $\mathcal{E}_{Z}(v)$, $v$ only has dendric extended images
under $\sigma_{0}\dots\sigma_{k-1}$ and $u$ is dendric. ∎

By construction, on an alphabet $\mathcal{A}$ of size $d$, the graphs
$\mathcal{G}^{L}(\mathcal{S})$ and $\mathcal{G}^{R}(\mathcal{S})$ have
$d^{d-2}$ vertices (see sequence A000272 on OEIS) each, meaning that if we
take the product of these graphs, we obtain a characterization with a unique
graph $\mathcal{G}(\mathcal{S})$ with $d^{2(d-2)}$ vertices.

However, it is possible to reduce the number of vertices with a clever use of
permutations. Indeed, the vertices of $\mathcal{G}(\mathcal{S})$ are pairs of
labeled trees and some of these pairs are equivalent, in the sense that they
are equal up to a permutation of the letters. Thus, by keeping only one pair
per equivalence class and adding permutations to the morphisms of the set
$\mathcal{S}$, we obtain a smaller graph.

In the case of a ternary alphabet, this allows to replace a graph with 9
vertices by a graph with 2 vertices, as done in [29]. For an alphabet of size
4, we obtain a graph with 14 vertices instead of 256.

###  7.3. An example: $\mathcal{S}$-adic characterization of minimal dendric
shifts with one right special factor of each length

While we do not have an easy description of an explicit set $\mathcal{S}$ for
which any minimal dendric shift (over some fixed alphabet) has an
$\mathcal{S}$-adic representation, restricting ourselves to subfamilies of
minimal dendric shifts allows to build examples. Furthermore, and in
accordance to what was stated in the beginning of the previous subsection, if
we consider all possible multi-cliques as the vertices of
$\mathcal{G}^{L}(\mathcal{S})$ and $\mathcal{G}^{R}(\mathcal{S})$ (and not
just the covering trees), any primitive $\mathcal{S}$-adic representation
${\boldsymbol{\sigma}}$ of $X$ will label, among others, the paths
$(G^{L}(X_{\boldsymbol{\sigma}}^{(n)}))_{n\geq 0}$ and
$(G^{R}(X_{\sigma}^{(n)}))_{n\geq 0}$ (in $\mathcal{G}^{L}(\mathcal{S})$ and
$\mathcal{G}^{R}(\mathcal{S})$ respectively).

We now use this observation to build a graph characterizing the family $F$ of
minimal dendric shift spaces over $\\{0,1,2,3\\}$ having exactly one right
special factor of each length.

Let $X$ be such a shift space. If ${\boldsymbol{\sigma}}$ is an $S$-adic
representation of $X$ (with dendric return morphisms) then, for all $n$, the
shift space $X_{\boldsymbol{\sigma}}^{(n)}$ also has a unique right special
factor of each length. Indeed, $G^{R}(X)$ is the complete monochromatic graph
$K_{4}$ thus, by Proposition 41, $G^{R}(X_{\boldsymbol{\sigma}}^{(1)})$
contains a complete subgraph of size four and, as
$X_{\boldsymbol{\sigma}}^{(1)}$ is dendric, we have
$G^{R}(X_{\boldsymbol{\sigma}}^{(1)})=K_{4}$. Hence,
$X_{\boldsymbol{\sigma}}^{(1)}$ can only have one right special factor of each
length. We iterate for $X_{\boldsymbol{\sigma}}^{(n)}$.

As a consequence, it makes sense to look for an $S$-adic characterization of
$F$ using infinite paths. It also implies that the elements of $F$ have
$\mathcal{S}_{1\text{R}}$-adic representations where $\mathcal{S}_{1\text{R}}$
is the set of dendric return morphisms for a letter which has four right
extensions. These morphisms can easily be found using the possible extension
graphs for the empty word.

######  Example 52.

Assume that the extension graph of the empty word is given by

$0$$1$$2$$3$$0$$1$$2$$3$

The associated Rauzy graph of order 1 is

$0$$1$$2$$3$

and the return words for $0$, corresponding to paths from and to the vertex
$0$, are given by $0$, $01$, $02$ and $032$. Thus, the morphisms of
$\mathcal{S}$ associated with this extension graph are the elements of
$\beta\Sigma_{4}$ where $\beta$ is the morphism of Example 40, i.e.
$\beta:0\mapsto 0,1\mapsto 01,2\mapsto 02,3\mapsto 032$, and $\Sigma_{4}$ is
the set of permutations over $\\{0,1,2,3\\}$.

Up to a permutation of the alphabet, the possible extension graphs (with a
unique right special letter) and their associated morphisms are given in
Figure 6. Notice that, as we take the return morphisms for the only right
special letter, there is, up to a permutation, only one morphism corresponding
to each extension graph. The set $\mathcal{S}_{1\text{R}}$ is then finite and
given by $\Sigma_{4}\\{\alpha,\beta,\gamma,\delta\\}\Sigma_{4}$, where
$\alpha,\beta,\gamma,\delta$ are defined in Figure 6.

$0$$1$$2$$3$$0$$1$$2$$3$ | $0$$1$$2$$3$$0$$1$$2$$3$ | $0$$1$$2$$3$$0$$1$$2$$3$ | $0$$1$$2$$3$$0$$1$$2$$3$
---|---|---|---
| $\alpha:\begin{cases}0\mapsto 0\\\ 1\mapsto 01\\\ 2\mapsto 02\\\ 3\mapsto
03\end{cases}$
---
| $\beta:\begin{cases}0\mapsto 0\\\ 1\mapsto 01\\\ 2\mapsto 02\\\ 3\mapsto
032\end{cases}$
---
| $\gamma:\begin{cases}0\mapsto 0\\\ 1\mapsto 01\\\ 2\mapsto 021\\\ 3\mapsto
031\end{cases}$
---
| $\delta:\begin{cases}0\mapsto 0\\\ 1\mapsto 01\\\ 2\mapsto 021\\\ 3\mapsto
0321\end{cases}$
---
Figure 6. Possible extension graphs of the empty word in a minimal dendric
shift over $\\{0,1,2,3\\}$ and their associated return morphisms.

We now build the graph that will give us the characterization. For the right
side, we consider that the graph $\mathcal{G}^{R}(\mathcal{S}_{1\text{R}})$ is
built with all the right valid triplets. However, as we have observed before,
any $\mathcal{S}_{1\text{R}}$-adic representation ${\boldsymbol{\sigma}}$ of
$X\in F$ labels the path $(G^{R}(X_{\boldsymbol{\sigma}}^{(n)}))_{n\geq
0}=(K_{4})_{n\geq 0}$. We can thus assume that the right side graph is reduced
to the vertex $K_{4}$ without losing $\mathcal{S}_{1\text{R}}$-adic
representations.

For the left side, we consider the usual graph
$\mathcal{G}^{L}(\mathcal{S}_{1\text{R}})$ (with trees as vertices). When
taking the product with the right side graph, we can use permutations and,
since $K_{4}$ is symmetric, this gives us a graph with only two vertices
$(G_{1},K_{4})$ and $(G_{2},K_{4})$ where $G_{1}$ and $G_{2}$ are represented
in Figure 7.

$0$$1$$2$$3$$1$$0$$2$$3$ Figure 7. Graphs $G_{1}$ on the left and $G_{2}$ on
the right

In the end, we obtain that each minimal shift space in $F$ has a primitive
$\mathcal{S}_{1\text{R}}$-adic representation in the graph represented in
Figure 8. Note that, to reduce the number of morphisms, we added a loop on
$(G_{1},K_{4})$ (resp., $(G_{2},K_{4})$) labeled with the permutations that
fix the graph $G_{1}$ (resp., $G_{2}$). We will then consider that
$\mathcal{S}_{1\text{R}}$ also contains the permutations. To improve the
readability of the graph, we also introduce the following notations:
$\Sigma_{\\{1,2,3\\}}$ is the subset of permutations of $\Sigma_{4}$ fixing
$0$, $\pi_{ab}$ stands for the cyclic permutation $(a\ \ b)$ and we define the
following morphisms

$\beta^{\prime}=\beta\pi_{23},\quad\delta^{\prime}=\delta\pi_{23},\quad\gamma^{\prime}=\gamma\pi_{12},\quad\gamma^{\prime\prime}=\pi_{23}\gamma\pi_{23}.$

$(G_{1},K_{4})$$(G_{2},K_{4})$$\Sigma_{4}$$\Sigma_{4}$pt$\Sigma_{\\{1,2,3\\}}$,
$\alpha$, $\pi_{01}\alpha\pi_{01}$, $\pi_{02}\alpha\pi_{02}$,
$\pi_{03}\alpha\pi_{03}$,$\gamma^{\prime}\pi_{02}$,$\delta\pi_{02}$,
$\delta^{\prime}\pi_{02}$pt$\pi_{02}\pi_{13}$,$\alpha$,
$\pi_{01}\alpha\pi_{01}$, $\pi_{02}\alpha\pi_{02}$,
$\pi_{03}\alpha\pi_{03}$,$\pi_{01}\pi_{02}\beta\pi_{01}$,
$\pi_{01}\pi_{02}\beta^{\prime}\pi_{01}$,$\pi_{02}\beta\pi_{03}$,
$\pi_{02}\beta^{\prime}\pi_{03}$,$\gamma\pi_{01}$,$\gamma\pi_{01}\pi_{03}$$\gamma^{\prime\prime}\pi_{01}$,$\gamma^{\prime\prime}\pi_{01}\pi_{03}$$\beta$,
$\beta^{\prime}$,
$\gamma^{\prime}\pi_{01}$,$\gamma^{\prime}\pi_{13}\pi_{01}$$\delta\pi_{01}$,
$\delta^{\prime}\pi_{01}$,$\delta\pi_{03}$,
$\delta^{\prime}\pi_{03}$$\pi_{02}\beta\pi_{02}$,
$\pi_{02}\beta^{\prime}\pi_{02}$,$\gamma\pi_{02}$,
$\gamma^{\prime\prime}\pi_{02}$ Figure 8. A shift space over $\\{0,1,2,3\\}$
is minimal, dendric and has exactly one right special factor of each length if
and only if it has a primitive $\mathcal{S}_{1\text{R}}$-adic representation
labeling an infinite path in this graph.

The converse result is also true, i.e. if a shift space $X$ has a primitive
$\mathcal{S}_{1\text{R}}$-adic representation ${\boldsymbol{\sigma}}$ labeling
an infinite path in the graph of Figure 8, then it is a minimal dendric shift
space over $\\{0,1,2,3\\}$ having exactly one right special factor of each
length. Indeed, it is minimal dendric by the proof of Theorem 1. To conclude,
we show that we can find infinitely many factors having four right extensions
in $X$. This will imply that, for each length, there is a factor having four
right extensions and it must be the unique right special factor since $X$ is
dendric.

It follows from this observation: if $v$ has a left extension $a$ such that
$av$ has four right extensions and if $\sigma\in\mathcal{S}_{1\text{R}}$ is a
return morphism for $\ell$, then the extended image $\sigma(v)\ell$ has a left
extension $b$ such that $b\sigma(v)\ell$ has four right extensions. Indeed, it
suffices to take $b=\varphi^{L}_{\sigma,\varepsilon}(a)$ by Proposition 12 and
by definition of the morphisms of $\mathcal{S}_{1\text{R}}$. For any $k>0$,
starting with $\varepsilon$ in $X_{\boldsymbol{\sigma}}^{(k)}$, we can then
find a word $u\in\mathcal{L}(X)$ of length at least $k$ having four right
extensions.

###  7.4. Characterization of eventually dendric shifts

Using the $S$-adic characterization obtained for minimal dendric shifts, we
can deduce an $S$-adic characterization of minimal eventually dendric shifts.
It is based on the fact that any eventually dendric shift space can be
obtained from a dendric shift space in the following way.

######  Proposition 53.

Let $X$ be a minimal eventually dendric shift space with threshold $N$. For
any non empty $w\in\mathcal{L}(X)$, the derived shift $\mathcal{D}_{w}(X)$ is
eventually dendric with threshold at most $\max\\{0,N-|w|\\}$.

###### Proof.

The proof is almost exactly the same as in the dendric case (see [8, Theorem
5.13]), replacing [8, Proposition 5.7] by [18, Lemma 9.3]. ∎

By [18, Theorem 7.3], if $X$ is eventually dendric and $w$ is of length at
least $N$, $\mathcal{D}_{w}(X)$ is on an alphabet of size
$1+p_{X}(N+1)-p_{X}(N)$.

The next result directly follows from the previous one and from Proposition
19.

######  Theorem 54.

A minimal shift $X$ is eventually dendric if and only if it has a dendric
derived shift, if and only if every derived shift with respect to a long
enough factor of $X$ is dendric.

The $S$-adic characterization of minimal eventually dendric shifts is now a
direct consequence of Theorem 1.

######  Theorem 55.

A shift space is minimal eventually dendric if and only if it has a primitive
$S$-adic representation $(\sigma_{n})_{n\geq 0}$ where $\sigma_{0}$ is a
return morphism, $\sigma_{n}$ is a dendric return morphism for all $n\geq 1$
and $(\sigma_{n})_{n\geq 1}$ labels infinite paths in
$\mathcal{G}^{L}(\mathcal{S})$ and $\mathcal{G}^{R}(\mathcal{S})$ where
$\mathcal{S}=\\{\sigma_{n}:n\geq 1\\}$.

###  7.5. Decidability of eventual dendricity for minimal substitutive shifts

A deeply studied class of shift spaces is the one of substitutive (or morphic)
shifts that roughly correspond to $S$-adic spaces with an eventually periodic
$S$-adic representation. A shift space $X$ is said to be morphic if there
exist morphisms $\sigma:\mathcal{B}^{*}\to\mathcal{B}^{*}$ and
$\tau:\mathcal{B}^{*}\to\mathcal{A}^{*}$ such that

$X=\\{x\in\mathcal{A}^{\mathbb{Z}}\mid\forall u\in\mathcal{L}(x),\exists
b\in\mathcal{B},n\in\mathbb{N}:u\in\mathcal{L}(\tau(\sigma^{n}(b))\\}.$

We let $X(\sigma,\tau)$ denote such a shift. In this section, we show that,
under minimality, (eventual) dendricity is decidable for this class of shift
spaces. Whenever $\tau$ is the identity, the minimality of $X$ is also
decidable [11].

It is classical [15] that we can always suppose that $\sigma$ is non-erasing
($\sigma(a)\neq\varepsilon$ for every letter) and $\tau$ is a coding
($|\tau(a)|=1$ for every letter) so we always make such an assumption.

Observe that one usually considers the restricted version of morphic shifts
consisting in shifts generated by a morphic word. The shift space generated by
an infinite word $x\in\mathcal{A}^{\mathbb{N}}$ is the shift space
$X_{x}=\\{y\in\mathcal{A}^{\mathbb{Z}}\mid\mathcal{L}(y)\subset\mathcal{L}(x)\\}$.
Whenever $x$ is uniformly recurrent (that is, every finite word
$u\in\mathcal{L}(x)$ occurs infinitely many times in $x$ and with bounded
gaps), the shift space $X_{x}$ is minimal. An infinite word $x$ is morphic if
there exist morphisms $\sigma:\mathcal{B}^{*}\to\mathcal{B}^{*}$ and
$\tau:\mathcal{B}^{*}\to\mathcal{A}^{*}$ such that $\sigma$ is prolongable on
some letter $b\in\mathcal{B}$ (that is, $\sigma(b)\in b\mathcal{B}^{*}$ and
$\lim_{n\to+\infty}|\sigma^{n}(b)|=+\infty$) and
$x=\tau(\sigma^{\omega}(b))=\lim_{n\to+\infty}\tau(\sigma^{n}(b^{\omega}))$.
It is also decidable whether a morphic word is uniformly recurrent [23].
Though, the shift space $X_{x}$ could be minimal with $x$ not uniformly
recurrent. Thus, deciding if $X(\sigma,\tau)$ is minimal is an open problem.

A key argument to decide eventual dendricity in a minimal morphic shift is to
make more deterministic the $S$-adic construction by return words described in
Section 7.1. More precisely, using the notation of the $S$-adic construction
of Section 7.1 (on Page 7.1), we want to algorithmically chose the words
$w_{n}$ for which we consider return words as well as the coding morphisms
$\sigma_{n}:R_{n+1}^{*}\to R_{n}^{*}$. This can be achieved by fixing some
morphic word generating $X(\sigma,\tau)$.

######  Lemma 56.

If $X(\sigma,\tau)$ is minimal, then it is generated by a uniformly recurrent
morphic word $x$ and one can compute morphisms $\sigma^{\prime},\tau^{\prime}$
such that $x=\tau^{\prime}(\sigma^{\prime\omega}(b^{\prime}))$.

###### Proof.

If $X(\sigma,\tau)$ is finite, then it is generated by $x=u^{\omega}$, where
$u$ is a finite word. It is direct to check that
$x=\sigma^{\prime\omega}(b^{\prime})$, where $b^{\prime}$ is the first letter
of $u$ and $\sigma(a)=u^{2}$ for every letter $a$.

Assume now that $X(\sigma,\tau)$ is aperiodic and let $B_{g},B_{b}$ be the
subalphabets of growing and bounded letters, i.e.,

$\displaystyle B_{g}$
$\displaystyle=\\{b\in\mathcal{B}\mid\lim_{n\to+\infty}|\sigma^{n}(b)|=+\infty\\}$
$\displaystyle B_{b}$
$\displaystyle=\\{b\in\mathcal{B}\mid(|\sigma^{n}(b)|)_{n\geq 0}\text{ is
bounded}\\}.$

The set $B_{g}$ is non-empty by aperiodicity, so let $a\in B_{g}$. For every
$n\in\mathbb{N}$, we set $\sigma^{n}(a)=u_{n}a_{n}v_{n}$, where $a_{n}\in
B_{g}$ and $u_{n}\in B_{b}^{*}$. By the pigeonhole principle, we can find
$k<\ell$ such that $a_{k}=a_{\ell}=b^{\prime}$. We thus have
$\sigma^{\ell-k}(b^{\prime})=ub^{\prime}v$ for some word $u\in B_{b}^{*}$.
Since $\sigma,\tau$ are non-erasing and since $X(\sigma,\tau)$ is aperiodic
and minimal, we must have $u=\varepsilon$. In other words,
$\sigma^{\prime}=\sigma^{\ell-k}$ is prolongable on $b^{\prime}$ and, by
minimality, the word $\tau(\sigma^{\prime\omega}(b^{\prime}))$ generates
$X(\sigma,\tau)$. ∎

Assume now that $x\in\mathcal{A}^{\mathbb{N}}$ is a uniformly recurrent
morphic word generating $X(\sigma,\tau)$. If $u$ is a non-empty prefix of $x$,
we set $R(u)=\\{1,\dots,\operatorname{Card}(\mathcal{R}(u))\\}$ and we define
$\theta_{u}:R(u)^{*}\to\mathcal{A}^{*}$ so that
$\theta_{u}(R(u))=\mathcal{R}(u)$ and according to the order of appearance of
return words to $u$ in $x$. That is, for all $i\in R(u)$, if $k$ is the first
occurrence of $\theta_{u}(i)u$ in $x$, then $x_{[0,k)}$ belongs to
$\theta_{u}(\\{1,\dots,i-1\\}^{*})$. Then there exists a unique infinite word
$\mathcal{D}_{u}(x)$, called the derived sequence of $x$ (with respect to $u$)
such that $\theta_{u}(\mathcal{D}_{u}(x))=x$.

######  Theorem 57 (Durand [23]).

Let $x=\tau(\sigma^{\omega}(b))$ be an aperiodic uniformly recurrent morphic
word in $\mathcal{A}^{\mathbb{N}}$.

  1. (1)

For every non-empty prefix $u$ of $x$, the morphism $\theta_{u}$ is computable
and there exist some computable morphisms
$\sigma_{u}:\mathcal{C}^{*}\to\mathcal{C}^{*}$ and
$\tau_{u}:\mathcal{C}^{*}\to R(u)^{*}$ such that
$\mathcal{D}_{u}(x)=\tau_{u}(\sigma_{u}^{\omega}(1))$.

  2. (2)

There is computable constant $D$ such that the set
$\\{(\sigma_{u},\tau_{u})\mid u\text{ non-empty prefix of }x\\}$ has
cardinality at most $D$. In particular, the number of derived sequences of $x$
(on its non-empty prefixes) is at most $D$.

###### Proof.

The existence of $\sigma_{u}$ and $\tau_{u}$ is [23, Proposition 28] and the
fact that $\theta_{u}$, $\sigma_{u}$ and $\tau_{u}$ are computable is
explained in [23, Section 4]. The bound on the number of possible pairs
$(\sigma_{u},\tau_{u})$ is [23, Theorem 29]. ∎

######  Lemma 58 (Durand [20]).

Let $x$ be an aperiodic uniformly recurrent infinite word and let $u$ be a
non-empty prefix of $x$. For every non-empty prefix $v$ of
$\mathcal{D}_{u}(x)$, we have
$\mathcal{D}_{v}(\mathcal{D}_{u}(x))=\mathcal{D}_{w}(x)$, where
$w=\theta_{x,u}(v)u$111Note that we added a subscript $x$ to $\theta_{x,u}$ to
emphasize that it is a coding morphism for return words to $u$ in $x$..

######  Theorem 59.

Let $x=\tau(\sigma^{\omega}(b))$ be an aperiodic uniformly recurrent morphic
word. One can algorithmically compute (from $(\sigma,\tau,b)$) two return
morphisms $\theta:\mathcal{C}^{*}\to\mathcal{C}^{*}$ and
$\lambda:\mathcal{C}^{*}\to\mathcal{A}^{*}$ such that $\theta$ is primitive
and $x=\lambda(\theta^{\omega}(1))$.

###### Proof.

We define a sequence of derivated sequence of $x$ as follows. Fix $x^{(0)}=x$
and $w_{0}=x^{(0)}_{0}$, i.e., $w_{0}$ is the first letter of $x^{(0)}$. For
every integer $n\geq 1$, we set $x^{(n)}=\mathcal{D}_{w_{n-1}}(x^{(n-1)})$ and
$w_{n}=1$. In other words, $x^{(1)}$ is the derived sequence of $x$ with
respect to the first letter of $x$ and, for every $n\geq 2$, $x^{(n)}$ is the
derived sequence of $x^{(n-1)}$ with respect to the letter 1 (which is the
first letter of $x^{(n-1)}$). By iterating Lemma 58, we deduce that there is a
sequence of words $u_{n}\in\mathcal{L}(x)$ such that
$\lim_{n\to+\infty}|u_{n}|=+\infty$ and $x^{(n)}$ is the derived sequence of
$x$ with respect to $u_{n}$.

Every sequence $x^{(n)}$ is uniformly recurrent and, by Theorem 57, we can
compute some morphisms $\theta_{n},\sigma_{n},\psi_{n}$ such that
$x^{(n)}=\psi_{n}(\sigma_{n}^{\omega}(1))=\theta_{n}(x^{(n+1)})$. Still by
Theorem 57, there exists $1\leq m<n$ bounded by a computable constant such
that $(\sigma_{m},\psi_{m})=(\sigma_{n},\psi_{n})$, so that $x^{(m)}=x^{(n)}$.
The construction being deterministic, this implies that for all $k\geq m$, we
have $x^{(k+m-n)}=x^{(k)}$, so that $\theta_{k+m-n}=\theta_{k}$. In
particular, setting $\lambda=\theta_{0}\circ\cdots\circ\theta_{m-1}$ and
$\theta=\theta_{m}\circ\cdots\circ\theta_{n-1}$, we have $x=\lambda(x^{(m)})$
and $x^{(m)}=\theta(x^{(m)})$. In particular, $\theta(1)$ starts with 1.
Furthermore, both $\lambda$ and $\theta$ are return morphisms and, using
Theorem 42, $\theta$ is primitive, hence prolongable on $1$. We finally get
$x=\lambda(\theta^{\omega}(1))$. ∎

The next result directly follows from Theorem 1, Theorem 54 and Theorem 55.

######  Theorem 60.

Let $x=\tau(\sigma^{\omega}(b))$ be an aperiodic uniformly recurrent morphic
word and let $\lambda,\theta$ be the computable morphisms given by Theorem 59.

  1. (1)

The shift space $X_{x}$ is eventually dendric if and only if $\theta$ is
dendric and the sequence $(\theta,\theta,\dots)$ labels an infinite path in
$\mathcal{G}^{L}(\\{\theta\\})$ and in $\mathcal{G}^{R}(\\{\theta\\})$.

  2. (2)

The shift space $X_{x}$ is dendric if and only if $\lambda$ and $\theta$ are
dendric and the sequence $(\lambda,\theta,\theta,\dots)$ labels an infinite
path in $\mathcal{G}^{L}(\\{\lambda,\theta\\})$ and in
$\mathcal{G}^{R}(\\{\lambda,\theta\\})$.

######  Proposition 61.

Let $x=\tau(\sigma^{\omega}(b))$ be an aperiodic uniformly recurrent morphic
word. If $X_{x}$ is eventually dendric, then we can compute the graphs
$G^{L}(X_{x})$ and $G^{R}(X_{x})$ and the threshold for which it is eventually
dendric.

###### Proof.

Let $\lambda,\theta$ be the computable morphisms given by Theorem 59 and let
$y=\theta^{\omega}(1)$. Let us first show that we can compute the graphs
$G^{L}(X_{y})$ and $G^{R}(X_{y})$. If $X_{x}$ is eventually dendric, then
$X_{y}$ is dendric by Theorem 60. By Proposition 32, there exists $K$ such
that $G^{L}(X_{y})=G^{L}_{K}(X_{y})$ and $G^{R}(X_{y})=G^{R}_{K}(X_{y})$,
i.e., the factors of $\mathcal{L}_{\geq K-1}(X_{y})$ are ordinary. Moreover,
there exists $M$ such that each length-$(K-1)$ factor is an extended image of
a $\theta$-initial factor by some $\theta^{m}$ with $m<M$. Let $Z$ be an
Arnoux-Rauzy shift space over the same alphabet as $X_{y}$. Then every
$w\in\mathcal{L}_{K-1}(X_{y})$ is a factor of $\theta^{M}\cdot Z$ with the
same extension graph. Observe conversely that every factor of $\theta^{M}\cdot
Z$ is either a factor of $X_{y}$ (with the same extension graph) or an
extended image of a factor of $Z$ by $\theta^{M}$. In the second case, as
every factor of $Z$ is ordinary, so are their extended images under
$\theta^{M}$ by Remark 15. This shows that any factor of $\theta^{M}\cdot Z$
that is not in $X_{y}$ is ordinary. In particular, the elements of
$\mathcal{L}_{\geq K-1}(\theta^{M}\cdot Z)$ are ordinary. We then conclude
that $G^{L}(X_{y})=G^{L}_{K}(X_{y})=G^{L}_{K}(\theta^{M}\cdot
Z)=G^{L}(\theta^{M}\cdot Z)$, and similarly that
$G^{R}(X_{y})=G^{R}(\theta^{M}\cdot Z)$. Moreover, this remains true for any
$M^{\prime}\geq M$.

Let us study the sequence $(G^{L}(\theta^{n}\cdot Z))_{n\geq 0}$. Since
$G^{L}(Z)$ is the complete graph, $G^{L}(\theta\cdot Z)$ is one of its
subgraph. By Proposition 41, $G^{L}(\theta^{n+1}\cdot
Z)=\theta^{L}(G^{L}(\theta^{n}\cdot Z))$ for all $n$. This then implies by
induction that $G^{L}(\theta^{n+1}\cdot Z)$ is a subgraph of
$G^{L}(\theta^{n}\cdot Z)$ for all $n$. Moreover, if they are equal, then
$G^{L}(\theta^{n+k}\cdot Z)=G^{L}(\theta^{n}\cdot Z)$ for all $k\geq 0$.

This shows that, to compute $G^{L}(X_{y})$, one simply needs to iteratively
compute the graphs $G^{L}(\theta^{n}\cdot Z)$ using Proposition 41 (and
starting from the complete graph) until they stabilize. We can similarly
compute the graph $G^{R}(X_{y})$. By Proposition 41 for the morphism
$\lambda$, we then obtain $G^{L}(X_{x})$ and $G^{R}(X_{x})$.

We now show that we can compute the dendricity threshold of $X_{x}$. As
$X_{y}$ is dendric, if $G^{L}_{N}(X_{y})=G^{L}(X_{y})$ and
$G^{R}_{N}(X_{y})=G^{R}(X_{y})$, then any word of $\mathcal{L}_{\geq
N}(X_{y})$ is ordinary. Knowing $G^{L}(X_{y})$ and $G^{R}(X_{y})$, we can find
such $N$ by iteratively computing the graphs $G^{L}_{n}(X_{y})$ and
$G^{R}_{n}(X_{y})$. By Proposition 19, this gives an upper bound on the
dendricity threshold of $X_{x}$. We can then compute its precise value by
checking all small factors. ∎

Note that, using the notations of the proof, $y$ is dendric if and only if the
sequence $(\theta,\theta,\dots)$ labels the paths $(G^{L}(\theta^{n}\cdot
Z))_{n\geq 0}$ in $\mathcal{G}^{L}(\\{\theta\\})$ and $(G^{R}(\theta^{n}\cdot
Z))_{n\geq 0}$ in $\mathcal{G}^{R}(\\{\theta\\})$. In other words, the study
of the sequences $(G^{L}(\theta^{n}\cdot Z))_{n\geq 0}$ and
$(G^{R}(\theta^{n}\cdot Z))_{n\geq 0}$ also leads to an alternative method to
decide (eventual) dendricity.

######  Corollary 62.

Given two morphisms $\sigma,\tau$ such that $X(\sigma,\tau)$ is minimal, it is
decidable whether $X(\sigma,\tau)$ is eventually dendric of threshold $N$.

###### Proof.

By Lemma 56, we can compute morphisms $\sigma^{\prime},\tau^{\prime}$ such
that $X(\sigma,\tau)=X_{x}$, with $x=\tau^{\prime}(\sigma^{\prime\omega}(b))$.
It is decidable whether $x$ is periodic and, if so, one can compute the
minimal period [22]. In that case, $X(\sigma,\tau)$ is eventually dendric and
the dendricity threshold is bounded by the minimal period. If $x$ not
periodic, then we use Theorem 60 and Proposition 61 to conclude. ∎

##  8\. Interval exchanges

An interval exchange transformation is a pair $(\\{I_{a}\mid
a\in\mathcal{A}\\},T)$, where $\mathcal{A}$ is an alphabet, $\\{I_{a}\mid
a\in\mathcal{A}\\}$ is a partition of $[0,1)$ into left-closed and right-open
intervals and $T:[0,1)\to[0,1)$ is a bijection whose restriction to each
interval $I_{a}$ is a translation. Another way of defining an interval
exchange transformation is by means of a pair $\binom{\leq_{1}}{\leq_{2}}$ of
total orders on $\mathcal{A}$. An interval exchange transformation is said to
be regular if the orbits of the non-zero left endpoints of the intervals
$I_{a}$ are infinite and disjoint. We refer to [27] for more precise
definitions.

###  8.1. Extension graphs in codings of IET

With an interval exchange transformation is associated a shift space, called
the natural coding of $T$ and defined as the set of infinite words
$(x_{n})_{n\in\mathbb{Z}}$ over $\mathcal{A}$ such that for every factor
$u=u_{0}\cdots u_{n-1}$ of $x$, the set $\bigcap_{0\leq i<n}T^{-i}(I_{u_{i}})$
is non-empty. The definition using total orders allows to give the following
characterization of natural codings of regular interval exchange
transformations.

######  Theorem 63 (Ferenczi-Zamboni [27]).

A shift space $X$ over $\mathcal{A}$ is the natural coding of a regular
interval exchange transformation with the pair of orders
$\binom{\leq_{1}}{\leq_{2}}$ if and only if it is minimal,
$\mathcal{A}\subset\mathcal{L}(X)$ and it satisfies the following conditions
for every $w\in\mathcal{L}(X)$:

  1. (1)

for all $(a_{1},b_{1}),(a_{2},b_{2})\in E_{X}(w)$, if $a_{1}<_{2}a_{2}$, then
$b_{1}\leq_{1}b_{2}$;

  2. (2)

for all $a_{1},a_{2}\in E^{L}_{X}(w)$, if $a_{1},a_{2}$ are consecutive for
$\leq_{2}$, then $E^{R}_{X}(a_{1}w)\cap E^{R}_{X}(a_{2}w)$ is a singleton.

In particular, for every $w\in\mathcal{L}(X)$, $E_{X}^{L}(w)$ is an interval
for $\leq_{2}$ and $E^{R}_{X}(w)$ is an interval for $\leq_{1}$.

This result can be reformulated as follows. Let $\leq^{L}$ and $\leq^{R}$ be
two total orders on $\mathcal{A}$. A factor $w$ of a shift space $X\subset
A^{\mathbb{Z}}$ is said to be _planar_ for $(\leq^{L},\leq^{R})$ if item 1 is
satisfied for $\binom{\leq^{R}}{\leq^{L}}$. This implies that, placing the
left and right vertices of $\mathcal{E}_{X}(w)$ on parallel lines and ordering
them respectively by $\leq^{L}$ and $\leq^{R}$, the edges of
$\mathcal{E}_{X}(w)$ may be drawn as straight noncrossing segments, resulting
in a planar graph. In particular, $\mathcal{E}_{X}(w)$ is acyclic.

If $w$ is planar for $(\leq^{L},\leq^{R})$, item 2 is then equivalent to the
fact that $\mathcal{E}_{X}(w)$ is a tree. In particular, this proves that
codings of regular interval exchanges are dendric shift spaces [6].

A shift space over $\mathcal{A}$ is said to be _planar_ for
$(\leq^{L},\leq^{R})$ if every $w\in\mathcal{L}(X)$ is planar for
$(\leq^{L},\leq^{R})$. Theorem 63 then states that a shift space is the
natural coding of a regular interval exchange transformation for the orders
$\binom{\leq^{R}}{\leq^{L}}$ if and only if it is a minimal dendric shift
space planar for $(\leq^{L},\leq^{R})$. Note that, in this case, it is known
that the pair $(\leq^{L},\leq^{R})$ is _irreducible_ , i.e. for any
$0<k<\operatorname{Card}(\mathcal{A})$, the $k$ $\leq^{L}$-smallest letters
are not the $k$ $\leq^{R}$-smallest letters.

The next result is classical when dealing with interval exchange
transformations. We give a combinatorial proof.

######  Proposition 64.

Let $X$ be a minimal dendric shift over $\mathcal{A}$ which is planar for
$(\leq^{L},\leq^{R})$.

  1. (1)

Any long enough left special factor $w$ is such that $E^{L}_{X}(w)$ is equal
to $\\{a,b\\}$, where $a,b$ are consecutive for $\leq^{L}$. Furthermore, for
every two $\leq^{L}$-consecutive letters $a,b$ and for all $n\in\mathbb{N}$,
there is a (unique) left special factor $w$ of length $n$ such that
$\\{a,b\\}\subset E_{X}^{L}(w)$.

  2. (2)

The same holds on the right, i.e., any long enough right special factor $w$ is
such that $E^{R}_{X}(w)$ is equal to $\\{a,b\\}$, where $a,b$ are consecutive
for $\leq^{R}$. Furthermore, for every two $\leq^{R}$-consecutive letters
$a,b$ and for all $n\in\mathbb{N}$, there is a (unique) right special factor
$w$ of length $n$ such that $\\{a,b\\}\subset E_{X}^{R}(w)$.

###### Proof.

We prove the first item. Since $X$ is dendric, there exists $N$ satisfying the
conditions of Proposition 17. Let $w\in\mathcal{L}_{\geq N}(X)$ be a left
special factor. By Theorem 63, the letters of $E_{X}^{L}(w)$ are consecutive
for $\leq^{L}$ and it suffices to prove that
$\operatorname{Card}(E^{L}_{X}(w))=2$. Assume that there exist $a,b,c\in
E^{L}_{X}(w)$ such that $a<^{L}b<^{L}c$.

We claim that $bw$ is not right special. Otherwise, by definition of $N$,
$E^{R}_{X}(bw)=E^{R}_{X}(w)$ and, as there exist $a^{\prime},c^{\prime}$ such
that $E^{R}_{X}(aw)=\\{a^{\prime}\\}$ and $E^{R}_{X}(cw)=\\{c^{\prime}\\}$,
$wa^{\prime}$ and $wc^{\prime}$ are left special. However, this contradicts
the definition of $N$ thus $a^{\prime}=c^{\prime}$. Using item 1 of Theorem
63, this implies that $E^{R}_{X}(bw)=\\{a^{\prime}\\}$, a contradiction.

Thus $bw$ is not right special and there exists a unique letter $b^{\prime}$
such that $bwb^{\prime}\in\mathcal{L}(X)$. By definition of $N$,
$E^{L}(wb^{\prime})=E^{L}_{X}(w)$ and we can iterate the reasoning to show
that no word of $bw\mathcal{A}^{*}\cap\mathcal{L}(X)$ is right special. This
is a contradiction as $X$ is minimal dendric.

We now prove the second part of item 1 by induction on $n$. It is true for
$n=0$ and if $u$ is the unique word of $\mathcal{L}_{n}(X)$ such that $a,b\in
E^{L}_{X}(u)$ then, by item 2 of Theorem 63, there exists $c$ such that
$E^{R}_{X}(au)\cap E^{R}_{X}(bu)=\\{c\\}$. Thus, $uc$ is the unique word of
$\mathcal{L}_{n+1}(X)$ having $a$ and $b$ as left extensions. ∎

###  8.2. S-adic characterization of regular interval exchange transformations

From Theorem 63, we know that the natural coding of a regular interval
exchange transformation is a minimal dendric shift. By Theorem 1, any of its
$\mathcal{S}$-adic representation made of return morphisms labels a path in
$\mathcal{G}^{L}(\mathcal{S})$ and in $\mathcal{G}^{R}(\mathcal{S})$. In this
section, we characterize those labeled paths.

######  Definition 65.

A _line graph_ on $\mathcal{A}$ is a graph $G$ such that, if
$\mathcal{A}=\\{a_{1},\dots,a_{n}\\}$, the edges are exactly the pairs
$(a_{i},a_{i+1})$, $i<n$. This graph is associated with the orders

$a_{1}<a_{2}<\dots<a_{n}\quad\text{and}\quad a_{n}\prec a_{n-1}\prec\dots\prec
a_{1}.$

We then define $G(\leq)$ and $G(\preceq)$ as the graph $G$.

The following result is a direct consequence of Proposition 64. Its converse
is false, as seen in Example 36.

######  Corollary 66.

If $X$ is a minimal dendric shift planar for the orders $(\leq^{L},\leq^{R})$,
then $G^{L}(X)=G(\leq^{L})$ and $G^{R}(X)=G(\leq^{R})$.

If $\preceq$ and $\leq$ are two total orders on $\mathcal{A}$, a partial map
$\varphi:\mathcal{A}\to\mathcal{A}$ is _order preserving_ from $\preceq$ to
$\leq$ if, for all $x,y\in\operatorname{dom}(\varphi)$, we have

$x\prec y\Rightarrow\varphi(x)\leq\varphi(y).$

A return morphism $\sigma:\mathcal{A}^{*}\to\mathcal{A}^{*}$ is _left order
preserving_ from $\preceq$ to $\leq$ if, for all
$s\in\mathcal{T}^{L}(\sigma)$, $\varphi^{L}_{\sigma,s}$ is order preserving
from $\preceq$ to $\leq$. Similarly, $\sigma$ is _right order preserving_ from
$\preceq$ to $\leq$ if, for all $p\in\mathcal{T}^{R}(\sigma)$,
$\varphi^{R}_{\sigma,p}$ is order preserving from $\preceq$ to $\leq$.

######  Lemma 67.

For every return morphism $\sigma:\mathcal{A}^{*}\to\mathcal{A}^{*}$ and every
total order $\leq$ on $\mathcal{A}$, there exists a unique total order
$\preceq$ on $\mathcal{A}$ such that $\sigma$ is left (resp., right) order
preserving from $\preceq$ to $\leq$.

###### Proof.

We prove the result for left order preserving. Let us begin with the existence
of such an order $\preceq$. For all
$s\in\operatorname{Suff}(\sigma(\mathcal{A}))$, we will build an order
$\preceq_{s}$ on
$\mathcal{B}_{s}=\\{a\in\mathcal{A}\mid\sigma(a)\in\mathcal{A}^{*}s\\}$222Note
the difference with
$\mathcal{A}^{L}_{\sigma,s}=\\{a\in\mathcal{A}\mid\sigma(a)\in\mathcal{A}^{+}s\\}$.
such that, for all $s^{\prime}\in\mathcal{A}^{*}s$, the map
$\varphi^{L}_{\sigma,s^{\prime}}$ is order preserving from $\preceq_{s}$ to
$\leq$. The conclusion will follow with $s=\varepsilon$.

We proceed by induction on the length of $s$, starting with $|s|$ maximal. If
$s$ is maximal, i.e. for all $a\in\mathcal{A}$, $\mathcal{B}_{as}$ is empty,
then $s\in\sigma(\mathcal{A})$ and $\mathcal{B}_{s}$ contains a unique element
thus $\preceq_{s}$ is a trivial order.

Assume now that $s$ is not of maximal length and that we have the orders
$\preceq_{as}$ for all $a\in\varphi^{L}_{\sigma,s}(\mathcal{A})$. Since
$\sigma(\mathcal{A})$ is a suffix code, the sets $\mathcal{B}_{as}$ form a
partition of $\mathcal{B}_{s}$ thus, we can define the order $\preceq_{s}$ on
$\mathcal{B}_{s}$ by $x\prec_{s}y$ if

  1. (1)

$x,y\in\mathcal{B}_{as}$ and $x\prec_{as}y$, or

  2. (2)

$x\in\mathcal{B}_{as}$, $y\in\mathcal{B}_{bs}$ and $a<b$.

For all $s^{\prime}\in\mathcal{A}^{*}as$, $\varphi^{L}_{\sigma,s^{\prime}}$ is
order preserving from $\preceq_{as}$ to $\leq$ thus it is order preserving
from $\preceq_{s}$ to $\leq$. In addition, if $x,y\in\mathcal{B}_{s}$ are as
in case 1, then

$\varphi^{L}_{\sigma,s}(x)=a=\varphi^{L}_{\sigma,s}(y)$

and if they are as in case 2, then

$\varphi^{L}_{\sigma,s}(x)=a<b=\varphi^{L}_{\sigma,s}(y).$

Thus, $\varphi^{L}_{\sigma,s}$ is also order preserving from $\preceq_{s}$ to
$\leq$.

We now prove the uniqueness. Assume that $\sigma$ is left order preserving
from $\preceq$ to $\leq$ and from $\preceq^{\prime}$ to $\leq$ and let
$x,y\in\mathcal{A}$ be such that $x\prec y$ and $y\prec^{\prime}x$. If
$s=s_{\sigma}(x,y)$, then
$\varphi^{L}_{\sigma,s}(x)\neq\varphi^{L}_{\sigma,s}(y)$. Since $\sigma$ is
left order preserving from $\preceq$ to $\leq$, we have
$\varphi^{L}_{\sigma,s}(x)<\varphi^{L}_{\sigma,s}(y)$. Since $\sigma$ is also
left order preserving from $\preceq^{\prime}$ to $\leq$, we have the converse
inequality, which is a contradiction. ∎

######  Example 68.

Let us consider the morphism $\beta:0\mapsto 0,1\mapsto 01,2\mapsto
02,3\mapsto 032$ of Example 40 and let us build the order $\preceq$ such that
$\beta$ is left order preserving from $\preceq$ to $\leq$ where $3<0<2<1$.
Using the notations of the previous proof, we have $3\prec_{2}2$ since $3<0$.
We then have $0\prec_{\varepsilon}3\prec_{\varepsilon}2\prec_{\varepsilon}1$
since $0<2<1$, and $\preceq$ is given by the order $\preceq_{\varepsilon}$.

We say that a return morphism $\sigma$ is _planar preserving_ from
$(\preceq^{L},\preceq^{R})$ to $(\leq^{L},\leq^{R})$ if it is left order
preserving from $\preceq^{L}$ to $\leq^{L}$ and right order preserving from
$\preceq^{R}$ to $\leq^{R}$. And it is $(\leq^{L},\leq^{R})$_-planar_ if all
of the $\sigma$-initial factors are planar for $(\leq^{L},\leq^{R})$. Note
that this definition is completely independent on the choice of the word $w$
for which $\sigma$ codes the return words.

The terminology planar preserving comes from the following results.

######  Proposition 69.

Let $X$ be a shift space and $\sigma$ be a return morphism planar preserving
from $(\preceq^{L},\preceq^{R})$ to $(\leq^{L},\leq^{R})$. A word
$v\in\mathcal{L}(X)$ is planar for $(\preceq^{L},\preceq^{R})$ if and only if
every extended image of $v$ under $\sigma$ is planar for
$(\leq^{L},\leq^{R})$.

###### Proof.

We prove that the graph $\mathcal{E}_{X}(v)$ has two crossing edges for
$(\preceq^{L},\preceq^{R})$ if and only if there exists an extended image $u$
such that $\mathcal{E}_{\sigma\cdot X}(u)$ has two crossing edges for
$(\leq^{L},\leq^{R})$. Let $(x_{1},y_{1})$ and $(x_{2},y_{2})$ be two bi-
extensions of $v$ such that $x_{1}\neq x_{2}$ and $y_{1}\neq y_{2}$. If
$s=s_{\sigma}(x_{1},x_{2})$ and $p=p_{\sigma}(y_{1},y_{2})$, we denote

$x^{\prime}_{1}=\varphi_{\sigma,s}^{L}(x_{1}),\quad
x^{\prime}_{2}=\varphi_{\sigma,s}^{L}(x_{2}),\quad
y^{\prime}_{1}=\varphi_{\sigma,p}^{R}(y_{1})\quad\text{and}\quad
y^{\prime}_{2}=\varphi_{\sigma,p}^{R}(y_{2}).$

By construction, $(x^{\prime}_{1},y^{\prime}_{1})$ and
$(x^{\prime}_{2},y^{\prime}_{2})$ are two bi-extensions of the extended image
$u:=s\sigma(v)p$ and are such that $x^{\prime}_{1}\neq x^{\prime}_{2}$ and
$y^{\prime}_{1}\neq y^{\prime}_{2}$. Remark that, for any such pair of bi-
extensions of an extended image $u^{\prime}$ of $v$, it is possible to find a
corresponding pair of bi-extensions of $v$.

To conclude, it suffices to prove that $(x_{1},y_{1})$ and $(x_{2},y_{2})$ are
crossing edges in $\mathcal{E}_{X}(v)$ if and only if
$(x^{\prime}_{1},y^{\prime}_{1})$ and $(x^{\prime}_{2},y^{\prime}_{2})$ are
crossing edges in $\mathcal{E}_{\sigma\cdot X}(u)$. Assume that
$x_{1}\prec^{L}x_{2}$. Since $\sigma$ is planar preserving,
$\varphi^{L}_{\sigma,s}$ is order preserving from $\preceq^{L}$ to $\leq^{L}$
and we have $x^{\prime}_{1}<^{L}x^{\prime}_{2}$. Moreover,
$\varphi^{R}_{\sigma,p}$ is order preserving from $\preceq^{R}$ to $\leq^{R}$
thus

$y_{1}\prec^{R}y_{2}\Leftrightarrow y^{\prime}_{1}<^{R}y^{\prime}_{2}.$

This ends the proof. ∎

######  Corollary 70.

Let $X$ and $Y$ be two dendric shifts such that $Y=\sigma\cdot X$ where
$\sigma$ is $(\leq^{L},\leq^{R})$-planar and planar preserving from
$(\preceq^{L},\preceq^{R})$ to $(\leq^{L},\leq^{R})$. The shift $X$ is planar
for $(\preceq^{L},\preceq^{R})$ if and only if $Y$ is planar for
$(\leq^{L},\leq^{R})$.

We can now prove a result similar to Theorem 1 but in the case of interval
exchanges. This time, the characterization only uses one graph. Observe that,
if $\leq^{*}$ denotes the reverse order of $\leq$, then the planar shift
spaces (or codings of interval exchange transformations) for
$(\leq^{L},\leq^{R})$ and for $((\leq^{L})^{*},(\leq^{R})^{*})$ coincide.
Therefore, to avoid duplicates in the graph, we fix $a<^{L}b$ for some
$a,b\in\mathcal{A}$.

######  Definition 71.

Let $a,b$ be two distinct letters in $\mathcal{A}$. Let $\mathcal{S}$ be a set
of dendric return morphisms from $\mathcal{A}^{*}$ to $\mathcal{A}^{*}$. The
graph $\mathcal{G}_{IET}(\mathcal{S})$ is such that its vertices are the
irreducible pairs of orders $(\leq^{L},\leq^{R})$ such that $a<^{L}b$, and
there is an edge from $(\leq^{L},\leq^{R})$ to $(\preceq^{L},\preceq^{R})$
labeled by $\sigma\in\mathcal{S}$ if

  1. (1)

$(G(\leq^{L}),\sigma,G(\preceq^{L}))$ is an edge of
$\mathcal{G}^{L}(\mathcal{S})$;

  2. (2)

$(G(\leq^{R}),\sigma,G(\preceq^{R}))$ is an edge of
$\mathcal{G}^{R}(\mathcal{S})$;

  3. (3)

$\sigma$ is $(\leq^{L},\leq^{R})$-planar;

  4. (4)

$\sigma$ is planar preserving from $(\preceq^{L},\preceq^{R})$ to
$(\leq^{L},\leq^{R})$, or from $((\preceq^{L})^{*},(\preceq^{R})^{*})$ to
$(\leq^{L},\leq^{R})$.

By Lemma 67, the graph $\mathcal{G}_{IET}$ is deterministic in the sense that,
for each vertex and each morphism, there is at most one edge labeled by the
morphism leaving the vertex.

######  Theorem 72.

Let $\mathcal{S}$ be a family of dendric return morphisms from
$\mathcal{A}^{*}$ to $\mathcal{A}^{*}$ and let $X$ be a shift space having an
$\mathcal{S}$-adic representation ${\boldsymbol{\sigma}}=(\sigma_{n})_{n\geq
0}$. Then $X$ is the coding of a regular interval exchange if and only if
${\boldsymbol{\sigma}}$ is primitive and labels an infinite path in the graph
$\mathcal{G}_{IET}(\mathcal{S})$. Moreover, if this path starts in the pair
$(\leq^{L},\leq^{R})$, then $X$ is the coding of a regular interval exchange
for the orders $\binom{\leq^{R}}{\leq^{L}}$.

###### Proof.

Let us assume that $X$ is the coding of a regular interval exchange for the
orders $\binom{\leq^{R}_{0}}{\leq^{L}_{0}}$, we can moreover assume that
$a<^{L}_{0}b$, where $a$ and $b$ are the letters used to define
$\mathcal{G}_{IET}(\mathcal{S})$. Then, $\sigma_{0}$ is
$(\leq^{L}_{0},\leq^{R}_{0})$-planar, and by Lemma 67, there exist two orders
$\leq^{L}_{1}$ and $\leq^{R}_{1}$ such that $a<^{L}_{1}b$ and $\sigma$ is
planar preserving from $(\leq^{L}_{1},\leq^{R}_{1})$ to
$(\leq^{L}_{0},\leq^{R}_{0})$ or from
$((\leq^{L}_{1})^{*},(\leq^{R}_{1})^{*})$ to $(\leq^{L}_{0},\leq^{R}_{0})$.

As $X_{\boldsymbol{\sigma}}^{(1)}$ is dendric, by Corollary 70, it is the
coding of a regular interval exchange for the orders
$\binom{\leq^{R}_{1}}{\leq^{L}_{1}}$. In particular, the pair
$(\leq^{L}_{1},\leq^{R}_{1})$ is irreducible. Moreover, $\sigma_{0}$ labels an
edge from $G(\leq^{L}_{0})$ to $G(\leq^{L}_{1})$ in
$\mathcal{G}^{L}(\mathcal{S})$ and from $G(\leq^{R}_{0})$ to $G(\leq^{R}_{1})$
in $\mathcal{G}^{R}(\mathcal{S})$. Therefore, $\sigma_{0}$ labels an edge from
$(\leq^{L}_{0},\leq^{R}_{0})$ to $(\leq^{L}_{1},\leq^{R}_{1})$ in
$\mathcal{G}_{IET}(\mathcal{S})$. We then iterate this reasoning to show that
${\boldsymbol{\sigma}}$ labels an infinite path in
$\mathcal{G}_{IET}(\mathcal{S})$.

Assume now that ${\boldsymbol{\sigma}}$ is primitive and labels a path
$((\leq^{L}_{n},\leq^{R}_{n}))_{n\geq 0}$ in $\mathcal{G}_{IET}(\mathcal{S})$.
Since ${\boldsymbol{\sigma}}$ also labels an infinite path in
$\mathcal{G}^{L}(\mathcal{S})$ and $\mathcal{G}^{R}(\mathcal{S})$, $X$ is
minimal dendric. Let us prove that it is planar for
$(\leq^{L}_{0},\leq^{R}_{0})$. The $\sigma_{0}$-initial factors of $X$ are
planar for $(\leq^{L}_{0},\leq^{R}_{0})$ since $\sigma_{0}$ is
$(\leq^{L}_{0},\leq^{R}_{0})$-planar. Let $u\in\mathcal{L}(X)$ be a
non-$\sigma_{0}$-initial factor of $X$. There exist a unique $k>0$ and a
unique $v\in\mathcal{L}(X_{\boldsymbol{\sigma}}^{(k)})$ $\sigma_{k}$-initial
such that $u$ is an extended image of $v$ by $\sigma_{0}\dots\sigma_{k-1}$ by
Proposition 8. However, $\sigma_{k}$ is $(\leq^{L}_{k},\leq^{R}_{k})$-planar
thus $v$ is planar for these orders. Iterating Proposition 69 $k$ times allows
us to conclude that $u$ is planar for $(\leq^{L}_{0},\leq^{R}_{0})$. As this
is true for any $u\in\mathcal{L}(X)$, $X$ is the coding of a regular interval
exchange for the orders $\binom{\leq^{R}_{0}}{\leq^{L}_{0}}$. ∎

As in the dendric case, we can reduce the number of vertices of this graph
using permutation. As a first step, we can completely fix the right (or top)
order. However we can reduce this graph even more. For example, on the
alphabet $\\{0,1,2,3\\}$, the irreducible pairs $\binom{0<1<2<3}{1<3<2<0}$ and
$\binom{0<1<2<3}{3<1<0<2}$ are equivalent up to permutation even if they have
the same top order. Indeed, $\binom{0<1<2<3}{3<1<0<2}$ is equivalent to
$\binom{3<2<1<0}{2<0<1<3}$ which becomes $\binom{0<1<2<3}{1<3<2<0}$ with a
simple permutation of the letters. In particular, this then gives a graph with
$2$ vertices on a ternary alphabet, as done in [29], and with $9$ vertices for
an alphabet of size 4.

##  9\. Future work

Given a set $\mathcal{S}$ of dendric return morphisms, Theorem 1 characterizes
the $\mathcal{S}$-adic shifts that are minimal and dendric. We thus directly
obtain the following corollary.

######  Corollary 73.

Let $\mathcal{S}$ be a set of dendric return morphisms defined on some
alphabet $\mathcal{A}$ such that any minimal dendric shift over $\mathcal{A}$
admits an $\mathcal{S}$-adic representation. Then a shift space
$X\subseteq\mathcal{A}^{\mathbb{Z}}$ is minimal and dendric if and only if it
has a primitive $\mathcal{S}$-adic representation labeling paths in the graphs
$\mathcal{G}^{L}(\mathcal{S})$ and $\mathcal{G}^{R}(\mathcal{S})$.

This corollary is however not completely satisfactory. Indeed it is in general
difficult to find such a set $\mathcal{S}$ of dendric return morphisms. Recall
that Theorem 43 ensures that all morphisms in $\mathcal{S}$ can be assume to
be tame, i.e., are compositions of permutations and of the elementary
morphisms

$R_{ab}:\begin{cases}a\mapsto ab,\\\ c\mapsto c,&\text{for }c\neq
a,\end{cases}\qquad\text{and}\qquad L_{ab}:\begin{cases}a\mapsto ba,\\\
c\mapsto c,&\text{for }c\neq a.\end{cases}$

Over the alphabet $\mathcal{A}=\\{0,1,2\\}$, a sufficient [29] set of
morphisms is given by the permutations and by

$\begin{array}[]{lll}\alpha:\begin{cases}0\mapsto 0\\\ 1\mapsto 01\\\ 2\mapsto
02\end{cases}&\beta:\begin{cases}0\mapsto 0\\\ 1\mapsto 01\\\ 2\mapsto
021\end{cases}&\gamma:\begin{cases}0\mapsto 0\\\ 1\mapsto 01\\\ 2\mapsto
012\end{cases}\\\ \delta_{n}:\begin{cases}0\mapsto 0\\\ 1\mapsto 012^{n}\\\
2\mapsto 012^{n+1}\end{cases}&\zeta_{n}:\begin{cases}0\mapsto 02^{n}\\\
1\mapsto 01\\\ 2\mapsto 02^{n+1}\end{cases}&\eta:\begin{cases}0\mapsto 02\\\
1\mapsto 01\\\ 2\mapsto 012\end{cases}\end{array}$

Furthermore, there exists a regular language over the alphabet of elementary
morphisms that exactly corresponds to the set
$\mathcal{S}_{3}=\\{\alpha,\beta,\gamma,\delta_{n},\zeta_{n},\eta\mid
n\in\mathbb{N}\\}$:

$\displaystyle\alpha=L_{10}L_{20}\quad$
$\displaystyle\beta=L_{20}R_{21}L{10}\quad\gamma=L_{10}L_{21}$
$\displaystyle\delta_{n}=L_{10}R_{12}^{n}L{21}\quad$
$\displaystyle\zeta_{n}=L_{10}R_{02}^{n}L{20}\quad\eta=L_{10}R_{02}L{21}$

For more general alphabets, it is also possible to find regular languages over
the alphabet of elementary morphisms, but only for restricted classes of
dendric shifts. Such a regular language is for instance trivially described
for Arnoux-Rauzy shifts, and can be obtain from the Rauzy diagrams for regular
interval exchange transformations. The Rauzy diagrams encode the behavior of
interval exchanges under the Rauzy induction, and this induction process
transfers to the codings by means of elementary morphisms [32]. For codings of
regular IET, derivation with respect to a word $w$ corresponds to induction on
a particular interval associated with $w$, and this induction can be performed
by a sequence of Rauzy inductions [17]. Hence the return morphisms appearing
in codings of $k$-regular interval exchange form a regular language over the
alphabet of elementary morphisms and an automaton can be deduced from the
Rauzy diagram.

This raises the question of finding a regular language for the general case.
More precisely, if $\mathcal{A}$ is fixed, is there a regular language over
the alphabet of elementary morphisms over $\mathcal{A}$ that exactly
corresponds to dendric return morphisms over $\mathcal{A}$ ?

## References

  * [1] Vladimir I. Arnold.  Small denominators and problems of stability of motion in classical and celestial mechanics.  Uspehi Mat. Nauk, 18(6 (114)):91–192, 1963.
  * [2] Pierre Arnoux and Gérard Rauzy.  Représentation géométrique de suites de complexité $2n+1$.  Bull. Soc. Math. France, 119(2):199–215, 1991.
  * [3] Nicolas Bédaride, Arnaud Hilion, and Martin Lustig.  Tower power for $S$-adics.  Math. Z., 297(3-4):1853–1875, 2021.
  * [4] Valérie Berthé, Paulina Cecchi Bernales, Fabien Durand, Julien Leroy, Dominique Perrin, and Samuel Petite.  On the dimension group of unimodular $\mathcal{S}$-adic subshifts.  Monatsh. Math., 194(4):687–717, 2021.
  * [5] Valérie Berthé, Clelia De Felice, Francesco Dolce, Julien Leroy, Dominique Perrin, Christophe Reutenauer, and Giuseppina Rindone.  Acyclic, connected and tree sets.  Monatsh. Math., 176(4):521–550, 2015.
  * [6] Valérie Berthé, Clelia De Felice, Francesco Dolce, Julien Leroy, Dominique Perrin, Christophe Reutenauer, and Giuseppina Rindone.  Bifix codes and interval exchanges.  J. Pure Appl. Algebra, 219(7):2781–2798, 2015.
  * [7] Valérie Berthé, Clelia De Felice, Francesco Dolce, Julien Leroy, Dominique Perrin, Christophe Reutenauer, and Giuseppina Rindone.  The finite index basis property.  J. Pure Appl. Algebra, 219(7):2521–2537, 2015.
  * [8] Valérie Berthé, Clelia De Felice, Francesco Dolce, Julien Leroy, Dominique Perrin, Christophe Reutenauer, and Giuseppina Rindone.  Maximal bifix decoding.  Discrete Math., 338(5):725–742, 2015.
  * [9] Valérie Berthé and Vincent Delecroix.  Beyond substitutive dynamical systems: $S$-adic expansions.  In Numeration and substitution 2012, RIMS Kôkyûroku Bessatsu, B46, pages 81–123. Res. Inst. Math. Sci. (RIMS), Kyoto, 2014.
  * [10] Valérie Berthé, Francesco Dolce, Fabien Durand, Julien Leroy, and Dominique Perrin.  Rigidity and substitutive dendric words.  Internat. J. Found. Comput. Sci., 29(5):705–720, 2018.
  * [11] Marie-Pierre Béal, Dominique Perrin, and Antonio Restivo.  Decidable problems in substitution shifts, 2021.
  * [12] Nicolas Bédaride, Arnaud Hilion, and Martin Lustig.  Invariant measures on finite rank subshifts, 2020.
  * [13] Julien Cassaigne, Sébastien Labbé, and Julien Leroy.  Almost everywhere balanced sequences of complexity $2n+1$.  Mosc. J. Comb. Number Theory, 11(4):287–333, 2022.
  * [14] Julien Cassaigne and François Nicolas.  Factor complexity.  In Combinatorics, automata and number theory, volume 135 of Encyclopedia Math. Appl., pages 163–247. Cambridge Univ. Press, Cambridge, 2010.
  * [15] Alan Cobham.  On the hartmanis-stearns problem for a class of tag machines.  In 9th Annual Symposium on Switching and Automata Theory (swat 1968), pages 51–60, 1968.
  * [16] Michael Damron and Jon Fickenscher.  The number of ergodic measures for transitive subshifts under the regular bispecial condition.  Ergod. Theory Dyn. Syst., 42(1):86–140, 2022.
  * [17] Francesco Dolce and Dominique Perrin.  Interval exchanges, admissibility and branching Rauzy induction.  RAIRO Theor. Inform. Appl., 51(3):141–166, 2017.
  * [18] Francesco Dolce and Dominique Perrin.  Eventually dendric shift spaces.  Ergod. Theory Dyn. Syst., 41(7):2023–2048, 2021.
  * [19] Sebastián Donoso, Fabien Durand, Alejandro Maass, and Samuel Petite.  Interplay between finite topological rank minimal Cantor systems, $\mathcal{S}$-adic subshifts and their complexity.  Trans. Am. Math. Soc., 374(5):3453–3489, 2021.
  * [20] Fabien Durand.  A characterization of substitutive sequences using return words.  Discrete Math., 179(1-3):89–101, 1998.
  * [21] Fabien Durand.  Linearly recurrent subshifts have a finite number of non-periodic subshift factors.  Ergod. Theory Dyn. Syst., 20(4):1061–1078, 2000.
  * [22] Fabien Durand.  Decidability of the HD0L ultimate periodicity problem.  RAIRO Theor. Inform. Appl., 47(2):201–214, 2013.
  * [23] Fabien Durand.  Decidability of uniform recurrence of morphic sequences.  Internat. J. Found. Comput. Sci., 24(1):123–146, 2013.
  * [24] Fabien Durand, Julien Leroy, and Gwenaël Richomme.  Do the properties of an $S$-adic representation determine factor complexity?  J. Integer Seq., 16(2):Article 13.2.6, 30, 2013.
  * [25] Bastián Espinoza and Alejandro Maass.  On the automorphism group of minimal $\mathcal{S}$-adic subshifts of finite alphabet rank.  Ergod. Theory Dyn. Syst., 42(9):2800–2822, 2022.
  * [26] Sébastien Ferenczi.  Rank and symbolic complexity.  Ergod. Theory Dyn. Syst., 16(4):663–682, 1996.
  * [27] Sébastien Ferenczi and Luca Q. Zamboni.  Languages of $k$-interval exchange transformations.  Bull. Lond. Math. Soc., 40(4):705–714, 2008.
  * [28] 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.
  * [29] France Gheeraert, Marie Lejeune, and Julien Leroy.  $\mathcal{S}$-adic characterization of minimal ternary dendric shifts.  Ergod. Theory Dyn. Syst., 42(11):3393–3432, 2022.
  * [30] Marston Morse and Gustav A. Hedlund.  Symbolic dynamics II. Sturmian trajectories.  Amer. J. Math., 62:1–42, 1940.
  * [31] Valery I. Oseledets.  The spectrum of ergodic automorphisms.  Dokl. Akad. Nauk SSSR, 168:1009–1011, 1966.
  * [32] Gérard Rauzy.  Échanges d’intervalles et transformations induites.  Acta Arith., 34(4):315–328, 1979.