CORRIGENDUM

MIKE BOYLE AND ALEJANDRO MAASS

In our paper [BM], a part of the proof of Proposition 3.2 is incorrect. (The statement of Proposition 3.2 is correct.) The error in the proof is the claim that the follower set cover of a nonSFT sofic shift cannot be irreducible. A counterexample to the claim is the sofic shift presented by the labeled graph with adjacency matrix (\begin{matrix}a + b & c + d \\ b & a \end{matrix}). For this shift, the predecessor set cover is also irreducible. We thank Ulf Fiebig for pointing out our error and for providing the counterexample, which is part of a forthcoming work on the possible structures of Krieger covers [F].

The part of Proposition 3.2 which requires a correct proof is the claim that a sofic shift whose bilateral dimension group has rank one must be a shift of finite type. The application of this claim in [BM] is a special case of the subsequent decisive result of M. Nasu [N] that all expansive invertible onesided onedimensional cellular automata are shifts of finite type. Nevertheless, because Proposition 3.2 is of independent interest and because we want to maintain the unified framework of the proofs in [BM], we will give a correct proof of the claim here.

A word W is a synchronizing word, or Markov magic word, for a subshift if whenever there are points x and y in the subshift and a nonnegative integer n such that x[0, n] = y[0, n] = W, then the bisequence x(−∞, −1]W y[n + 1, +∞) is a point in the subshift. Every sofic shift contains synchronizing words [K, Observation 6.1.5]. Therefore the proof of Proposition 3.2 is repaired by the following proposition (which applies more generally to the large and interesting class of subshifts with a synchronizing word [BH, FF]).

Proposition Suppose S is a subshift with a synchronizing word and the group Bilat(S) has rank one. Then S is a shift of finite type.

Proof. We first present the group Bilat(S) = ℤCO(X)/K(S) of [BM] as a certain direct limit group G = lim G_{n}. Define an equivalence relation on S-words as follows: [W] = [W′] if the words W and W′ have equal length and for all words A and B, AW B is an S-word iff AW′B is an S-word. Given a positive integer n, let G_{n} be the free abelian group whose generating set is the set E_{n} of equivalence classes of S-words of length 2n + 1. Define the system of group homomorphisms π_{n,n+k}: G_{n} → G_{n+k} determined by [x_{−n}...x_{n}] ↦ ∑[ax_{−n}...x_{n}b], where the sum is over the pairs (a, b) such that a and b have length k and ax_{−n}...x_{n}b is an S-word. The group G is the direct limit group obtained from this system of homomorphisms, and Bilat(S) is isomorphic to G. The isomorphism is induced by the map which sends a cylinder set x[−n, n] to [x_{−n} ⋯ x_{n}] ∈ E_{n}.

Let W be a synchronizing word for S. Any word which has a synchronizing word as a

subword is also synchronizing, so we can take W of the form W = W_{−n} ⋯ W_{n}. Let W′ be

another S-word of length 2n + 1. Because G has rank one, there exist positive integers k, p, q

such that

pπ_{n,n+k}(W) = qπ_{n,n+k}(W′) .

In particular, if a′W′b′ is an S-word with a′, b′ of length k, then there is an S-word aW b with

[aW b] = [a′W′b′]; because aW b is synchronizing, it follows that a′W′b′ is synchronizing. The

length k can be chosen uniformly for all words W′ of length 2n + 1, and it follows that any

sufficiently long S-word is synchronizing. Therefore S is a shift of finite type. □

It is an open problem (3.4 in [BM]) as to whether the assumption in the proposition that

S have a synchronizing word can be dropped. A proof that the assumption can be dropped

would, together with [BM], give an alternate proof for the result of Nasu stated earlier.

References

[BH] F. Blanchard and G. Hansel, Systèmes codés, Theoret. Comput. Sci. 44 (1986), no. 1, 17–49.

[BM] M. Boyle and A. Maass, Expansive invertible onesided cellular automata, J. Math. Soc, Japan 52 (2000), no. 4, 725-740.

[F] U. Fiebig, personal communication (2001).

[FF] D. Fiebig and U. Fiebig, The automorphism group of a coded system, Trans. Amer. Math. Soc. 348 (1996), no. 8, 3173–3191.

[K] B. Kitchens, Symbolic Dynamics, One-sided, two-sided and countable state Markov shifts, Springer-Verlag, 1998.

[N] M. Nasu, The dynamics of expansive invertible onesided cellular automata, preprint, 2000.

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

   E-mail address: mmb@math.umd.edu

Departamento de Ingeniería Matemática, Universidad de Chile, Casilla 170/3 correo 3, Santiago, Chile.

   E-mail address: amaass@dim.uchile.cl