{'fraction_non_alphanumeric': 0.07349734486031656, 'fraction_numerical': 0.014545547830994586, 'mean_word_length': 3.204724409448819, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the existence of open and bi-continuing codes

Given an irreducible sofic shift X, we show that an an irreducible SFT Y of lower entropy is a factor of X if and only if it is a factor of X by an open bi-continuing code. If these equivalent conditions hold and Y is mixing, then any code from a proper subshift of X to Y can be extended to an open bi-continuing code on X. These results are still valid when X is assumed to be only an almost specified shift, i.e., a subshift satisfying an irreducible version of the specification property.


Introduction and Preliminaries
Let X and Y be shift spaces. Suppose that there exists a factor code from X to Y . If we denote by h(X) the topological entropy of X, then h(X) ≥ h(Y ). Also, whenever x is a periodic point of X, there exists a periodic point of Y whose period divides the period of x. We denote this condition by P (X) P (Y ) and call it the periodic condition. These two conditions (on entropies and periodic points) are necessary for X to factor onto Y . To find satisfactory sufficient conditions for X to factor onto Y (by a code with certain properties) is one of the important problems in symbolic dynamics.
In [5], Boyle proved the following theorem: Given irreducible shifts of finite type X and Y with h(X) > h(Y ), Y is a factor of X if and only if the periodic condition P (X) P (Y ) holds. One can consider two directions of generalizing this result: One is to impose certain properties on the factor code, and the other is to weaken the finite-type constraints on X and Y .
The first type of generalization is due to Boyle and Tuncel. In [7], they showed that the entropy and the periodic conditions also imply that Y is a factor of X by a right continuing code. A right continuing code is a code which is surjective on each unstable set (see Definition 2.1). It is a natural dual version of a right closing code and plays a fundamental role in the class of infinite-to-one codes [7,6].
The other direction of generalization is considered by Thomsen [16], who investigated the existence of factor codes between irreducible sofic shifts. In particular, he gave a necessary and sufficient condition for an irreducible shift of finite type to be a factor of a given synchronized system of greater synchronized entropy (see §5).
In this paper, we focus on two kinds of codes: Open codes and bi-continuing codes, i.e., left and right continuing codes. We will generalize the above results in both codes between shifts of finite type have been studied in several contexts [9,14,10]. A finite-to-one factor code between irreducible shifts of finite type is open if and only if it is bi-closing [14]. A natural generalization exists: A factor code from a shift of finite type to a shift space is open if and only if it is bi-continuing (see Theorem 2.6). In §2 , we investigate these two types of codes and give several sufficient conditions for one to imply the other.
To enlarge the class of domains satisfying the theorem of Boyle and Tuncel, we consider the class of shifts with the almost specification property (or almost specified shifts) which are subshifts satisfying an irreducible version of the specification property (see Definition 3.1). Every irreducible sofic shift is almost specified, and almost specified shifts behave much like shifts with the specification property except being mixing. Our main theorem is stated as follows.
Theorem 5.2. Let X be an almost specified shift and Y an irreducible shift of finite type such that h(X) > h(Y ). Then the following are equivalent.
(1) Y is a factor of X by a bi-continuing code with a bi-retract.
(2) Y is a factor of X by an open code with a uniform lifting length.
(3) Y is a factor of X. If X is of finite type, then the above conditions are also equivalent to: (4) P (X) P (Y ).
As a corollary, it follows that given an irreducible shift of finite type X, a shift space Y is a lower entropy open factor of X exactly when h(X) > h(Y ), P (X) P (Y ) and Y is an irreducible shift of finite type (see Corollary 5.4).
It is not surprising that factor problems usually involve extension problems [1,5,7]. Even in the case where X and Y are irreducible shifts of finite type and P (X) P (Y ), not every code can be extended (see Example 5.6). In §5, we give a necessary condition for a code on a proper subshift of X to be extended to a code on X and show that it is the only obstruction to extend it to a code on X. We give an extension theorem as follows.
Theorem 5.5. Let X be an almost specified shift and Y an irreducible shift of finite type such that h(X) > h(Y ) and Y is a factor of X. Then any code from a proper subshift of X to Y , which can be extended to a code on X, can be extended to an open bi-continuing code of X onto Y .
In particular, if Y is mixing, then any code from a proper subshift of X to Y can be extended to an open bi-continuing code of X onto Y (see Theorem 4.5). The theorem says that the openness and the bi-continuing property of a code are both global in the sense that these properties cannot be ruled out by any property a code might exhibit on a proper subshift.
We introduce some notations and definitions used. If X is a shift space with the shift map σ, denote by B n (X) the set of all words of length n appearing in the points of X and B(X) = n≥0 B n (X). Also let A(X) = B 1 (X) and B X n (a, b) = {u 1 . . . u n ∈ B n (X) : u 1 = a, u n = b} for each a, b ∈ A(X). A shift space X is called irreducible if for all u, v ∈ B(X), there is a word w with uwv ∈ B(X). It is called mixing if for all u, v ∈ B(X), there is an integer N ∈ N such that whenever n ≥ N , we can find w ∈ B n (X) with uwv ∈ B(X). If there is such an N which works for all u, v ∈ B(X), then we call N + 1 a transition length for X.
A code φ : X → Y is a continuous σ-commuting map between shift spaces. It is called a factor code if it is onto. In this case we say that Y is a factor of X. Any code can be recoded to be a 1-block code, i.e. a code for which x 0 determines φ(x) 0 .
A subshift X is called a shift of finite type if there is a finite set F of words such that X consists of all points on A(X) in which there is no occurrence of words from F. Any shift of finite type is conjugate to an edge shift, i.e., a shift space which consists of all bi-infinite trips in a directed graph G. If A is the adjacency matrix for G, denote by X A the edge shift on G. A shift space is called sofic if it is a factor of a shift of finite type. A mixing sofic shift always has a transition length.
A word v ∈ B(X) is synchronizing if whenever uv and vw are in B(X), we have uvw ∈ B(X). Following [4], an irreducible shift space X is a synchronized system if it has a synchronizing word. For a given set of words W , let X W be the smallest shift space containing all the sequences obtained by concatenating words in W . We call X W a coded system. A synchronized system is coded [4].
For a shift space X with periodic points, let per(X) be the greatest common divisor of periods of all periodic points of X. Let X be an irreducible edge shift and p = per(X). Then there exists a unique partition {A 0 , A 1 , · · · , A p−1 } of A(X) such that whenever ab ∈ B(X) and a ∈ A i , then b ∈ A i+1 (mod p) . Also there is n ∈ N with the property that B X n (a, b) = ∅ for any a, b ∈ A i and i = 0, 1, · · · , p − 1. This n is called a weak transition length for X.
The entropy of a shift space X is defined by h(X) = lim n→∞ (1/n) log |B n (X)|, which equals the topological entropy of (X, σ) as a dynamical system. If X is an irreducible shift of finite type and p = per(X), then for any a, b ∈ A(X) we have the following equalities: where p k (X) (resp. q k (X)) denotes the number of periodic points of X with period k (resp. least period k). If X is mixing, then limsup becomes limit. For more details on symbolic dynamics, see [12]. For a perspective for open maps between shift spaces, see [10].

Properties of continuing codes
A code φ : X → Y is called right closing if whenever x ∈ X, y ∈ Y and φ(x) is left asymptotic to y, then there exists at most onex ∈ X such thatx is left asymptotic to x and φ(x) = y. Right closing codes form an important class of finite-to-one codes, especially between irreducible shifts of finite type. The following notion, which can be thought as a dual of the above property, first appeared in [7]. Definition 2.1. A code φ : X → Y between shift spaces is called right continuing if whenever x ∈ X, y ∈ Y and φ(x) is left asymptotic to y, then there exists at least onex ∈ X such thatx is left asymptotic to x and φ(x) = y. A left continuing code is defined similarly. If φ is both left and right continuing, it is called bi-continuing.
A right continuing code into an irreducible sofic shift must be onto. In general it need not be onto. The Perron-Frobenius theory implies that a factor code between irreducible shifts of finite type with the same entropy is right continuing exactly when it is right closing.
Note that having a retract is a conjugacy invariant. If φ has both left and right continuing retracts n, we simply say that φ has bi-retract n.
A code φ : X → Y between shift spaces is open if and only if for each k ∈ N, there is m ∈ N such that whenever x ∈ X, y ∈ Y and φ( and φ(x) = y. We say that φ has a uniform lifting length if for each k ∈ N, there exists m satisfying the above property such that sup k |m − k| < ∞. In this case, we can assume that m − k is constant and nonnegative. Note that having a uniform lifting length is also a conjugacy invariant.
Lemma 2.1. Let φ : X → Y be a code between shift spaces. If φ is open with a uniform lifting length, then it is bi-continuing with a bi-retract. When Y is of finite type, then the converse holds.
Proof. First, suppose that φ is open with a uniform lifting length. We can assume φ is a 1-block code. Choose l ≥ 0 so that for each central 2k + 1 cylinder in X, its image consists of central 2k + 2l + 1 cylinders. Let x ∈ X and y ∈ Y satisfy φ(x) (−∞,0] = y (−∞,0] . By considering φ( −2k−l [x −2k−l · · · x −l ]) for k ∈ N, we obtain points z (k) such that z Next, assume that φ is bi-continuing with bi-retract n ∈ N and Y is of finite type. We can assume that Y is an edge shift and φ is a 1-block code. Suppose that l ≥ 0 and u ∈ B 2l+1 (X). Choose x ∈ −l [u] and let y ∈ Y with y [−l−n,l+n] = φ(x) [−l−n,l+n] . The pointȳ, given byȳ Since n is also a left continuing retract, there is anx ∈ X such thatx [−l,∞) = z [−l,∞) and φ(x) = y. Note thatx [−l,l] Thus φ is open with uniform lifting length n. Remark 2.2. Note that the proof of the second statement in Lemma 2.1 is still valid under a weaker assumption on Y , that is, when there is a shift of finite type Z such that φ(X) ⊂ Z ⊂ Y and Z is open and closed in Y .

Lemma 2.3. [10]
Let X be a shift of finite type and φ an open factor code from X to a shift space Y . Then Y is of finite type.
In [7], the first statement of the following proposition is proved when both shift spaces are of finite type. We show that the codomain need not be of finite type.
Proposition 2.4. Let φ : X → Y be a code between shift spaces and X of finite type.
(1) If φ is right continuing, then it has a retract.
(2) If φ is open, then it has a uniform lifting length.
Proof. By recoding, we can assume that X is an edge shift and φ is 1-block.
This n in the claim is indeed a retract. Suppose x ∈ X and y ∈ Y satisfy (2) Choose l ≥ 0 so that φ([a]) consists of central 2l+1 cylinders for all a ∈ B 1 (X).
Since φ is open, Z = φ(X) is open and closed in Y . Also Z is a shift of finite type by Lemma 2.3. Thus by Remark 2.2, φ is open with a uniform lifting length.
Remark 2.5. A code φ : X → Y between shift spaces is called right continuing a.e. (almost everywhere) if whenever x ∈ X is left transitive in X and φ(x) is left asymptotic to a point y ∈ Y , then there existsx ∈ X such thatx is left asymptotic to x and φ(x) = y. Similarly we have the notions called left continuing a.e. and bi-continuing a.e. A slight modification of the proof of Lemma 2.4 (2) shows that an open code from a synchronized system is bi-continuing a.e. Theorem 2.6. Let φ be a factor code from a shift of finite type X to a sofic shift Y . Then φ is open if and only if it is bi-continuing.
Proof. Suppose first that φ is open. By Lemma 2.3, Y is of finite type. It follows from Proposition 2.4 (2) and Lemma 2.1 that φ is bi-continuing.
Suppose φ is bi-continuing. Since Y is sofic, there are a shift of finite type Z and a factor code π : Z → Y . Consider the fiber product (Σ, ψ 1 , ψ 2 ) of (φ, π) [12]. Then Σ is of finite type. By a usual fiber product argument, it is easy to show that ψ 2 is also bi-continuing. Since Σ and Z are of finite type, it follows from Proposition 2.4 (1) and Lemma 2.1 that ψ 2 is open. Since fiber product pulls down the openness of a code, it follows that φ is open [10, Lemma 2.4].
Remark 2.7. Recently, J. Yoo [17] showed us that a right continuing factor of a shift of finite type is also of finite type. This result, combined with Proposition 2.4 (1) and Lemma 2.1, implies the 'if' part of Theorem 2.6.
Remark 2.8. It is well known that a finite-to-one factor code between irreducible shifts of finite type is open if and only if it is bi-closing [14]. Thus Theorem 2.6 can be thought as an infinite-to-one version of this fact. In the finite-to-one case, we also have the following relation: A finite-to-one factor code between irreducible shifts of finite type is open exactly when it is constant-to-one. By virtue of this relation, it is natural to ask whether an infinite-to-one code between irreducible shifts of finite type is open if and only if it is infinite-to-one everywhere, i.e., |φ −1 (y)| = ∞ for all y. However, it turns out that each implication is not true.
We summarize the implications between factor codes in the following diagram. When X is of finite type, then all conditions but bi-continuing a.e. are equivalent by Proposition First we show that φ is not right continuing. Take and there are i ≤ −l and j ≥ l withx i =x j = a. If x already has this property, we are done. Otherwise, there are two cases (up to symmetry): ∞) . Suppose first that a occurs in x (−l,l) . Letī andj be the leftmost and rightmost occurrence of a in x, respectively.
satisfies the property. Other cases can be proved similarly. This proves the claim. Take Thus φ is an example of an open code which is neither right nor left continuing. By Lemma 2.1, φ has no uniform lifting length. Thus the converse of (a) does not hold in general.
We first show that φ is right continuing: Suppose x ∈ X and y ∈ Y satisfy is in X, then we are done. Otherwise, the word12 n 3 occurs exactly once in x (1) . Let x (2) be the point obtained from x (1) by replacing12 n 3 with 12 n 3. Then φ(x (2) ) = y and x (2) is left asymptotic to x. But considering x =1 ∞ 2 n .22 ∞ and y = 1 ∞ 2 n .23 ∞ for each n ∈ N, one can see that φ has no (right continuing) retract.
. Thus φ is left continuing with retract 0, hence it is bi-continuing but does not have a right continuing retract. So a continuing code may not have a retract and the converse of (b) does not hold.
Moreover, φ is an example of a bi-continuing code which is not open.
, a contradiction comes. Indeed X is an irreducible strictly sofic shift.
(3) As is easily seen, if Y is the even shift and φ : X A → Y is its canonical cover (i.e., a code given by its minimal right resolving presentation [12]), then φ is bicontinuing a.e. but neither open nor bi-continuing. Thus the converses of (c) and (d) are false even if the domain is of finite type.

Almost specified shifts
To investigate the existence of continuing codes, we consider the almost specified shifts. In this section we present several properties of almost specified shifts defined as follows. These will be used in subsequent sections.
Note that an irreducible sofic shift is almost specified.
If X is an almost specified shift, then it is a synchronized system.
Proof. Let N satisfy the condition in Definition 3.1 (2). For given u, v ∈ B(X), let B(u, v) be the set of words w such that uwv ∈ B(X) and |w| ≤ N . Note that B(u, v) is a nonempty finite set. Fix two words u (0) and v (0) in B(X). We define u (n) and v (n) inductively as follows. Suppose that u (0) , · · · , u (n−1) and v (0) , · · · , v (n−1) are given. If there are u, v ∈ B(X) such that then let u (n) = u and v (n) = v. Since B(u, v)'s are nonempty finite sets, this process eventually terminates in the sense that there is m ∈ N such that by lettinḡ u = u (m) · · · u (0) andv = v (0) · · · v (m) we have B(uū,vv) = B(ū,v) for all u, v ∈ B(X) with uū,vv ∈ B(X). Thenūwv is a synchronizing word for each w ∈ B(ū,v).
The following lemma shows that the almost specification property is a natural irreducible version of the specification property. Proof. Suppose X is almost specified. Let N be given as in Definition 3.1 (2) and by using Lemma 3.1 take a synchronizing word w ∈ B(X). Since X is mixing, there is L > 0 such that for all l ≥ L, we can find u ∈ B l (X) with wuw ∈ B(X). Let M = 2N + 2|w| + L. For any u, v ∈ B(X), there existū,v ∈ B(X) with |ū|, |v| ≤ N and uūw, wvv ∈ B(X). Also we can findw ∈ B L+2N −|ū|−|v| (X) with www ∈ B(X). Letw =ūwwwv. Then uwv ∈ B(X) and |w| = M . Thus M satisfies the condition in Definition 3.1 (1) and X has the specification property.
For a shift space X, denote by X − (X + , resp.) the set of left (right, resp.) infinite sequences of X. For x ∈ X, we denote by x − (resp. x + ) the sequence x (−∞,−1] ∈ X − (resp. x [0,∞) ∈ X + ). If x − ∈ X − and u ∈ B(X), their concatenation x − u is naturally defined. We write x − u ∈ X − when there exists a sequence y ∈ X + such that x − uy ∈ X. A similar operation is defined on B(X) and X + . Then we have the following lemma whose proof is obvious by compactness. (1) X has the specification property if and only if there is N ∈ N such that whenever x − ∈ X − and u ∈ B(X), there is w ∈ B N (X) such that x − wu ∈ X − . (2) X is almost specified if and only if there is N ∈ N such that whenever x − ∈ X − and u ∈ B(X), there is w ∈ B(X) such that |w| ≤ N and x − wu ∈ X − .
Example 3.4. Let S = {n 1 , n 2 , . . .} ⊂ Z + with n i < n i+1 (possibly, finite) and X = X(S) the coded system generated by {10 n : n ∈ S}. This X(S) is called the S-gap shift [12]. Note that X is a synchronized system. Then we have the following characterizations.
(1) X is almost specified if and only if sup i |n i+1 − n i | < ∞.
(1) If S is finite, then X is of finite type (hence almost specified) and sup i |n i+1 − n i | < ∞, thus the equivalence is clear. So we may assume S is infinite. Suppose that X is almost specified. Let N be given as in Definition 3.1 (2). Then for each n i ∈ S, there exists w such that 10 n i +1 w1 ∈ B(X) and |w| ≤ N . Thus |n i+1 − n i | ≤ N + 1 for all i. Conversely, if L = sup i |n i+1 − n i | < ∞, then let N = max(n 1 , L). For any v, w ∈ B(X), there exist i, j ≤ N with v0 i 1, 10 j w ∈ B(X). Then v0 i 10 j w ∈ B(X) and |0 i 10 j | ≤ 2N + 1. Thus X is almost specified.
(2) If X is mixing, then there exists N > 0 such that for all n ≥ N , there exists w ∈ B n (X) with 1w1 ∈ B(X). Thus there are words of length N + 1 and N + 2 of the form 10 i 1 10 i 2 . . . 10 im with i k ∈ S, implying that gcd{n + 1 : n ∈ S} = 1.
On the other hand, if gcd{n + 1 : n ∈ S} = 1 then for all sufficiently large n, there is a word of length n of the form 10 i 1 10 i 2 . . . 10 im 1. Since 1 is synchronizing and X is irreducible, the result follows.
(3) This follows from (1), (2) and Lemma 3.2. Then it is a nonsofic almost specified shift without the specification property. (2) For any X with the specification property, define its root X by where a is a symbol which is not in B 1 (X). Then Y = X ∪ σ( X) is almost specified, but does not have the specification property.
(3) Let W = {ab k c k : k ≥ 1} and X = X W . It is easy to see that X is mixing and synchronized. But if x − = b ∞ , then there is no w ∈ B(X) such that x − wa ∈ X − . By Lemma 3.3, X cannot be almost specified.
A synchronized system has a global periodic structure similar to an irreducible shift of finite type. The collection of the subsets D i in the following theorem is called the cyclic cover of X. It is unique up to cyclic permutation.
Theorem 3.6. [16] Let X be a synchronized system. Then there exist a unique p ∈ N and closed sets D i ⊂ X, i = 0, 1, · · · , p − 1, such that iii) σ p | D i is mixing for all i = 0, 1, · · · , p − 1, and vi) D i ∩ D j has empty interior when i = j.
If X is an irreducible shift of finite type, then this decomposition is well known (cf, [12]). In this case p = per(X) and D i ∩ D j = ∅ for i = j.
Let X p be the pth higher power shift of X and γ : X → X p the pth higher power code [12] given by γ( is naturally defined. This γ is a topological conjugacy between (X, σ p ) and (X p , σ). When X is a synchronized system, we define X i = γ(D i ). Then X i is an irreducible subshift of X p and γ is also a topological conjugacy between (D i , σ p ) and (X i , σ) for each 0 ≤ i < p. Note that for a block u ∈ B pM (X), γ(u) ∈ B(X i ) if and only if there exists a point x ∈ D i with x [0,pM −1] = u. From the construction of the cyclic cover of X, it follows that the sets {γ(u) ∈ B(X i ) : u is a synchronizing word for X} are disjoint. This is because X i is the closure of an 'irreducible subshift' of X p in the sense of Thomsen (see [16, §3]). Thus for a synchronized word u ∈ B pM (X), there exists a unique i with γ(u) ∈ B(X i ). We use this fact to prove the following result.
Lemma 3.7. Let X be an almost specified shift. If {D 0 , · · · , D p } is the cyclic cover of X, then σ p | D i has the specification property.
Proof. It suffices to show the case i = 0. Note that σ p | D 0 has the specification property if and only if X 0 has the specification property. Since X is almost specified, there exists N satisfying the condition in Definition 3.1 (2). We claim that X 0 is also almost specified.
Proposition 3.8. Let X be an almost specified shift with h(X) > 0. For given > 0, there exist an irreducible shift of finite type Z ⊂ X and k ∈ N such that h(Z) > h(X) − and any k-block of Z is a synchronizing word of X. If X is mixing, then Z can be chosen to be mixing.
Proof. The proof essentially follows the lines in [5,13]. First, we prove the case where X has the specification property. Using Lemma 3.1 find a synchronizing word w ∈ B(X). For each k > |w|, let X k be the (k − 1)-step shift of finite type whose k-blocks are a 1 . . . a k ∈ B k (X) such that w occurs in a 2 . . . a k . Then X k ⊂ X.
Let N be given in Definition 3.1 (1). Fix k > 2N + 2|w|. For each l = mk with m ∈ N, we have since for each m pair of words v (1) , · · · , v (m) ∈ B k−2N −2|w| , there exists a word in B l (X k ) whose initial sequence is of the form wu (1) It is easy to see that X k is mixing for all large k. Take k large so that X k is mixing, h(X k ) > h(X) − and let Z = X k .
Next, we prove the case where X is almost specified. Let {D 0 , · · · , D p } be the cyclic cover of X and take X 0 = γ(D 0 ) as in the remark following Theorem 3.6. Since X 0 has the specification property by Lemma 3.7, by applying the previous result to X 0 , we get Z 0 ⊂ X 0 satisfying the properties. Define Then Z satisfies all the desired properties.
Remark 3.9. There is a synchronized system X such that sup Y ⊂X h(Y ) < h(X), where the supremum is taken over all sofic subshifts Y of X [15]. Thus Proposition 3.8 does not hold when X is merely synchronized.

Extension Theorem: A mixing case
In this section, we prove that when X is almost specified and Y is mixing and of finite type, the entropy and the periodic conditions guarantee the existence of a bi-continuing factor code from X to Y with a bi-retract. With little extra work, in fact we prove further that every code from a proper subshift of X to Y can be extended to an open bi-continuing code. First we need some lemmas. Then there exist an irreducible shift of finite type Z ⊂ X and a bi-closing factor code π : Z → Y .
Proof. We can assume Y = X B with B irreducible. Let m be the size of B. For each n ∈ N, define Y n = X Bn , where B n is the nm × nm irreducible matrix given by Note that per(Y n ) = n · per(Y ) and p kn (Y n ) = n · p kn (Y ) for each k ∈ N. For each n ∈ N, it is easy to see that the natural projection code from Y n to Y is bi-resolving (e.g., see [14]). So it suffices to show that Y n embeds into X for large n. Let = (h(X) − h(Y ))/3. Take n large such that per(X)|n, n −1 log n < , Then for each k ∈ N, so we have n · p kn (Y ) < q kn (X), and therefore Since p j (Y n ) = 0 if j / ∈ nN, we have q j (Y n ) ≤ q j (X) for all j ∈ N. Now applying the Krieger's Embedding Theorem [11] gives the result.

Lemma 4.3 (Extension Lemma). [5]
Let X be a shift space and Y a mixing shift of finite type such that P (X) P (Y ). Then any code from a proper subshift of X to Y can be extended to a code from X to Y .
It is the following theorem which we extend in this section. By usual reduction to the mixing case, Theorem 4.4 shows that the entropy and the periodic conditions guarantee the existence of a right continuing factor code between two irreducible shifts of finite type. However, to extend an arbitrary code on a proper subshift to a code on the whole domain, the mixing condition on Y is crucial (see Example 5.6).

Theorem 4.4. [7]
Let X be an irreducible shift of finite type and Y a mixing shift of finite type such that h(X) > h(Y ) and P (X) P (Y ). Then any code from a proper subshift of X to Y can be extended to a right continuing code on X. Now we are ready to prove the main theorem in this section. As indicated in §1, we extend the above theorem in two directions. This extension result will be used in §5 to obtain our main results: Theorem 5.2 and Theorem 5.5. Theorem 4.5. Let X be an almost specified shift and Y a mixing shift of finite type such that h(X) > h(Y ) and P (X) P (Y ). Then any code from a proper subshift of X to Y can be extended to an open bi-continuing code on X with a bi-retract.
Proof. Suppose that X is a proper subshift of X andφ : X → Y is a code. We will construct a bi-continuing code φ : X → Y with a bi-retract such that φ| e X =φ. We divide the proof into three parts. In Part I, we construct an extension code in the case where X has the specification property. In Part II, we prove that the code constructed in Part I is bi-continuing with a bi-retract. In Part III, by using the results in Part I and II we prove the case where X is almost specified.
Part I. In this part, we prove the case where X has the specification property.
By Proposition 3.8, there exists a mixing shift of finite type Z 0 with h(Z 0 ) > h(Y ) in which all sufficiently long blocks are synchronizing for X. By Lemma 4.2, we can find a mixing shift of finite type Z 1 ⊂ Z 0 disjoint from X with h(Z 1 ) > h(Y ). Also by Lemma 4.1, there exist an irreducible shift of finite type Z ⊂ Z 1 and a biclosing factor code π : Z → Y . By Lemma 4.3, we can find a factor code ψ : X → Y such that ψ| Z = π and ψ| e X =φ. Finally find a mixing shift of finite type V ⊂ Z 1 disjoint from Z with h(V ) > h(Y ) by using Lemma 4.2.
By passing to higher block shifts, we can assume that (a) Z 0 , Z, V and Y are edge shifts, (b) A(Z) ∩ A( X) = ∅ and A(Z) ∩ A(V ) = ∅, (c) ψ is a 1-block code, (d) if a, b ∈ A(Z) and ab ∈ B(X), then ab ∈ B(Z), (e) each a ∈ A(Z 0 ) is a synchronizing word for X. Let D be the right and left closing delay of π [12]. Take N large such that N is a transition length for X, Y and a weak transition length for Z. Fix a synchronizing word α ∈ A(V ). Since X has the specification property, by Lemma 3.3 for each x ∈ X there exist w,w ∈ B N (X) such that x − wα ∈ X − and αwx + ∈ X + .
Fix i 3N . For each a ∈ A(X), b ∈ A(Z) and w ∈ B N (X), define . This is possible since N is a transition length for Y . These maps will be used as marker fillers.
For given x ∈ X, we divide x ∈ X into low and high-stretches as in [7]. Call a segment of x a low-stretch if it is a Z-word of length > 2N + D, and not preceded or followed by a symbol from A(Z), i.e., a maximal Z-word of length > 2N + D. Remaining stretches of maximal length are called high-stretches (of x). By the condition (d), low-stretches of x cannot overlap and hence x is uniquely decomposed as low and high-stretches. Also, if a high-stretch of x is of length greater than 2I, then it is called a long high-stretch. Otherwise, call it a short high-stretch. The figure below shows a typical decomposition of x.

Now we define a code
is the end of some long high-stretch and x [i+I,i+N +I) is the beginning of some low-stretch, then define v) low-high transition. Similarly as in (iv), using Ψ LH . The figure above describes the action of φ on parts of a point corresponding to some of these cases. Note that these cases cover all parts of x and φ is a well-defined code from X to Y . Indeed φ has memory and anticipation 2N + 2I + D. Since x ∈ Z consists of a single low-stretch and x ∈ X consists of a single high-stretch, we have φ| Z = π and φ| e X =φ and hence φ is a factor code which is an extension ofφ.
Part II.
We show that φ is bi-continuing with bi-retract n = 2I + 6N + 3D. Suppose x ∈ X, y ∈ Y satisfy φ(x) (−∞,0] = y (−∞,0] . Case 1. Suppose there exists an i ∈ [−n, −2N − D] such that x [i,i+2N +D] is part of a low-stretch. Then, since π is a right closing factor code, there exists a one-sided sequence z [i+N,∞) is a part of low-stretch ofx and therefore rule i) applies for k ≥ i + N and we have φ(x) = y. Proof. Let p = per(Z). Then there exists a partition {A 0 , A 1 , · · · , A p−1 } whose union is A(Z) with the property that whenever ab ∈ B(Z) and a ∈ A k , we have b ∈ A k+1(mod p) . Since Y is mixing and π : Z → Y is a factor code, for each k π| A k : and v [N +2,I−N ) ∈ B(V ). There exist d ∈ A(Z) and c ∈ A(Z 0 ) \ A(Z) such that cd ∈ B(X). If we takek with d ∈ Ak, then there exists b ∈ Ak such that π(b) = y i+I+N −1 . Since N is a weak transition length for Z, there exists a block u ∈ B N (Z) with u 1 = d and u N = b. As Z 0 is an edge shift containing Z, we have cu ∈ B(X). Since N is a transition length for X, we can find a block w ∈ B N (X) with vwcu ∈ B(X). Then vwcu ∈ HL I+N (a; w; b), which completes the proof.
Since Ψ a,b HL | HL I+N (a;w;b) is onto, there exists u [i,i+I+N ) ∈ HL I+N (a; w; b) with Ψ a,b HL (u) = y [i,i+I+N ) . Since u i+I+N −1 ∈ A(Z) and π is right closing, there exists Thenx ∈ X since α and u i+I+N −1 are synchronizing. Note thatx [−n+2N +D,i+I) is a part of long high-stretch andx [i+I,∞) is a low-stretch (our chosen blockx i = x i = a / ∈ A(Z) guarantees no occurrence of a Z-block of length greater than 2N + D in x [−n+2N +D,i+I) ). Therefore rules ii), iv) and i) apply tox [−n+2N +D+I,∞) and we have φ(x) = y. So φ is right continuing with retract n. Similarly φ is left continuing with retract n, which completes the proof when X has the specification property.
Part III.
We prove the general case where X is merely almost specified. Let {D 0 , D 1 , · · · , D p−1 } be the cyclic cover of X. Define Then Z is a proper subshift of X. By using Lemma 4.3, we may assume that Z is contained in X. Note that σ p | D 0 ∩ e X is (conjugate to) a shift space. Also σ p | D 0 has the specification property by Lemma 3.7. The codeφ naturally induces a codẽ ψ : (D 0 ∩ X, σ p ) → (Y, σ p ) by restriction. By applying Parts I and II, we have a σ p -commuting bi-continuing code ψ : (D 0 , σ p ) → (Y, σ p ) with a bi-retract such that ψ| D 0 ∩ e X =ψ. Define a code φ : X → Y as follows: Given x ∈ X, there exists 0 ≤ i < p with x ∈ D i . Then we let φ(x) = σ i ψ(σ −i (x)). If x ∈ D j for some j = i, then x ∈ Z ⊂ X and therefore Thus φ is well defined. These equalities also show that φ| e X =φ. Note that φ is continuous. It is easy to see that φ is indeed σ-commuting (hence a code) and bicontinuing with a bi-retract. By Lemma 2.1, φ is also an open code with a uniform lifting length.
Remark 4.6. Suppose X is assumed to be of finite type in Theorem 4.5. Then we can take Z 0 = X in Part I. Also Case 2 in Part II can be proved as easily as in Case 1 (since any word is synchronizing) and by using a usual reduction to the mixing case, Part III can be removed. Thus in this case the proof gives an alternative proof of bi-continuing version of Theorem 4.4 in which the definition of φ is much simpler. This is because by using the extension lemma, we need not consider the marker sets as in [7] and thus φ on low-high and high-low transitions can be defined more easily.

