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), 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 $ (respectively, $s = \varepsilon $ ) we say that u is a prefix (respectively, suffix) of w. For a word $u \in \mathcal {A}^{*}$ , an index $ 1 \le j \le \ell $ such that $w_{j}\cdots w_{j+|u|-1} =u$ is called an occurrence of u in w and we use the same term for bi-infinite word in $\mathcal {A}^{{\mathbb {Z}}}$ . The number of occurrences of a word $u \in \mathcal {A}^*$ in a finite word w is denoted as $|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 ( (x_n)_{n \in \mathbb {Z}} ) = (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$ is $\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 $\cup _{x\in X} \mathcal {L}(x)$ and we set $\mathcal {L}_n(X) = \mathcal {L}(X) \cap \mathcal {A}^n$ , $n \in {\mathbb {N}}$ . Its factor complexity is the function $p_X:{\mathbb {N}} \to {\mathbb {N}}$ defined by $p_X(n) = \#\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, that is, 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

$$ \begin{align*} E_F^-(w) &= \{ a \in \mathcal{A} \mid aw \in F\}; \\ E_F^+(w) &= \{ b \in \mathcal{A} \mid wb \in F\}; \\ E_F(w) &= \{ (a,b) \in \mathcal{A} \times \mathcal{A} \mid awb \in F\}. \end{align*} $$

The elements of $E_F^-(w)$ , $E_F^+(w)$ , and $E_F^-(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^-(w)$ and $E_X^+(w)$ . A word w is said to be right special (respectively, left special) if $\#(E^+(w))\geq 2$ (respectively, $\#(E^-(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.1. (Cassaigne and Nicolas [Reference Cassaigne and NicolasCN10])

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

$$ \begin{align*} p_X(n+1)-p_X(n) &= \sum_{w \in \mathcal{L}_n(X)} (\#E^+(w)-1) \\ &= \sum_{w \in \mathcal{L}_n(X)} (\#E^-(w)-1). \end{align*} $$

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

(2.1) $$ \begin{align} \#E(w) - \# E^-(w) - \# E^+(w) + 1 = 0, \end{align} $$

then $p_X(n) = (p_X(1)-1)n +1$ for every n.

A classical family of bispecial factors satisfying (2.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 (2.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^-(w)$ and $E_F^+(w)$ and its edges are the pairs $(a,b) \in E_F^-(w) \times E_F^+(w)$ such that $awb \in F$ . For an illustration, see Example 2.2 below. 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)$ . 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^-(u_n) = \mathcal {A} = E^+(v_n)$ ; all bispecial factors of an Arnoux–Rauzy shift are ordinary). By Proposition 2.1, we deduce that any dendric shift has factor complexity $p_X(n) = (p_X(1)-1)n +1$ for every n.

Example 2.2. Let $\sigma $ be the Fibonacci substitution defined over the alphabet $\{0,1\}$ by $\sigma \colon 0 \mapsto 01, 1 \mapsto 0$ and consider the shift space generated by $\sigma $ (that is, the set of bi-infinite words over $\{0,1\}$ whose factors are factors of some $\sigma ^n (0)$ ). The extension graphs of the empty word and of the two letters $0$ and $1$ are represented in Figure 1.

Figure 1

The extension graphs of $\varepsilon $ (a), $0$ (b) and $1$ (c) are trees.

2.3 $\mathcal {S}$ -adicity

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 non-erasing monoid homomorphism (also called a substitution when $\mathcal {A} = \mathcal {B}$ ). By non-erasing, we mean that 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 {N}}$ and $\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

$$ \begin{align*} Y = \{S^k \sigma(x) \mid x \in X, 0\leq k < |\sigma(x_0)|\}. \end{align*} $$

The incidence matrix of $\sigma $ is the matrix $M_{\sigma } \in \mathbb {N}^{\mathcal {B} \times \mathcal {A}}$ such that $(M_{\sigma })_{b,a} = |\sigma (a)|_b$ for any $a \in \mathcal {A}$ , $b \in \mathcal {B}$ .

The morphism $\sigma $ is said to be left proper (respectively, right proper) when there exists a letter $\ell \in \mathcal {B}$ such that for all $a \in \mathcal {A}$ , $\sigma (a)$ starts with $\ell $ (respectively, ends with $\ell $ ). It is strongly left proper (respectively, strongly right proper) if it is left proper (respectively, right proper) and the starting letter (respectively, ending letter) $\ell $ only occurs once in each image $\sigma (a)$ , $a \in \mathcal {A}$ . It is said to be proper if it is both left and right proper. With a left proper morphism $\sigma :\mathcal {A}^* \to \mathcal {B}^*$ with first letter $\ell $ , we associate a right proper morphism $\bar {\sigma }:\mathcal {A}^* \to \mathcal {B}^*$ by

$$ \begin{align*} \sigma(a)\ell = \ell \bar{\sigma}(a) \quad \text{for all}\ \ a \in \mathcal{A}. \end{align*} $$

Let ${\boldsymbol {\sigma }} = (\sigma _n : \mathcal {A}_{n+1}^* \to \mathcal {A}_n^*)_{n \geq 1}$ be a sequence of morphisms such that $ \max _{a \in \mathcal {A}_n} |\sigma _1 \circ \cdots \circ \sigma _{n-1}(a)| $ goes to infinity when n increases. We assume that all the alphabets $\mathcal {A}_{n}$ are minimal, in the sense that for all $n \in \mathbb {N}$ and $b \in \mathcal {A}_{n}$ , there exists $a \in \mathcal {A}_{n+1}$ such that b is a factor of $\sigma _n(a)$ . For $1\leq n<N$ , we define the morphism $\sigma _{[n,N)} = \sigma _n \circ \sigma _{n+1} \circ \cdots \circ \sigma _{N-1}$ . For $n\geq 1$ , the language $\mathcal {L}^{(n)}({{\boldsymbol {\sigma }}})$ of level n associated with ${\boldsymbol {\sigma }}$ is defined by

$$ \begin{align*} \mathcal{L}^{(n)}({{\boldsymbol{\sigma}}}) = \{ w \in \mathcal{A}_n^* \mid w\ \mbox{occurs in}\ \sigma_{[n,N)}(a)\ \mbox{for some}\ a \in \mathcal{A}_N\ \mbox{and}\ N>n \}. \end{align*} $$

As $\max _{a \in \mathcal {A}_n} |\sigma _{[1,n)}(a)|$ goes to infinity when n increases, $\mathcal {L}^{(n)}({{\boldsymbol {\sigma }}})$ defines a non-empty shift space $X_{{\boldsymbol {\sigma }}}^{(n)}$ that we call the shift space generated by $\mathcal {L}^{(n)}({{\boldsymbol {\sigma }}})$ . More precisely, $X_{{\boldsymbol {\sigma }}}^{(n)}$ is the set of points $x \in \mathcal {A}_n^{\mathbb {Z}}$ such that $\mathcal {L} (x) \subseteq \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 $\mathcal {L}({{\boldsymbol {\sigma }}}) = \mathcal {L}^{(1)}({{\boldsymbol {\sigma }}})$ , $X_{{\boldsymbol {\sigma }}} = X_{{\boldsymbol {\sigma }}}^{(1)}$ , and call $X_{{\boldsymbol {\sigma }}}$ the $\mathcal {S}\kern-0.5pt$ -adic shift generated by the directive sequence ${\boldsymbol {\sigma }}$ . We also say that the directive sequence ${\boldsymbol {\sigma }}$ is an $\mathcal {S}\!$ -adic representation of $X_{{\boldsymbol {\sigma }}}$ .

We say that ${\boldsymbol {\sigma }}$ is primitive if, for any $n\geq 1$ , 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 _{[1,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 [Reference DurandDur00, Lemma 7]).

We say that ${\boldsymbol {\sigma }}$ is ((strongly) left, (strongly) right) proper whenever each morphism $\sigma _n$ is ((strongly) left, (strongly) right) proper. We also say that ${\boldsymbol {\sigma }}$ is injective if each morphism $\sigma _n$ is injective (seen as an application from $\mathcal {A}_{n+1}^*$ to $\mathcal {A}_n^*$ ). By abuse of language, we say that a shift space is a (strongly left or right proper, primitive, injective) $\mathcal {S}$ -adic shift if there exists a (strongly left or right proper, primitive, injective) sequence of morphisms ${\boldsymbol {\sigma }}$ such that $X = X_{{\boldsymbol {\sigma }}}$ .

3.1 $\mathcal {S}$ -adicity using return words and derived shifts

Let X be a minimal shift space over the alphabet $\mathcal {A}$ and let $w \in \mathcal {L}(X)$ be a non-empty word. A return word to w in X is a non-empty word r such that w is a prefix of $rw$ and, $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.

Let $w \in \mathcal {L}(X)$ be a non-empty word and write $R_X(w) = \{1,\ldots ,\#(\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 injective. 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 left proper and primitive $\mathcal {S}$ -adic representations. We inductively define the sequences $(a_n)_{n \geq 1}$ , $(R_n)_{n \geq 1}$ , $(X_n)_{n \geq 1}$ , and $(\sigma _n)_{n \geq 1}$ by:

• • $X_1 = X$ , $R_1 = \mathcal {A}$ and $a_1 \in \mathcal {A}$ ;

• • for all n, $R_{n+1} = R_{X_{n}}(a_n)$ , $\sigma _n: R_{n+1}^* \to R_n^*$ is a coding morphism associated with $a_n$ , $X_{n+1} = \mathcal {D}_{a_n}(X_n)$ and $a_{n+1} \in R_{n+1}$ .

Observe that the sequence $(a_n)_{n \geq 1}$ is not uniquely defined as well as the morphism $\sigma _n$ (even if $a_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 1}$ and it is understood that we may consider any such sequence. Also observe that as we consider derived shifts with respect to letters, each coding morphism $\sigma _n$ is strongly left proper. It is furthermore a characterization: a morphism $\sigma :\{1,\ldots ,n\}^* \to \mathcal {A}^*$ is injective and strongly left proper (with first letter $\ell $ ) if and only if there is a shift space X over $\mathcal {A}$ such that $\sigma $ is a coding morphism associated with $\ell $ .

In the case of minimal dendric shifts, the $\mathcal {S}$ -adic representation ${\boldsymbol {\sigma }}$ can be made stronger. This is summarized by the following result. 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{align*} \begin{cases} a \mapsto ab, \\ c \mapsto c & \text{for } c \neq a, \end{cases} \quad \text{and} \quad \begin{cases} a \mapsto ba, \\ c \mapsto c & \text{for } c \neq a. \end{cases} \end{align*} $$

3.2 Rauzy graphs

Let X be a shift space over an alphabet $\mathcal {A}$ . The Rauzy graph of order n of X, is the directed graph $G_n(X)$ whose set of vertices is $\mathcal {L}_n(X)$ and there is an edge from u to v if there are letters $a,b$ such that $ub = av \in \mathcal {L}(X)$ ; this edge is sometimes labeled by a.

Assuming that X is minimal, any Rauzy graph $G_n(X)$ is strongly connected. It is also easily seen that any return word to a non-empty word $w \in \mathcal {L}(X)$ labels a path from w to w in $G_{|w|}(X)$ in which no internal vertex is w. As a consequence, the shape of the Rauzy graph $G_1(X)$ provides restrictions on the possible return words to a letter a in X. Furthermore, for the extension graph of the empty word having for edges the pairs $(a,b) \in E_X(\varepsilon )$ , it completely determines $\mathcal {L}_2(X)$ , and hence the Rauzy graph $G_1(X)$ . Therefore, the extension graph $\mathcal {E}_X(\varepsilon )$ provides restrictions on the possible return words to letters in X.

Example 3.3. The Rauzy graph of order two of the shift space X generated by the Fibonacci substitution is given in Figure 2. The word $00100$ belongs to $\mathcal {L}(X)$ , so that $001$ is a return word to $00$ and it labels the circuit $(00,01,10,00)$ . The converse however does not hold, that is, there might exist paths from w to w whose label is not a return word. For any $n \geq 1$ , the word $0(01)^n$ labels a path from $00$ to $00$ but does not belong to $\mathcal {L}(X)$ when $n \geq 3$ .

Figure 2

Rauzy graph of order two for the Fibonacci shift.

4.1 Description of bispecial factors in injective strongly left proper $\mathcal {S}$ -adic shifts

Our aim is to describe bispecial factors and their bi-extensions in an $\mathcal {S}$ -adic shift $X_{\boldsymbol {\sigma }}$ . A classical way to do this is to ‘desubstitute’ a bispecial factor u, that is, to find the set of ‘minimal’ factors $v_i$ in $\mathcal {L}(X_{\boldsymbol {\sigma }}^{(k)})$ such that u is a factor of the words $\sigma _{[1,k)}(v_i)$ and then to deduce the extensions of u from those of the $v_i$ . The set of such $v_i$ can be easily described when ${\boldsymbol {\sigma }}$ is an injective and strongly left proper sequence of morphisms.

Proposition 4.1. Let X be a shift space over $\mathcal {A}$ , $\sigma :\mathcal {A}^* \to \mathcal {B}^*$ be an injective and strongly left proper morphism (with first letter $\ell $ ), Y the image of X under $\sigma $ , and u a non-empty word in $\mathcal {L}(Y)$ . If $\ell $ does not occur in u, then there exists $b \in \mathcal {A}$ such that u is a non-prefix factor of $\sigma (b)$ . Otherwise, there is a unique triplet $(s,v,p) \in \mathcal {B}^* \times \mathcal {L}(X) \times \mathcal {B}^*$ for which there exists a pair $(a,b) \in E_{X}(v)$ such that $u = s \sigma (v)p$ with:

1. (1) s a proper suffix of $\sigma (a)$ ;

2. (2) p is a non-empty prefix of $\sigma (b)$ .

In the case where $\ell $ occurs in u, the left, right, and bi-extensions of u are governed by those of v through the equation

(4.1) $$ \begin{align} E_Y(u) =\,& \{(a',b') \in \mathcal{B} \times \mathcal{B} \mid\ \text{there exists}\ \ (a,b) \in E_X(v)\nonumber\\ &:\sigma(a) \in \mathcal{B}^* a' s \wedge \sigma(b)\ell \in p b' \mathcal{B}^* \}. \end{align} $$

Proof Since u is a word in $\mathcal {L}(Y)$ , it is a factor of $\sigma (w)$ for some $w \in \mathcal {L}(X)$ . The word u being non-empty, any such w is non-empty as well. We say that w is covering u if u is a factor of $\sigma (w)$ and for any proper factor $w'$ of w, u is not a factor of $\sigma (w')$ . Recall that $\ell $ is the first letter of $\sigma (a)$ for all $a \in \mathcal {A}$ . Thus, if $|u|_\ell = 0$ , then any word w covering u is a letter and u is a non-prefix factor of $\sigma (w)$ .

Now assume that $|u|_\ell \geq 1$ and let $u = s u' p$ with $|s|_\ell = 0$ , $p \in \ell (\mathcal {A}\setminus \{\ell \})^*$ , and $u' \in \{\varepsilon \} \cup \ell \mathcal {A}^*$ . As the letter $\ell $ occurs only as a prefix in any image $\sigma (a)$ , $a \in \mathcal {A}$ , any word w covering u is of the form $x v' y$ with $x \in \mathcal {A} \cup \{\varepsilon \}$ and $y \in \mathcal {A}$ , where one has $\sigma (v') = u'$ , s is a suffix of $\sigma (x)$ (which is proper if $x \neq \varepsilon $ ), and p is a prefix of $\sigma (y)$ . In particular, the triplet $(s,v,p)$ satisfies the requirements of the result (take $b = y$ and $a = x$ if $x \neq \varepsilon $ or any $a \in E^-(vy)$ if $x = \varepsilon $ ).

Let us show the uniqueness of $(s,v,p)$ . Assume that $(s',v',p')$ is a triplet satisfying the requirements with the extension $(a',b') \in E(v')$ . As $u = s'\sigma (v')p'$ , where $s'$ is a proper suffix of $\sigma (a')$ and $p'$ is a non-empty proper prefix of $\sigma (b')\ell $ , we have $|s'|_\ell = 0$ , $p' \in \ell (\mathcal {A}\setminus \{\ell \})^*$ , and $\sigma (v') \in \{\varepsilon \} \cup \ell \mathcal {A}^*$ . This implies that $(s',\sigma (v'), p') = (s,\sigma (v),p)$ and, as $\sigma $ is injective, that $(s',v',p') = (s,v,p)$ .

Let us now prove (4.1). The inclusion

$$ \begin{align*} E_Y(u) \supset\,& \{(a', b') \in \mathcal{B} \times \mathcal{B} \mid\ \text{there exists}\ \ (a,b) \in E_X(v)\\ &: \sigma(a) \in \mathcal{B}^* a' s \wedge \sigma(b)\ell \in p b' \mathcal{B}^* \} \end{align*} $$

is trivial. For the other one, assume that $(a',b')$ is in $E_Y(u)$ . Thus we have $a'ub' \in \mathcal {L}(Y)$ . Let $w \in \mathcal {L}(X)$ be a covering word for $a'ub'$ . By definition of v, v is a factor of w, and thus one has $w = xvy$ for some words $x,y$ . We then have $a'ub' = a's\sigma (v)pb'$ , with $a's$ a suffix of $\sigma (x)$ and $pb'$ a prefix of $\sigma (y)\ell $ . In particular, x and y are non-empty. Let a be the last letter of x and b be the first letter of y. We have $(a,b) \in E_X(v)$ and, as $|s|_{\ell } = 0$ , s is a proper suffix of $\sigma (a)$ , from which we have $\sigma (a) \in \mathcal {B}^* a's$ . We also have that p is a prefix of $\sigma (b)$ . If it is proper, then $pb'$ is a prefix of $\sigma (b)$ so that $\sigma (b)\ell \in pb' \mathcal {B}^*$ . Otherwise, $p = \sigma (b)$ , y has length at least 2, and $b'$ is the first letter of $\sigma (c)$ , where c is such that $bc$ is a prefix of y. Otherwise stated, $b' = \ell $ and we indeed have $\sigma (b)\ell \in pb'\mathcal {B}^*$ .

Motivated by the previous result, if X is a shift space over $\mathcal {A}$ and $\sigma :\mathcal {A}^* \to \mathcal {B}^*$ is a strongly left proper morphism (with first letter $\ell $ ), then for any words $v \in \mathcal {L}(X)$ and $x,y \in \mathcal {B}^*$ , we define the sets

$$ \begin{align*} E_{X,x}^-(v) &= \{ a \in E_X^-(v) \mid \sigma(a) \in \mathcal{B}^* x \}, \\ E_{X,y}^+(v) &= \{ b \in E_X^+(v) \mid \sigma(b)\ell \in y \mathcal{B}^* \}, \\ E_{X,x,y}(v) &= E_X(v) \cap (E_{X,x}^-(v) \times E_{X,y}^+(v)). \end{align*} $$

Thus (4.1) can be written as

$$ \begin{align*} E_Y(u) = \{(a',b') \in \mathcal{B} \times \mathcal{B} \mid\ \text{there exists}\ (a,b) \in E_{X,a's,pb'}(v) \}. \end{align*} $$

Whenever u and v are as in the previous proposition with $|u|_\ell \geq 1$ , the word v is called the antecedent of u under $\sigma $ and u is said to be an extended image of v. Thus, the antecedent is defined only for words containing an occurrence of the letter $\ell $ and an extended image always contains an occurrence of $\ell $ . Whenever u is a bispecial factor, the next result gives additional information about s and p. We first need to define the following notation. If $\sigma : \mathcal {A}^* \rightarrow \mathcal {B}^*$ is a morphism and $a_1, a_2 \in \mathcal {A}$ , let us denote by $s(a_1,a_2)$ (respectively, $p(a_1,a_2)$ ) the longest common suffix (respectively, prefix) between $\sigma (a_1)$ and $\sigma (a_2)$ .

Proof First assume that there exist $(a_1,b_1),(a_2,b_2) \in E_X(v)$ with $a_1 \neq a_2$ , $b_1 \neq b_2$ , and $u = s(a_1,a_2) \sigma (v) p(b_1,b_2)$ . Let us fix $s = s(a_1,a_2)$ and $p = p(b_1,b_2)$ . Since $\sigma $ is injective, $\sigma (a_1) \neq \sigma (a_2)$ , and hence s is a proper suffix of one of them. Thus, as $\sigma $ is strongly left proper, s does not contain any occurrence of the letter $\ell $ . As a consequence, s is a proper suffix of both $\sigma (a_1)$ and $\sigma (a_2)$ . In particular, u is left special. The same reasoning shows that p is a proper prefix of $\sigma (b_i)$ for some $i \in \{1,2\}$ and that u is right special, and hence bispecial. Furthermore, p is non-empty since it admits $\ell $ as a prefix. The pair $(a_i,b_i)$ thus satisfies Proposition 4.1.

Now assume that u is a bispecial extended image of v with $u = s \sigma (v)p$ . Since u is bispecial, there exist $(a_1',b_1'),(a_2',b_2') \in E_Y(u)$ with $a_1' \neq a_2'$ and $b_1' \neq b_2'$ . From 4.1, there exist $(a_1,b_1),(a_2,b_2) \in E_{X,s,p}(v)$ such that

$$ \begin{align*} \sigma(a_i) \in \mathcal{B}^* a_i's \quad \text{and} \quad \sigma(b_i)\ell \in pb_i'\mathcal{B}^* \end{align*} $$

for all $i \in \{1,2\}$ . We deduce that $s = s(a_1,a_2)$ and $a_1 \neq a_2$ . As $b_1'$ and $b_2'$ cannot be simultaneously equal to $\ell $ , we deduce that $b_1 \neq b_2$ and that $p = p(b_1,b_2)$ .

Example 4.4. Consider the morphism

$$ \begin{align*} \delta: \begin{cases} 1 \mapsto 1 \\ 2 \mapsto 123 \\ 3 \mapsto 1233 \\ \end{cases} \end{align*} $$

that will appear again in §5. Assume that v is a bispecial factor of $X \subset \{1,2,3\}^{\mathbb {Z}}$ whose extension graph is

By Corollary 4.3, the word v admits $\delta (v) 1$ and $3 \delta (v) 1$ as bispecial extended images. Using Proposition 4.1, their extension graphs are given in Figure 3.

Figure 3

Extension graphs of the bispecial extended images of v.

Assume that $X_{\boldsymbol {\sigma }}$ is an $\mathcal {S}$ -adic shift where the directive sequence ${\boldsymbol {\sigma }} = (\sigma _n:\mathcal {A}_{n+1}^* \to \mathcal {A}_n^*)_{n \geq 1}$ is primitive and contains only strongly left proper injective morphisms. The directive sequence ${\boldsymbol {\sigma }}$ being primitive, the sequence $(\min _{a \in \mathcal {A}_n} |\sigma _{[1,n)}(a)|)_{n \geq 1}$ goes to infinity. Hence, iterating Proposition 4.1, with any word $u \in \mathcal {L}(X_{\boldsymbol {\sigma }})$ , one can associate a unique finite sequence $(u_1,u_2,\ldots ,u_k)$ such that $u_1 = u$ , $u_k \in \mathcal {L}(X_{\boldsymbol {\sigma }}^{(k)})$ does not have any antecedent under $\sigma _k$ and, for $i <k$ , $u_{i+1} \in \mathcal {L}(X_{\boldsymbol {\sigma }}^{(i+1)})$ is the antecedent of $u_i$ under $\sigma _i$ . We say that u is a descendant of each $u_i$ , $1 \leq i \leq k$ , and, reciprocally, that each $u_i$ , $1 \leq i \leq k$ , is an ancestor of u. The word $u_k \in \mathcal {L}(X_{\boldsymbol {\sigma }}^{(k)})$ is its oldest ancestor and it is either empty or a non-prefix factor of $\sigma _k (b)$ for some letter $b \in \mathcal {A}_{k+1}$ . Observe that with our definition, u is an ancestor and a descendant of itself.

Let X be an $\mathcal {S}$ -adic shift with a strongly left proper and injective $\mathcal {S}$ -adic representation ${\boldsymbol {\sigma }}$ . Let u be a bispecial factor of X. From Corollary 4.3, all ancestors of u are bispecial factors of some $X_{\boldsymbol {\sigma }}^{(k)}$ . From Proposition 4.1, the extensions of u are completely governed by those of its oldest ancestor. More precisely, we have the following direct corollary.

4.2 Action of morphisms on extension graphs

Proposition 4.1 shows that whenever v is the antecedent of u under $\sigma $ , the extension graph $\mathcal {E}_Y(u)$ is the image under a graph morphism of a subgraph of $\mathcal {E}_X(v)$ (where by subgraph we mean the subgraph generated by a subset of edges). In particular, if $\#(E^-_Y(u)) = \#(E^-_X(v))$ and $\#(E^+_Y(u)) = \#(E^+_X(v))$ , then $\mathcal {E}_Y(u)$ and $\mathcal {E}_X(v)$ are isomorphic. In this section, we formalize this observation and study the behavior of a tree structure when we consider the extension graphs of bispecial extended images.

In this section, X is a shift space over $\mathcal {A}$ , $\sigma :\mathcal {A}^* \to \mathcal {B}^*$ an injective and strongly left proper morphism (with first letter $\ell $ ), Y the image of X under $\sigma $ , and v a bispecial word in $\mathcal {L}(X)$ . By Corollary 4.3, the bispecial extended images of v under $\sigma $ are the words u of the form $s \sigma (v) p$ where $s=s(a_1,a_2)$ and $p=p(b_1,b_2)$ for some $(a_1,b_1),(a_2,b_2) \in E_X(v)$ such that $a_1 \neq a_2$ and $b_1 \neq b_2$ . For any such $\sigma $ and v, we introduce the following notation:

$$ \begin{align*} \mathcal {T}^{\kern1.5pt-}(\sigma) &= \{s(a_1,a_2) \mid a_1, a_2 \in \mathcal{A}, a_1 \neq a_2\}; \\ \mathcal {T}^{\kern1.5pt+}(\sigma) &= \{p(b_1,b_2) \mid b_1, b_2 \in \mathcal{A}, b_1 \neq b_2\}; \\ \mathcal {T}^{\kern1.5pt-}_v(\sigma) &= \{s(a_1,a_2) \mid a_1,a_2 \in E^-_{X}(v), a_1 \neq a_2\}; \\ \mathcal {T}^{\kern1.5pt+}_v(\sigma) &= \{p(b_1,b_2) \mid b_1,b_2 \in E^+_{X}(v), b_1 \neq b_2\}; \\ \overline{\mathcal {T}^{\kern1.5pt-}_v(\sigma)} &= \mathcal {T}^{\kern1.5pt-}_v(\sigma) \cup \sigma(E_X^-(v));\\ \overline{\mathcal {T}^{\kern1.5pt+}_v(\sigma)} &= \mathcal {T}^{\kern1.5pt+}_v(\sigma) \cup \sigma(E_X^+(v)) \ell. \end{align*} $$

The prefix strict order (respectively, suffix strict order) defines a tree structure called radix tree on $\overline {\mathcal{T}^{\kern1.5pt+}_v(\sigma )}$ (respectively, on $\overline {\mathcal {T}^{\kern1.5pt-}_v(\sigma )}$ ), where the root $p_0$ (respectively, $s_0$ ) is the shortest word of the set. In particular, $E^-_{X,s_0}(v) = E^-_X(v)$ and $E^+_{X,p_0}(v) = E^+_X(v)$ . Furthermore, the leafs of $\overline {\mathcal{T}^{\kern1.5pt+}_v(\sigma )}$ (respectively, $\overline {\mathcal {T}^{\kern1.5pt-}_v(\sigma )}$ ) are exactly the elements of $\sigma (E_X^+(v)) \ell $ (respectively, $\sigma (E_X^-(v))$ ) and every internal node (that is, every element of $\mathcal{T}^{\kern1.5pt+}_v(\sigma )$ or $\mathcal {T}^{\kern1.5pt-}_v(\sigma )$ ) has at least two children.

For $(s,p) \in \mathcal {T}^{\kern1.5pt-}_v(\sigma ) \times \mathcal{T}^{\kern1.5pt+}_v(\sigma )$ , we define the subgraph $\mathcal {E}_{X,s,p}(v)$ of $\mathcal {E}_X(v)$ whose vertices are those involved by the edges in $E_{X,s,p}(v)$ . Observe that the sets of left and right vertices of $\mathcal {E}_{X,s,p}(v)$ are respectively included in $E^-_{X,s}(v)$ and $E^+_{X,p}(v)$ . Furthermore, if $s'\in \overline {\mathcal {T}^{\kern1.5pt-}_v(\sigma )}$ (respectively, $p'\in \overline {\mathcal{T}^{\kern1.5pt+}_v(\sigma )}$ ) is a child of s (respectively, of p), then $\mathcal {E}_{X,s',p}(v)$ (respectively, $\mathcal {E}_{X,s,p'}(v)$ ) is a subgraph of $\mathcal {E}_{X,s,p}(v)$ .

