zbMATH — the first resource for mathematics

Languages, equicontinuity and attractors in cellular automata. (English) Zbl 0876.68075
Summary: 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 R. H. Gilman [ibid. 7, 105-118 (1987; Zbl 0588.68029)]. The third one is based on the concept of attractors and it refines the classification introduced by M. Hurley [\((*)\) ibid. 10, No. 1, 131-140 (1990; Zbl 0666.58029)]. 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 \((*)\).

37B15 Dynamical aspects of cellular automata
68Q80 Cellular automata (computational aspects)
Full Text: DOI