From One-dimensional to Two-dimensional Cellular Automata

• Autorzy: Dennunzio A.
• Języki publikacji: EN

Abstrakty

EN

We enlighten the differences between one-dimensional and two-dimensional cellular automata by considering both the dynamical and decidability aspects. We also show a canonical representation theorem for the slicing constructions, a tool allowing to give the 2D version of important 1D CA notions as closing and positive expansivity and lift 1D results to the 2D settings.

Słowa kluczowe

EN

cellular automata; symbolic dynamics; decidability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 115, nr 1
• Strony: 87--105
• Opis fizyczny: Bibliogr. 50 poz., tab., wykr.

Twórcy

autor

Dennunzio A.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Universita degli Studi di Milano– Bicocca, Viale Sarca 336, 20126 Milano, Italy,

Bibliografia

• [1] Acerbi, L., Dennunzio, A., Formenti, E.: Conservation of Some Dynamcal Properties for Operations on Cellular Automata, Theoretical Computer Science, 410, 2009, 3685-3693.
• [2] Alarcon, T., Byrne, H., Maini, P.: A cellular automaton model for tumour growth in inhomogeneous environment, Journal of Theoretical Biology, 225, 2003, 257-274.
• [3] Amoroso, S., Patt, Y. N.: Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures, Journal of Computer and System Sciences, 6, 1972, 448-464.
• [4] Ballier, A., Guillon, P., Kari, J.: Limit Sets of Stable and Unstable Cellular Automata, Fundamenta Informaticae, 110, 2011, 45-57.
• [5] Berger, R.: The undecidability of the domino problem, Memoirs of the American Mathematical Society, 66, 1966, 1-72.
• [6] Blanchard, F.: Dense periodic points in cellular automata, Http://www.math.iupui.edu/mmisiure/open/.
• [7] Blanchard, F., Maass, A.: Dynamical properties of expansive one-sided cellular automata, Israel Journal of Mathematics, 99, 1997, 149-174.
• [8] Blanchard, F., Tisseur, P.: Some properties of cellular automata with equicontinuity points, Ann. Inst. Henri Poincaré, Probabilité et Statistiques, 36, 2000, 569-582.
• [9] Boyle, M., Kitchens, B.: Periodic points for cellular automata, Indagationes Mathematicae, 10, 1999, 483-493.
• [10] Cattaneo, G., Dennunzio, A., Margara, L.: Chaotic Subshifts and Related Languages Applications to One-Dimensional Cellular Automata, Fundamenta Informaticae, 52, 2002, 39-80.
• [11] Cattaneo, G., Dennunzio, A., Margara, L.: Solution of Some Conjectures about Topological Properties of Linear Cellular Automata, Theoretical Computer Science, 325, 2004, 249-271.
• [12] Cervelle, J., Dennunzio, A., Formenti, E.: Chaotic behavior of cellular automata, in: Mathematical basis of cellular automata (B. Meyers, Ed.), Encyclopedia of Complexity and System Science, Springer Verlag, 2009, 978-989.
• [13] Cervelle, J., Formenti, E., Guillon, P.: Ultimate Traces of Cellular Automata, 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, 5, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010.
• [14] Chaudhuri, P., Chowdhury, D., Nandi, S., Chattopadhyay, S.: Additive Cellular Automata Theory and Applications, vol. 1, IEEE Press, 1997.
• [15] Chopard, B.: Cellular Automata and Lattice Boltzmann Modeling of Physical Systems, in: Handbook of Natural Computing: Theory, Experiments, and Applications (G. R. et al., Ed.), Springer, 2010.
• [16] Dennunzio, A., Di Lena, P., Formenti, E., Margara, L.: On the Directional Dynamics of Additive Cellular Automata, Theoretical Computer Science, 410, 2009, 4823-4833.
• [17] Dennunzio, A., Formenti, E.: Decidable Properties of 2D Cellular Automata, 12th Conference on Developments in Language Theory (DLT 2008), 5257, Springer-Verlag, 2008.
• [18] Dennunzio, A., Formenti, E., Kůrka, P.: Cellular Automata Dynamical Systems, Handbook of Natural Computing: Theory, Experiments, and Applications, Springer, 2010.
• [19] Dennunzio, A., Formenti, E., Weiss, M.: 2D Cellular Automata: new constructions, dynamics, and (un)decidability, 2009, Preprint, CoRR, abs/0906.0857.
• [20] Dennunzio, A., Formenti, E., Weiss, M.: 2D Cellular Automata: dynamics and undecidability, Proceedings of 6th Conference on Computability in Europe (CiE 2010), 2010.
• [21] Dennunzio, A., Masson, B., Guillon, P.: Sand Automata as Cellular Automata, Theoretical Computer Science, 410, 2009, 3962-3974.
• [22] Devaney, R. L.: An Introduction to chaotic dynamical systems, Second edition, Addison-Wesley, 1989.
• [23] Di Lena, P., Margara, L.: On the undecidability of the limit behavior of Cellular Automata, Theoretical Computer Science, 411, 2010, 1075-1084.
• [24] Durand, B.: The Surjectivity Problem for 2D Cellular Automata, Journal of Computer and System Sciences, 49(3), 1994, 718-725.
• [25] Durand, B.: Global properties of cellular automata, in: Cellular Automata and Complex Systems (E. Goles, S. Martinez, Eds.), Kluwer, 1998.
• [26] Durand, B., Formenti, E., Varouchas, G.: On undecidability of equicontinuity classification for cellular automata, Discrete Mathematics and Theoretical Computer Science, AB, 2003, 117-128.
• [27] Farina, F., Dennunzio, A.: A Predator-Prey CA with Parasitic Interactions and Environmentals Effects, Fundamenta Informaticae, 83, 2008, 337-353.
• [28] Formenti, E., Grange, A.: Number conserving cellular automata II: dynamics, Theoretical Computer Science, 304(1-3), 2003, 269-290.
• [29] Formenti, E., Kari, J., Taati, S.: On the hierarchy of conservation laws in a cellular automaton, Natural Computing, 10, 2011, 1275-1294.
• [30] Guillon, P., Richard, G.: Revisiting the Rice Theorem of Cellular Automata, 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, 5, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010.
• [31] Hedlund, G. A.: Endomorphism and Automorphism of the shift Dynamical System, Mathematical System Theory, 3, 1969, 320-375.
• [32] Kari, J.: The Nilpotency Problem of One Dimensional Cellular Automata, SIAM Journal on Computing, 21, 1992, 571-586.
• [33] Kari, J.: Reversibility and surjectivity problems of cellular automata, Journal of Computer and System Sciences, 48, 1994, 149-182.
• [34] Kari, J.: Theory of cellular automata: A survey, Theor. Comput. Sci., 334, 2005, 3-33.
• [35] Kier, L., Seybold, P., Cheng, C.-K.: Modeling Chemical Systems using Cellular Automata, Springer, 2005.
• [36] Kůrka, P.: Languages, Equicontinuity and Attractors in Cellular Automata, Ergodic Theory & Dynamical Systems, 17, 1997, 417-433.
• [37] Kůrka, P.: Topological and Symbolic Dynamics, Volume 11 of Cours Spécialisés, Société Mathématique de France, 2004.
• [38] Lukkarila, V.: Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata, Journal of Cellular Automata, 5, 2010, 241-272.
• [39] Manzini, G.,Margara, L.: A complete and efficiently computable topological classification of D-dimensional linear cellular automata over Zm, Theoretical Computer Science, 221(1-2), 1999, 157-177.
• [40] Maruoka, A., Kimura, M.: Conditions for Injectivity of Global Maps for Tessellation Automata, Inf. & Control, 32, 1976, 158-162.
• [41] Moore, E. F.: Machine models of self-reproduction, Proceedings of Symposia in Applied Mathematics, 14, 1962, 13-33.
• [42] Myhill, J.: The converse to Moore's garden-of-eden theorem, Proceedings of the American Mathematical Society, 14, 1963, 685-686.
• [43] Ollinger, N., Richard, G.: Four states are enough!, Theoretical Computer Science, 412, 2011, 22-32.
• [44] Shereshevsky, M. A.: Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms, IndagationesMathematicae, 4, 1993, 203-210.
• [45] Shereshevsky,M. A., Afraimovich, V. S.: Bipermutative cellular automata are topologically conjugate to the one-sided Bernoulli shift, Random Comput. Dynam., 1(1), 1993, 91-98.
• [46] Sutner, K.: De Bruijn Graphs and Linear Cellular Automata, Complex Systems, 5, 1991, 19-30.
• [47] Theyssier, G., Sablik, M.: Topological Dynamics of Cellular Automata: Dimension Matters, Theory of Computing Systems, 48, 2011, 693-714.
• [48] Wang, H.: Dominoes and the ∀∃∀-case of the decision problem, Proceedings of the Symposium on Mathematical Theory of Automata, 1962.
• [49] Wolfram, S.: A new kind of science, Wolfram-Media, 2002.
• [50] Zinoviadis, C.: Dimension sensitive properties of cellular automata and subshifts of finite type, TUCS Technical Report 977, Turku Centre for Computer Science, May 2010.