On the Undecidability of Attractor Properties for Cellular Automata

• Autorzy: Di Lena P. , Margara L.
• Języki publikacji: EN

Abstrakty

EN

The attractor properties in Cellular Automata dynamical systems have been extensively investigated and well characterized. We consider here two attractor classification for Cellular Automata and we prove the computational undecidability of some questions related to such classifications.

Słowa kluczowe

EN

cellular automata; attractor; computational undecidability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 115, nr 1
• Strony: 75--85
• Opis fizyczny: Bibliogr. 24 poz.

Twórcy

autor

Di Lena P.

autor

Margara L.

• Department of Computer Science University of Bologna Mura Anteo Zamboni, 40127 Bologna, Italy,

Bibliografia

• [1] Acerbi, L., Dennunzio, A., Formenti, E.: Conservation of some dynamical properties for operations on cellular automata, Theoret. Comput. Sci., 410(38-40), 2009, 3685-3693.
• [2] Cattaneo, G., Dennunzio, A.,Margara, L.: Solution of some conjectures about topological properties of linear cellular automata, Theoretical Computer Science, 325(2), 2004, 249 - 271.
• [3] Cervelle, J., Guillon, P.: Towards a Rice theoremon traces of cellular automata, in: Mathematical foundations of computer science 2007, vol. 4708 of Lecture Notes in Comput. Sci., Springer, Berlin, 2007, 310-319.
• [4] Culik, II, K., Yu, S.: Undecidability of CA classification schemes, Complex Systems, 2(2), 1988, 177-190.
• [5] Dennunzio, A., Di Lena, P., Formenti, E., Margara, L.: On the directional dynamics of additive cellular automata, Theoret. Comput. Sci., 410(47-49), 2009, 4823-4833.
• [6] Dennunzio, A., Guillon, P., Masson, B.: Sand automata as cellular automata, Theoretical Computer Science, 410(38-40), 2009, 3962 - 3974.
• [7] Di Lena, P.: Decidable properties for regular cellular automata, in: Fourth IFIP International Conference on Theoretical Computer Science-TCS 2006, vol. 209 of IFIP Int. Fed. Inf. Process., Springer, New York, 2006, 185-196.
• [8] Di Lena, P., Margara, L.: Computational complexity of dynamical systems: the case of cellular automata, Inform. and Comput., 206(9-10), 2008, 1104-1116.
• [9] Di Lena, P., Margara, L.: On the undecidability of the limit behavior of cellular automata, Theoret. Comput. Sci., 411(7-9), 2010, 1075-1084.
• [10] Durand, B., Formenti, E., Varouchas, G.: On undecidability of equicontinuity classification for cellular automata, in: Discrete models for complex systems, DMCS '03 (Lyon), Discrete Math. Theor. Comput. Sci. Proc., AB, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2003, 117-127 (electronic).
• [11] Formenti, E., Kůrka, P.: Subshift attractors of cellular automata, Nonlinearity, 20(1), 2007, 105-117.
• [12] Formenti, E., Kůrka, P., Zahradn´ınk, O.: A search algorithm for subshift attractors of cellular automata, Theory Comput. Syst., 46(3), 2010, 479-498.
• [13] Gilman, R. H.: Classes of linear automata, Ergodic Theory Dynam. Systems, 7(1), 1987, 105-118.
• [14] Guillon, P., Richard, G.: Revisiting the Rice Theorem of Cellular Automata, Symposium on Theoretical Aspects of Computer Science, 2010.
• [15] Hedlund, G. A.: Endomorphisms and automorphisms of the shift dynamical system, Theory of Computing Systems, 3, 1969, 320-375.
• [16] Hurley, M.: Attractors in cellular automata, Ergodic Theory Dynam. Systems, 10(1), 1990, 131-140.
• [17] Kari, J.: The nilpotency problem of one-dimensional cellular automata, SIAM J. Comput., 21(3), 1992, 571-586.
• [18] Kari, J.: Rice's theorem for the limit sets of cellular automata, Theoret. Comput. Sci., 127(2), 1994, 229-254.
• [19] Kůrka, P.: Languages, equicontinuity and attractors in cellular automata, Ergodic Theory Dynam. Systems, 17(2), 1997, 417-433.
• [20] Kůrka, P.: Topological and symbolic dynamics, vol. 11 of Cours Spécialisés [Specialized Courses], Société Mathématique de France, Paris, 2003.
• [21] Kůrka, P.: Cellular automata with an infinite number of subshift attractors, Complex Systems, 17(3), 2007, 219-230.
• [22] Lukkarila, V.: Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata, J. Cell. Autom., 5(3), 2010, 241-272.
• [23] Sablik, M.: Directional dynamics for cellular automata: a sensitivity to initial condition approach, Theoret. Comput. Sci., 400(1-3), 2008, 1-18.
• [24] Sutner, K.: Cellular automata and intermediate degrees, Theoret. Comput. Sci., 296(2), 2003, 365-375, Machines, computations and universality (Chis¸in˘au, 2001).