Proof. Let $\sigma =\alpha \circ \beta $ with $\beta : A^*\to B^*$ and $\alpha : B^*\to C^*$ . Assume that $\alpha ,\beta $ are recognizable for aperiodic points. Let $z\in C^{\mathbb {Z}}$ be an aperiodic point. Let $(x,k)$ be a centered $\sigma $ -representation of z. Since $0\le k<|\sigma (x_0)|$ , there is a decomposition $\beta (x_0)=ubv$ with $u,v\in B^*$ and $b\in B$ such that $|\alpha (u)|\le k<|\alpha (ub)|$ . Set $\ell =|u|$ , $m=|\alpha (u)|$ , and $y=S^{\ell }(\beta (x))$ . Then, $y_0=b$ and $z=S^{k-m}(\alpha (y))$ (see Figure 1). Thus, $(y,k-m)$ is a centered $\alpha $ -representation of z and $(x,\ell )$ is a $\beta $ -representation of y. Conversely, if $(y,n)$ is an $\alpha $ -representation of z and $(x,\ell )$ is a centered $\beta $ -representation of y, then $(x,k)$ with $k=|\beta (y_{-\ell }\ldots y_{-1})|+n$ is a centered $\sigma $ -representation of z. This shows the uniqueness of $(x,k)$ .

Proof. Indeed, if $\sigma =\alpha \circ \beta $ with $\beta : A^*\to B^*$ and $\alpha : B^*\to C^*$ , then

$$ \begin{align*} M(\sigma)=M(\,\beta)M(\alpha). \end{align*} $$

If $\operatorname {\mathrm {rank}}(M(\sigma ))=\operatorname {\mathrm {Card}}(A)$ , then $\operatorname {\mathrm {Card}}(A)=\operatorname {\mathrm {rank}}(M(\sigma ))\le \operatorname {\mathrm {rank}}(M(\alpha ))\le \operatorname {\mathrm {Card}}(B)$ . Thus, $\sigma $ is elementary.

Proof. Set $\sigma =\alpha \circ \beta $ . We have

$$ \begin{align*} \ell(\sigma)-\ell(\,\beta)&=\sum_{a\in A}(|\sigma(a)|-|\beta(a)|) =\sum_{a\in A}\sum_{b\in B}(|\alpha(b)||\beta(a)|_b-|\beta(a)|_b)\\ &=\sum_{a\in A}\sum_{b\in B}(|\alpha(b)|-1)||\beta(a)|_b =\sum_{b\in B}\bigg((|\alpha(b)|-1)\sum_{a\in A}|\beta(a)|_b\bigg). \end{align*} $$

Since $\alpha $ is non-erasing, every factor $|\alpha (b)|-1$ is non-negative. Since every b appears in some $\beta (a)$ , every factor $\sum _{a\in A}|\beta (a)|_b$ is positive, whence the conclusion.

Proof. By the hypothesis, there exist $u_0,u_{1},\ldots $ and $u^{\prime }_0,u^{\prime }_{1},\ldots $ with $u_i,u^{\prime }_i\in U$ such that $u_0u_{1}\ldots =u^{\prime }_0u^{\prime }_{1}\ldots. $ We may assume that $u_0\ne u^{\prime }_0$ . For every $n\ge 0$ , there is $v_n$ and $n'\ge 0$ such that $u_0\ldots u_n = u^{\prime }_0\ldots u^{\prime }_{n'}v_n$ . Since $\sigma $ is injective, we have $v_n\notin U^*$ . We may moreover assume that $v_n$ is a prefix of $u^{\prime }_{n'+1}$ . Let $n<m$ be such that $v_n=v_m$ . Set $u^{\prime }_{n'+1}\ldots u^{\prime }_{m'}=v_nw$ (see Figure 2). Then $u=u^{\prime }_0\ldots u^{\prime }_{n'}$ , $v=v_n=v_m$ , and w satisfy equation (4.2).

Proof of Proposition 4.6

