Bruno Durand ; Enrico Formenti ; Georges Varouchas
-
On undecidability of equicontinuity classification for cellular automata
dmtcs:2302 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2003,
DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03)
-
https://doi.org/10.46298/dmtcs.2302
On undecidability of equicontinuity classification for cellular automata
Authors: Bruno Durand 1; Enrico Formenti 1; Georges Varouchas 1
NULL##0000-0002-1007-7912##NULL
Bruno Durand;Enrico Formenti;Georges Varouchas
1 Laboratoire d'informatique Fondamentale de Marseille - UMR 6166
Equicontinuity classification is a popular classification of cellular automata based on their dynamical behavior. In this paper we prove that most of its classes are undecidable.
Cervelle, Julien; Dennunzio, Alberto; Formenti, Enrico, 2009, Chaotic Behavior Of Cellular Automata, Encyclopedia Of Complexity And Systems Science, pp. 978-989, 10.1007/978-0-387-30440-3_65.
Di Lena, Pietro; Margara, Luciano, 2008, Computational Complexity Of Dynamical Systems: The Case Of Cellular Automata, Information And Computation, 206, 9-10, pp. 1104-1116, 10.1016/j.ic.2008.03.012.
Di Lena, Pietro; Margara, Luciano, 2014, Nondeterministic Cellular Automata, Information Sciences, 287, pp. 13-25, 10.1016/j.ins.2014.07.007.
Kari, Jarkko, 2009, Tiling Problem And Undecidability In Cellular Automata, Encyclopedia Of Complexity And Systems Science, pp. 9158-9172, 10.1007/978-0-387-30440-3_552.
Kari, Jarkko, 2012, Tiling Problem And Undecidability In Cellular Automata, Computational Complexity, pp. 3198-3211, 10.1007/978-1-4614-1800-9_198.
Kari, Jarkko, 2015, Tiling Problem And Undecidability In Cellular Automata, Encyclopedia Of Complexity And Systems Science, pp. 1-20, 10.1007/978-3-642-27737-5_552-5.
Kari, Jarkko, 2018, Tiling Problem And Undecidability In Cellular Automata, Cellular Automata, pp. 201-219, 10.1007/978-1-4939-8700-9_552.
Kari, Jarkko J., 2012, Basic Concepts Of Cellular Automata, Handbook Of Natural Computing, pp. 3-24, 10.1007/978-3-540-92910-9_1.
Sablik, Mathieu; Theyssier, Guillaume, 2008, Topological Dynamics Of 2D Cellular Automata, Logic And Theory Of Algorithms, pp. 523-532, 10.1007/978-3-540-69407-6_56.
Sablik, Mathieu; Theyssier, Guillaume, 2010, Topological Dynamics Of Cellular Automata: Dimension Matters, Mathematical Systems Theory, 48, 3, pp. 693-714, 10.1007/s00224-010-9255-x.
Stepney, Susan, 2012, Nonclassical Computation â A Dynamical Systems Perspective, Handbook Of Natural Computing, pp. 1979-2025, 10.1007/978-3-540-92910-9_59.