ERGODIC PROPERTIES OF CERTAIN SURJECTIVE CELLULAR AUTOMATA

We consider one-dimensional cellular automata, i.e. the maps T : P(Z) --> P(Z) (P is a finite wt with more than one element) which are given by (Tx)i = = F(x(i + l), ..., x(i + r)), x = (x(i)) (is-an-element-of Z) is-an-element-of P(Z) for some integers l less-than-or-equal-to r and a mapping F : P(r - l + 1) --> P. We prove that if F is right- (left-) permutative (in Hedlund's terminology) and 0 less-than-or-equal-to l 0 and T is surjective, then the natural extension of the system (P(Z), B, mu, T) is a K-automorphism. We also prove that the shift Z2-action on a two-dimensional subshift of finite type canonically associated with the cellular automaton T is mixing, if F is both right and left permutative. These results answer some questions raised in [SR]