Set $U=\sigma (A)$ . Since U is a prefix code, $\sigma $ is injective on $A^{\mathbb {N}}$ . If it is not injective on $A^{-\mathbb {N}}$ , by the symmetric version of Lemma 4.7, there are words $u,v,w$ such that $u,vu,vw,wv\in U^*$ but $v\notin U^*$ . We may assume that $u,v,w$ are chosen of minimal length. Since $\sigma $ is left marked, either u is a prefix of w or w is a prefix of u. In the first case, set $w=uw'$ . Then, since U is prefix, $u,wv=uw'v\in U^*$ imply $w'v\in U^*$ . However, then $(vu)(w'v)(u)=(vuw')(vu)$ , which is a contradiction. Finally, if $u=wu'$ , then $vw,vu=vwu'\in U^*$ imply $u'\in U^*$ , and we may replace $u,v,w$ by $u',w,v$ , which is a contradiction again. Thus, $\sigma $ is injective on $A^{-\mathbb {N}}$ .

Assume now that $y\in B^{\mathbb {Z}}$ has two distinct centered $\sigma $ -representations $(x,k)$ and $(x',k')$ . We may assume $k=0$ . Since $\sigma $ is injective on $A^{-\mathbb {N}}$ , we have $k'\ne 0$ . We will prove that y is periodic.

Let P be the set of proper prefixes of U. For $p\in P$ and $a\in A$ , there is at most one $q\in P$ such that $p\sigma (a)\in U^*q$ . We denote $q=p\cdot a$ . Let $p_0=y_{-k'}\ldots y_{-1}$ . Since $y=\sigma (x)=S^{k'}(\sigma (x'))$ , we have

$$ \begin{align*} \sigma(\ldots x^{\prime}_{-2}x^{\prime}_{-1})p_0&=\sigma(\ldots x_{-1}),\\ p_0\sigma(x_0x_1\ldots)&=\sigma(x^{\prime}_0x^{\prime}_1\ldots). \end{align*} $$

As a consequence, there exists for each $n\in \mathbb {Z}$ a word $p_n\in P$ such that $p_n\cdot x_n=p_{n+1}$ . Since $\sigma $ is left marked, there is for every non-empty $p\in P$ at most one $a\in A$ such that $p\cdot a$ is in P. However, all $p_n$ are non-empty. This is clear if $n<0$ since otherwise $p_0$ is also empty. For $n>0$ , we have

$$ \begin{align*} \sigma(\ldots x^{\prime}_{i_n})p_n&=\sigma(\ldots x_n),\\ p_n\sigma(x_{n+1}\ldots)&=\sigma(x^{\prime}_{i_n+1}\ldots), \end{align*} $$

and thus, since $\sigma $ is injective on $A^{\mathbb {Z}}$ , $p_n=\varepsilon $ implies that $x=x'$ . Thus, x is periodic and y is also periodic.

Consider the labeled graph with P as a set of vertices and edges $(p,a,q)$ if $p\cdot a=q$ . By what we have seen, the path $\ldots p_n\stackrel {x_n}{\rightarrow }p_{n+1}\ldots $ is a cycle and thus y is periodic.

Proof. Assume first that $\sigma $ is non-erasing. We use an induction on $\ell (\sigma )$ . If $\ell (\sigma )=0$ , set $B=\sigma (A)$ . Let $\alpha $ be the identity on B and let $\beta =\sigma $ . All conditions are clearly satisfied.

Assume now the statement is true for $\ell <\ell (\sigma )$ . Since $\sigma $ is not injective on $A^{\mathbb {N}}$ , we have $\sigma (a_0a_1\ldots )=\sigma (a^{\prime }_0a^{\prime }_1\ldots )$ for some $a_i,a^{\prime }_i\in A$ with $a_0\ne a^{\prime }_0$ . We can assume that $\sigma (a_0)$ is a prefix of $\sigma (a^{\prime }_0)$ . Set $\sigma (a^{\prime }_0)=\sigma (a_0)v$ . If v is empty, set $B=A\setminus \{a_0\}$ . Let $\alpha $ be the restriction of $\sigma $ to B and let $\beta $ be defined by $\beta (a^{\prime }_0)=a_0$ and $\beta (a)=a$ for $a\ne a^{\prime }_0$ . Clearly, $\sigma =\alpha \circ \beta $ and all conditions are satisfied.

Next, assume the v is non-empty. Define $\alpha _1:A^*\to C^*$ by $\alpha _1(a^{\prime }_0)=v$ and $\alpha _1(a)=\sigma (a)$ for $a\ne a^{\prime }_0$ . Next, define $\beta _1:A^*\to A^*$ by $\beta _1(a^{\prime }_0)=a_0a^{\prime }_0$ and $\beta _1(a)=a$ for $a\ne a^{\prime }_0$ . Then, $\sigma =\alpha _1\circ \beta _1$ since

$$ \begin{align*} \alpha_1\circ\beta_1(a^{\prime}_0)=\alpha_1(a_0a^{\prime}_0)=\sigma(a_0)v=\sigma(a^{\prime}_0) \end{align*} $$

and $\alpha _1\circ \beta _1(a)=\alpha _1(a)=\sigma (a)$ if $a\ne a^{\prime }_0$ . The morphism $\beta _1$ is injective on $A^{\mathbb {N}}$ because no word in $\beta _1(A)$ begins with $a^{\prime }_0$ . Thus, $\alpha _1$ is not injective on $A^{\mathbb {N}}$ . By equation (4.1), we have $\ell (\alpha _1)<\ell (\sigma )$ . By induction hypothesis, we have a decomposition $\alpha _1=\alpha _2\circ \beta _2$ for $\beta _2:A^*\to B^*$ and $\alpha _2:B^*\to C^*$ with $\operatorname {\mathrm {Card}}(B)<\operatorname {\mathrm {Card}}(A)$ , the morphism $\alpha _2$ being injective on $B^{\mathbb {N}}$ , and every letter $b\in B$ appearing as the initial letter in the word $\beta _2(a)$ for some $a\in A$ . Note that since $\alpha _1$ is non-erasing, $\beta _2$ is non-erasing.

Set $\beta =\beta _2\circ \beta _1$ . Since $\beta _1,\beta _2$ are non-erasing, $\beta $ is non-erasing. Then, $\sigma =\alpha _1\circ \beta _1=\alpha _2\circ \beta _2\circ \beta _1=\alpha _2\circ \beta $ . The decomposition $\sigma =\alpha _2\circ \beta $ satisfies all the required conditions. Indeed, let $b \in B$ . Then there is $a \in A$ such that b is the first letter of $\beta _2(a)$ . If $a \ne a_0$ , we have $\beta _1(a) = a$ and thus b is the first letter of $\beta (a)$ . Suppose next that $a=a^{\prime }_0$ . Since $\sigma (a_0a_1\ldots )=\sigma (a^{\prime }_0a^{\prime }_1\ldots )$ and since $\alpha _2$ is injective on $B^{\mathbb {N}}$ , we have $\beta (a_0a_1\ldots )=\beta (a^{\prime }_0a^{\prime }_1\ldots )$ . Since $\beta _1(a_0)=a_0$ and $\beta _1(a^{\prime }_0)=a_0a^{\prime }_0$ , we obtain $\beta _2(a_0)\beta (a_1\ldots )=\beta _2(a_0a^{\prime }_0)\beta (a^{\prime }_1\ldots )$ and thus

$$ \begin{align*} \beta(a_1\ldots)=\beta_2(a^{\prime}_0)\beta(a^{\prime}_1\ldots), \end{align*} $$

showing, since $\beta $ is non-erasing, that b is the initial letter of $\beta (a_1)$ .

Consider now a morphism $\sigma $ such that the set $B=\{a\in A\mid \sigma (a)\ne \varepsilon \}$ is strictly contained in A. Let $\beta : A^*\to B^*$ be defined by $\beta (a)=a$ if $a\in B$ and $\beta (a)=\varepsilon $ otherwise. Let $\alpha $ be the restriction of $\sigma $ to $B^*$ . Then, $\sigma =\alpha \circ \beta $ and $\alpha $ is non-erasing. If $\alpha $ is injective on $B^{\mathbb {N}}$ , we are done. Otherwise, by the first part of the proof, we have $\alpha =\alpha _1\circ \beta _1$ with $\alpha _1: B_1^*\to C^*$ and $\beta _1: B^*\to B_1^*$ with $\alpha _1$ injective on $B_1^{\mathbb {N}}$ , $\operatorname {\mathrm {Card}}(B_1)<\operatorname {\mathrm {Card}}(B)$ , and every $b_1\in B_1$ appears as the first letter of some $\beta _1(b)$ . Then, the decomposition $\sigma =\alpha _1\circ (\beta _1\circ \beta )$ satisfies all the conditions.

Proof of Theorem 4.5

Let $\sigma : A^*\to B^*$ be an elementary morphism. We use an induction on $\ell (\sigma )$ . Since $\sigma $ is elementary, it has no erasable letter and the minimal possible value of $\ell (\sigma )$ is $0$ . In this case, $\sigma $ is a bijection from A to B and thus it is recognizable.

Assume now that $\sigma $ is not recognizable on aperiodic points. Thus, there exist ${x,x'\in A^{\mathbb {N}}}$ and w with $0<|w|<|\sigma (x_0)|$ such that $\sigma (x)=w\sigma (x')$ for some proper suffix w of $\sigma (a')$ . Set $\sigma (a')=vw$ . We can then write $\sigma =\sigma _1\circ \tau _1$ with $\tau _1: A^*\to A_1^*$ and $\sigma _1: A_1^*\to B^*$ and $A_1=A\cup \{a"\}$ , where $a"$ is a new letter. We have $\tau _1(a')=a'a"$ and $\tau _1(a)=a$ otherwise. Next, $\sigma _1(a')=v$ , $\sigma _1(a")=w$ , and $\sigma _1(a)=\sigma (a)$ otherwise. Since $\ell (\tau _1)>0$ , we have $\ell (\sigma _1)<\ell (\sigma )$ by equation (4.1).

Since $\tau _1$ is injective on $A^{\mathbb {N}}$ , $\sigma _1$ is not injective on $A_1^{\mathbb {N}}$ . By Proposition 4.9, we can write $\sigma _1=\sigma _2\circ \tau _2$ with $\sigma _2:A_2^*\to B^*$ and $\tau _2:A_1^*\to A_2^*$ for some alphabet $A_2$ such that $\operatorname {\mathrm {Card}}(A_2)<\operatorname {\mathrm {Card}}(A_1)$ and that every letter $c\in A_2$ appears as the first letter of some $\tau _2(a)$ for $a\in A_1$ . Then, by equation (4.1), we have

(4.3) $$ \begin{align} \ell(\sigma_1)\ge \ell(\sigma_2)+\ell(\tau_2). \end{align} $$

If $\operatorname {\mathrm {Card}}(A_2)<\operatorname {\mathrm {Card}}(A)$ , then $\sigma $ is not elementary and we are done. Otherwise, we have $\operatorname {\mathrm {Card}}(A_2)=\operatorname {\mathrm {Card}}(A)$ . We may also assume that $\sigma _2$ and $\tau _2\circ \tau _1$ are elementary since otherwise $\sigma $ is not elementary.

Since $\sigma _2$ is elementary and since $\ell (\sigma _2)\le \ell (\sigma _1)<\ell (\sigma )$ , by the induction hypothesis, $\sigma _2$ is recognizable for aperiodic points.

Since $\sigma =\sigma _2\circ \tau _2\circ \tau _1$ , we have also

(4.4) $$ \begin{align} \ell(\sigma)\ge \ell(\sigma_2)+\ell(\tau_2\circ\tau_1). \end{align} $$

Thus, if $\ell (\sigma _2)>0$ , the inequality $\ell (\tau _2\circ \tau _1)<\ell (\sigma )$ holds. Since $\tau _2\circ \tau _1$ is elementary, we obtain that $\tau _2\circ \tau _1$ is recognizable for aperiodic points by induction hypothesis. Thus, by Proposition 3.6, $\sigma $ is recognizable for aperiodic points.

Let us finally assume that $\ell (\sigma _2)=0$ . Then, $\sigma $ is left marked because $\sigma _2$ is a bijection from $A_2$ onto B and every letter of $A_2$ appears as an initial of $\tau _2(a)$ for $a\in A_1$ . We obtain the conclusion by Proposition 4.6.

Proof. Let $k=|\sigma |$ . Let y be in $X(\sigma )$ . For every $n> 2k$ , there is an integer $m \geq 1$ such that $y_{[-n,n]}$ is a factor of $\sigma ^m(a)$ for some letter $a \in A$ .

Hence, $y_{[-n, n]} = s \sigma (a_1 \ldots a_\ell ) p$ , where $a_i \in A$ , $a_1 \ldots a_\ell $ is a factor of $\sigma ^{m-1}(a)$ , s is a suffix of a word in $\sigma (A)$ and p is a prefix of a word in $\sigma (A)$ . Since $n> 2k$ , at least one letter $a_i$ is such that $\sigma (a_i) \neq \varepsilon $ . We write $a_1 \ldots a_\ell = u_1 \ldots u_r$ , where $r \geq 1$ , $u_j = v_jb_j$ with $b_j \in A, v_j \in A^*$ (the word $v_j$ being possibly the empty word), $\sigma (v_j)=\varepsilon $ , and $\sigma (b_j) \neq \varepsilon $ .

Then, there are integers $n \leq k_1 < k_2 < \cdots < k_{r+1} \leq n+1$ such that $y_{[-n, n]} = s \sigma (u_1) \ldots \sigma (u_r) p$ , with $s = y_{[-n, k_1)}$ , $\sigma (u_j) = y_{[k_j,k_{j+1})}$ , $p= y_{[k_{r+1},n]}$ . Note that $\sigma (u_j)=\sigma (a_j)$ is non-empty and belongs to $\sigma (A)$ .

For every i with $-n + k \leq i \leq n-k$ , we denote by $f_n(i)$ the unique triple $(k_j, k_{j+1}-1, u_j)$ defined above such that $k_j \leq i < k_{j+1}$ .

Since $\sigma (A)$ is finite and since there is a finite number of erasable words in $\mathcal {L}(\sigma )$ by Proposition 2.2, there is a finite number of triples $f_n(0)$ . Thus, there is a strictly increasing sequence $(i_n)_{n \in \mathbb {N}}$ of natural integers such that $f_{i_n}(0)$ is constant. We denote this constant value by $f(0)$ .

Taking a subsequence of $(i_n)_{n \in \mathbb {N}}$ , we may also assume that all $f_{i_n}(-1)$ and $f_{i_n}(1)$ are equal to some triple $f(-1)$ and $f(1)$ , respectively. By iterating his process, we define for each $i \in \mathbb {Z}$ a triple $f(i)=(j_i, \ell _i, u_i)$ . By construction, $f(i) = f(i')$ for all $i, i' \in [j_i, \ell _i)$ .

We now concatenate the words $u_i$ to build a point x as follows. We define a strictly increasing sequence $(j_n)_{n \in \mathbb {Z}}$ of integers by $j_0 = 0$ , for $n> 0$ , $j_n$ is the least integer larger than $j_{n-1}$ such that $f(j_n) \neq f(j_{n-1})$ , and for $n < 0$ , $j_n$ is the largest integer less than $j_{n+1}$ such that $f(j_n) \neq f(j_{n+1})$ . Let $x= \ldots u_{j_{-2}}u_{j_{-1}}.u_{j_0}u_{j_1}u_{j_2}\ldots $ . By construction, $x \in X(\sigma )$ and there is some integer r such that $y = S^r(\sigma (x))$ .

Proof. We first assume that x contains a growing letter. Let $x_i= b$ be the first growing letter of x. Thus, $x = x_{[0, i)}bx'$ , where $x_{[0,i)}$ is non-growing. There are integers $m < m'$ such that $x_{[0,i)}b$ is a prefix of $\sigma ^m(a)$ and of $\sigma ^{m'}(a)$ . Let $r = m'-m$ .

Since $x_{[0,i)}b$ is a prefix of $\sigma ^m(a)$ , $\sigma ^{r}(x_{[0,i)}b)$ is a prefix of $\sigma ^{m'}(a)$ and thus $\sigma ^{r}(x_{[0,i)}b)$ is prefix comparable with $x_{[0,i)}b$ . Since $x_{[0,i)}$ is non-growing, $\sigma ^{r}(x_{[0, i)})$ is a prefix $x_{[0, j)}$ of $x_{[0, i)}$ and $\sigma ^{r}(b) = x_{[j,i)}bu$ , where u is a non-erasable word (otherwise, b would not be growing).

Then, for all integers n, $\sigma ^{nr}(x_{[0, i)}b) = x_{[0,i)}bu\sigma ^r(u) \ldots \sigma ^{(n-1)r}(u)$ . Thus, $\lim _{n \rightarrow +\infty } \sigma ^{m+rn}(a)$ exists. It follows that $\lim _{n \rightarrow +\infty } \sigma ^{m+k+rn}(a)$ exists for every $0 \leq k < r$ . It also follows that x is one of the points $x^{(k,r)}= \lim _{n \rightarrow +\infty } \sigma ^{k+rn}(a)$ for some $0 \leq k < r$ .

Let us show that there is a finite number of such points. If y is another point of S with a growing letter, $y = \lim _{n \rightarrow +\infty } \sigma ^{k'+r'n}(a)$ with $r'> r$ , $0 \leq k' < r'$ , then we have $y = x^{(k^{\prime\prime},r)}$ for some $0 \leq k^{\prime\prime} < r$ .

We now assume that all letters of x are non-growing. There are non-negative integers $r, p \leq \operatorname {\mathrm {Card}}(A)$ such that $\sigma ^r(a) = ubv$ and $\sigma ^p(b) = wbz$ with $u, w$ non-growing, $b \in A$ growing. We get that for any $k \geq 0$ ,

$$ \begin{align*} \sigma^{r + kp}(a) = \sigma^{kp}(u) \sigma^{(k-1)p}(w)\ldots \sigma^p(w)wbz^{(k)}. \end{align*} $$

Since u and w are non-growing, there are non-negative integers $i, i'$ such that $\sigma ^{i'p}(u) = \sigma ^{i'p + ip}(u)$ and $\sigma ^{i'p}(w) = \sigma ^{i'p + ip}(w)$ . It follows that

$$ \begin{align*} \sigma^{r + i'p + kip}(a) = \sigma^{i'p}(u) \sigma^{((i'+ki)-1)p}(w)\ldots \sigma^p(w)wbz^{(i'+ki)}. \end{align*} $$

Note that w is non-erasable since otherwise x would have a growing letter. Thus, for large enough k, we get

$$ \begin{align*} \sigma^{r + i'p + kip}(a) = t z^{k-1} \sigma^{(i'-1)p}(w) \ldots \sigma^p(w)wbz^{(i'+ki)}, \end{align*} $$

where $t = \sigma ^{i'p}(u) \sigma ^{(i' + i -1)p}(w) \ldots \sigma ^{i'p}(w)$ , and $z = \sigma ^{(i'+i -1)p}(w) \ldots \sigma ^{i'p}(w)$ .

Every $x_{[0, n]}$ is a prefix of some $\sigma ^{N_n} (a)$ . There is an infinite number of n such that $N_n$ is equal to $r + i'p + k_nip + h$ for some fixed $0 \leq h < ip$ for some non-negative integer $k_n$ . It follows that for an infinite number n, $x_{[0,n]}$ is a prefix of $\sigma ^h(tz^{k_n-1}t')$ , where $t' = \sigma ^{(i'-1)p}(w) \ldots \sigma ^p(w)w$ . It follows that there is a finite number of words $u,v$ depending only on $\sigma $ such that $x = uv^\omega $ . Hence the conclusion.

Proof. It is enough to show that $\mathcal {L}(\sigma ^n)=\mathcal {L}(\sigma )$ . We first clearly have $\mathcal {L}(\sigma ^n)\subset \mathcal {L}(\sigma )$ . Conversely, let $u\in \mathcal {L}(\sigma )$ . Then u is a factor of some $\sigma ^{m}(a)$ . Let k be such that $kn \leq m < (k+1)n$ . Since every letter appears in $\sigma (A)$ , the letter a appears in $\sigma ^{(k+1)n- m}(b)$ for some letter b and thus u is a factor of $\sigma ^{n(k+1)}(b)$ . Hence, $u \in \mathcal {L}(\sigma ^n)$ .

Proof. Let $\sigma : A^*\to A^*$ be a morphism.

Case 1. We first assume that every letter of A is a letter of some word of $\sigma (A)$ . By Lemma 5.3, we have $X(\sigma ) = X(\sigma ^n)$ for every positive integer n.

It is enough to prove the statement for a power $\sigma ^n$ of $\sigma $ . Indeed, assume that $\sigma ^n$ is recognizable on $X(\sigma ^n)=X(\sigma )$ for aperiodic points. Let x be an aperiodic point $x\in X(\sigma )$ and let $(z,K)$ be its unique centered $\sigma ^n$ -representation. Let $\sigma ^{n-1}(z_0)=uav$ with $a\in A$ be the unique factorization of $\sigma ^{n-1}(z_0)$ such that $|\sigma (u)|\le K<|\sigma (ua)|$ . Set $y=S^{|u|}\sigma ^{n-1}(z)$ and $\sigma (a)=sx_0t$ . Then, $(y,|s|)$ is the unique centered $\sigma $ -representation of x.

Indeed, it is a centered $\sigma $ -representation of x. If $(y',k')$ is another centered $\sigma $ -representation of x, let $(z',r')$ be a centered $\sigma ^{n-1}$ -representation of y. Set $\sigma ^{n-1}(z^{\prime }_0)=u'a'v'$ with $|u'|=r'$ and $\sigma (a')=s'x_0t'$ with $|s'|=k'$ . Then, $u'a'$ is a prefix of $\sigma ^{n-1}(z^{\prime }_0)$ such that $|\sigma (u')|\le |\sigma (u')|+k' <|\sigma (u'a')|$ . Since $(z',|\sigma (u')|+k')$ is a centered $\sigma ^n$ -representation of x, we have $z = z'$ , $K=|\sigma (u')|+k'$ and thus $ua=u'a'$ , which implies $y=y'$ and $ k' = |s|$ .

Choose n such that $\sigma ^n$ has a decomposition $\sigma ^n=\alpha \circ \beta $ with $\beta : A^*\to B^*$ and $\alpha : B^*\to A^*$ , and $\operatorname {\mathrm {Card}}(B)$ minimal. Then, $\tau =\beta \circ \alpha $ is elementary. Indeed, if $\tau =\gamma \circ \delta $ with $\delta :B^*\to C^*$ and $\gamma : C^*\to B^*$ is a decomposition of $\tau $ such that $\operatorname {\mathrm {Card}}(C)<\operatorname {\mathrm {Card}}(B)$ , then $\sigma ^{2n}=(\alpha \circ \gamma )\circ (\delta \circ \beta )$ is a decomposition of $\sigma ^{2n}$ with $\delta \circ \beta : A^*\to C^*$ and $\alpha \circ \gamma : C^*\to A^*$ such that $\operatorname {\mathrm {Card}}(C)<\operatorname {\mathrm {Card}}(B)$ , which is a contradiction.

It is easy to check that $\alpha $ is also elementary. Moreover, we have

(5.1) $$ \begin{align} \beta(X(\sigma))\subset X(\tau). \end{align} $$

Indeed, consider $x\in X(\sigma )$ and let w be a factor of $\beta (x)$ . We have to prove that w is a factor of some $\tau ^m(c)$ for $c\in B$ . Now, since $x \in X(\sigma ^n)$ , there in an $N\ge 1$ such that w is a factor of some $\beta \circ \sigma ^{Nn}(a)$ for $a\in A$ and $N\ge 1$ , and also a factor of $\beta \circ \sigma ^{(N+1)n}(b)$ with a a factor of $\sigma ^n(b)$ (see Figure 4). Since $\sigma ^n=\alpha \circ \beta $ , there is a letter c such that $a\in \alpha (c)$ and $c \in \beta (b)$ . Since $\beta \circ \sigma ^n=\tau ^n\circ \beta $ , we obtain that w is a factor of $\tau ^{(N+1)n}(c)$ .

Figure 4

Proving that w is a factor of $\tau ^m(c)$ .

Let $x\in X(\sigma )$ be an aperiodic point. Consider two centered $\sigma ^n$ -representations $(y,k)$ and $(y',k')$ of x with $y,y'\in X(\sigma )$ . Let $(z, \ell )$ and $(z', \ell ')$ be centered $\sigma ^n$ -representations of y and $y'$ , respectively, with $z,z'\in X(\sigma )$ (we use here Theorem 5.1). Then, $(\beta (z),m)$ and $(\beta (z'),m')$ are, for some unique $m,m'$ , some centered $\tau $ -representations of $\beta (y)$ and $\beta (y')$ , respectively (see Figure 5). The fact that $m,m'$ are unique results from the fact that $\tau $ is elementary and thus recognizable for aperiodic points by Theorem 4.5.

Figure 5

The points $x,y,z$ .

Since $\alpha $ is elementary, it is recognizable for aperiodic points. Since $\alpha (\beta (y))=\sigma ^n(y)$ and $\alpha (\beta (y'))=\sigma ^n(y')$ , this implies that $\beta (y),\beta (y')$ belong to the same orbit. Since $\tau $ is recognizable for aperiodic points, we obtain that $\beta (z)$ and $\beta (z')$ belong to the same orbit. Applying $\alpha $ again, we conclude that $y,y'$ belong to the same orbit. Since x is aperiodic, this implies that $y = y'$ and $k = k'$ . Thus, $\sigma ^n$ is recognizable for aperiodic points.

Case 2. We now prove the general case. We prove the result by induction on the number of letters which do not appear in some word of $\sigma (A)$ . The case where there is no such letter is Case 1 and thus the property holds. Let a be a letter of A which does not appear in a word in $\sigma (A)$ and set $B= A \setminus \{a\}$ . We denote by $\sigma _B$ the morphism $\sigma $ restricted to $B^*$ . By induction hypothesis, $\sigma _B$ is recognizable on $X(\sigma _B)$ for aperiodic points. We denote by K the maximal length of all $\sigma ^n(b)$ for non-growing letters b in B.

Let y be an aperiodic point having two centered $\sigma $ -representations $(x, k)$ and $(x', k')$ with $x, x' \in X(\sigma )$ . We cannot have $x,x'\in X(\sigma _B)$ and we may assume that x belongs to $X(\sigma ) \setminus X(\sigma _B)$ . Thus, there is an integer m such that $x_{[-m, m]}$ is not a factor of any $\sigma ^n(b)$ for $b \in B$ . For each integer $n \geq m$ , there is an integer $N(n)$ such that $x_{[-n,n]}$ is a factor of $\sigma ^{N(n)}(a)$ .

We have $\sigma (a) = b_1 \ldots b_\ell $ with $b_i \in B$ . Since $x_{[-m, m]}$ is not a factor of any $\sigma ^n(b_i)$ , there are integers $1 \leq i_n \leq \ell $ , $-m \leq k_n < m$ such that $x_{[-n, k_n)}$ is a suffix of $\sigma ^{N(n)-1}(b_1 \ldots b_{i_n})$ and $x_{[k_n, n]}$ is a prefix of $\sigma ^{N(n)-1}(b_{i_n+1} \ldots b_\ell )$ . Let $b_{j_n}$ be the last growing letter of $b_1 \ldots b_{i_n}$ and $b_{r_n}$ be the first growing letter of $b_{i_n+1} \ldots b_\ell $ . Note that such growing letters exist for large enough n.

There is an infinite number of integers n such that $i_n = i$ , $j_n = j$ , $r_n = r$ , $k_n = M$ , where $1 \leq j \leq i < r \leq \ell $ and $-m \leq M < m$ .

Since $b_{j+1} \ldots b_i$ and $b_{i+1} \ldots b_{r-1}$ are non-growing, the lengths of all words $\sigma ^{N(n)-1}(b_{j+1} \ldots b_i)$ and $\sigma ^{N(n)-1}(b_{i+1} \ldots b_{r-1})$ are bounded by $K \ell $ . Thus, there is an infinite number of integers n such that moreover $|\sigma ^{N(n)-1}(b_{j+1} \ldots b_i)| = p$ , $|\sigma ^{N(n)-1}(b_{i+1} \ldots b_{r-1})| = p'$ for some fixed integers $0 \leq p, p' \leq K\ell $ .

Let $b = b_j$ and $c = b_r$ . Since $b, c$ are growing, for each n, there are integers $m, m'$ such that $x_{[-n, M-p)}$ is a suffix of $\sigma ^m(b)$ and $x_{[M+p',n]}$ is a prefix of $\sigma ^{m'}(c)$ .

By Proposition 5.2, there are finite sets $L, R$ of respectively left- and right-infinite sequences, and a finite set U of words of length at most $2K\ell $ such that x is a shift of $tut'$ with $t \in L$ , $u \in U$ , and $t' \in R$ . Thus, there is a finite number of such orbits.

We define a sequence $(x^{(i)})_{i \geq 0}$ of two-sided infinite sequences $x^{(i)}$ by $x^{(0)} = x$ and $x^{(i)} \in X(\sigma ) \setminus X(\sigma _B)$ such that $x^{(i-1)} =S^k\sigma (x^{(i)})$ for some k. There is an infinite number of i such that $x^{(i)}$ are shifts of the same sequence. Thus, there are integers $i, j$ with $j \geq 1$ such that $\sigma ^j(x^{(i)})$ is a shift of $x^{(i)}$ . As a consequence, $y \in X(\sigma ) \setminus X(\sigma _B)$ . Thus, $x, x' \in X(\sigma ) \setminus X(\sigma _B)$ .

As above, we define sequences $(x^{(i)})$ and $({x'}^{(i)})$ for x and $x'$ . Thus, there are integers $i, j$ with $j \geq 1$ such that $\sigma ^j(x^{(i)})$ is a shift of $x^{(i)}$ and $\sigma ^{j}({x'}^{(i)})$ is a shift of ${x'}^{(i)}$ . We get that there is an integer i such that $x^{(i)}$ and ${x'}^{(i)}$ are in the same orbit and thus x and $x'$ also.

Now if $x \neq x'$ of $k \neq k'$ with $0 \leq k < |\sigma (x_0)|$ and $0 \leq k' < |\sigma (x^{\prime }_0)|$ , we get that y is periodic, which is excluded. Thus, y has a unique centered $\sigma $ -representation in $X(\sigma )$ .

Proof. Assume that $\sigma $ is not periodic. If $\sigma $ is not injective, there are some distinct ${u,v\in A^*}$ such that $\sigma (u)=\sigma (v)=d$ . Since $\sigma $ is not periodic, there is some w such that ${c=\sigma (w)}$ and $\sigma (u)$ are not powers of the same primitive word. Then, ${^\omega }c\cdot dc^\omega $ is aperiodic and has more than one centered $\sigma $ -representation. Thus, $\sigma $ is not recognizable for aperiodic points.

Proof. The morphism $\sigma $ is recognizable for aperiodic points if and only if every aperiodic point x of $B^{\mathbb {Z}}$ has at most one decomposition in words of $\sigma (A)$ , that is, if there is at most one two-sided infinite path of $\mathcal {A}$ labeled by x going through the state $\omega $ for an infinite number of positive and negative indices. As $\sigma (A)$ is finite, every two-sided infinite path of $\mathcal {A}$ goes through the state $\omega $ for an infinite number of positive and negative indices. Thus, $\sigma $ is recognizable for aperiodic points if and only if $\mathcal {A}$ is unambiguous for aperiodic points.

Proof. Assume that $\mathcal {A}$ is not weakly deterministic. Then there is a state p and a right-infinite sequence x such that there are two paths starting at p labeled x. Since $\mathcal {A}$ is strongly connected, there is a left-infinite path ending at p. Let y be the label of this path. Since $\mathcal {A}$ is non-periodic, we may choose y aperiodic. Then, $y\cdot x$ is an aperiodic point which is the label of more than one path in $\mathcal {A}$ . The case where $\mathcal {A}$ is not weakly co-deterministic is symmetrical.

Proof. Assume that $\mathcal {A}$ is unambiguous for aperiodic points. By Proposition 6.6, condition (i) is satisfied. Let e be an idempotent in $M(\mathcal {A})$ of degree $d\ge 2$ . If the group $G=H(e)$ is not strongly cyclic, there are words of arbitrary large minimal period in $L=\varphi _{\mathcal {A}}^{-1}(G)$ and thus there is an aperiodic sequence $x\in A^{\mathbb {Z}}$ such that all its factors are factors of words in L. Indeed, if G is not strongly cyclic, there are words $u,v$ which are not powers of the same primitive word such that $e\in \varphi _{\mathcal {A}}(u)\cap \varphi _{\mathcal {A}}(v)$ . Then, $\{u,v\}^*$ contains words of arbitrary large minimal period and thus an infinite sequence x with all its factors which are factors of words in $\{u,v\}^*$ . Then, x is the label of d paths in $\mathcal {A}$ and consequently, $\mathcal {A}$ is not recognizable for aperiodic points. This proves that condition (ii) holds. Assume finally that m is such that $p\stackrel {m}{\rightarrow }q$ and $p'\stackrel {m}{\rightarrow }q'$ for some fixed points $p,p'$ and $q,q'$ of two idempotents $e,f\in \varphi (A^+)$ . If $e,f$ do not belong to the same $\mathcal D$ -class, we have $e\in \varphi _{\mathcal {A}}(u^+)$ and $f\in \varphi _{\mathcal {A}}(v^+)$ for non-conjugate primitive words $u,v$ (two idempotents are in the same $\mathcal D$ -class if and only if they are conjugate). Let w be such that $\varphi (w)=m$ . Then ${^\omega }u w v^\omega $ is an aperiodic sequence which is the label of two distinct paths.

Assume conversely that the conditions are satisfied. Consider a point $x\in A^{\mathbb {Z}}$ which is the label of more than one path. Since $M=M(\mathcal {A})$ is a finite monoid, there is, by Proposition 6.3, some $m\in M$ and idempotents $e,f\in M$ with $em=mf=m$ such that $x\in {^{\omega }EwF^\omega }$ with $E=\varphi _{\mathcal {A}}^{-1}(e)$ , $\varphi _{\mathcal {A}}(w)=m$ , and $F=\varphi _{\mathcal {A}}^{-1}(f)$ . The two paths have the form $p\stackrel {e}{\rightarrow }p\stackrel {m}{\rightarrow }q\stackrel {f}{\rightarrow }q$ and $p'\stackrel {e}{\rightarrow }p'\stackrel {m}{\rightarrow }q'\stackrel {f}{\rightarrow }q'$ . If $p=p'$ , then $\mathcal {A}$ is not weakly deterministic. Similarly, if $q=q'$ , it is not weakly co-deterministic. Thus, by condition (iii), $e,m,f$ belong to the same $\mathcal D$ -class. By condition (ii), using equation (6.1), this implies that x is periodic.

Proof. Since $\mathcal {A}$ is unambiguous, $\mathcal {A} \times \mathcal {A}$ is unambiguous. Note that the set of diagonal states is a non-trivial strongly connected component of $\mathcal {A} \times \mathcal {A}$ . It cannot contain non-diagonal states since $\mathcal {A}$ is unambiguous.

We first show that the conditions are necessary. Let C be a non-trivial strongly connected component of $\mathcal {A} \times \mathcal {A}$ which is non-diagonal. Let $\pi $ be a simple cycle labeled by u around $(p,q)$ with $p \neq q$ in C and another cycle $\pi '$ which is not a power of $\pi $ around $(p,q)$ labeled by v. Since $\mathcal {A} \times \mathcal {A}$ is unambiguous, u and v are not a power of the same word. Thus, there is a two-sided infinite sequence x which is a concatenation of words u and v which is not periodic. This sequence is the label of a two-sided infinite path of $\mathcal {A} \times \mathcal {A}$ going through $(p,q)$ after reading u or v. Since $p \neq q$ , this leads to two distinct paths labeled by x in $\mathcal {A}$ and thus $\mathcal {A}$ is not unambiguous for aperiodic points.

Let C and $C'$ be two non-trivial non-diagonal strongly connected components of $\mathcal {A} \times \mathcal {A}$ . Then C and $C'$ are reduced to a cycle. Let $(p,q) \in C$ with $p \neq q$ and $(r,s) \in C'$ with $r \neq s$ , let $\pi $ be a simple cycle labeled by u around $(p,q)$ , and $\pi '$ be a simple cycle labeled by v around $(r,s)$ . Let us assume that there is a path from $(p,q)$ to $(r,s)$ labeled by w in $\mathcal {A} \times \mathcal {A}$ . Assume that u and v are not powers of two conjugate words, then the two-sided infinite word $x = {^\omega }uwv^\omega $ is aperiodic and $\mathcal {A}$ is not unambiguous for aperiodic points. Assume now that $u=(rs)^k$ and $v = (sr)^{k'}$ with $rs$ primitive. The word $x = {^\omega }uwv^\omega $ is periodic if and only if $w \in (rs)^*r$ . However, in this case, if $w = (rs)^mr$ , the word $(rs)^{kk'} (rs)^m r = (rs)^m r (sr)^{kk'}$ is the label of two distinct paths from $(p,q)$ to $(r,s)$ which is impossible since $\mathcal {A} \times \mathcal {A}$ is unambiguous.

Let us now assume that the strongly connected component of diagonal points is connected to a non-trivial non-diagonal strongly connected component. For instance, if there is a path labeled by w from a state $(p,p)$ to a state $(q,r)$ with $q \neq r$ belonging to an non-trivial strongly connected component.

Assume that the graph of $\mathcal {A}$ is not reduced to one cycle. Then there are a simple cycle $\pi $ around $(p,p)$ labeled u and another cycle $\pi '$ around $(p,p)$ labeled v which is not a power of $\pi $ . The words u and v are not a power of a same word. Hence, there is a left-infinite word y being a concatenation of words u and v labeling a path ending in $(p,p)$ and which is not ultimately periodic. Let z be the label of a cycle around $(q,r)$ . Then $ywz^\omega $ is an aperiodic point labeling two distinct paths of $\mathcal {A}$ .

If $\mathcal {A}$ is reduced to one cycle, there is no path from a diagonal state to a non-diagonal one in $\mathcal {A} \times \mathcal {A}$ . Thus, if condition (ii) is not satisfied, $\mathcal {A}$ is not unambiguous for aperiodic points.

We now show that the conditions are sufficient. We show that if all conditions hold, $\mathcal {A}$ is unambiguous for aperiodic points. Let x be an aperiodic point which is the label of two distinct paths of $\mathcal {A}$ . Then there is a two-sided infinite path $(p_i,q_i)_{i \in \mathbb {Z}}$ in $\mathcal {A} \times \mathcal {A}$ labeled by x such that $(p_i)_{i \in \mathbb {Z}} \neq (q_i)_{i \in \mathbb {Z}}$ . Without loss of generality, we may assume that $p_0 \neq q_0$ . There is an infinite number of $i <0$ such that $(p_i,q_i) = (p,q)$ for some states $p, q$ . There is also an infinite number of $j> 0$ such that $(p_j,q_j) = (r,s)$ for some states $r, s$ . We cannot have $p = q$ and $r = s$ since $\mathcal {A}$ is unambiguous.