17 April 1997 in Ergodic Theory and Dynamical Systems
We consider three related classifications of cellular automata: the first is based on the complexity of languages generated by clopen partitions of the state space, i.e. on the complexity of the factor subshifts; the second is based on the concept of equicontinuity and it is a modification of the classification introduced by Gilman [9]. The third one is based on the concept of attractors and it refines the classification introduced by Hurley [16]. We show relations between these classifications and give examples of cellular automata in the intersection classes. In particular, we show that every positively expansive cellular automaton is conjugate to a one-sided subshift of finite type and that every topologically transitive cellular automaton is sensitive to initial conditions. We also construct a cellular automaton with minimal quasi-attractor, whose basin has measure zero, answering a question raised in Hurley [16].
1 March 1997 in Theoretical Computer Science
1 April 1997 in Physica D: Nonlinear Phenomena
1 September 2000 in Journal of Statistical Physics
8 December 2006 in Nonlinearity
1 February 2010 in Mathematical Biosciences