On B. Mossé's unilateral recognizability theorem
Shigeki Akiyama Bo Tan Hisatoshi Yuasa
math.DS cs.FL 68R15, 37B10


the unilateral recognizability]
On B. Mossé's unilateral recognizability theorem

S. Akiyama]Shigeki Akiyama
Institute of Mathematics, University of Tsukuba, Tennodai 1-1-1,
Tsukuba, Ibaraki, 305-8571 JAPAN.
akiyama@math.tsukuba.ac.jp

B. Tan]Bo Tan
School of Mathematics and Statistics, Huazhong University of Science & Technology, Wuhan 
430074, P.R.CHINA.
tanbo@hust.edu.cn

H. Yuasa]Hisatoshi Yuasa
Division of Science, Mathematics and Information, Osaka Kyoiku University,
4-698-1 Asahigaoka, Kashiwara, Osaka 582-8582, JAPAN.



hyuasa@cc.osaka-kyoiku.ac.jp


We complete statement and proof for B. Mossé's unilateral recognizability theorem. We also 
provide an algorithm for deciding the unilateral non-recognizability of a given primitive substitution. 




[2000] Primary 68R15; Secondary 37B10

[
    [
    December 30, 2023
=====================





§ INTRODUCTION


Let A be a finite alphabet consisting of at least two letters. Let A^+ denote the set of nonempty 
words over the alphabet A. Every map σ from the alphabet A to A^+ is called a 
substitution on the alphabet A. The substitution σ is said to be primitive if 
there exists k ∈={1,2,…} such that for any pair (a,b) ∈ A × A, the letter 
a occurs in the word σ^k(b). Throughout the present paper, a given substitution is assumed 
to be primitive. Suppose that the substitution σ has a fixed point 
u=u_0u_1u_2 … in A^_+, where _+=0∪. If the fixed point u is aperiodic 
under the left shift T on A^_+, i.e. T^iu=u for all i ∈, then the substitution 
σ is said to be aperiodic. There is an algorithm <cit.> which can check 
whether a given substitution is aperiodic. We always assume that the substitution σ is aperiodic. 
For every p ∈, set 

    E_p=0∪|σ^p(u_[0,n)) | | n ∈,

where |w| is the length of a word w. The elements of E_p are called natural 
p-cutting points; see also <cit.>, <cit.> and 
<cit.>. It is clear that E_q ⊊ E_p whenever q > p. 
The substitution σ is said to be unilaterally recognizable 
<cit.> if there exists L ∈ such that if 
u_[i,i+L)=u_[j,j+L) and i ∈ E_1 then j ∈ E_1. This definition does not depend on the 
choice of the fixed point u of the substitution σ. Also, the substitution σ is said 
to be bilaterally recognizable <cit.> if there exists 
L ∈ such that if u_[i-L,i+L)=u_[j-L,j+L) and i ∈ E_1 then j ∈ E_1. 

The unilateral recognizability is an important notion from viewpoints of subshifts arising from 
substitutions. If the substitution σ is unilaterally recognizable, 
then a unilateral subshift X_σ arising from the substitution σ has a Kakutani-Rohlin 
partition <cit.> built on a clopen subset σ(X_σ) of X_σ. 
Proposition VI. 6 of <cit.> states that given a point x=x_0x_1x_2 …∈ X_σ, the 
first return time of the point σ(x) to the clopen subset σ(X_σ) equals 
|σ(x_0)|. This leads to a fact that the first return map on 
σ(X_σ) is a topological factor of X_σ, which shows a self-similarity of 
X_σ if the substitution σ is injective on the alphabet A; see 
<cit.>. 
It is also a significant consequence of the unilateral recognizability that 
σ(X_σ) is open; see <cit.> and <cit.>. 
The unilateral recognizability is a premise of the celebrated theorem of <cit.>, which 
characterizes eigenvalues and eigenfunctions of the subshift X_σ. 

B. Mossé gave <cit.> to characterize the unilateral 
non-recognizability. However, if we dare say, it is incomplete and should be 
formulated as follows. 

The following are equivalent:


  * 
the substitution σ is not unilaterally recognizable;

  * 
for each L ∈, there exist i,j ∈_+ such that 


  * σ(u_j) is a strict suffix of σ(u_i);

  * σ(u_i+k)=σ(u_j+k) for each integer k with 1 ≤ k ≤ L.



Recall that the substitution σ is assumed to be aperiodic. 
The word B appearing in the statement of <cit.> corresponds to a factor 
of σ(u_iu_i+1… u_i+L). The letters a and b in the statement correspond to u_i and 
u_j, respectively. It is important to regard u_i and u_j as letters accompanied with information 
on the positions i and j where they occur. 

B. Mossé's proof for her characterization would be difficult to completely 
follow, in particular, Part (4) in p. 332. No proofs for it can be found in recent textbooks 
<cit.>, though a proof for the bilateral recognizability 
is written in <cit.>. However, the difficulty is overcome in Step 3 in the 
proof of Theorem <ref>, which is one of the goals of the present paper. 
In Lemma <ref>, we also show that an index under which the aperiodic substitution 
σ is bilaterally recognizable can be described in terms of only parameters derived from the 
substitution σ itself. In fact, the statement of the lemma excluding the computability of the 
index is exactly <cit.>, which is presented in terms of 
local unique composition property defined by Property (6) in <cit.>. As a consequence of 
the lemma, Proposition <ref> affirms that a constant p ∈ for which 
if σ^p-1(a) σ^p-1(b) and a, b ∈ A then σ^k(a) σ^k(b) 
for all k ∈_+. 


The other goal is to present an algorithm which determines whether or not a given aperiodic, 
primitive substitution is unilaterally recognizable. The algorithm is described in terms of 
the existence of a cycle in a directed, finite graph whose vertex set consists of a pair of those 
words of constant length which occur in the sequence u. 



In view of Theorem <ref>, it may be of interest to find a computable constant 
M, such that the existence of a word v=v_1v_2 … v_M+1 of length M+1 satisfying that 


  * σ(v_1) is not a strict suffix of σ(w_1), or 

  * σ(v_k) σ(w_k) for some integer k with 2 ≤ k ≤ M+1

is equivalent to the unilateral recognizability of the substitution σ, 

which would give an easier algorithm.



§ K-POWER FREE SEQUENCES


We shall make terminology excepting that done in the preceding section. The empty word is denoted 
by Λ. Set A^∗=A^+ ∪Λ. We say that a word w ∈ A^∗ occurs in a 
word v ∈ A^∗ if there exist p,s ∈ A^∗ such that v=pws. 
We then write w ≺ v. More specifically, w is said to occurs at the 
position |p|+1 in v. The position is called an occurrence of w in v. Let |v|_w 
denote the number of occurrences of w in v. 
The words p and s are called a prefix and suffix of v, 
respectively. We then write p ≺_ v and s ≺_ v, respectively. If 
|p|<|v| (resp. |s|<|v|), then p (resp. s) is called a strict prefix (resp. suffix) 
of v, and then we write p ≺_ v (resp. s ≺_ v). We can also define 
e ≺_ f for e,f ∈ A^_+ in such a way that e=f_[n,+∞) for some n ∈_+. 
A power of a word w ∈ A^∗ is a word of the form 
ww … w_n  times with some n ∈_+. The power is denoted by w^n. 
In particular, w^0 = Λ. Set 

    I_i = min_a ∈ A|σ^i(a)|  and  S_i = max_a ∈ A|σ^i(a)|.


A nonnegative square matrix M is said to be primitive if there exists k ∈ for which 
M^k is positive. The incidence matrix M_σ of the substitution σ is defined to 
be an A × A matrix whose (a,b)-entry equals |σ(a)|_b. The matrix M_σ is 
primitive and has a positive, right eigenvector β=(β_a)_a ∈ A corresponding to Perron 
eigenvalue λ of M_σ, i.e. the absolute value of any other eigenvalue is less than 
λ. See for example <cit.>. Since for all a ∈ A,

    ∑_b ∈ A(M_σ^n)_a,bβ_b= λ^n β_a,

it follows that for all a ∈ A and n ∈,

    min_b ∈ Aβ_b/max_b ∈ Aβ_b·λ^n ≤∑_b ∈ A
    (M_σ^n)_a,b≤max_b ∈ Aβ_b/min_b ∈ Aβ_b·λ^n.

Put 

    C = ⌈max_b ∈ Aβ_b/min_b ∈ Aβ_b⌉.

It follows that for all a ∈ A and n ∈,

    C^-1λ^n ≤ |σ^n(a)| ≤ Cλ^n.


Given a sequence v ∈ A^_+, set 

    Ł(v)^+    = v_[i,j]:=v_iv_i+1… v_j|i,j ∈_+,i ≤ j; 
    Ł(v)    = Ł(v)^+ ∪Λ; 
    Ł_k(v)    = w ∈Ł(v)| | w| =k.


We say that a word w ∈ A^∗ occurs at a position i ∈_+ in v if 
v_[i,i+|w|)=w. The integer i is called an occurrence of the word w. The fixed point u 
of the substitution σ is uniformly recurrent, i.e. given a word w ∈Ł(u), there 
exists g ∈ so that any interval of length g, which is a subset of _+, includes an 
occurrence of the word w. For, the primitivity of the substitution σ implies the existence 
of n ∈ such that w ≺σ^n(a) for all a ∈ A. Then, the length g can be chosen 
to be 2max_a ∈ A|σ^n(a)|, because 

    u=σ^n(u)=σ^n(u_0)σ^n(u_1) …
 
We shall refer to the length g as a gap of occurrences of the word w in the sequence u. 
Let g be the maximal value of gaps of occurrences of words belonging to Ł_2(u). 

The value g is computable.


Consider an auxiliary substitution σ_2:Ł_2(u) →Ł_2(u)^+ <cit.>, 
where Ł_2(u) is regarded as a finite alphabet. The substitution σ_2 is defined by for 
w ∈Ł_2(u),

    σ_2(w)=σ(w)_[1,2]σ(w)_[2,3]…σ(w)_[|σ(w_1)|,|σ(w_1)|+1].

The substitution σ_2 is primitive <cit.>. Observe that #Ł_2(u) ≤ 
(# A)^2 and |σ_2(w)|=|σ(w_1)| for all w ∈Ł_2(u). 
Set 

    u^(2)=(u_0u_1)(u_1u_2)(u_2u_3) …,

which is a fixed point of σ_2 in Ł_2(u)^_+ <cit.>. Observe that 
given w ∈Ł_2(u) and i ∈_+, i is an occurrence of w in u if and only if u^(2)_i=w. 
In view of <cit.>, the least n ∈ for which every entry of (M_σ_2)^n 
is positive has a upper bound (#Ł_2(u))^2-2 ·#Ł_2(u) + 2 ≤ (# A)^4 -2(# A)^2 + 2. 
Put 

    n_0=(# A)^4 -2(# A)^2 + 2.

As done in the proof of <cit.>, define a 
Ł_2(u) × A-matrix N by letting N_w,a=(M_σ)_w_1,a for all 
(w,a) ∈Ł_2(u) × A. Let v be a positive eigenvector of M_σ corresponding to 
λ, as above. Since M_σ_2N=NM_σ, whose (w,a)-entry is |σ^2(w_1)|_a for 
all (w,a) ∈Ł_2(u) × A, a positive vector Nv is an eigenvector of M_σ_2 
corresponding to its eigenvalue λ. Consequently, the number λ is a dominant eigenvalue 
of a primitive matrix M_σ_2; see for example <cit.>. 
We then obtain that for all w ∈Ł_2(u) and n ∈,

    (C max_a ∈ A|σ(a)|)^-1λ^n ≤ |σ_2^n(w)| ≤ 
    C max_a ∈ A|σ(a)| λ^n.

It follows finally that the value g has a upper bound 2C max_a ∈ A|σ(a)| λ^n_0. 


A word v ∈ A^+ is said to be primitive <cit.> if it holds that 

    v = w^n, w ∈ A^+, n ∈⇒ w = v.

We say that a sequence v=v_0v_1v_2 …∈ A^_+ is ultimately periodic if there exist 
n ∈_+ and word w ∈ A^+ for which 

    v=v_[0,n)www …

If an ultimately periodic sequence v is uniformly recurrent, then 
v is periodic, i.e. v is written as an infinite repetition of a single word. 
Recall that the substitution σ is assumed to be aperiodic. 

There does not exist N,p ∈ and primitive word v ∈ A^+ for which


  * σ^p(w) ≺ v^N for any w ∈Ł_2(u);

  * 2|v| ≤min_a ∈ A|σ^p(a)|. 




For the sake of completeness, we give a proof. Of course, the idea is due to 
B. Mossé <cit.>. Assume that there exists such a triple N,p and v. Since 
σ^p(u_i) ≺ v^N, there exist words α_i ≺_ v, β_i ≺_ v and 
n_i ∈_+ for which σ^p(u_i)=α_i v^n_iβ_i. If n_i=0, then 
|σ^p(u_i)| < 2|v|, which contradicts the hypothesis. Since 

    σ^p(u_iu_i+1) = α_iv^n_iβ_i α_i+1v^n_i+1β_i+1≺ v^N,

we see that vβ_i α_i+1v ≺ v^N. This implies that β_i α_i+1 is a power 
of v; see <cit.>. Hence, u=σ^p(u)=α_0 vvv … This is 
a contradiction as σ is aperiodic. 



If n ∈ and w^n ∈Ł(u)^+, then n < 2λ(g+1)C^2.


For the sake of completeness, we present a proof. Again, the idea is due to B. Mossé <cit.>. 
Suppose that w is a primitive word 
and w^n ∈Ł(u) for some n ∈. There exists p ∈ for which 

    1/2min_a ∈ A|σ^p-1(a)| ≤ |w| < 1/2min_a ∈ A|σ^p(a)|.

Recall that v ≺ u_[i,i+g) for all words v ∈Ł_2(u) and i ∈_+. Since 
2|w| < min_a ∈ A|σ^p(a)| and σ is aperiodic, it follows from 
Lemma <ref> that 

    n|w|=|w^n| < (g+1)max_a ∈ A|σ^p(a)|.

Hence,

    n < (g+1)max_a ∈ A|σ^p(a)|/1/2min_a ∈ A|σ^p-1(a)|≤ 2(g+1)C^2
    λ.

The last inequality follows from (<ref>). 



♯Ł_n(u) ≤λ C^2 (# A)^2 n for every n ∈.


This proof follows that of <cit.>. Fix n ∈. Find p ∈ 
so that min_a ∈ A|σ^p-1(a)| ≤ n ≤min_a ∈ A|σ^p(a)|. Then, 

    #Ł_n(u) ≤ (# A)^2 min_a ∈ A|σ^p(a)| ≤ (# A)^2 min_a ∈ A|σ^p(a)|/min_a ∈ A|σ^p-1(a)| n ≤λ C^2 (# A)^2 n.

This completes the proof. 

See also <cit.> and <cit.>. Set 

    K= ⌈λ C^2 max 2(g+1), (# A)^2⌉.

Then, the fixed point u of the substitution σ is K-power free, in other words, it 
holds that if v^N ∈Ł(u) and N ≥ K then v = Λ. Hence, the constant K is inevitably 
greater than or equal to two. In general, if a uniformly recurrent 
sequence v ∈ A^_+ is aperiodic, then given a word w ∈Ł(v)^+ there exists a constant 
L ∈ for which w^L ∉Ł(v). However, the constant L may depend on the choice of 
the word w. 



§ B. MOSSÉ'S CHARACTERIZATION OF THE UNILATERAL NON-RECOGNIZABILITY





  * 
A finite sequence: 

    α,σ^p(u_i^'),σ^p(u_i^'+1),…,
    σ^p(u_i^'+k-1),β

of words over the alphabet A is called a natural p-cutting of u_[i,i+ℓ) if 


  * α≺_σ^p(u_i^'-1);

  * β≺_σ^p(u_i^'+k);

  * u_[i,i+ℓ)=ασ^p(u_i^') σ^p(u_i^'+1) …σ^p(u_i^'+k-1)β, where i;

  * i+|α| = |σ^p(u_[0,i^'))|.


  * 
If a word w occurs at positions i and j in the sequence u, then the word w is said to have 
the same natural p-cutting at the positions i and j if 

    (E_p ∩ [i,i+|w|)) + (j-i) = E_p ∩ [j,j+|w|),

where E+i=e+i|e ∈ E if E is a finite subset of _+ and i ∈_+. 



Compare these definitions with the original ones in <cit.>. 
We do not exclude the possibility that 

    α = σ^p(u_i^'-1), α = Λ, β = σ^p(u_i^'+k) 
     or β = Λ.

Since we always require k ≥ 1 in Definition <ref> (<ref>), 
not every u_[i,i+ℓ) has a natural p-cutting. It is not necessary that a natural p-cutting 
is uniquely determined for given i and ℓ in 
Definition <ref> (<ref>). 




Put 

    k=C^4(K+1)+2C^2+1.

To show the implication (<ref>) ⇒ (<ref>), 
assume that the substitution σ is not unilaterally recognizable. 

Step 1. It follows from  Lemma <ref> below that for each p ∈, there 
exist integers i_p ∈ E_1, j_p ∉ E_1, i_p^',j_p^'≥ 0, 
h_p,ℓ_p ≥ 1 and words α_p,γ_p^'∈ A^∗, γ_p ∈ A^+ 
such that 


  * u_[i_p,i_p+ℓ_p) =u_[j_p,j_p+ℓ_p);

  * u_[i_p,i_p+ℓ_p) has a natural p-cutting: 

    α_p,σ^p(u_i_p^'),σ^p(u_i_p^'+1),…,
    σ^p(u_i_p^'+k-1);
 

  * u_[j_p+|α_p|,j_p+ℓ_p) has a natural p-cutting:

    γ_p,σ^p(u_j_p^'),σ^p(u_j_p^'+1),…,
    σ^p(u_j_p^'+h_p-1),γ_p^'.


Set 

    m_p = minm ∈|α_p γ_p ≺_σ^p(u_[j_p^'-m,j_p^')).

Since 

    (m_p-1)I_p ≤ |σ^p(u_[j_p^'-m_p+1,j_p^'))| < |α_p γ_p| 
    ≤ 2S_p,

we obtain that for all p ∈, 

    m_p < 2C^2+1.

Since

    h_p I_p ≤ |γ_p σ^p(u_[j_p^',j_p^'+h_p))γ_p^'| 
     = |σ^p(u_[i_p^',i_p^'+k)| ≤ k S_p

and

    (h_p + 2)S_p ≥ |γ_p σ^p(u_[j_p^',j_p^'+h_p))γ_p^'| 
    = |σ^p(u_[i_p^',i_p^'+k)| ≥ k I_p,

we obtain that for all p ∈,

    kC^-2-2 ≤ h_p ≤ kC^2.

It follows that a set:

    (m_p,h_p,u_[i^'_p-1,i^'_p+k),u_[j_p^'-m_p,j_p^'+h_p])|p ∈

has a finite cardinality. Hence, the pigeonhole principle implies that for some infinite set 
I ⊂, a set:

    (m_p,h_p,u_[i^'_p-1,i^'_p+k),u_[j_p^'-m_p,j_p^'+h_p])| p ∈ I

is a singleton. It allows us to put m = m_p and h = h_p for any p ∈ I. 

Step 2.
Let p,q ∈ I with p < q be arbitrary. We have two natural q-cuttings: 

    γ_q,σ^q(u_j_q^'),σ^q(u_j_q^'+1), …, 
    σ^q(u_j_q^'+h-1),γ_q^'

of a word occurring at the position j_q+|α_q| and 

    σ^q-p(γ_p),σ^q(u_j_q^'),σ^q(u_j_q^'+1), …, 
    σ^q(u_j_q^'+h-1),σ^q-p(γ_p^')

of a word occurring at the position j_q+|α_q γ_q|-|σ^q-p(γ_p)|. It would be 
worthwhile observing that σ^q-p(γ_p) ≺_σ^q(u_j_q^'-1) and 
σ^q-p(γ_p^') ≺_σ^q(u_j_q^'+h_q). 
Assume that the natural q-cuttings (<ref>) and (<ref>) are different. Then, 
one of the inequalities |γ_q|  |σ^q-p(γ_p)| and 
|γ_q^'|  |σ^q-p(γ_p^')| follows.

Consider the case |γ_q| > |σ^q-p(γ_p)|. 
Since 

    γ_qσ^q(u_[j_q^',j_q^'+h)) γ_q^'   =
    σ^q(u_[i_q^',i_q^'+k)) 
       = σ^q-p(σ^p(u_[i_p^',i_p^'+k))) 
        = σ^q-p(γ_p σ^p(u_[j_p^',j_p^'+h)) γ_p^') 
        = σ^q-p(γ_p)σ^q(u_[j_q^',j_q^'+h))σ^q-p(γ_p^'),

a power v^N of a nonempty word v ≺_γ_q occurs in 
σ^q(u_[j_q^',j_q^'+h)) as a prefix. 
By using the fact that v ≺_σ^q(u_j_q^'-1), we can see that 

    maxN ∈| v^N ≺_σ^q(u_[j_q^',j_q^'+h))    ≥h I_q/S_q -1 
       ≥ (kC^-2-2)C^-2-1 
        = K + C^-4
        > K,

where the equality follows from (<ref>). This contradicts the (K+1)-power freeness of the 
sequence u, i.e. Lemma <ref>. The same contradiction 
emerging in the other cases, we conclude that for any p,q ∈ I with p < q, 

    γ_q=σ^q-p(γ_p).


Step 3. 
Choose integers p < q in I so that 

    |σ^q-p-1(γ_p)| ≥ L.

Observe how u_[i_q^'-1,i_q^'+k) goes to 
σ^q(u_[i_q^'-1,i_q^'+k)) via 
σ^p(u_[i_q^'-1,i_q^'+k)); see Figure <ref>. Since 
γ_p ≺_σ^p(u_[i_q^',i_q^'+k)), γ_q ≺_σ^q(u_[i_q^',i_q^'+k)) and σ^q-p(γ_p) = γ_q, we can see 
that 
u_[i_q+|α_q|,i_q+|α_qγ_q|)=γ_q has a natural 1-cutting: 

    σ(u_i^''),σ(u_i^''+1), …, 
    σ(u_i^''+ |σ^q-p-1(γ_p) | -1),

where i^''=|σ^q-1(u_[0,i_q^'))|. 
Remark that

    u_[i^'',i^''+|σ^q-p-1(γ_p)|)
    =σ^q-p-1(γ_p).



Then, observe how u_[j_q^'-m,j_q^'+h] goes 
to σ^q(u_[j_q^'-m,j_q^'+h]) via 
σ^p(u_[j_q^'-m,j_q^'+h]); see Figure <ref>. 
Recalling that the natural q-cuttings (<ref>) and (<ref>) are the 
same, we can see that 
u_[j_q+|α_q|,j_q+|α_qγ_q|)=γ_q has a natural 1-cutting:

    σ(u_j^''),σ(u_j^''+1), …, 
    σ(u_j^''+ |σ^q-p-1(γ_p) | -1),

where 
j^''=
|σ^q-p-1(u_[0,|σ^p(u_[0,j_q^'))|-|γ_p|))|. 
Remark that 

    u_[j^'',j^''+|σ^q-p-1(γ_p)|)=σ^q-p-1(γ_p).


We are finally in a situation that 


  * α_qγ_q occurs at the positions i_q ∈ E_1 and j_q ∉ E_1 in u;

  * γ_q has the same natural 1-cutting at the positions i_q+|α_q| and j_q+|α_q|; 
recall (<ref>) and (<ref>);

  * all of the positions i_q+|α_q|,i_q+|α_qγ_q|,j_q+|α_q| and 
j_q+|α_qγ_q| are natural 1-cutting points;

  * the same natural 1-cutting of γ_q consists of at least L words.

Actually, the second and third conditions are implied by a stronger statement that the same 
1-cutting of γ_q at the positions i_q+|α_q| and j_q+|α_q| comes from the same 
word (<ref>) and (<ref>), in other words, the 
word γ_q has the same ancestor word (<ref>) and 
(<ref>) at the positions. We will again encounter this kind of fact in the 
proof of “local unique composition property” (Lemma <ref>). 

We reach the desired positions i,j ∈_+ by executing the following procedure in this order:


  * Set ℓ = i_q+|α_q| and m=j_q + |α_q|. 

  * 
Let ℓ^' < ℓ and m^' < m be natural 1-cutting 
points which are nearest to ℓ and m respectively. 

  * 
If ℓ - ℓ^' = m-m^', then set ℓ = ℓ^' and m = m^' and 
go back to (P. <ref>). 

  * In this step, we have that ℓ - ℓ^' m-m^'. The desired positions i and 
j are determined by the facts that 


  * ℓ - ℓ^' < m - m^' ⇒ |σ(u_[0,j))|=ℓ^' and 
|σ(u_[0,i))|=m^';

  * m - m^' < ℓ - ℓ^' ⇒ |σ(u_[0,j))|=m^' and 
|σ(u_[0,i))|=ℓ^'.


The loop between (P. <ref>) and (P. <ref>) continues up to 
⌈ |α_qγ_q|/I_1 ⌉ times. 





Let k ≥ 3C^2 be an integer. If the substitution σ is not recognizable, then for each 
p ∈ there exist integers i_p ∈ E_1,j_p ∉ E_1,i_p^',j_p^'≥ 0,
h_p, ℓ_p ≥ 1 and words α_p,γ_p^'∈ A^∗, γ_p ∈ A^+ such 
that 


  * u_[i_p,i_p+ℓ_p)=u_[j_p,j_p+ℓ_p);

  * u_[i_p,i_p+ℓ_p) has a natural p-cutting:

    α_p,σ^p(u_i_p^'),σ^p(u_i_p^'+1),…,
    σ^p(u_i_p^'+k-1);


  * u_[j_p+|α_p|,j_p+ℓ_p) has a natural p-cutting:

    γ_p,σ^p(u_j_p^'),σ^p(u_j_p^'+1),…,
    σ^p(u_j_p^'+h_p-1),γ_p^'.





Fix an integer m_p with 

    m_p > (k+2)S_p.

Since σ is not recognizable, there exist integers i_p ∈ E_1 and j_p ∉ E_1 
such that u_[i_p,i_p+m_p)=u_[j_p,j_p+m_p).
The choice of m_p guarantees that u_[i_p,i_p+m_p) has a natural p-cutting, say 

    {α_p,σ^p(u_i_p^'),σ^p(u_i_p^'+1),…,
    σ^p(u_i_p^'+k_p-1),β_p}.

Since 

    k_p ≥m_pS_p-2>k,

we can see that u_[i_p,i_p+ℓ_p) has a natural p-cutting: 

    α_p,σ^p(u_i_p^'),σ^p(u_i_p^'+1), …, 
    σ^p(u_i_p^'+k-1),

where ℓ_p=|α_pσ^p(u_[i_p^',i_p^'+k))|. Since 

    ℓ_p-|α_p| ≥ k I_p ≥ k C^-1λ^p 
    ≥ kC^-2 S_p ≥ 3 S_p,

u_[j_p+|α_p|,j_p+ℓ_p) has a natural p-cutting: 

    γ_p,σ^p(u_j_p^'),σ^p(u_j_p^'+1),…,
    σ^p(u_j_p^'+h_p-1),γ_p^'

with γ_p Λ. 




§ AN ALGORITHM FOR THE UNILATERAL NON-RECOGNIZABILITY

Following Property (6) in <cit.>, we make a definition:

We say that the substitution σ has the local unique composition property under an index 
L ∈ if 


  * the substitution σ is bilaterally recognizable under the index L;

  * if u_[i-L,i+L)=u_[j-L,j+L), |σ(u_[0,m))| ≤ i < |σ(u_[0,m+1))|  and  
|σ(u_[0,n))| ≤ j < |σ(u_[0,n+1))| then u_m = u_n.


See also <cit.> and <cit.>. 
None has given a computable value of an index under which the local unique composition property holds, 
which is now done by the following lemma. The lemma excluding the computability is due to 
<cit.>, though the theorem do not mention any decidability of the 
index L. 


The aperiodic, primitive substitution σ has the local unique composition property under an 
index L_0={C^4(K+1)+2C^2+1}S_p_0, where 

    p_0 = K^2 {C^4(K+1)+2C^2+1 }×∑_n=C^2(K+1)+2^(K+1)C^6+2C^4+C^2+2 
    n + 1.



Put k=C^4(K+1)+2C^2+1. Assume that u_[i-L_0,i+L_0)=u_[j-L_0,j+L_0). The integer 
L_0 is so large that we can choose m_p,n_p ∈|1 ≤ p ≤ p_0 so that 


  * u_[i-m_p,i+n_p)=u_[j-m_p,j+n_p);

  * u_[i-m_p,i+n_p) has a natural p-cutting:

    σ^p(u_i_p),σ^p(u_i_p+1),…,σ^p(u_i_p+k-1).


Let 

    γ_p,σ^p(u_j_p),σ^p(u_j_p+1),…,σ^p(u_j_p+h_p-1),γ_p^'

be a natural p-cutting of u_[j-m_p,j+n_p). Since for every integer p with 1 ≤ p ≤ p_0, 
we have 

    C^2(K+1)+C^-2 = kC^-2-2 ≤ h_p ≤ kC^2

in view of an equality: 

    |σ^p(u_[i_p,i_p+k))|=|γ_p σ^p(u_[j_p,j_p+h_p))γ_p^'|,

it follows from Lemma <ref> that the cardinality of a set: 

    (u_[i_p,i_p+k),u_[j_p-1,j_p+h_p])|1 ≤ p ≤ p_0

is at most p_0-1. The pigeonhole principle implies that for some integers 
p and q with 1 ≤ p < q ≤ p_0, 

    u_[i_p,i_p+k) = u_[i_q,i_q+k) and  u_[j_p-1,j_p+h_p] = u_[j_q-1,j_q+h_q].

Hence, h_p = h_q. In view of an equality: 

    γ_qσ^q(u_[j_q,j_q+h_q)) γ_q =σ^q-p(γ_p)σ^q(u_[j_q,j_q+h_q))
    σ^q-p(γ_p^'),

and the (K+1)-power freeness of the sequence u; recall (<ref>), we obtain that 
γ_q=σ^q-p(γ_p) and γ_q^'=σ^q-p(γ_p^'). Taking account 
into the positions of the natural q-cutting of u_[j-m_q,j+n_q), we see that 
u_[i-m_q,i+n_q) and u_[j-m_q,j+n_q) have the same natural (q-p)-cutting, which is yielded 
by application of σ^q-p to identical words:

    σ^p(u_[i_q,i_q+k))=γ_p σ^p(u_[j_q,j_q+h_q)) γ_p^',

so that u_[i-m_q,i+n_q) and u_[j-m_q,j+n_q) have the same natural 1-cutting. 


To verify <cit.>, B. Mossé discusses such a constant p ∈ that if 
σ^p-1(a) σ(b)^p-1 and a, b ∈ A then σ^k(a) σ^k(b) for all 
k ∈_+. The constant p is formally obtained by setting 

    p=
    max_(a,b) ∈ Bmin k ∈ | σ^k(a) = σ^k(b)+1     if  
    B ∅; 
    
    1     otherwise,

where 

    B=(a,b) ∈ A × A| a  b, σ^k(a)= σ^k(b)  for some  k ∈.

See also the proof of <cit.>. As an application of Lemmas  <ref> and 
<ref>, we can see that 

the constant p is computable. 


Put 

    N=K (⌊ L_0 λ^-1(C-C^-1) ⌋ + 1) + ⌊ CL_0 λ^-1⌋ + 1.

Choose an integer k_0 with k_0 > log_λ (CN). Then, for all letters a ∈ A, 

    |σ^k_0(a)| ≥ C^-1λ^k_0 > N.

Following <cit.>, given letter a ∈ A and integer k with k ≥ k_0, let _N(σ^k(a)) 
(resp. _N(σ^k(a))) denote a suffix (resp. prefix) of σ^k(a) whose length is N. 
Fix distinct letters a_1,a_2 ∈ A. Lemma <ref> together with the pigeonhole principle 
allows us to find those integers i_m < j_m and k_m < ℓ_m which belong to a closed interval 
[k_0, k_0 + λ C^2 (# A)^2 N ] for which and for all m=1,2, 



  * _N(σ^i_m(a_m))=_N(σ^j_m(a_m));

  * #_N(σ^k(a_m))|k_0 ≤ k ≤ j_m=j_m - k_0;

  * _N(σ^k_m(a_m))=_N(σ^ℓ_m(a_m));

  * #_N(σ^k(a_m))|k_0 ≤ k ≤ℓ_m = ℓ_m - k_0.

For m=1,2, regard 

    𝒫_m=_N(σ^k(a_m))|k ≥ i_m and 𝒮_m = _N(σ^k(a_m))|k ≥ k_m,

as sequences of words, which have periods j_m-i_m and ℓ_m - k_m, respectively. Observe that 
𝒫_1 ∩𝒫_2 = ∅ unless 𝒫_1 = 𝒫_2. This fact is 
also valid for 𝒮_m. 

If 𝒫_1 ∩𝒫_2 = ∅ or 𝒮_1 ∩𝒮_2 = ∅, 
then σ^k(a) σ^k(b) for all k ∈. Then, set p_a_1,a_2=1. 
If 𝒫_1=𝒫_2 and 𝒮_1=𝒮_2, then set 

    p_a_1,a_2=maxi_1,i_2,k_1,k_2,log_λ(CN+C^2L_0λ^-1) + 1.

Let p denote p_a_1,a_2 for the simplicity of notation. 
Let us verify that if σ^p-1(a_1) σ^p-1(a_2) then 
σ(a_1)^k σ^k(a_2) for all k ∈_+. To this end, it is enough for us to consider 
only the case where 𝒫_1=𝒫_2 and 𝒮_1=𝒮_2. Let us see that if 
σ^p(a_1) = σ^p(a_2) then σ^p-1(a_1) = σ^p-1(a_2). For each m = 1,2, 
let q_m < r_m be unique integers satisfying that 

    |σ(σ^p-1(a_m)_[1,q_m)) |   ≤ L_0; 
    |σ(σ^p-1(a_m)_[1,q_m]) |    > L_0; 
    |σ(σ^p-1(a_m)_[1,r_m)) |    < |σ^p(a_m)| - L_0; 
    |σ(σ^p-1(a_m)_[1,r_m]) |   ≥ |σ^p(a_m)| - L_0.

These inequalities together with (<ref>) imply that for all m=1,2, 

    C^-1L_0 λ^-1    < q_m ≤ CL_0λ^-1; 
    
    C^-1L_0λ^-1    < |σ^p-1(a_m)| - r_m + 1 ≤ CL_0λ^-1 + 1

and hence 

    |q_1-q_2|     < L_0λ^-1(C-C^-1); 
    ||σ^p-1(a_1)| -r_1 + 1 -(|σ^p-1(a_2)| -r_2 + 1) |     < 
    L_0λ^-1(C-C^-1) + 1; 
    
    |σ^p-1(a_m)| -q_m + 1    ≥ N +1; 
    
    r_m    ≥ N.


Lemma <ref> allows us to know that 

    σ^p-1(a_1)_[q_1,r_1]=σ^p-1(a_2)_[q_2,r_2].

Since _N(σ^p(a_1))=_N(σ^p(a_2)) and 
_N(σ^p(a_1))=_N(σ^p(a_2)), it follows from the choice of p that 

    _N(σ^p-1(a_1))    = _N(σ^p-1(a_2)); 
    _N(σ^p-1(a_1))    = _N(σ^p-1(a_2)).

If q_1  q_2, then the K-power of a word length |q_1-q_2| must occur at minq_1, q_2 
in σ^p-1(a_m) if q_m attains the minimum value, which is impossible in virtue of 
Lemma <ref>. Hence, we obtain that 

    q_1=q_2,

which is less than N in view of 
(<ref>) and (<ref>). Similarly, we also obtain that 

    |σ^p-1(a_1)_[r_1,|σ^p-1(a_1)|]|    = 
    |σ^p-1(a_1)| -r_1 + 1 
       = |σ^p-1(a_2)| -r_2 + 1 = 
    |σ^p-1(a_2)_[r_2,|σ^p-1(a_2)|]|,

which is less than N in virtue of (<ref>) and (<ref>). 
Now, putting together (<ref>)-(<ref>), we see that 
the words σ^p-1(a_1) and σ^p-1(a_2) must coincide with each other. 


In order to see that a constant L_1 appearing in Lemma <ref> is computable, we will need 
some facts about Birkhoff contraction coefficients for allowable nonnegative square matrices. We 
consult <cit.> and <cit.> for them. 
Let us consider a projective metric d which is defined by for positive, row vectors 
x,y ∈^A, i.e. all entries are positive,

    d(x,y)=lnmax_a ∈ Ax_ay_a/min_b ∈ Ax_by_b.

Suppose that a primitive matrix M=(m_a,b)_a,b ∈ A is allowable, i.e. every row and 
column has a positive entry. Birkhoff contraction coefficient τ_B(M) is 
defined by

    τ_B(M)= supd(xM,yM)/d(x,y)|x,y ∈^A  are 
    positive and linearly independent..

There are known properties <cit.> that 
0 ≤τ_B(M) ≤ 1 and τ_B(MN) ≤τ_B(M)τ_B(N) if 
N is another allowable, nonnegative A × A matrix. The coefficient τ_B(M) is 
computable: 

    τ_B(M)=1-√(ϕ(M))/1+√(ϕ(M)),

where 

    ϕ(M)=minm_i,jm_k,ℓ/m_i,ℓm_k,j, 
    m_i,ℓm_k,j/m_i,jm_k,ℓ|[ m_i,j m_i,ℓ; m_k,j m_k,ℓ ] is a submatrix of  M.

if M is positive, and otherwise, ϕ(M) = 0. Put 

    n_0=(# A)^2-2(# A)+2.

Since it follows from <cit.> that M_σ^n is positive for all integers n 
with n ≥ n_0, we have that ϕ(M_σ^n) > 0 for all such integers n. It follows 
from (<ref>) that for all such integers n, 

    τ_B(M_σ^n) < 1.


As in Section <ref>, let α be a positive, left eigenvector of M_σ 
corresponding to its Perron eigenvalue λ. Given a word w ∈ A^∗, set 

    (w)=(|w|_b)_b ∈ A,

which is viewed as a row vector in ^A. Define a row vector e_a in ^A by for each letter 
b ∈ A, 

    (e_a)_b = 
    1     if  a = b; 
    
    0     otherwise.

It is clear that (σ^n(a)) = e_a M_σ^n. 
It follows from <cit.> and <cit.> that 
for all letter a ∈ A and integer n with n ≥ 2n_0, 

    ‖(σ^n(a))/|σ^n(a)| - α/‖α‖_1‖_1 
       =
    ‖e_a M_σ^n/‖ e_a M_σ^n ‖_1 - α/‖α‖_1‖_1 
       ≤exp(d(e_a M_σ^n, α))-1 
       ≤exp(τ_B(M_σ^n-n_0)d(e_aM_σ^n_0,α))-1 
       ≤exp(τ_B(M_σ^n_0)^[n-n_0/n_0]max_a ∈ Ad(e_aM_σ^n_0,α) )-1 
       ≤exp(max_a ∈ Ad(e_aM_σ^n_0,α) )^
    τ_B(M_σ^n_0)^[n/n_0-1]-1,

which monotonically decreases to zero in virtue of (<ref>) as n increases. As a 
trivial consequence, we obtain that 

    max_a,b,c ∈ A||σ^n(a)|_c/|σ^n(a)| - |σ^n(b)|_c/|σ^n(b)||≤ 2 exp(max_a ∈ Ad(e_aM_σ^n_0,α) )^
    τ_B(M_σ^n_0)^[n/n_0-1]-2.



For every real number ρ with 1 < ρ < λ, there exists a computable number 
L_1 ∈ so that for all integers L ≥ L_1 and i ≥ 0, we have an inequality:

    |σ(u_[i,i+L)) |≥ρ| u_[i,i+L)| = ρ L.

In particular, it holds that for all i ∈_+,

    |σ(u_[i,i+L_1))| ≥ L_1+1.
 


Let ϵ denote a number satisfying that ρ=(1-ϵ)λ. This forces that 
0 < ϵ < 1. Let n_0 be as in (<ref>). Choose an integer n with n ≥ n_0 so large 
that 

    2 exp(max_a ∈ Ad(e_aM_σ^n_0,α) )^
    τ_B(M_σ^n_0)^[n/n_0-1]-2 < ϵλ/4 (# A)‖ M_σ‖_1,

where ‖ M_σ‖_1 is a norm of M_σ defined by 

    ‖ M_σ‖_1 = max‖ x M_σ‖_1| x ∈^A, ‖ x ‖_1 = 1=
    max_b ∈ A∑_a ∈ A(M_σ)_a,b.

Consequently, the right hand side of (<ref>) is also less than (<ref>). 
If the integer L is not less than 2S_n, then we obtain a natural n-cutting: 

    v, σ^n(u_j+1), σ^n(u_j+2), … , σ^n(u_j+k), w

of u_[i,i+L) so that v ≺_σ^n(u_j) and w ≺_σ^n(u_j+k+1). 
Put 

    δ_k=1-1/2C^2k^-1+1,

which monotonically decreases as k increases. Since k ≥S_n^-1L -2, we have that 

    δ_k ≤2C^2/S_n^-1L+2(C^2-1).

Choose L_1 ∈ so that for all integers L with L ≥ L_1,

    maxδ_k, 2S_n L^-1 < ϵλ/4 (# A)‖ M_σ‖_1.


Suppose that the integer L is not less than L_1. Let i ∈_+ and c ∈ A be arbitrary. Since

    |u_[i,i+L)|_c/L = ∑_ℓ = j+1^j+k |σ^n(u_ℓ)|_c/∑_ℓ = j+1^j+k |σ^n(u_ℓ)|·∑_ℓ = j+1^j+k |σ^n(u_ℓ)|/L + |v|_c + |w|_c/L,

we obtain that 

    min_a ∈ A|σ^n(a)|_c/|σ^n(a)|·∑_ℓ = j+1^j+k |σ^n(u_ℓ)|/L   ≤|u_[i,i+L)|_c/L
       ≤max_a ∈ A|σ^n(a)|_c/|σ^n(a)|·∑_ℓ = j+1^j+k |σ^n(u_ℓ)|/L+2S_nL^-1.

However, 

    1-δ_k=1/2C^2k^-1+1≤∑_ℓ = j+1^j+k |σ^n(u_ℓ)|/L≤ 1.

Let b ∈ A be arbitrary. Putting (<ref>) and (<ref>) together, we obtain that 

    (1-δ_k)min_a ∈ A|σ^n(a)|_c/|σ^n(a)| - |σ^n(b)|_c/|σ^n(b)|≤|u_[i,i+L)|_c/L  - |σ^n(b)|_c/|σ^n(b)|≤max_a ∈ A|σ^n(a)|_c/|σ^n(a)| - |σ^n(b)|_c/|σ^n(b)| + 2S_nL^-1,

and hence,

    ||u_[i,i+L)|_c/L - |σ^n(b)|_c/|σ^n(b)||≤max_a ∈ A||σ^n(a)|_c/|σ^n(a)| - 
    |σ^n(b)|_c/|σ^n(b)|| + maxδ_k, 2S_nL^-1.

Using (<ref>), (<ref>) and (<ref>), we hence obtain that 

    ‖(u_[i,i+L))/L - (σ^n(b))/|σ^n(b)|‖_1 
       ≤∑_c ∈ Amax_a ∈ A||σ^n(a)|_c/|σ^n(a)| - 
    |σ^n(b)|_c/|σ^n(b)|| + (# A) maxδ_k, 2S_nL^-1
       ≤ϵλ/2 ‖ M_σ‖_1.

We finally obtain that 

    ‖(u_[i,i+L))/L - α/‖α‖_1‖_1    ≤‖(u_[i,i+L))/L - (σ^n(b))/|σ^n(b)|‖_1 + 
    ‖(σ^n(b))/|σ^n(b)| - α/‖α‖_1‖_1 
       ≤ϵλ/‖ M_σ‖_1

and hence,

    |σ(u_[i,i+L)) |   = L ‖ (u_[i,i+L))/LM_σ‖_1 
       ≥ 
    L|‖α/‖α‖_1M_σ‖_1 - 
    ‖( (u_[i,i+L))/L-α/‖α‖_1)M_σ‖_1|
       ≥ L(1-ϵ)λ = ρ L.


It is now clear that L_1 is computable, because in virtue of (<ref>) and 
(<ref>) it is sufficient to choose L_1 so that 

    max2C^2/S_n^-1L_1+2(C^2-1), 2S_n L_1^-1 < ϵλ/4 (# A)‖ M_σ‖_1.

This completes the proof. 

Fix 1 < ρ < λ and L_1 ∈ as in Lemma <ref>. 
Fix an integer N greater than 

    maxS_1 (L_1+1) -1, 1+L_0(I_1^-1+1)/ρ-1.

Set 

    V^∗=(xac,ybc) ∈Ł_N+L_1+1(u) ×Ł_N+L_1+1(u) | a,b ∈ A  (a  b),  c 
    ∈Ł_L_1(u),

which is nonempty, because the sequence u over the finite alphabet A is assumed to be 
aperiodic; see <cit.> and <cit.>. Define an equivalence 
relation ∼ on V^∗ so that (v,w) ∼ (v^',w^') if and only if 
(v,w) = (v^',w^') or (v,w) ∼ (w^',v^'). Set V=V^∗/∼. Let 
[v,w] denote the equivalence class of a given element (v,w) of V^∗. 
Consider a directed,finite graph G with vertex set V and edge set E. 
The edge set E is defined by declaring that there exists an edge from a vertex v to a vertex 
v^' if and only if there exist word w ∈ A^+, representatives (s,t) and 
(s^',t^') of the equivalence classes v and v^', respectively, such that 
s^' w ≺_σ(s) and t^' w ≺_σ(t). 

The number of edges leaving a given vertex is at most one. 





We say that a vertex of the directed, finite graph G generates a gap of natural 1-cutting 
points if there exist letters α, β, words γ, δ of the same length and 
representative (v,w) of the vertex so that 


  * σ(α) ≺_σ(β);

  * σ(γ_i)=σ(δ_i) for every integer i with 1 ≤ i ≤ |γ|;

  * αγ≺_σ(v) and βδ≺_σ(w).


We define a unilateral subshift:

    X_σ=x=(x_i)_i ∈_+|x_[i,j]∈Ł(u)  for all i,j ∈_+.

In other words, the unilateral subshift X_σ is generated by the language of the sequence u. 

The following are equivalent:


  * 
the substitution σ is not unilaterally recognizable;

  * 
the directed, finite graph G has a cycle including a vertex generating a gap of natural 
1-cutting points.




(<ref>) ⇒ (<ref>): Assume that the directed, finite graph G 
includes a cycle: 

    [x_ia_ic_i,y_ib_ic_i] ∈ V|0 ≤ i ≤ℓ

of length ℓ so that 


  * the vertex [x_0a_0c_0,y_0b_0c_0] generates a gap of natural 1-cutting points;

  * x_ℓ a_ℓ c_ℓ = x_0 a_0 c_0 and y_ℓ b_ℓ c_ℓ = y_0 b_0 c_0;

  * for every integer i with 0 ≤ i < ℓ, there exists w_i+1∈ A^+ satisfying that 

    x_i+1a_i+1c_i+1w_i+1≺_σ(x_ia_ic_i)  and  
    y_i+1b_i+1c_i+1w_i+1≺_σ(y_ib_ic_i).


For every integer i with i > ℓ, put w_i=w_(i ℓ) + 1. 
It is straightforward to see that for every k ∈, 

    x_0a_0c_0 w_kℓσ(w_kℓ-1) σ^2(w_kℓ-2) …σ^kℓ-2(w_2) 
    σ^kℓ-1(w_1)    ≺_σ^kℓ(x_0a_0c_0); 
    
    y_0b_0c_0 w_kℓσ(w_kℓ-1) σ^2(w_kℓ-2) …σ^kℓ-2(w_2) 
    σ^kℓ-1(w_1)    ≺_σ^kℓ(y_0b_0c_0).

Hence, Condition (<ref>) in Theorem <ref> is satisfied. 

(<ref>) ⇒ (<ref>): 
Assume that σ is not unilaterally recognizable. We shall see that the directed, finite graph 
G has a vertex which generates a gap of natural 1-cutting points. Using the pigeonhole principle 
together with Theorem <ref> and the uniform recurrence of the sequence u, we 
can find x,y ∈Ł_N(u), a,b ∈ A and z,w ∈ X_σ so that 


  * xaz,ybw ∈ X_σ;

  * σ(a) ≺_σ(b);

  * σ(z_i)=σ(w_i) for all i ∈_+.

Lemma <ref> allows us to find ℓ∈_+ such that 


  * z_ℓ-1 w_ℓ-1;

  * z_[ℓ,+∞)=w_[ℓ,+∞);

  * |σ(z_[0,ℓ))| ≤ L_0;

  * |σ(w_[0,ℓ))|≤ L_0,

where we use a convention that z_-1=a and w_-1=b. 

By the pigeonhole principle again, using the hypothesis that the sequence u is assumed to be 
aperiodic, we can find e,f ∈ X_σ for which 

    xaz ≺_σ(e),  xaz ⊀_σ(e_[1,+∞)),  ybw ≺_σ(f) 
     and  ybw ⊀_σ(f_[1,+∞)).

In view of Lemma <ref> again, there exist m,n ∈ such that 


  * α:=e_m-1 f_n-1=:β;

  * ζ:=e_[m,+∞)=f_[n,+∞). 

Recall that z_ℓ-1 w_ℓ-1. There exists a prefix s ∈ A^∗ of 
z_[ℓ,+∞)=w_[ℓ,+∞) such that 

    |s| ≤ L_0,  xaz_[0,ℓ)s ≺_σ(e_[0,m))  and  
    ybw_[0,ℓ)s ≺_σ(f_[0,n)).

Since 

    m S_1 ≥ |σ(e_[0,m))| ≥ |xa| = N+1 ≥ S_1 (L_1+1),

we obtain that m-1 ≥ L_1. This together with Lemma <ref> implies that 

    ρ(m-1) ≤ |σ(e_[1,m))| < |xaz_[0,ℓ)s| ≤ N + 1 + L_0(I_1^-1+1) < ρ N,

where the second inequality follows from the second property of (<ref>), so that 
m-1 < N. 
Similarly, we obtain that n-1 < N. These facts allow us to find words χ,τ∈Ł_N(u) so that 


  * e_[0,m-1)≺_χ;

  * χαζ∈ X_σ;

  * f_[0,n-1)≺_τ;

  * τβζ∈ X_σ.

Consequently, we obtain that 


  * σ(e) ≺_σ(χ)σ(e_[m-1,+∞)) = σ(χαζ);

  * σ(f) ≺_σ(τ)σ(f_[n-1,+∞)) = σ(τβζ).

This together with (<ref>) shows that 


  * xaz ≺_σ(χαζ);

  * ybw ≺_σ(τβζ).

Since in virtue of (<ref>) we know that xaz_[0,ℓ)s ≺_σ(χα), letting 
γ = ζ_[0,L_1), we obtain that 
xaz_[0,ℓ)s σ(γ) ≺_σ(χαγ), and also that 
ybw_[0,ℓ)sσ(γ) ≺_σ(τβγ). 
We have obtained a vertex [χαγ, τβγ] ∈ V which generates a 
gap of natural 1-cutting points. 

Now, apply the procedure to (χαζ, τβζ), which has been 
applied to (xaz,ybw) for obtaining (χαζ, τβζ). 
It yields another vertex where an edge 
leaves for (χαγ, τβγ). Applying the procedure inductively 
yields an infinite path in the directed, finite graph, which results in a cycle in virtue of 
Remark <ref>. 






  
Acknowledgments
The first revision was undertaken during the third author's visit in 2014 at Laboratoire 
Amiénois de Mathématiques Fondamentales et Appliquées, CNRS-UMR 6140, Université de 
Picardie Jules Verne. He is grateful for hospitality and kind support extended to him by the 
institution. The second revision was done in 2015 after his visit at Institute of 
Mathematics, University of Tsukuba. This revision was done in 2017 after his visit at Centre 
International de Rencontres Mathématiques. He is also grateful for their hospitality and discussion. 
This work was partially supported by JSPS KAKENHI Grant Number 17K05159.

99

CH
Ethan M. Coven and G. A. Hedlund, Sequences with Minimal Block Growth, Theory Comput. Syst. 
7 (1973), 138-153.

MR1709427
F. Durand, B. Host, and C. Skau, Substitutional dynamical systems, Bratteli diagrams and
dimension groups, Ergodic Theory Dynam. Systems 19 (1999), no. 4, 953–993. MR 1709427

ELR1
A. Ehrenfeucht and K. P. Lee and G. Rozenberg, Subword complexities of various classes of 
deterministic developmental languages without interactions, Theoret. Comput. Sci. 1 
(1975), no. 1, 59-75.

MR1970385
N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in 
Mathematics, vol. 1794, Springer-Verlag, Berlin, 2002, Edited by V. Berthé, S. Ferenczi, 
C. Mauduit and A. Siegel. MR 1970385

HL
Tero Harju and Matti Linna, On the periodicity of morphisms on free monoids, 
Theor. Inform. Appl. 20 (1986), no. 1, 47-54.

hartfiel
Darald J. Hartfiel, Nonhomogeneous Matrix Products, World Scientific, 2002. 

HPS
Richard H. Herman, Ian F. Putnam and Christian F. Skau, Ordered Bratteli diagrams, dimension 
groups and topological dynamics, Internat. J. Math. 3 (1992), 827-864.

MR873430
B. Host, Valeurs propres des systèmes dynamiques définis par des substitutions de longueur 
variable, Ergodic Theory Dynam. Systems 6 (1986), no. 4, 529–540. MR 873430

MR2041676
Petr, Kůrka, Topological and symbolic dynamics, Cours Spécialisés [Specialized Courses], 
vol. 11, Société Mathématique de France, Paris, 2003. MR 2041676

MR1369092
Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, 
Cambridge University Press, Cambridge, 1995. MR 1369092

MR1168468
Brigitte Mossé, Puissances de mots et reconnaissabilité des points fixes d'une 
substitution, Theoret. Comput. Sci. 99 (1992), no. 2, 327–334. MR 1168468

MR1414542
Brigitte Mossé, Reconnaissabilité des substitutions et complexité des suites 
automatiques, Bull. Soc. Math. France 124 (1996), no. 2, 329–346. MR 1414542

pansiot1
Jean-Jacques Pansiot, Complexité des facteurs des mots infinis engendré par morphismes 
itérés", Automata, languages and programming (Antwerp, 1984), Lecture Notes in Comput. Sci., 
vol. 172, Springer, Berlin, 1984, pp. 380-389. 

pansiot2
Jean-Jacques Pansiot, Decidability of periodicity for infinite words, Theor. Inform. Appl. 
20 (1986), no. 1, 43-46.

MR924156
Martine Queffélec, Substitution dynamical systems—spectral analysis, Lecture Notes in 
Mathematics, vol. 1294, Springer-Verlag, Berlin, 1987. MR 924156

MR2590264
Martine Queffélec, Substitution dynamical systems—spectral analysis, second ed., 
Lecture Notes in Mathematics, vol. 1294, Springer-Verlag, Berlin, 2010. MR 2590264

Ro
Grzegorz Rozenberg, D0L Sequences, Discrete Math. 7 (1974), no. 3-4, 323–347.

Sen
E. Seneta, Non-negative Matrices and Markov Chains, Springer Science & Business Media, 
2006.

Sol
B. Solomyak, Nonperiodicity implies unique composition for self-similar translationally finite 
tilings, Discrete Comput. Geom. 20 (1998), no. 2, 265-279.

Y4
Hisatoshi Yuasa, Invariant measures for the subshifts arising from non-primitive substitutions, 
J. Anal. Math., 102 (2007), 143–180. MR 2346556



