SOME SOFIC SHIFTS CANNOT COMMUTE WITH NONWANDERING SHIFTS OF FINITE TYPE

MIKE BOYLE

Abstract. Suppose S is a nonwandering shift of finite type (SFT), and T is an expansive automorphism of S. We show T cannot be a strictly sofic almost Markov shift. Also included is an example of D. Fiebig, a reducible SFT with an expansive automorphism which is not SFT.

1. Introduction

In his 1995 memoir [19], Masakazu Nasu asked if an expansive automorphism of a shift of finite type must be a shift of finite type ([19, p.33, Question 2.a]). As already announced in [3], Doris Fiebig produced a counterexample in the case that the shift of finite type is allowed to be reducible. Her example is included in the Appendix.

The irreducible case of Nasu’s question remains a major open problem for understanding the dynamics of automorphisms of shifts of finite type and the related ℤ^{d} actions. There has been excellent progress on related questions involving positively expansive maps or onesided shifts of finite type [3, 7, 19, 20, 21]; however, since D. Fiebig’s counterexample, there have been no results on Nasu’s original question, despite considerable efforts.

In this paper, we will at least resolve a meaningful case of Nasu’s question. We will prove that an expansive automorphism of a nonwandering shift of finite type cannot be conjugate to an almost Markov strictly sofic shift. In the example of D. Fiebig, the expansive automorphism of the reducible shift of finite type is almost Markov (Remark A.4), and the reducible shift of finite type is wandering. The two results together highlight the importance of the irreducibility condition, or more precisely the condition that the SFT be nonwandering (Remark 3.4).

I thank the anonymous referee for a useful report.

2000 Mathematics Subject Classification. Primary: 37B10; Secondary: 37B15, 37B50.

Key words and phrases. expansive, shift of finite type, Markov, sofic, Z^{2} action, automorphism.

2. Definitions and background

We will be concerned with certain selfhomeomorphisms of compact metric spaces. The particular choice of metric compatible with the topology will be of no importance in this paper. For a lighter notation, we will generally use the same symbol (e.g., S) for both the homeomorphism and its domain; the correct interpretation should be clear in context.

Such a homeomorphism S is expansive if there exists ε > 0 such that for all distinct x and y in S, there exists n ∈ ℤ such that dist(S^{n}x, S^{n}y) > ε. Such an ε is called an expansive constant for S. Expansiveness is a multifaceted condition of considerable importance in dynamics; see the brief discussion in [6, Section 5], its references, and also [1].

Next we recall some elementary symbolic dynamics; see [15] or [13] for a thorough introduction. We regard {0, 1, …, n − 1}^{ℤ} as the space of doubly infinite sequences x = … x_{−1}x_{0}x_{1} …. The full shift on n symbols is the map on this space which sends x to the bisequence y such that y_{n} = x_{n+1} for all n. The restriction of such a map to a closed, shift-invariant subset is a subshift. A subshift S is a shift of finite type (SFT) if there exists a finite set W of (finite) words such that the space S consists of all sequences on {0, 1, …, n − 1}^{ℤ} in which words from W never occur. An SFT S is 1-step if for all x, y in S, if z is a bisequence such that z_{i} = x_{i} for i ≤ 0 and z_{i} = y_{i} for i ≥ 0, then z ∈ S.

A block code is a map φ between subshifts such that there exists N such that for all x in the domain the word x[−N, N] determines the symbol (φx)_{0}. Here φ is a one-block code if it is possible to choose N = 0. The homomorphisms of subshifts (continuous maps between subshifts intertwining the shift actions) are precisely the block codes. A sofic shift is a subshift which is the image of an SFT under a block code.

We will say a subshift is irreducible if it has a dense forward orbit. An irreducible SFT can be presented by an irreducible matrix with nonnegative integer entries with a standard construction [13, 15]. An irreducible sofic shift is the image of an irreducible SFT under a block code.