Example 4.6. Using the notation from Example 4.4, we have the following radix trees:

These structures help us understand the construction of the extension graphs of Figure 3. Let $s \in \mathcal {T}^{\kern1.5pt-}_v(\sigma )$ and $p \in \mathcal{T}^{\kern1.5pt+}_v(\sigma )$ be such that $u = s\sigma (v)p$ . The extension graph of u can be obtained from the extension graph of v as follows.

1. (1) Start by selecting the elements of $E^-_{X, s}(v)$ and $E^+_{X, p}(v)$ (see Table 1). These elements are the letters such that the corresponding leaf in $\overline {\mathcal {T}^{\kern1.5pt-}_v(\sigma )}$ (respectively, $\overline {\mathcal{T}^{\kern1.5pt+}_v(\sigma )}$ ) is in the subtree with root s (respectively, p).

   Table 1

   Step 1.

   

2. (2) Take the subgraph of $\mathcal {E}_X(v)$ with only the vertices which are in these two sets and remove the isolated vertices that were created. This gives the graph $\mathcal {E}_{X, s, p}(v)$ (see Figure 4).

   Figure 4

   Step 2.

   

3. (3) For any letter $a \in \mathcal {A}$ , merge the vertices b on the left side such that $\sigma (b) \in \mathcal {A}^*as$ into a new left vertex labeled by a. In other words, for any left vertex b, map it to the left vertex labeled by the letter a such that the leaf corresponding to b is in the subtree whose root is the only child of s ending by $as$ . Do the same on the right side with the vertices b such that $\sigma (b) \ell \in pa\mathcal {A}^*$ (see Table 2).

   Table 2

   Step 3.

   

