Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-28T11:29:40.852Z Has data issue: false hasContentIssue false
  • English
  • Français

Limit sets of stable cellular automata

Published online by Cambridge University Press:  09 October 2013

ALEXIS BALLIER
ALEXIS BALLIER*
Affiliation:
Centro de Modelamiento Matemático, Av. Blanco Encalada 2120, Santiago, Chile email [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study limit sets of stable cellular automata from a symbolic dynamics point of view, where they are a special case of sofic shifts admitting a steady epimorphism. We prove that there exists a right-closing almost-everywhere steady factor map from one irreducible sofic shift onto another one if and only if there exists such a map from the domain onto the minimal right-resolving cover of the image. We define right-continuing almost-everywhere steady maps, and prove that there exists such a steady map between two sofic shifts if and only if there exists a factor map from the domain onto the minimal right-resolving cover of the image. To translate this into terms of cellular automata, a sofic shift can be the limit set of a stable cellular automaton with a right-closing almost-everywhere dynamics onto its limit set if and only if it is the factor of a full shift and there exists a right-closing almost-everywhere factor map from the sofic shift onto its minimal right-resolving cover. A sofic shift can be the limit set of a stable cellular automaton reaching its limit set with a right-continuing almost-everywhere factor map if and only if it is the factor of a full shift and there exists a factor map from the sofic shift onto its minimal right-resolving cover. Finally, as a consequence of the previous results, we provide a characterization of the almost of finite type shifts (AFT) in terms of a property of steady maps that have them as range.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 35 , Issue 3 , May 2015 , pp. 673 - 690
Copyright
© Cambridge University Press, 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ashley, J.. Resolving factor maps for shifts of finite type with equal entropy. Ergod. Th. & Dynam. Sys. 11 (2) (1991), 219–240.CrossRefGoogle Scholar
Ashley, J.. An extension theorem for closing maps of shifts of finite type. Trans. Amer. Math. Soc. 336 (1993), 389–420.Google Scholar
Ballier, A., Guillon, P. and Kari, J.. Limit sets of stable and unstable cellular automata. Fund. Inform. 110 (2011), 45–57.Google Scholar
Barth, J. and Dykstra, A.. Weak equivalence for shifts of finite type. Indag. Math. 18 (4) (2007), 495–506.Google Scholar
Boyle, M.. Lower entropy factors of sofic systems. Ergod. Th. & Dynam. Sys. 4 (1984), 541–557.Google Scholar
Boyle, M.. Putnam’s resolving maps in dimension zero. Ergod. Th. & Dynam. Sys. 25 (2005), 1485–1502.Google Scholar
Boyle, M.. Open problems in symbolic dynamics. Contemp. Math. 469 (2008), 69–118.Google Scholar
Boyle, M., Kitchens, B. and Marcus, B.. A note on minimal covers for sofic systems. Proc. Amer. Math. Soc. 95 (3) (1985), 403–411.Google Scholar
Boyle, M., Marcus, B. and Trow, P.. Resolving maps and the dimension group for shifts of finite type. Mem. Amer. Math. Soc. 70 (377) (1987).Google Scholar
Boyle, M. and Tuncel, S.. Infinite-to-one codes and markov measures. Trans. Amer. Math. Soc. 285 (2) (1984), 657–684.Google Scholar
Fischer, R.. Sofic systems and graphs. Monatsh. Math. 80 (3) (1975), 179–186.Google Scholar
Hedlund, G. A.. Endomorphisms and automorphisms of the shift dynamical systems. Math. Syst. Theory 3 (4) (1969), 320–375.Google Scholar
Jung, U.. On the existence of open and bi-continuing codes. Trans. Amer. Math. Soc. 363 (3) (2011), 1399–1417.CrossRefGoogle Scholar
Lind, D. A. and Marcus, B.. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, New York, NY, USA, 1995.CrossRefGoogle Scholar
Maass, A.. On the sofic limit sets of cellular automata. Ergod. Th. & Dynam. Sys. 15 (1995), 663–684.CrossRefGoogle Scholar
Marcus, B.. Sofic systems and encoding data. IEEE Trans. Inform. Theory 31 (1985), 366–377.Google Scholar
von Neumann, J.. Theory of Self-reproducing Automata. Ed. Burks, A. W.. University of Illinois Press, Illinois, 1966.Google Scholar
Trow, P.. Decompositions of finite-to-one factor maps. Israel J. Math. 91 (1–3) (1995), 129–155.CrossRefGoogle Scholar
Trow, P.. Lifting covers of sofic shifts. Monatsh. Math. 125 (4) (1998), 327–342.Google Scholar
Trow, P. and Williams, S.. Core dimension group constraints for factors of sofic shifts. Ergod. Th. & Dynam. Sys. 13 (1) (1993), 213–224.Google Scholar
Wolfram, S.. Universality and complexity in cellular automata. Phys. D 10 (1984), 1–35.Google Scholar
Yoo, J.. On continuing codes. Preprint, 2013, arXiv:math.DS/1307.7412.Google Scholar