A block code is left closing if it never collapses distinct forwardly asymptotic points; it is right closing if it never collapses distinct backwardly asymptotic points; and it is biclosing if it is both left and right closing. A sofic shift is almost Markov if it is the image of a SFT under a biclosing map [5]. An irreducible almost Markov sofic shift is called almost finite type (AFT) [16]. The AFT shifts are a natural and large class of relatively well behaved sofic shifts (see e.g. [16, 4, 27, 11, 25] and [15, Sec. 13.1]), and their study leads to the study of general almost Markov shifts [5]. For a homeomorphism S, whether S has one of the following properties does not change under passage to a power S^{n}: SFT; sofic; strictly sofic; almost Markov.

By a ℤ^{d} action α we will mean an action of ℤ^{d} by homeomorphisms on a compact metric space, and for n ∈ ℤ^{d} we let α_{n} denote the homeomorphism by which n acts. One approach to the study of ℤ^{d} actions is to impose some condition on a single homeomorphism α_{n} in the action. Two such conditions are the Markov condition (in the zero-dimensional case, α_{n} is Markov iff it is SFT) and expansiveness. An expansive component of vectors for a given ℤ^{d} action is a maximal connected open set U of ℝ^{d} such that tU = U for t > 0 and α_{m} is expansive if n ∈ U [6]. (Expansive components are descendants of the causal cones of Milnor [17]. The “Weyl chambers” of Katok and Spatzier [12] are important examples of expansive components; in that smooth setting, expansiveness arises from hyperbolicity.) For n within an expansive component, quantitative properties of α_{n} vary nicely, and qualitative properties of α_{n} (such as the Markov property) tend to hold for all or for no α_{n} in an expansive component [6, 9, 12]). However, outside a smooth or algebraic setting, it is not clear what kind of relation must hold between actions in different expansive components. The first problem here, already isolated by Nasu [19] and still unsolved, is to understand when expansive Markov and nonMarkov actions can coexist (necessarily in different expansive components) within the same ℤ^{2} action.

Two homeomorphisms S and T are topologically conjugate, or isomorphic, if there is a homeomorphism φ such that φS = T φ. Here if S = T then we may call φ an automorphism of S. (Caveat: Our interest is in dynamically invariant properties. So, in a phrase like “S is SFT”, the word “is” may mean “is topologically conjugate to some”.)

3. Recurrence conditions

Let S be a selfhomeomorphism of a metric space. For x, y in S, an ε-chain from x to y is a finite sequence of points x_{0}, x_{1}, …, x_{n} such that x = x_{0}, y = x_{n} and dist((Sx)_{i}, x_{i+1}) < ε for 0 ≤ i < n. S is chain recurrent if for all x and all ε > 0 there exists an ε-chain from x to x. S is chain transitive if for all x, y and all ε > 0 there exists an ε-chain from x to y. (Chain recurrence and chain transitivity are significant concepts for dynamical systems [23].) A point x is a wandering point (for S) if it has a neighborhood U such that U ∩ S^{n}U is empty for all n > 0. S is nonwandering if it has no wandering point. A closed open set is nontrivial if both it and its complement are nonempty. A subshift S is indecomposable if there is no nontrivial closed open set B such that SB = B. For any property P, we say that S is totally P if S^{n} is P for all n > 0.

Given a subshift S, we define its nth Markov approximation to be the subshift S_{n} on all sequences x such that for all i, the word x[i, i + n − 1] is an S-word (i.e. a word occurring in some point of S). The SFTs S_{n} form a decreasing sequence with intersection S.

Proposition 3.1. Suppose S is a shift of finite type. Then the following are equivalent.

(1) S is nonwandering.

(2) S is chain recurrent.

(3) S has periodic points dense.

(4) S is a disjoint union of finitely many irreducible SFTs.

Proposition 3.2. Suppose S is a subshift.

(1) S is chain recurrent if and only if every S_{n} is a nonwandering SFT.

(2) S is chain transitive if and only if every S_{n} is an irreducible SFT.

(3) S is totally chain transitive if and only if every S_{n} is a mixing SFT.

(4) When S is chain recurrent: S is totally chain transitive if and only if it is totally indecomposable.

Proposition 3.3. Suppose S is a sofic shift. Then the following are equivalent.

(1) S is the image of a nonwandering SFT.

(2) S has periodic points dense.

(3) S is nonwandering.