The next result gives a more formal description of this construction and directly follows from (4.1).

Observe that the morphism $\varphi _{v,s,p}$ of the previous result acts independently on the left and right vertices of $\mathcal {E}_{X,s,p}(v)$ , that is, it can be seen as the composition of two commuting graph morphisms $\varphi ^-_{v,s}$ and $\varphi ^+_{v,p}$ , where $\varphi ^-_{v,s}$ acts only on the left vertices of $\mathcal {E}_{X,s,p}(v)$ and $\varphi ^+_{v,p}$ acts only on the right vertices of $\mathcal {E}_{X,s,p}(v)$ . Furthermore, if a letter a belongs to $E^-_{X,s}(v) \cap E^-_{X,s}(v')$ (respectively, to $E^+_{X,p}(v) \cap E^+_{X,p}(v')$ ) then $\varphi ^-_{v,s}(a) = \varphi ^-_{v',s}(a)$ (respectively, $\varphi ^+_{v,p}(a) = \varphi ^+_{v',p}(a)$ ). Thus we can define partial maps $\varphi ^-_{s},\varphi ^+_{p}:\mathcal {A} \to \mathcal {B}$ by $\varphi ^-_{s}(a) = \varphi ^-_{\varepsilon ,s}(a)$ whenever $a \in E^-_{X,s}(\varepsilon )$ and by $\varphi ^+_{p}(a) = \varphi ^+_{\varepsilon ,p}(a)$ whenever $a \in E^+_{X,p}(\varepsilon )$ .

