×

zbMATH — the first resource for mathematics

Classes of linear automata. (English) Zbl 0588.68029
Let S be a finite set and X the set of all maps from the integers to S. The discrete topology on S determines a product topology on X. The successor map on the integers induces a shift homeomorphism of X to itself. A linear automaton (or one-dimensional cellular automaton) is a continuous self-map of X which commutes with the shift. Computer simulations suggest that linear automata may be divided into classes based on their dynamical behavior. This paper makes a division (based on the topological notions of equicontinuity and expansiveness) into three classes and shows the classes have distinct dynamical behavior. Also passing from an automaton to a certain kind of factor preserves the class of the automaton.

MSC:
68Q45 Formal languages and automata
68Q80 Cellular automata (computational aspects)
54H20 Topological dynamics (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Feller, An Introduction to Probability Theory and its Applications 1 (1950) · Zbl 0039.13201
[2] Farmer, Cellular Automata (1984)
[3] DOI: 10.1007/BF01705882 · Zbl 0191.21402 · doi:10.1007/BF01705882
[4] Adler, Mem. Amer. Math. Soc. 20 pp none– (1979)
[5] Furstenberg, Recurrence in Ergodic Theory and Combinatorial Number Theory (1981) · Zbl 0459.28023 · doi:10.1515/9781400855162
[6] DOI: 10.1007/BF01217347 · Zbl 0587.68050 · doi:10.1007/BF01217347
[7] Walters, An Introduction to Ergodic Theory (1982) · Zbl 0475.28009 · doi:10.1007/978-1-4612-5775-2
[8] DOI: 10.1007/BF01691062 · Zbl 0182.56901 · doi:10.1007/BF01691062
[9] Grassberger, Physica 10D pp 52– (1984)
[10] Wolfram, Physica 10D pp 1– (1984)
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.