Proof. We will prove (3) ⟹ (1) in Proposition 3.3 and leave the other proofs of the propositions above to the reader. Suppose S is sofic nonwandering. Let π : T → S be a bounded-to-one block code from an SFT T onto S. Let W denote the set of nonwandering points in T: this is the nonwandering SFT which is the closure of the periodic points of T. If π maps W onto S, we are done, so suppose y ∈ S \ πW. Let x_{1}, …, x_{m} denote the preimages of y in T: all of them are wandering points for T. Let U_{i} be an open neighborhood of x_{i} with disjoint forward images. Pick N such that T^{k}U_{i} ∩ U_{j} = ∅ for k > N and 1 ≤ i, j ≤ m. Then shrink the U_{i} sufficiently that in addition we have T^{k}U_{i} ∩ U_{j} = ∅ for 1 ≤ k ≤ N and 1 ≤ i, j ≤ m. Let E be the complement of ∪_{i=1}^{m}U_{i}. Then the complement of πE is a neighborhood of y which never returns to itself, and therefore y is wandering, which is a contradiction. □

Remark 3.4. A wandering sofic shift can be chain recurrent, and even totally chain transitive (for an example see Remark A.4). Also, it is easy to see the following are equivalent:

(1) Every expansive automorphism of a nonwandering SFT is SFT.

(2) Every expansive automorphism of an irreducible SFT is SFT. For (2) ⟹ (1), suppose S is an expansive automorphism of a nonwandering shift of finite type T. Then T is the disjoint union of irreducible SFTs T_{(i)} which are permuted by S, and for some n > 0, S^{n} fixes each T_{(i)}. The assumption (1) then implies that S^{n} is a disjoint union of SFTs, hence S^{n} is SFT. Therefore S is SFT.

4. Indecomposable automorphisms

We begin by recalling a little ergodic theory. For an automorphism S of a Lebesque probability space, with invariant measure μ and generating partition P, the Pinsker algebra of (S, μ) is the σ-algebra

𝔓(S, μ) = 𝔑 ∨ ( ∩_{n∈ℕ} 𝔓(S, n)) = 𝔑 ∨ ( ∩_{n∈ℕ} 𝔓(S, −n))

where 𝔑 is the σ-algebra of μ-null sets and

𝔓(S, n) = ∨_{i=n}^{∞}S^{−i}P .

For any finite partition Q, h(S, μ, Q) = 0 if and only if the elements of Q are contained in the Pinsker algebra [24, 26]. (In particular, 𝔓(S, μ) does not depend on the particular choice of generating partition P.) The system (S, μ) is a K-automorphism if it has a trivial Pinsker algebra; equivalently, for any partition B of X into two sets of positive measure, h(S, μ, B) > 0.

The next lemma assumes some familiarity with expansive subdynamics [6].

Lemma 4.1. Let α be a ℤ^{2} action on a zero dimensional compact metric space X. Suppose m, n are nonzero elements of ℤ^{2} such that the homeomorphisms α_{m} and α_{n} are expansive, with m and n lying in the same connected component of expansive 1-frames. Suppose μ is a Borel probability which is invariant for both α_{m} and α_{n}.

Then the Pinsker algebras 𝔓(α_{m}, μ) and 𝔓(α_{n}, μ) are equal.

Proof. Let P be a partition of X into closed open sets with diameters smaller than expansive constants for α_{m} and α_{n}. The proof of Proposition 8.1(3) in [6] includes the result that given a > 0 there is a c > 0 such that “([a, ∞)n)^{t} codes ([c, ∞)m)^{t}.” In the zero dimensional case, the last statement translates to “𝔓(α_{n}, a) refines 𝔓(α_{m}, c)”. Taking intersections, we conclude that the Pinsker algebra 𝔓(α_{n}, μ) refines 𝔓(α_{m}, μ). Similarly, the Pinsker algebra 𝔓(α_{m}, μ) refines 𝔓(α_{n}, μ). □

Proposition 4.2. Suppose S and T are commuting expansive homeomorphisms of a zero dimensional compact metric space X; μ is a Borel probability which is both S and T invariant; μ is nonzero on nonempty open sets; and (T, μ) is a K- automorphism.