4.3 Stability of dendricity

In this section, we use the results and notation of the previous section to understand under which conditions a dendric bispecial factor only has dendric bispecial extended images under some morphism. We then characterize the morphisms for which every dendric bispecial factor only has dendric bispecial extended images.

If X is a shift space over $\mathcal {A}$ and v is a dendric bispecial factor of X, we say that an injective and strongly left proper morphism $\sigma :\mathcal {A}^* \to \mathcal {B}^*$ is dendric preserving for $v \in \mathcal {L}(X)$ if all bispecial extended images of v under $\sigma $ are dendric. We extend this definition by saying that a morphism is dendric preserving for a shift space X if it is dendric preserving for all $v \in \mathcal {L}(X)$ .

Proof Let us first assume that every bispecial extended image of v is dendric. We show condition (2), the other one being symmetric. Consider $p \in \mathcal{T}^{\kern1.5pt+}_v(\sigma )$ . The graph $\mathcal {E}_{X,s_0,p}(v)$ is a subgraph of $\mathcal {E}_{X}(v)$ , which is a tree. Thus, $\mathcal {E}_{X,s_0,p}(v)$ is acyclic. Let us show that it is connected. As there is no isolated vertex, it suffices to show that for all distinct right vertices $b_1,b_2$ of $\mathcal {E}_{X,s_0,p}(v)$ , there is a path in $\mathcal {E}_{X,s_0,p}(v)$ from $b_1$ to $b_2$ . Assume by contrary that there exist two right vertices $b_1,b_2$ of $\mathcal {E}_{X,s_0,p}(v)$ that are not connected.

For $i \in \{1,2\}$ , let $A_i$ denote the set of left vertices of $\mathcal {E}_{X,s_0,p}(v)$ that are connected to $b_i$ . Consider a maximal word $s'$ (for the suffix order) in $\{s(a_1,a_2) \mid a_1 \in A_1,a_2 \in A_2\}$ . Let also $B_i$ , $i \in \{1,2\}$ , denote the set of right vertices of $\mathcal {E}_{X,s',p}(v)$ that are connected to vertices of $A_i$ and consider a maximal word $p'$ (for the prefix order) in $\{p(b_1',b_2') \mid b_1' \in B_1,b_2' \in B_2\}$ . We claim that the extension graph of the bispecial extended image $u = s' \sigma (v) p'$ is not connected.

Let Y be the image of X under $\sigma $ and let $\varphi $ be the morphism from $\mathcal {E}_{X,s',p'}(v)$ to $\mathcal {E}_Y(u)$ given by Proposition 4.7. By maximality of $s'$ and $p'$ , the morphism $\varphi $ identifies two left vertices $a,a'$ (respectively, right vertices $b,b'$ ) only if they belong to the same $A_i$ (respectively, $B_i$ ). This implies that $\mathcal {E}_Y(u)$ is not connected, which is a contradiction.

Let us now show that, under the conditions (1) and (2), any bispecial extended image of v is dendric. By Corollary 4.3, the bispecial extended images of v are of the form $s \sigma (v) p \in \mathcal {L}(Y)$ where s is in $\mathcal {T}^{\kern1.5pt-}_v(\sigma )$ and p is in $\mathcal{T}^{\kern1.5pt+}_v(\sigma )$ .

For any such pair $(s, p)$ , we first show that the graph $\mathcal {E}_{X,s,p}(v)$ is a tree. It is trivially acyclic as it is a subgraph of $\mathcal {E}_{X,s,p_0}(v)$ , which is assumed to be a tree. Let us show that it is connected. Let $b_1,b_2$ be right vertices of $\mathcal {E}_{X,s,p}(v)$ . As $\mathcal {E}_{X,s,p}(v)$ is a subgraph of both $\mathcal {E}_{X,s_0,p}(v)$ and $\mathcal {E}_{X,s,p_0}(v)$ which are trees, there exist a path q in $\mathcal {E}_{X,s_0,p}(v)$ and a path $q'$ in $\mathcal {E}_{X,s,p_0}(v)$ connecting $b_1$ and $b_2$ . In particular, the right vertices occurring in q belong to $E^+_{X,p}(v)$ and the left vertices occurring in $q'$ belong to $E^-_{X,s}(v)$ . As $\mathcal {E}_{X,s_0,p}(v)$ and $\mathcal {E}_{X,s,p_0}(v)$ are both subgraphs of $\mathcal {E}_{X,s_0,p_0}(v)$ , which is a tree, the paths q and $q'$ coincide. It means that this path only goes through left vertices belonging to $E^-_{X,s}(v)$ and through right vertices belonging to $E^+_{X,p}(v)$ . This implies that it is a path of $\mathcal {E}_{X,s,p}(v)$ , and hence that $b_1$ and $b_2$ are connected in $\mathcal {E}_{X,s,p}(v)$ .

