zbMATH — the first resource for mathematics

Dynamical behaviour of Coven’s aperiodic cellular automata. (English) Zbl 0874.68220
Summary: We show that the aperiodic cellular automata studied by E. Coven[Proc. Am. Math. Soc. 78, 590-594 (1980; Zbl 0452.54038)], that is the maps \(F:\{0,1\}^{\mathbb{Z}}\rightarrow \{0,1\}^{\mathbb{Z}}\) induced by block maps \(f:\{0,1\}^{r+1}\rightarrow \{0,1\}\) such that \(f(x_{0},x_{1},\ldots,x_{r})\) is equal to \((x_{0}+1)\) mod 2 if \(x_{1}\ldots x_{r}=b_{1}\ldots b_{r}\) and equal to \(x_{0}\) otherwise, where \(B=b_{1}\ldots b_{r}\) is a given aperiodic word, have the following position in classification of P. K\Durka [Ergodic Theory Dyn. Syst. 17, No. 2, 417-433 (1997)] : they are regular, contain equicontinuous points without being equicontinuous, and are chain transitive but not topologically transitive. Therefore they do not have the shadowing property; this answers in the negative a question raised by P. K\Durka.

68Q80 Cellular automata (computational aspects)
Full Text: DOI
[1] Blanchard, F., Cellular automata and transducers: a topological view, () · Zbl 0797.58037
[2] Coven, E., Topological entropy of block maps, (), 590-594 · Zbl 0452.54038
[3] Coven, E.; Hedlund, G.A., Periods of some non-linear shift registers, J. combina. theory, A27, 186-197, (1979) · Zbl 0419.94007
[4] Gilman, R.H., Classes of linear automata, Ergodic theory. dynamical. systems, 7, 105-118, (1987) · Zbl 0588.68029
[5] Hedlund, G.A., Endomorphisms and automorphisms of the shift dynamical system, Math. systems theory, 3, 320-375, (1969) · Zbl 0182.56901
[6] Hopcroft, J.E.; Ullmann, J.D., Introduction to automata theory, languages and computation, (1990), Addison-Wesley, Reading, MA
[7] Hurley, M., Ergodic aspects of cellular automata, Ergodic theory dynamical systems, 10, 671-685, (1990)
[8] K…rka, P., Languages, equicontinuity and attractors in linear cellular automata, (1994), pre-print
[9] P. K…rka, private communication.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.