×

zbMATH — the first resource for mathematics

On the sofic limit sets of cellular automata. (English) Zbl 0864.58030
Summary: It is not known in general whether any mixing sofic system is the limit set of some one-dimensional cellular automaton. We address two aspects of this question. We prove first that any mixing almost of finite type (AFT) sofic system with a receptive fixed point is the limit set of a cellular automaton, under which it is attained in finite time. The AFT condition is not necessary: we also give examples of non-AFT sofic systems having the same properties. Finally, we show that near Markov sofic systems (a subclass of AFT sofic systems) cannot be obtained as limit sets of cellular automata at infinity.

MSC:
37B99 Topological dynamics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1007/BF01217347 · Zbl 0587.68050 · doi:10.1007/BF01217347
[2] DOI: 10.1007/BF01319913 · Zbl 0314.54043 · doi:10.1007/BF01319913
[3] Denker, Springer Lecture Notes in Mathematics pp 527– (1976)
[4] DOI: 10.1137/0218057 · Zbl 0691.68060 · doi:10.1137/0218057
[5] DOI: 10.1007/BF02757884 · Zbl 0307.28015 · doi:10.1007/BF02757884
[6] DOI: 10.1007/BF01762187 · Zbl 0309.54032 · doi:10.1007/BF01762187
[7] Boyle, Springer Lecture Notes in Mathematics 1342 pp 33– (1988)
[8] DOI: 10.2307/2045810 · Zbl 0606.28016 · doi:10.2307/2045810
[9] Boyle, Ergod. Th. & Dynam. Sys. 4 pp 541– (1984)
[10] DOI: 10.2307/2154352 · Zbl 0839.54026 · doi:10.2307/2154352
[11] Adler, Memoirs Amer. Math. Soc. 219 pp none– (1979)
[12] Von Neumann, Theory of Self-reproducing Automata (1966)
[13] DOI: 10.1109/TIT.1985.1057037 · Zbl 0568.94015 · doi:10.1109/TIT.1985.1057037
[14] Maass, Cellular Automata and Cooperative Systems pp 433– (1993) · doi:10.1007/978-94-011-1691-6_35
[15] Krieger, Ergod. Th. & Dynam. Sys. 2 pp 195– (1982)
[16] Hurd, Complex Systems 4 pp 119– (1990)
[17] Hurd, Complex Systems 1 pp 69– (1987)
[18] DOI: 10.1007/BF01691062 · Zbl 0182.56901 · doi:10.1007/BF01691062
[19] DOI: 10.1016/0304-3975(93)90350-3 · Zbl 0774.68085 · doi:10.1016/0304-3975(93)90350-3
[20] DOI: 10.1007/BF01295322 · Zbl 0285.28021 · doi:10.1007/BF01295322
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.