Lower entropy factor theorems
For a synchronized system X, fix a synchronized word w ∈ B(X). Let C n (X) be the set of words v ∈ B n (X) such that wvw ∈ B(X). Then a synchronized entropy h syn (X) is defined by This value is independent of w and h(X) ≥ h syn (X). In general h(X) = h syn (X). If X is almost specified, then by Proposition 3.8 and Theorem 3.2 of [16] we have h syn (X) = h(X). By using the cyclic cover of a synchronized system, Thomsen has given a generalization of the lower entropy factor theorem in [5] for the case where Y is merely an irreducible shift of finite type.
Theorem 5.1. [16] Let X be a synchronized system and Y an irreducible shift of finite type such that h syn (X) > h(Y ). Then Y is a factor of X if and only if the following hold: i) P (X) P (Y ). ii) If q = per(Y ) and {D 0 , D 1 , · · · , D p−1 } is the cyclic cover of X, then q|p and Note that when X is of finite type, then the condition (ii) is trivial. Using this result, we have our main theorem.
Theorem 5.2. Let X be an almost specified shift and Y an irreducible shift of finite type such that h(X) > h(Y ). Then the following are equivalent.
(1) Y is a factor of X by a bi-continuing code with a bi-retract.
(2) Y is a factor of X by an open code with a uniform lifting length.
(3) Y is a factor of X. If X is of finite type, then the above conditions are also equivalent to: (4) P (X) P (Y ).
Proof. j=0 D jq . Note that {C, σ(C), · · · , σ q−1 (C)} is a partition of X and (C, σ q ) is (conjugate to) a shift space. As in the proof of Lemma 3.7, it is easy to see that σ q | C is an almost specified shift. Since q = per(Y ), σ q | E 0 is a mixing shift of finite type. By Theorem 4.5, there exists a (σ q -commuting) code ψ : (C, σ q ) → (E 0 , σ q ) which is bi-continuing with a bi-retract. As usual, we can define a factor code φ : X → Y as follows: For x ∈ X, there exists a unique 0 ≤ i < q with x ∈ σ i (C). Define φ(x) = σ i ψ(σ −i (x)). It is easy to check that φ is a (σ-commuting) code and bi-continuing with a bi-retract. Thus (1) holds.
Finally, when X is of finite type, then by using a usual reduction to mixing case (cf. [12]), the problem can be reduced to Proposition 4.5. Thus (4) implies (1).
Remark 5.3. The equivalence of (1), (2) and (3) in Theorem 5.2 fails under the hypothesis of Theorem 5.1, that is, when X is a synchronized system and Y is an irreducible shift of finite type with h syn (X) > h(Y ).
For example, let X = X W and Y = X W 1 , where W = {ab k c k : k ≥ 0} and W 1 = {a, abc}. Note that X is a synchronized system and Y is an irreducible shift of finite type. Since Y is a proper subsystem of a mixing sofic shift X W 2 , where . Since Y has the unique fixed point a ∞ , we have P (X) P (Y ) and Y is a factor of X. We claim that there exists no right continuing code from X to Y . Indeed, if φ : X → Y is a code, then let x = b ∞ and y = a ∞ . · · · where y [0,∞) is right transitive. Then φ(x) and y are left asymptotic. But when z = b ∞ is left asymptotic to x, then z is in the orbit of b ∞ .c ∞ , so φ(z) must be of the form a ∞ · · · a ∞ , since a ∞ is the only fixed point in Y . Thus φ(z) = y and φ cannot be right continuing. By Lemma 2.1, φ cannot be open with a uniform lifting length.
As we have shown in Example 2.9 (1), there is an open code from X to Y . At this time, it is an open question whether there exists an open factor code from a synchronized system X to an irreducible shift of finite type Y if there is a factor code from X to Y . From Lemma 2.3 and Theorem 5.2, the following result is immediate. Let X and Y be synchronized systems with their cyclic covers {D 0 , D 1 , · · · , D p−1 } and {E 0 , E 1 , · · · , E q−1 }, respectively. If φ : X → Y is a code, then there exists an integer 0 ≤ j < q with φ(D 0 ) ⊂ E j since σ pq acts transitively on D i . So for a codeφ : X → Y from a proper subshift X of X to be extended to a code on X, a necessary condition is that there exists an integer 0 ≤ j < q with φ( X ∩ D 0 ) ⊂ E j .
When this holds, we say thatφ satisfies the cyclic condition for X. Note that if Y is mixing, then any code from a proper subshift of X to Y satisfies the cyclic condition for X.
The following extension theorem says that if the conditions in Theorem 5.2 hold, then the above cyclic condition is the only obstruction to extend a code defined on a proper subshift of X to a code from X to Y . It is this obstruction which is responsible for the failure of Theorem 4.4 and 4.5 when the target is not mixing.
Theorem 5.5. Let X be an almost specified shift and Y an irreducible shift of finite type such that h(X) > h(Y ) and Y is a factor of X. For a codeφ : X → Y defined on a proper subshift X of X, the following are equivalent.
(1)φ satisfies the cyclic condition for X.
(3) There is a factor code φ : X → Y with φ| e X =φ which is open with a uniform lifting length and which is bi-continuing with a bi-retract.
Proof. It is clear that (3) ⇒ (2) ⇒ (1). So assume (1) and let {E 0 , E 1 , · · · , E q−1 } be the cyclic cover of Y . Since Y is a factor of X, we have the two conditions in Theorem 5.1. Let C = p q −1 j=0 D jq . Then σ q | C is an almost specified shift. Let ψ be the restriction ofφ to C. Sinceφ satisfies the cyclic condition for X, there exists an element E j in the cyclic cover of Y withφ(D 0 ∩ X) ⊂ E j . Then we havẽ φ(C ∩ X) ⊂ E j . Note that σ q | E j is a mixing shift of finite type. By Theorem 4.5, we have a (σ q -commuting) code ψ : (C, σ q ) → (E j , σ q ) which is an extension ofψ and bi-continuing with a bi-retract. Remainder of the proof goes as in that in Theorem 5.2.
We remark that in [2], Barth and Dykstra considered related conditions in the case of reducible shifts of finite type using phase matrices.
Our last example shows that even when both shift spaces are of finite type, the cyclic condition is very crucial to extend a code defined on a proper subshift of the domain. In contrast to the existence theorems, extension theorems do not directly follow from the mixing case. Suppose φ : X → Y is a code with φ| e X =φ. Write X = D 0∪ D 1 where D 0 = {x ∈ X : x 0 = 1 or 2} and D 1 = σ(D 0 ). Then (13) ∞ , (24) ∞ ∈ D 0 . Since σ 2 | D 0 is irreducible, σ 2 | φ(D 0 ) is also irreducible, hence φ(D 0 ) must be a single point. This is a contradiction. Thusφ cannot be extended to a code on X.