Then S is totally indecomposable.

Proof. We suppose there is a nontrivial closed open set B and some n > 0 such that S^{n}B = B, and argue to a contradiction. Without loss of generality, we suppose n = 1.

Let B be the partition {B, B′}. Let α be the ℤ^{2} action generated by S and T, with α_{(1,0)} = T and α_{(0,1)} = S. Expansiveness of α_{v} is an open condition on v depending only on the line ℝv; so for sufficiently large k, the map α_{(1,k)} = T S^{k} is expansive, and also (1, k) and (0, 1) lie in the same connected component of expansive 1-frames (vectors) [6]. Choose such a k > 0 and set S′ = T S^{k}.

Without loss of generality, suppose that all elements of the time zero partition P have diameter smaller than expansive constants for S and S′, and also that B is a union of elements of P. Because B is S-invariant, it holds for all x and i that (T S^{k})^{i}x ∈ B if and only if T^{i}x ∈ B. So, for all n, ∨_{i=0}^{n}(T S^{k})^{i}B = ∨_{i=0}^{n}T^{i}B. Therefore

h(S′, μ, B) = h(T, μ, B) > 0

where the last inequality holds because (T, μ) is a K-automorphism.

On the other hand, h(S, μ, B) = 0. Therefore B is μ-measurable with respect to the Pinsker algebra of (S, μ). It follows from Lemma 4.1 that (S, μ) and (S′, μ) have the same Pinsker algebra. Therefore h(S′, μ, B) = 0. This contradiction concludes the proof. □

Corollary 4.3. Suppose S is an expansive automorphism of a mixing sofic shift T. Then S is totally chain transitive.

Proof. For every n, the set of T -periodic points of period n is finite, and S (as an automorphism of T) maps that finite set onto itself. So, every T -periodic point is an S-periodic point. Since T has dense periodic points, so does S, and S is chain recurrent.

As an automorphism of T, S respects the unique measure of maximal entropy μ of T, so μ is both S and T invariant. When T is a mixing SFT, this (T, μ) is well known to be a K automorphism [26, Theorem 4.35] (and in fact Bernoulli). This still holds for T mixing sofic, since T is a quotient of some mixing SFT by a map which is a measurable conjugacy with respect to the measures of maximal entropy.

By Proposition 4.2, S is totally indecomposable. Because the subshift S is also chain recurrent, S is totally chain transitive. □

5. Ruling out AFT automorphisms

There are variants on the definition of “right resolving”. In this paper, we will use the following.

Definition 5.1. A right resolving map π : S → T is a surjective one-block code between subshifts such that for all w, x in S the following holds: if w_{0} = x_{0} and (πw)_{1} = (πx)_{1}, then w_{1} = x_{1}.

In the next lemma we adapt a construction of Kitchens [13, Proposition 4.3.3] to the general subshift setting.

Lemma 5.2. Suppose π : S → T is a right closing block code. Then there is a conjugacy of subshifts γ : S′ → S such that πγ : S′ → T is a right resolving code.

Proof. Without loss of generality suppose π is a one-block code. By a compactness argument, there exists N > 0 with the following property: for all x and w in S, if (πw)[−N, N] = (πx)[−N, N] and w[−N, 0] = x[−N, 0], then w_{1} = x_{1}. Define a new alphabet A as follows. An element of A is an equivalence class of S-words x[−N, N], where x[−N, N] ∼ w[−N, N] if (i) x[−N, 0] = w[−N, 0] and also (ii) the words x[1, N] and w[1, N] have the same image T -word under the one-block code π. Define S′ as the image of a block code ψ with domain S, where (ψx)_{0} is defined to be the element of A which contains x[−N, N]. Clearly ψ is injective and therefore defines a conjugacy.

Next consider the map ρ from S′ to the (2N + 1)-block presentation T′ of T, where ρ is the one-block code such that for all a in S′, (ρa)_{0} is the word which is the π image of the words x[−N, N] in the equivalence class a_{0}. By choice of N, the map ρ is right resolving. Let φ be the one-block code from T′ to T such that, when y ∈ T′ and y_{0} is a T -word z[−N, N], then (φy)_{0} = z_{N}. The map φ is right resolving and therefore so is the composition φρ. We see that T^{N}π = φρψ. Because all the block codes commute with the shift, we have πS^{N} = φρψ, so πS^{N}ψ^{−1} is right resolving. Let γ = S^{N}ψ^{−1}. □

