Limit Sets of Stable and Unstable Cellular Automata

• Autorzy: Ballier A. , Guillony P. , Kari J.
• Języki publikacji: EN

Abstrakty

EN

We construct a cellular automaton (CA) with a sofic and mixing limit set and then construct a stable CA with the same limit set, showing there exist subshifts that can be limit sets of both stable and unstable CAs, answering a question raised by A. Maass.

Słowa kluczowe

EN

cellular automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 45--56
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Ballier A.

autor

Guillony P.

autor

Kari J.

• Department of Mathematics, FI-20014 University of Turku, Finland,

Bibliografia

• [1] Ashley, J.: An Extension Theorem for Closing Maps of Shifts of Finite Type, Transactions of the American Mathematical Society, 336, 1993, 389-420.
• [2] Boyle, M.: Lower Entropy Factors of Sofic Systems, Ergodic theory and dynamical systems, 4, 1984, 541-557.
• [3] Boyle, M.: Open Problems in Symbolic Dynamics, Contemporary Mathematics, 469, 2008, 69-118.
• [4] Culik II, K., Pachl, J., Yu, S.: On the Limit Sets of Cellular Automata, SIAM Journal of Computing, 18(4), 1989, 831-842.
• [5] Formenti, E., K°urka, P.: Subshift Attractors of Cellular Automata, Nonlinearity, 20(1), 2007, 105-117.
• [6] Hedlund, G. A.: Endomorphisms and Automorphisms of the Shift Dynamical Systems, Mathematical Systems Theory, 3(4), 1969, 320-375.
• [7] Hurd, L. P.: Formal Language Characterizations of Cellular Automaton Limit Sets, Complex Systems, 1, 1987, 69-80.
• [8] Hurd, L. P.: Nonrecursive Cellular Automata Invariant Sets, Complex Systems, 4(2), 1990, 131-138.
• [9] Hurd, L. P.: Recursive Cellular Automata Invariant Sets, Complex Systems, 4(2), 1990, 119-129.
• [10] Kari, J.: Rice's Theorem for the Limit Set of Cellular Automata, Theoretical Computer Science, 127(2), 1994, 229-254.
• [11] di Lena, P., Margara, L.: Undecidable Properties of Limit Set Dynamics of Cellular Automata, 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 (S. Albers, J.-Y. Marion, Eds.), IBFI Schloss Dagstuhl, 2009.
• [12] Lind, D. A., Marcus, B.: An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, 1995.
• [13] Maass, A.: On the Sofic Limit Sets of Cellular Automata, Ergodic Theory and Dynamical Systems, 15, 1995, 663-684.