×

zbMATH — the first resource for mathematics

Periodic points for onto cellular automata. (English) Zbl 1024.37007
Summary: Let \(\varphi\) be a one-dimensional surjective cellular automaton map. We prove that if \(\varphi\) is a closing map, then the configurations which are both spatially and temporally periodic are dense. (If \(\varphi\) is not a closing map, then we do not know whether the temporally periodic configurations must be dense.) The results are special cases of results for shifts of finite type, and the proofs use symbolic dynamical techniques.

MSC:
37B15 Dynamical aspects of cellular automata
37B10 Symbolic dynamics
54H20 Topological dynamics (MSC2010)
68Q80 Cellular automata (computational aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ashley, J., An extension theorem for closing maps of shifts of finite type, Trans. AMS, 336, 389-420, (1993) · Zbl 0839.54026
[2] Blanchard, F.; Maass, A., Dynamical properties of expansive one-sided cellular automata, Israel J. math., 99, 149-174, (1997) · Zbl 0892.58042
[3] Boyle, M.; Fiebig, D.; Fiebig, U., A dimension group for local homeomorphisms and endomorphisms of onesided shifts of finite type, J. reine angew. math., 497, 27-59, (1997) · Zbl 0877.58038
[4] Boyle, M.; Tuncel, S., Infinite-to-one codes and Markov measures, Trans. AMS, 285, 657-684, (1984) · Zbl 0515.28011
[5] Hedlund, G.A., Endomorphisms and automorphisms of the shift dynamical system, Math. systems th., 3, 320-375, (1969) · Zbl 0182.56901
[6] Kitchens, B., Expansive dynamics on zero dimensional groups, Ergod. th. & dynam. sys., 7, 249-261, (1987) · Zbl 0597.54039
[7] Kitchens, B., Symbolic dynamics, one-sided, two-sided and countable state Markov shifts, (1998), Springer-Verlag Newhaven CT · Zbl 0892.58020
[8] Kitchens, B.; Schmidt, K., Automorphisms of compact groups, Ergod. th. & dynam. sys., 9, 691-735, (1989) · Zbl 0709.54023
[9] Kurka, P., Languages, equicontinuity and attractors in cellular automota, Ergod. th. & dynam. sys., 17, 417-433, (1997) · Zbl 0876.68075
[10] Lind, D.; Marcus, B., Symbolic dynamics and coding, (1995), Cambridge University · Zbl 1106.37301
[11] Martin, O.; Odlyzko, A.; Wolfram, S., Algebraic properties of cellular automata, Comm. math. phys., 93, 219-258, (1984) · Zbl 0564.68038
[12] Nasu, M., Textile systems for endomorphisms and automorphisms of the shift, Mem. AMS, 546, (1995) · Zbl 0845.54031
[13] Maps in symbolic dynamics, ()
[14] Parry, W., Symbolic dynamics and transformations of the unit interval, Trans. amer. math. soc., 122, 368-378, (1966) · Zbl 0146.18604
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.