Proposition 5.3. Suppose π : S → T is a right closing block code from a chain transitive subshift S onto a shift of finite type T.

Then S is an irreducible SFT.

Proof. This result is known by two proofs in the case that S is an irreducible sofic shift [8, Prop. 4.12]. The proof of Kitchens [8, pp.40-41] generalizes nicely to the chain transitive case. We include details for completeness.

Without loss of generality, we suppose T is a one-step SFT. Then by Lemma 5.2, also without loss of generality we suppose π is a right resolving one-block code. Because S is chain transitive, the 1-Markov approximation S_{1} to S is an irreducible SFT containing S. Because T is 1-step SFT, the surjective resolving one-block code π : S → T extends to a surjective resolving oneblock code π_{1} : S_{1} → T. Now, h(S) = h(T) = h(S_{1}) because resolving maps are finite to one and therefore respect topological entropy. As is well known (e.g. [15, Cor. 4.4.9] or [13, p.120]), an irreducible SFT contains no proper subsystem of equal entropy . Therefore S_{1} = S, and S is SFT. □

Lemma 5.4. Suppose S and T are commuting homeomorphisms, S is a mixing SFT and T is sofic. Then T is mixing.

Proof. T is the quotient of some SFT T̃ by some map π which is finite to one. Preimages of T -periodic points are therefore T̃-periodic. T has dense periodic points (because for each n the finite set of points in S-orbits of size n is permuted by T, and S has dense periodic points). Therefore T is the image of the nonwandering SFT which is the closure of the periodic points in T̃. So, without loss of generality suppose T̃ is the disjoint union of irreducible SFTs T_{1}, …, T_{k}. Also suppose without loss of generality that the collection of T_{i} is minimal, i.e. the image of any proper subcollection of these irreducible components is not all of T. Let T_{i} be the image under π of T̃_{i}.

Each T_{i} is a maximal subsystem of T for the property of having a dense orbit, and there are no other such subsystems, because any orbit is contained in some T_{i}. Therefore S, as an automorphism of T, permutes the T_{i}. Choose j such that S^{j} fixes each of the sets T_{i}. By the minimality condition, each of the S^{j}-invariant sets T_{i} must contain a nonempty open set not contained in the union of the other T_{j}. If k > 1, then there is a nonempty nondense open set invariant under the mixing map S^{j}, which is impossible. Therefore k = 1. If necessary after replacing T̃_{1} with the Fisher cover of T_{1}, we may suppose that the period p of the irreducible SFT T̃_{i} is smallest possible, and π : T̃_{1} → T_{1} is one to one a.e. Then we must have p = 1, for otherwise T_{i}^{p} would be the union of p mixing sofic shifts, each containing a nonempty open set not contained in the union of the others, and we would have a contradiction as before. □

Theorem 5.5. Suppose S and T are commuting homeomorphisms and S is a nonwandering shift of finite type. Then T cannot be a strictly sofic almost Markov shift.

Proof. We suppose T is strictly sofic almost Markov, and argue to a contradiction.

As a nonwandering SFT, S is a disjoint union of irreducible SFTs. For some k, S^{k} is then a disjoint union of mixing SFTs. Because T is an automorphism of S^{k}, it must permute these mixing SFTs. For some j, T^{j} fixes each of them. The restriction of T^{j} to at least one of them must be strictly sofic and almost Markov. So it suffices to obtain a contradiction under the additional condition that the shift of finite type S is mixing.

Because T is a sofic automorphism of the mixing SFT S, by Lemma 5.4 T is mixing. Let T′ be the canonical mixing SFT cover of the mixing strictly sofic almost Markov shift T, and let π : T′ → T be the covering map. Then S lifts by π to a unique automorphism S′ of T′ ([14] or [4]).