We now show that if $u = s \sigma (v)p$ is an extended image of v, then it is dendric. By Proposition 4.7, $\mathcal {E}_Y(u)$ is the image of $\mathcal {E}_{X,s,p}(v)$ under some graph morphism $\varphi $ , and hence it is connected. We proceed by contradiction to show that it is acyclic. Assume that $c = (a_1,b_1,a_2,b_2, \ldots , a_{n},b_{n},a_1)$ , $n \geq 2$ , is a non-trivial cycle in $\mathcal {E}_Y(u)$ , where $a_1,\ldots ,a_{n}$ are left vertices and $b_1,\ldots ,b_{n}$ are right vertices. Again by Proposition 4.7, for every $i\leq n$ , there exist

• • a child $s_i$ of s in $\overline {\mathcal {T}^{\kern1.5pt-}_v(\sigma )}$ ,

• • a child $p_i$ of p in $\overline {\mathcal{T}^{\kern1.5pt+}_v(\sigma )}$ ,

• • left vertices $a_i', a_i"$ of $\mathcal {E}_{X,s,p}(v)$ , belonging to $E^-_{X,s_i}(v)$ ,

• • right vertices $b_i', b_i"$ of $\mathcal {E}_{X,s,p}(v)$ , belonging to $E^+_{X,p_i}(v)$ ,

such that $\varphi (a_i') = \varphi (a_i") = a_i$ , $\varphi (b_i') = \varphi (b_i") = b_i$ and such that the pairs

$$ \begin{align*} & (a_j',b_j'), (a_{j+1}",b_j"), \quad j < n, \\[-3pt] & (a_n',b_n'), (a_1",b_n"),\\[-24pt] \end{align*} $$

are edges of $\mathcal {E}_{X,s,p}(v)$ .

Observe that as $\mathcal {E}_{X,s,p}(v)$ is a tree, for each $i\leq n$ there is a unique simple path $q_{i}$ from $a_{i}"$ to $a_{i}'$ and a unique simple path $q_i'$ from $b_i'$ to $b_i"$ . In $\mathcal {E}_{X,s,p}(v)$ , we thus have the circuit

$$ \begin{align*} c' = \,&(\underbrace{a_1",\ldots,a_1'}_{q_1}, \underbrace{b_1',\ldots,b_1"}_{q_1'}, \underbrace{a_2",\ldots,a_2'}_{q_2}, \underbrace{b_2',\ldots,b_2"}_{q_2'}, \ldots,\\ &\underbrace{a_n",\ldots,a_n'}_{q_n}, \underbrace{b_n',\ldots,b_n"}_{q_n'}, a_1"). \end{align*} $$

We will now prove that the image of $c'$ by $\varphi $ reduces to the non-trivial cycle c of $\mathcal {E}_Y(u)$ . By reducing, we mean that we remove consecutive redundant edges, that is, every occurrence of $a,b,a$ in the path is replaced by a. This will imply that $c'$ is not trivial and contradict the fact that $\mathcal {E}_{X,s,p}(v)$ is a tree, which will end the proof.