The map π : T′ → T is biclosing, so there exists ε > 0 such that dist(x, w) > ε whenever x ≠ w and πx = πw. Also, because S is expansive, points in different fibers of π are uniformly separated under the action of S′. It follows that S′ is expansive.

Because S′ is an expansive automorphism of the mixing SFT T′, by Corollary 4.3 S′ is totally chain transitive. Because preimage points under π are uniformly separated, the map π : S′ → S is biclosing, and in particular right closing. If follows from Lemma 5.2 that S′ is an irreducible SFT.

We now have a biclosing map of mixing SFTs, π : S′ → S. Nasu proved that such a map must be constant-to-one ([18] or [13, Proposition 3.4.4]). However, π is generically one-to-one by construction as the canonical irreducible cover π : T′ → T, and it is not everywhere one-to-one because T is strictly sofic. This gives the required contradiction and finishes the proof. □

Appendix A. The reducible example of Doris Fiebig

In this appendix we give an example of Doris Fiebig [10]: a twosided reducible SFT S, and an expansive automorphism T of S, with T not SFT. More precisely, there are two examples: a very simple one, and a modification to achieve positive entropy.

Example A.1. [10] S is defined as the union of four orbits: two fixed points, 0^{∞} and 3^{∞}, and two connecting orbits, 0^{∞}23^{∞} and 0^{∞}2′3^{∞}. The automorphism T just shifts the orbit 0^{∞}23^{∞} one step to the left, and the orbit 0^{∞}2′3^{∞} one step to the right. This is a bijective block code, thus T is an automorphism of S. T is expansive, since for any point x in S the bisequence (T^{n}x)_{0}, n ∈ ℤ, yields enough information to determine the point x.

T is not SFT. To see this we recode T to a subshift using the S-symbols as partition. Then the S-point x = 0^{∞}23^{∞} becomes 0^{∞}23^{∞} and the S-point y = 0^{∞}2′3^{∞} becomes 3^{∞}2′0^{∞}. So, in the recoding, for all n > 0 we see words 23^{n} and 3^{n}2′, but the word 23^{n}2′ does not occur. Therefore T is not SFT.

Example A.2. [10] To get a positive entropy example, consider the one-step SFT S on symbols {0, 1, 2, 2′, 3, 4} with exactly the following allowed transitions: elements of {0, 1} can be followed by elements of {0, 1, 2, 2′}; and elements of {2, 2′, 3, 4} can be followed by elements of {3, 4}. Then there is an automorphism U of S which shifts the symbol 2 two steps to the left and the symbol 2′ two steps to the right, that is: U maps ab2 → 2a′b′ and 2′a′b′ → ab2′, where (a, a′), (b, b′) ∈ {(0, 3), (1, 4)}. Otherwise, U fixes all symbols. Let T = SU.

T is expansive since on points without the symbols 2 and 2′, T is just the shift S and on the points with the symbol 2, the 2 goes in steps of size 3 to the left and on points with the symbol 2′, the 2′ goes 1 step to the right. Thus we can recover any point x from the sequence (T^{n}x)[−1, 1], n ∈ ℤ.

T is not a SFT. Consider the S-points x = 0^{∞}23^{∞} and y = 0^{∞}2′3^{∞}. Let A = 0^{3}, B = 0^{3}. Then the bisequence ((T^{n}x)[−1, 1])_{n}, n ∈ ℤ, is of the form A^{∞}(023)B^{∞}, and ((T^{n}y)[−1, 1])_{n}, n ∈ ℤ, is of the form B^{∞}(2′33)(02′3)(002′)A^{∞}, but for all n > 0 there is no point z having in its sequence ((T^{n}z)[−1, 1])_{n}, n ∈ ℤ, a subblock (002′)A^{n}(023). This proves T is not a SFT.

Remark A.3. Example A.1 can also be modified to have positive entropy by replacing the pair S, T with S × R, T × R, where R is a shift of finite type of positive entropy.

Remark A.4. In Example A.1, the nonSFT expansive automorphism T is totally chain transitive; as the union of two SFTs, it is also an almost Markov sofic shift. Thus a totally chain transitive strictly sofic almost Markov shift T can commute with a shift of finite type S (but only when both S and T are wandering).

References

[1] N. Aoki and K. Hiraide, Topological theory of dynamical systems, North-Holland (1994).

[2] R. Adler and B. Marcus, Topological entropy and equivalence of dynamical systems, Memoirs Amer. Math. Soc. 20 (1979), no. 219.

[3] M. Boyle, D. Fiebig and U. Fiebig, A dimension group for local homeomorphisms and endomorphisms of onesided shifts of finite type, J. Reine Angew. Math. 487 (1997), 27-59.

[4] M. Boyle, B. Kitchens and B. Marcus, A note on minimal covers for sofic systems, Proc. AMS 95 (1985), 403-411.

[5] M. Boyle and W. Krieger, Almost Markov and shift equivalent sofic systems, in Springer Lec. Notes in Math 1342 (1988), 33-93.

[6] M. Boyle and D. Lind, Expansive subdynamics, Trans. Amer. Math. Soc. 349 (1997), no. 1, 55–102.

[7] M. Boyle and A. Maass, Expansive invertible onesided cellular automata. J. Math. Soc. Japan 52 (2000), no. 4, 725–740; Erratum, J. Math. Soc. Japan 55 (2003), no. 4, 1137–1138.

[8] M.Boyle, B. Marcus and P. Trow, Resolving Maps and the Dimension Group for Shifts of Finite Type, Memoirs Amer. Math. Soc. 377 (1987).

[9] M. Einsiedler, D. Lind, R. Miles and T. Ward, Expansive subdynamics for algebraic ℤ^{d}-actions, Ergodic Theory Dynam. Systems 21 (2001), no. 6, 1695–1729.

[10] D. Fiebig, Personal communication (1996).

[11] R. Karabed and B.H.Marcus, Sliding-block coding for input-restricted channels, IEEE Trans. Inform. Theory 34 (1988), 2-26.

[12] A. Katok and R. Spatzier, Invariant measures for higher rank hyperbolic abelian actions, Ergodic Theory Dynam. Systems 16 (1996), no. 4, 751-778; corrections Ergodic Theory Dynam. Systems 18 (1998), no. 2, 503-507.

[13] B.P. Kitchens, Symbolic dynamics. One-sided, two-sided and countable state Markov shifts, Springer-Verlag (1998).

[14] W. Krieger, On sofic systems I, Israel J. Math 48 (1984), 305-330.

[15] D. Lind and B. Marcus, An introduction to Symbolic Dynamics and Coding, Cambridge University Press (1995).

[16] B. Marcus, Sofic systems and encoding data, IEEE-IT 31 (1985), 366-377.

[17] J. Milnor, On the entropy geometry of cellular automata, Complex Systems 2 (1988), no. 3, 357–385.

[18] M. Nasu, Constant-to-one and onto global maps of homomorphisms between strongly connected graphs, Ergodic Theory Dynam. Systems 3 (1983), 387-413.

[19] M. Nasu, Textile systems for endomorphisms and automorphisms of the shift. Memoirs Amer. Math. Soc. 114 (1995), no. 546.

[20] M. Nasu, The dynamics of expansive invertible onesided cellular automata, Trans. Amer. Math. Soc. 354 (2002), 4067-4084.

[21] M. Nasu, Nondegenerate q-biresolving textile systems and expansive automorphisms of onesided full shifts, Trans. Amer. Math. Soc., to appear.

[22] W. Parry, Entropy and generators in ergodic theory, W.A. Benjamin (1969).

[23] C. Robinson, Dynamical Systems, CRC Press (1995).

[24] D. Rudolph, Fundamentals of measurable dynamics, Oxford University Press (1990).

[25] P. Trow and S. Williams, Core dimension group constraints for factors of sofic shifts, Ergodic Theory Dynam. Systems 13 (1993), 213-224.

[26] P. Walters, An introduction to ergodic theory, Springer-Verlag (1982).

[27] S. Williams, Covers of non-almost-finite type sofic systems. Proc. Amer. Math. Soc. 104 (1988), 245–252.

Mike Boyle, Department of Mathematics, University of Maryland, College Park, MD 20742-4015, U.S.A.

E-mail address: mmb@math.umd.edu
URL: www.math.umd.edu/∼mmb