As $\mathcal {E}_{X,s_i,p}(v)$ is a sub-tree of $\mathcal {E}_{X,s,p}(v)$ , the path $q_i$ is a path of $\mathcal {E}_{X,s_i,p}(v)$ , otherwise this would contradict the fact that $\mathcal {E}_{X,s,p}(v)$ is acyclic. In particular, the only left vertex of $\varphi (q_i)$ is $a_i$ and thus $\varphi (q_i)$ reduces to the length- $0$ path $a_i$ in $\mathcal {E}_Y(u)$ . Similarly, $q_i'$ is a path of $\mathcal {E}_{X,s,p_i}(v)$ and thus $\varphi (q_i')$ reduces to the length- $0$ path $b_i$ . This concludes the proof that $\varphi (c')$ reduces to c.

The previous result is illustrated in the preceding examples. Indeed, for $\delta $ and v as in Example 4.4, we have $\mathcal {T}^{\kern1.5pt-}_v(\delta ) = \{3, \varepsilon \}$ and $\mathcal{T}^{\kern1.5pt+}_v(\delta ) = \{1\} = \{p_0\}$ . The extension graph $\mathcal {E}_{X,3,1}(v)$ in Figure 4 being a tree, v has only dendric bispecial extended images, as already observed in Figure 3.

Another consequence of Proposition 4.8 is given by the following corollary.

Proof If $\mathcal {T}^{\kern1.5pt-}(\sigma ) = \{s_0\}$ and $\mathcal{T}^{\kern1.5pt+}(\sigma ) = \{p_0\}$ , the fact that $\sigma $ is dendric preserving for any dendric bispecial word v is a direct consequence of Proposition 4.8 since $\mathcal {T}^{\kern1.5pt-}_v(\sigma ) \subset \mathcal {T}^{\kern1.5pt-}(\sigma )$ and $\mathcal{T}^{\kern1.5pt+}_v(\sigma ) \subset \mathcal{T}^{\kern1.5pt+}(\sigma )$ .

To prove the other implication, let us assume that $s_0,s_1 \in \mathcal {T}^{\kern1.5pt-}(\sigma )$ , where $s_0$ is the root of $\mathcal {T}^{\kern1.5pt-}(\sigma )$ and $s_1 \neq s_0$ . Let $a, b$ be such that $s_1 = s(a, b)$ . As $s_0 \in \mathcal {T}^{\kern1.5pt-}(\sigma )$ , there exists c such that $s_1$ is not a suffix of $\sigma (c)$ . In particular, we have $\#\mathcal {A} \geq 3$ .

Let $a_1, \ldots , a_n$ be the elements of $\mathcal {A} \setminus \{a, b, c\}$ . Let us denote by X the shift space coding the interval exchange transformation represented below (for precise definitions and more details about interval exchanges, see Subsection 6.2).

The extension graph of the word $\varepsilon $ is given by

It is a tree and thus $\varepsilon $ is dendric bispecial. However, the graph $\mathcal {E}_{X, s_1, p_0}(\varepsilon )$ is not connected as it does not contain the vertex c on the left but both a and b are left vertices. By Proposition 4.8, $\sigma $ is not dendric preserving for $\varepsilon $ . This proves that $\mathcal {T}^{\kern1.5pt-}(\sigma )$ must contain exactly one element. Similarly, $\mathcal{T}^{\kern1.5pt+}(\sigma )$ also contains exactly one element.

The previous result characterizes injective and strongly left proper morphisms for which every dendric bispecial factor has only dendric bispecial extended images. However, the condition does not imply that the image of a dendric shift by such a morphism $\sigma $ is again dendric. Indeed, the result gives information only on the bispecial factors that are extended images under $\sigma $ , that is, that have an antecedent. The next result characterizes those morphisms $\sigma $ for which even the new initial bispecial factors are dendric. For any letter $a \in \mathcal {A}$ , let $\alpha _a$ and $\bar {\alpha }_a$ denote the so-called Arnoux–Rauzy morphisms

$$ \begin{align*} \alpha_a(b) = \begin{cases} a & \text{ if } b = a,\\ ab & \text{ otherwise,} \end{cases} \quad \bar{\alpha}_a(b) = \begin{cases} a & \text{ if } b = a,\\ ba & \text{ otherwise.} \end{cases} \end{align*} $$

Proposition 4.11. The injective and strongly left proper morphisms preserving dendricity, that is, such that the image of any dendric shift is a dendric shift, are exactly the morphisms

$$ \begin{align*} \bar{\alpha}_{a_1} \circ \cdots \circ \bar{\alpha}_{a_n} \circ \alpha_\ell \circ \pi \end{align*} $$

for any $n \geq 0$ , any $a_1, \ldots , a_n \in \mathcal {A} \setminus \{\ell \}$ and any permutation $\pi $ of $\mathcal {A}$ .

Proof Using Corollary 4.10, an injective and strongly left proper morphism $\sigma $ for the letter $\ell $ preserves dendricity if and only if the following conditions are satisfied:

1. (1) the sets $\mathcal {T}^{\kern1.5pt-}(\sigma )$ and $\mathcal{T}^{\kern1.5pt+}(\sigma )$ both only contain one element;

2. (2) if $F_\sigma $ is the set

   $$ \begin{align*} F_\sigma = \operatorname{\mathrm{Fac}}(\{\sigma(a)\ell : a \in \mathcal{A}\}), \end{align*} $$
   then any word $w \in F_\sigma $ such that $|w|_\ell = 0$ is dendric in $F_\sigma\kern-1.2pt $ .

Let $\sigma = \bar {\alpha }_{a_1} \circ \cdots \circ \bar {\alpha }_{a_n} \circ \alpha _\ell \circ \pi $ for $a_1, \ldots , a_n \in \mathcal {A} \setminus \{\ell \}$ . It is easily verified that $\sigma $ is injective and strongly left proper for the letter $\ell $ . As conditions (1) and (2) only depend on the set $\sigma (\mathcal {A})$ , one can assume that $\pi = {\textrm {id}}$ . For any letter c, $\ell c$ is a prefix of $\alpha _\ell (c) \ell $ and thus

$$ \begin{align*} (\bar{\alpha}_{a_1} \circ \cdots \circ \bar{\alpha}_{a_n}(\ell)) c \end{align*} $$

is a prefix of $\sigma (c) \ell $ . This shows that

$$ \begin{align*} \mathcal {T}^{\kern1.5pt+}(\sigma) = \{\bar{\alpha}_{a_1} \circ \cdots \circ \bar{\alpha}_{a_n}(\ell)\}. \end{align*} $$

Similarly, $c \ell $ is a suffix of $\ell \bar {\alpha }_\ell (c)$ and thus

$$ \begin{align*} c (\alpha_{a_1} \circ \cdots \circ \alpha_{a_n} (\ell)) \end{align*} $$

is a suffix of

$$ \begin{align*} \ell (\alpha_{a_1} \circ \cdots \circ \alpha_{a_n} \circ \bar{\alpha}_\ell(c)) = (\bar{\alpha}_{a_1} \circ \cdots \circ \bar{\alpha}_{a_n} \circ \alpha_\ell(c)) \ell = \sigma(c) \ell. \end{align*} $$

Thus $\mathcal {T}^{\kern1.5pt-}(\sigma )$ only contains one element and $\sigma $ satisfies the condition (1). To prove condition (2), let us proceed by induction on n. If $n = 0$ , then the only bispecial word is $\varepsilon $ and it is easy to verify that it is dendric. If $\sigma ' = \bar {\alpha }_{a_2} \circ \cdots \circ \bar {\alpha }_{a_n} \circ \alpha _\ell $ satisfies condition (2), then simple adaptions of Proposition 4.1 and of Proposition 4.8 tell us that, as $\bar {\alpha }_{a_1}$ is strongly right proper for the letter $a_1$ and the images of letters by $\bar {\alpha }_{a_1}$ have a unique longest common suffix and a unique longest common prefix, it suffices to prove that the words $w \in F_\sigma $ such that $|w|_{a_1} = 0$ are dendric. These words are the elements of $\{\varepsilon \} \cup \mathcal {A} \setminus \{a_1\}$ , of which only $\varepsilon $ is bispecial. The conclusion follows.

Let us now assume that $\sigma '$ is a strongly left proper morphism for the letter $\ell $ which satisfies conditions (1) and (2). As $\mathcal {S}(\sigma ') = \{s_0\}$ , for any letter $a \in \mathcal {A}$ , $as_0$ is the suffix of some $\sigma '(b)$ . In particular, for $a = \ell $ , this implies that there exists $b \in \mathcal {A}$ such that $\ell s_0 = \sigma '(b)$ and that, for any letter $c \ne b$ , $\sigma '(c)$ is strictly longer than $\sigma '(b)$ . Similarly, $p_0 \ell $ is the prefix of some $\sigma (b') \ell $ and thus $\sigma '(b') = p_0$ and, as $\sigma '(b')$ must be strictly shorter than any other $\sigma '(a)$ , we obtain $b = b'$ and $p_0 = \ell s_0$ . We can thus assume that $\sigma ' = \sigma \circ \pi $ where $\pi $ is a permutation of $\mathcal {A}$ such that $\ell s_0 a$ is a prefix of $\sigma (a) \ell $ for all $a \in \mathcal {A}$ . In particular, $\sigma (\ell ) = \ell s_0$ . We have

$$ \begin{align*} F_\sigma = F_{\sigma'}. \end{align*} $$

By construction, for any prefix u of $s_0 \ell $ and any suffix v of $\ell s_0$ ,

$$ \begin{align*} E_{F_\sigma}^-(u) = \mathcal{A} \quad \text{and} \quad E_{F_\sigma}^+ = \mathcal{A}. \end{align*} $$

In particular, if $s_0 \ell \in a \mathcal {A}^*$ and $\ell s_0 \in \mathcal {A}^* b$ , then

$$ \begin{align*} E_{F_\sigma}(\varepsilon) = (\mathcal{A} \times \{a\}) \cup (\{b\} \times \mathcal{A}) \end{align*} $$

because $\varepsilon $ is dendric in $E_{F_\sigma }$ . Thus, any occurrence of $c \ne b$ in $F_\sigma $ can only be followed by an occurrence of a. Let us use this observation to prove that $\sigma = \bar {\alpha }_{a_1} \circ \cdots \circ \bar {\alpha }_{a_n} \circ \alpha _\ell $ for some letters $a_1, \ldots , a_n \in \mathcal {A} \setminus \{\ell \}$ . If $s_0 = \varepsilon $ , then $a = b = \ell $ and thus $\sigma (c) = \ell c$ for all $c \in \mathcal {A} \setminus \{\ell \}$ and $\sigma = \alpha _\ell $ . If $s_0$ is not empty, then a is the first letter of $s_0$ and b the last one. In particular, a and b cannot be the letter $\ell $ and, as $s_0\ell $ is an element of $F_\sigma $ , a cannot only be followed by occurrences of a; thus a must be equal to b. For any letter $c \in \mathcal {A}$ , we know that $\sigma (c)$ begins with $\ell $ and that any letter $d \ne a$ in $\sigma (c)$ is followed by an a; thus

$$ \begin{align*} \sigma(c) \in \ell a (\{a\} \cup (\mathcal{A} \setminus \{\ell\}) a)^*. \end{align*} $$

Let us define the morphism $\tau $ such that

$$ \begin{align*} \sigma(c) = \bar{\alpha}_a \circ \tau(c). \end{align*} $$

This morphism is unique and $\tau (c)$ is obtained by removing an occurrence of a after each letter $d \ne a$ in $\sigma (c)$ . By construction, $\tau $ is injective and strongly left proper for the letter $\ell $ . In addition, $s_0$ begins and ends with the letter a, and thus there exists $s_0' \in \mathcal {A}^*$ such that

$$ \begin{align*} a \bar{\alpha}_a (s_0') = s_0. \end{align*} $$

It is easy to check that, as $\ell s_0 c$ is a prefix of $\sigma (c) \ell $ , $\ell s_0' c$ is a prefix of $\tau (c) \ell $ and that, as $c s_0$ is a suffix of $\sigma (c)$ , $c s_0'$ is a suffix of $\tau (c)$ for all $c \in \mathcal {A}$ . Thus, $\mathcal {S}(\tau )$ and $\mathcal {P}(\tau )$ both contain only one element and $\tau $ satisfies the condition (1). In addition, for all $w \in F_\tau $ and all $c, d \in \mathcal {A}$

$$ \begin{align*} cwd \in F_\tau \Leftrightarrow ca \bar{\alpha}_a(w) d \in F_\sigma. \end{align*} $$

Indeed, this equivalence is direct if $c \ne a$ and, for $c = a$ , it derives from the fact that $a \ne \ell $ ; thus, if $awd \in F_\tau $ , then there exists $c'$ such that $c'awd \in F_\tau $ . As a consequence, the extension graph of w in $F_\tau $ is the same as the extension graph of $a \bar {\alpha }_a(w)$ in $F_\sigma $ and $\tau $ satisfies the condition (2). By construction, we have $|s_0'| < |s_0|$ and thus we can conclude by iterating the proof on $\tau $ .

5.1 Return morphisms in the ternary case

Let us start with an example. Assume that X is a minimal dendric shift over $\mathcal {A}_3$ and that the extension graph of $\varepsilon $ in X is

The associated Rauzy graph $G_1(X)$ is

From it, we deduce that:

• • the return words to $1$ are $1$ , $12$ , and $132$ ;

• • the return words to $2$ are of the form $21^k$ or $21^k3$ with $k \geq 1$ ;

• • the return words to $3$ belong to $3(21^+)^+$ .

An additional restriction concerning the powers of $1$ occurring in the return words to $2$ can be deduced from the fact that X is dendric. We claim that if $21^k$ is a return word to $2$ , then the other return words cannot be of the form $21^\ell $ for some $\ell \geq k+2$ . Indeed, if both $21^k$ and $21^{\ell }$ , $k \geq 1$ , $\ell \geq k+2$ , are return words, then by definition of return words, the words $21^k2, 21^\ell 2$ belong to $\mathcal {L}(X)$ . This implies that there is a cycle in the extension graph of $1^{k}$ , which contradicts the fact that X is dendric. In addition, the third return word cannot be of the form $21^n3$ with $n \geq \min \{k, \ell \} + 2$ for the same reason. Similarly, if $21^k3$ and $21^\ell 3$ are return word to $2$ then $|k - \ell | \leq 1$ and the third return word is $21^n$ with $n \leq \min \{k, \ell \} + 1$ . Therefore, the set of return words to $2$ is one of the following for some $k \geq 1$ and some $1 \leq \ell \leq k+1$ :

$$ \begin{align*} \{21^k,21^{k+1},21^\ell 3\}, \ \{21^\ell, 21^k 3,21^{k+1}3\}. \end{align*} $$

Return words to $3$ are less easily described. Since $\mathcal {R}(3) \subset 3(21^+)^+$ and $\#(\mathcal {R}(3)) = 3$ , the set $\mathcal {R}(3)$ is determined by three sequences $(k^{(j)}_i)_{1 \leq i \leq n_j}$ , $j \in \{1,2,3\}$ such that

$$ \begin{align*} \mathcal{R}(3) = \{321^{k^{(j)}_1}21^{k^{(j)}_2} \cdots 21^{k^{(j)}_{n_j}} \mid j \in \{1,2,3\}\}. \end{align*} $$

Similar arguments show that there exist inequality constraints between the $k^{(j)}_i$ , but precisely describing the three sequences $(k^{(j)}_i)_{1 \leq i \leq n_j}\kern-1pt$ , $j \in \{1,2,3\}$ , is much more tricky. The main reason for this difference is that the letter $3$ is not left special in X. If u is the smallest left special factor having $3$ as a suffix, then writing $u = v3$ , we have $v \mathcal {R}(3) = \mathcal {R}(u)v$ . To better understand the possible sequences $(k^{(j)}_i)_{1 \leq i \leq n_j}$ , we thus need the Rauzy graph of order $|u|$ of X and not just $G_1(X)$ .

With the notation of Theorem 3.1, any choice of sequence of letters $(a_n)_{n \geq 1}$ leads to a directive sequence of X. Consequently, in the following we will only consider return words to left special letters with the ‘simplest’ return words. In other words, if the extension graph of the empty word in X is as in the previous example, we will only consider the coding morphisms associated with the left special letter $1$ .

Up to a permutation on $\mathcal {A}_3$ , the possible extension graphs of the empty word for minimal dendric shifts on $\mathcal {A}_3$ are given in Figures 5 and 6. They must satisfy two conditions: $\mathcal {E}(\varepsilon )$ must be a tree and the associated Rauzy graph $G_1(X)$ must be strongly connected (by minimality of X). We always assume that $1$ is a left special letter and we present these associated Rauzy graph of order 1 as well as coding morphisms associated with $\mathcal {R}(1)$ . Whenever some power appear in an image, we always have $k \geq 1$ . The reason why we only have k and $k+1$ as exponent is the same as in the previous example: a bigger difference would contradict dendricity by inducing a cycle in some extension graph. We denote the set

$$ \begin{align*} \mathcal{S}_3 = \{\alpha,\beta,\gamma,\eta\} \cup \{\delta^{(k)},\zeta^{(k)} \mid k \geq 1\} \end{align*} $$

of morphisms as defined in Figures 5 and 6.

Figure 5

The cases with a unique left special letter and/or a unique right special letter.

Figure 6

The cases with two left special letters and two right special letters.

Let $\Sigma _3$ be the symmetric group on $\mathcal {A}_3 = \{1, 2, 3\}$ . If $\mathcal {A}_3 = \{a, b, c\}$ , we let $\pi _{abc} \in \Sigma _3$ denote the permutation $1 \mapsto a$ , $2 \mapsto b$ , $3 \mapsto c$ .

Note that the previous result is also true when considering $\Sigma _3\mathcal {S}_3$ -adic representations but, for our results, $\Sigma _3\mathcal {S}_3\Sigma -3$ -adic representations are more convenient.

While Proposition 5.1 deals with $\Sigma _3\mathcal {S}_3\Sigma _3$ -adic representations, it is obvious that only the morphisms in $\mathcal {S}_3$ really matter. In the next sections, we essentially focus on them and we involve permutations only when they are needed.

5.2 Conditions for having only dendric bispecial extended images

Assume that X is a minimal shift space over $\mathcal {A}$ and that $v \in \mathcal {L}(X)$ is a bispecial factor and let Y be the image of X under some injective and strongly left proper morphism $\sigma : \mathcal {A}^* \to \mathcal {B}^*$ . Recall from §4.2 (and, in particular, Proposition 4.7) that the extension graph of any bispecial extended image of v under $\sigma $ is the image under two consecutive graph morphisms $\varphi ^-_s$ and $\varphi ^+_p$ of a subgraph of $\mathcal {E}_X(v)$ . In this section, we determine those graph morphisms when $\sigma $ is a morphism in $\mathcal {S}_3$ and we give necessary and sufficient conditions on the extension graph of $v \in \mathcal {L}(X)$ so that v only has dendric bispecial extended images. In this particular case, since the alphabet has cardinality 3, $\mathcal{T}^{\kern1.5pt+}(\sigma )$ and $\mathcal {T}^{\kern1.5pt-}(\sigma )$ have cardinality at most 2. Tables 3 and 4 define the (possibly partial) maps $\varphi ^-_s, \varphi ^+_p: \mathcal {A}_3 \to \mathcal {A}_3$ associated with each morphism $\sigma \in \mathcal {S}_3$ .

Table 3

Definition of the graph morphisms $\varphi ^-_s$ and $\varphi ^+_p$ associated with the morphisms $\alpha $ , $\beta $ , and $\gamma $ .

Table 4

Definition of the graph morphisms $\varphi ^-_s$ and $\varphi ^+_p$ associated with the morphisms $\delta ^{(k)}$ , $\zeta ^{(k)}$ , and $\eta $ .

A direct application of Proposition 4.8 shows that whenever v is dendric, then v has only dendric bispecial extended images if and only if the following conditions are satisfied:

1. (1) either $\mathcal {T}^{\kern1.5pt-}_v(\sigma ) = \{s_0\}$ , or both $\mathcal {T}^{\kern1.5pt-}_v(\sigma ) = \{s_0,s\}$ and $\mathcal {E}_{X,s,p_0}(v)$ is a tree;

2. (2) either $\mathcal{T}^{\kern1.5pt+}_v(\sigma ) = \{p_0\}$ , or both $\mathcal{T}^{\kern1.5pt+}_v(\sigma ) = \{p_0,p\}$ and $\mathcal {E}_{X,s_0,p}(v)$ is a tree.

We first give a handier interpretation of these conditions. Observe that for convenience, we actually characterize the dendric bispecial factors $v \in \mathcal {L}(X)$ that have a non-dendric bispecial extended image. When considering a letter $a \in \mathcal {A}_3$ as a vertex of $\mathcal {E}(v)$ , we respectively write $a^-$ or $a^+$ to emphasize that a is considered as a left or right vertex.

For $v \in \mathcal {L}(X)$ , we define $\mathcal {C}_X^-(v)$ (respectively, $\mathcal {C}_X^+(v)$ ) as the set of letters $a \in \mathcal {A}$ such that the subgraph of $\mathcal {E}_X(v)$ obtained by removing the vertex $a^-$ (respectively, $a^+$ ) and all the induced isolated vertices (if any) are not connected. When the context is clear, the subscript X will be omitted.

Example 5.4. Assume that v is a dendric bispecial factor in some minimal ternary shift space X with extension graph

Thus, we have $3 \in \mathcal {C}^-(v)$ and $1 \in \mathcal {C}^+(v)$ . If $Y_1$ is the image of X under $\beta $ , the bispecial extended images of v in $Y_1$ are $u_1 = \beta (v)1$ and $u_2 = 2 \beta (v)1$ and they have the following extension graphs:

Similarly, if $Y_2$ is the image of X under $\gamma $ , the bispecial extended images of v in $Y_2$ are $w_1 = \gamma (v)1$ and $w_2 = \gamma (v)12$ and they have the following extension graphs:

5.3 Ternary dendric preserving morphisms

Assuming that $v \in \mathcal {L}(X)$ is a dendric bispecial factor, Proposition 5.3 characterizes under which conditions v has a non-dendric bispecial extended image under $\sigma \in \mathcal {S}_3$ or, in other words, under which conditions $\sigma \in \mathcal {S}_3$ is not dendric preserving for v. As we consider the ternary case, we denote by $\operatorname {\mathrm {DP}}(v)$ the set of dendric preserving morphisms for v in $\mathcal {S}_3$ .

When X is a ternary dendric shift, we extend the notation $\mathcal {C}^-$ and $\mathcal {C}^+$ and set

$$ \begin{align*} \mathcal{C}^-(X) & = \bigcup_{v \,{\in}\, \mathcal{L}(X)} \mathcal{C}^-_X(v), \\ \mathcal{C}^+(X) & = \bigcup_{v \,{\in}\, \mathcal{L}(X)} \mathcal{C}^+_X(v), \\ \operatorname{\mathrm{DP}}(X) &= \bigcap_{v \,{\in}\, \mathcal{L}(X)} \operatorname{\mathrm{DP}}(v). \end{align*} $$

Using Proposition 5.3, the sets $\mathcal {C}^-(X)$ and $\mathcal {C}^+(X)$ completely determine the set $\operatorname {\mathrm {DP}}(X)$ of all morphisms in $\mathcal {S}_3$ that are dendric preserving for X. In this section, we in particular show that $\mathcal {C}^-(X)$ and $\mathcal {C}^+(X)$ contain at most one letter and we show that, when Y is the image of X under $\sigma \in \operatorname {\mathrm {DP}}(X)$ , $\mathcal {C}^-(Y)$ (respectively, $\mathcal {C}^+(Y)$ ) is completely determined by $\mathcal {C}^-(X)$ (respectively, $\mathcal {C}^+(X)$ ) and $\sigma $ . The next lemma is a trivial consequence of Remark 5.2.

Lemma 5.6. Let X be a shift space over $\mathcal {A}_3$ which is the image under $\sigma \in \mathcal {S}_3$ of another shift space Z over $\mathcal {A}_3$ . The sets $\mathcal {C}_X^-(\varepsilon )$ and $\mathcal {C}_X^+(\varepsilon )$ are given in Table 5.

Table 5

Sets $\mathcal {C}_X^-(\varepsilon )$ and $\mathcal {C}_X^+(\varepsilon )$ whenever X is the image under $\sigma $ of a shift space over $\mathcal {A}_3$ .

We say that a morphism $\sigma \in \mathcal {S}_3$ is left-invariant (respectively, right-invariant) if $\mathcal {T}^{\kern1.5pt-}(\sigma )$ (respectively, $\mathcal{T}^{\kern1.5pt+}(\sigma )$ ) is a singleton, that is, $\mathcal {T}^{\kern1.5pt-}(\sigma ) = \{s_0\}$ (respectively, $\mathcal{T}^{\kern1.5pt+}(\sigma ) = \{p_0\}$ ). The next lemma directly follows from the definition of the morphisms in $\mathcal {S}_3$ .

We let $\mathcal {S}_{\textrm {LI}}$ and $\mathcal {S}_{\textrm {RI}}$ respectively denote the left-invariant and right-invariant morphisms, that is,

$$ \begin{align*} \mathcal{S}_{\textrm{LI}} = \{\alpha,\gamma\} \quad \text{and} \quad \mathcal{S}_{\textrm{RI}} = \{\alpha,\beta\}. \end{align*} $$

Observe that if $\sigma \in \mathcal {S}_{\textrm {LI}}$ (respectively, $\sigma \in \mathcal {S}_{\textrm {RI}}$ ), then the associated graph morphism $\varphi ^-_{s_0}$ (respectively, $\varphi ^+_{p_0}$ ) is the identity. Moreover, from Table 5, a morphism $\sigma $ belongs to $\mathcal {S}_{\textrm {LI}}$ (respectively, to $\mathcal {S}_{\textrm {RI}}$ ) if and only if $\mathcal {C}_X^-(\varepsilon )$ (respectively, $\mathcal {C}_X^+(\varepsilon )$ ) is empty, where X is the image under $\sigma $ of a shift over $\mathcal {A}_3$ .

Lemma 5.10. Let X be a shift space over $\mathcal {A}_3$ , $\sigma \in \mathcal {S}_3$ a left-invariant (respectively, right-invariant) morphism and Y the image of X under $\sigma $ . If $v \in \mathcal {L}(X)$ is a dendric bispecial factor, then

(5.1) $$ \begin{align} \mathcal{C}^-_X(v) &= \bigcup_{u \text{ bispecial extended image of } v} \mathcal{C}^-_Y(u)\nonumber \\ \bigg(\text{respectively, } \mathcal{C}^+_X(v) &= \bigcup_{u \text{ bispecial extended image of } v} \mathcal{C}^+_Y(u)\bigg). \end{align} $$

In particular, if X is dendric and $\sigma $ is in $DP(X)$ , then $\mathcal {C}^-(Y) = \mathcal {C}^-(X)$ (respectively, $\mathcal {C}^+(Y) = \mathcal {C}^+(X)$ ).

Proof Let us assume that $\sigma $ is left-invariant, the other case is symmetric. We first show that if u is a bispecial extended image of v, then $\mathcal {C}^-_Y(u) \subset \mathcal {C}^-_X(v)$ . As $\mathcal {T}^{\kern1.5pt-}(\sigma ) = \{s_0\}$ , there exists $p \in \mathcal{T}^{\kern1.5pt+}(\sigma )$ such that $u = s_0 \sigma (v) p$ . Assume that $a \in \mathcal {C}^-_Y(u)$ . Writing $\mathcal {A}_3 = \{a,b,c\}$ , Remark 5.2 states that the path q from $b^-$ to $c^-$ in $\mathcal {E}_Y(u)$ has length 4. This path q is the image under $\varphi _{s_0,p}$ of a path $q'$ of length at least 4 in $\mathcal {E}_X(v)$ . As $\mathcal {E}_X(v)$ is a tree with at most six vertices and the extremities of $q'$ are left vertices, the path has length exactly 4. As $\varphi ^-_{s_0}$ is the identity, we conclude that $q'$ is a path of length 4 from $b^-$ to $c^-$ in $\mathcal {E}_X(v)$ , and hence that $a \in \mathcal {C}^-_X(v)$ .

If $\mathcal {C}^-_X(v) = \emptyset $ , then equality (5.1) is direct. Thus we only need to prove it when $\mathcal {C}^-_X(v) \neq \emptyset $ . As $\sigma $ is left-invariant, we have by Lemma 5.8 that $\sigma = \alpha $ or $\sigma = \gamma $ .

If $\sigma = \alpha $ , then as $\alpha $ is also right-invariant (see Lemma 5.8), Proposition 4.7 implies that u is the unique bispecial extended image of v and that $\mathcal {E}_Y(u) = \mathcal {E}_X(v)$ (the graph morphism is the identity), and hence that $\mathcal {C}^-_Y(u) = \mathcal {C}^-_X(v)$ .

If $\sigma = \gamma $ , then as $\mathcal{T}^{\kern1.5pt+}(\sigma ) = \{1,12\}$ , (see Table 3), Corollary 4.3 implies that v has at most two bispecial extended images $u_1 = \sigma (v)1$ and $u_2 = \sigma (v)12$ . Let $\varphi = \varphi _{\varepsilon ,1}$ and $\varphi ' = \varphi _{\varepsilon ,12}$ . The morphism $\varphi ^-_{\varepsilon }$ is the identity and thus we have $\varphi = \varphi ^+_{1}$ and $\varphi ' = \varphi ^+_{12}$ .

As $\mathcal {C}^-_X(v) \neq \emptyset $ , by Lemma 5.5 there is a letter $a \in \mathcal {A}_3$ such that $\mathcal {C}^-_X(v) = \{a\}$ . Using Remark 5.2, the path q from $b^-$ to $c^-$ has length 4 in $\mathcal {E}_X(v)$ . Let us write $q = (b^-,x^+,a^-,y^+,c^-)$ , with $x,y \in \mathcal {A}_3$ .

If $1 \in \{x,y\}$ , we assume without loss of generality that $1 = x$ . Then we have $\varphi (q) = (b^-,1^+,a^-,2^+,c^-)$ which is a path of length 4 from $b^-$ to $c^-$ in $\mathcal {E}_Y(u_1)$ . By Remark 5.2 and Lemma 5.5, one has $\mathcal {C}^-_Y(u_1) = \{a\}$ . As $\mathcal {C}^-_Y(u_2) \subset \mathcal {C}^-_X(v)$ by the first part of the proof, we get $\mathcal {C}^-_Y(u_1) \cup \mathcal {C}^-_Y(u_2) = \mathcal {C}^-_X(v)$ .

If $\{x,y\} = \{2,3\}$ , we assume without loss of generality that $(x,y) = (2,3)$ . Then we have $\varphi '(q) = (b^-,1^+,a^-,3^+,c^-)$ which is a path of length 4 from $b^-$ to $c^-$ in $\mathcal {E}_Y(u_2)$ . By Remark 5.2 and Lemma 5.5, one has $\mathcal {C}^-_Y(u_2) = \{a\}$ . As $\mathcal {C}^-_Y(u_1) \subset \mathcal {C}^-_X(v)$ by the first part of the proof, we also get $\mathcal {C}^-_Y(u_1) \cup \mathcal {C}^-_Y(u_2) = \mathcal {C}^-_X(v)$ .

Let us finally show that $\mathcal {C}^-(Y) = \mathcal {C}^-(X)$ . With $\sigma \in \{\alpha , \gamma \}$ , the non-prefix factor of $\sigma (a)$ , $a \in \mathcal {A}_3$ , are not bispecial. Hence, using Proposition 4.1, a bispecial factor $u \in \mathcal {L}(Y)$ is either empty, or a bispecial extended image of some bispecial factor $v \in \mathcal {L}(X)$ . As $\sigma $ is left-invariant, we have $\mathcal {C}^-_Y(\varepsilon ) = \emptyset $ by Lemma 5.6. Using equation (5.1), we get

$$ \begin{align*} \mathcal{C}^-(Y) &= \bigcup_{v \in \mathcal{L}(X), \text{ bispecial}} \bigcup_{u \text{ bispecial extended image of } v} \mathcal{C}^-_Y(u) \\ &=\bigcup_{v \in \mathcal{L}(X), \text{ bispecial}} \mathcal{C}^-_X(v) \\ &= \mathcal{C}^-(X), \end{align*} $$

which ends the proof.

The following corollary is a direct consequence of Lemmas 5.9 and 5.10.