Decidability and undecidability in cellular automata

References

• Amoroso , S. and Patt , Y.N. 1972 . Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures . Journal of Computer and System Sciences , 6 ( 5 ) : 448 – 464 .
   Google Scholar
• Berger , R. 1966 . The Undecidability of the Domino Problem . Memoirs of the American Mathematical Society , 66 : 72
   Google Scholar
• Cattaneo , G. , Formenti , E. , Manzini , G. and Margara , L. 2000 . Ergodicity, Transitivity, and Regularity for Linear Cellular Automata over Zm . Theoretical Computer Science , 233 ( 1–2 ) : 147 – 164 .
   Web of Science ®Google Scholar
• Cervelle , J. , Formenti , E. and Guillon , P. 2010 . “ Ultimate Traces of Cellular Automata ” . In 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4–6, 2010 , LIPIcs Schloss Dagstuhl – Leibniz-Zentrum fur Informatik Edited by: Marion , J.Y. and Schwentick , T. Vol. 5 , 155 – 166 . Nancy, France : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik .
   Google Scholar
• Codenotti , B. and Margara , L. 1996 . Transitive Cellular Automata are Sensitive . The American Mathematical Monthly , 103 ( 1 ) : 58 – 62 .
   Web of Science ®Google Scholar
• Culik , K. II . 1996 . An Aperiodic Set of 13 Wang Tiles . Discrete Mathematics , 160 ( 1–3 ) : 245 – 251 .
   Web of Science ®Google Scholar
• Culik , K. II , Pachl , J.K. and Yu , S. 1989 . On the Limit Sets of Cellular Automata . SIAM Journal on Computing , 18 ( 4 ) : 831 – 842 .
   Web of Science ®Google Scholar
• Culik , K. II and Yu , S. 1988 . Undecidability of CA Classification Schemes . Complex Systrems , 2 : 177 – 190 .
   Google Scholar
• D'amico , M. , Manzini , G. and Margara , L. 2003 . On Computing the Entropy of Cellular Automata . Theoretical Computer Science , 290 ( 3 ) : 1629 – 1646 .
   Web of Science ®Google Scholar
• Durand , B. 1994 . The Surjectivity Problem for 2D Cellular Automata . Journal of Computer and System Sciences , 49 ( 3 ) : 718 – 725 .
   Web of Science ®Google Scholar
• Durand , B. , Formenti , E. and Róka , Z. 2003a . Number-Conserving Cellular Automata I: Decidability . Theoretical Computer Science , 299 ( 1–3 ) : 523 – 535 .
   Web of Science ®Google Scholar
• Durand , B. , Formenti , E. and Varouchas , G. 2003b . “ On Undecidability of Equicontinuity Classification for Cellular Automata ” . In Discrete Models for Complex Systems, DMCS'03 , DMTCS Proceedings Discrete Mathematics and Theoretical Computer Science Edited by: Morvan , M. and Rémila , É. Vol. AB , 117 – 128 . France : Nancy .
   Google Scholar
• Durand, B., Romashchenko, A.E., and Shen, A. (2009), ‘Fixed-Point Tile Sets and their Applications,’ CoRR, abs/0910.2415
   Google Scholar
• Finelli , M. , Manzini , G. and Margara , L. 1998 . Lyapunov Exponents Versus Expansivity and Sensitivity in Cellular Automata . Journal of Complexity , 14 : 210 – 233 .
   Web of Science ®Google Scholar
• Formenti , E. , Kari , J. and Taati , S. 2011 . On the Hierarchy of Conservation Laws in a Cellular Automaton . Natural Computing , 10 ( 4 ) : 1275 – 1294 .
   Web of Science ®Google Scholar
• Gajardo , A. , Kari , J. and Moreira , A. 2012 . On Time-Symmetry in Cellular Automata . Journal of Computer and System Sciences , 78 ( 4 ) : 1115 – 1126 .
   Web of Science ®Google Scholar
• Guillon , P. and Richard , G. 2010 . “ Revisiting the Rice Theorem of Cellular Automata ” . In 27th International Symposium on Theoretical Aspects f Computer Science, STACS 2010, March 4–6, 2010 , LIPIcs Schloss Dagstuhl – Leibniz-Zentrum fur Informatik Edited by: Marion , J.Y. and Schwentick , T. Vol. 5 , 441 – 452 . Nancy, France
   Google Scholar
• Gurevich , Y. and Koryakov , I.O. 1972 . Remark on Berger's Paper on the Domino Problem . Siberian Mathematical Journal , 13 ( 2 ) : 319 – 321 .
   Google Scholar
• Hattori , T. and Takesue , S. 1991 . Additive Conserved Quantities in Discrete-Time Lattice Dynamical Systems . Physica D: Nonlinear Phenomena , 49 ( 3 ) : 295 – 322 .
   Web of Science ®Google Scholar
• Hedlund , G.A. 1969 . Endomorphisms and Automorphisms of the Shift Dynamical Systems . Mathematical Systems Theory , 3 ( 4 ) : 320 – 375 .
   Google Scholar
• Hurd , L. , Kari , J. and Culik , K. 1992 . The Topological Entropy of Cellular Automata is Uncomputable . Ergodic Theory and Dynamical Systems , 12 : 255 – 265 .
   Web of Science ®Google Scholar
• Ito , M. , Osato , N. and Nasu , M. 1983 . Linear Cellular Automata over Zm . Journal of Computer and System Sciences , 27 ( 1 ) : 125 – 140 .
   Web of Science ®Google Scholar
• Kari , J. 1990 . Reversibility of 2D Cellular Automata is Undecidable . Physica D: Nonlinear Phenomena , 45 ( 1–3 ) : 379 – 385 .
   Web of Science ®Google Scholar
• Kari , J. 1992 . The Nilpotency Problem of One-Dimensional Cellular Automata . SIAM Journal on Computing , 21 ( 3 ) : 571 – 586 .
   Web of Science ®Google Scholar
• Kari , J. 1994a . Reversibility and Surjectivity Problems of Cellular Automata . Journal of Computer and System Sciences , 48 ( 1 ) : 149 – 182 .
   Web of Science ®Google Scholar
• Kari , J. 1994b . Rice's Theorem for the Limit Sets of Cellular Automata . Theoretical Computer Science , 127 ( 2 ) : 229 – 254 .
   Web of Science ®Google Scholar
• Kari , J. 1996 . A Small Aperiodic Set of Wang Tiles . Discrete Mathematics , 160 : 259 – 264 .
   Web of Science ®Google Scholar
• Kari , J. 2005 . Theory of Cellular Automata: A Survey . Theoretical Computer Science , 334 ( 1–3 ) : 3 – 33 .
   Web of Science ®Google Scholar
• Kari , J. 2007 . “ The Tiling Problem Revisited (Extended Abstract) ” . In MCU , Lecture Notes in Computer Science Edited by: Durand-Lose , J.O. and Margenstern , M. Vol. 4664 , 72 – 79 . Berlin/Heidelberg : Springer .
   Google Scholar
• Kari , J. 2008 . “ Undecidable Properties on the Dynamics of Reversible One-Dimensional Cellular Automata ” . In JAC , Edited by: Durand , B. 3 – 14 . Moscow : MCCME Publishing House .
   Google Scholar
• Kari , J. 2009 . “ Tiling Problem and Undecidability in Cellular Automata ” . In Encyclopedia of Complexity and Systems Science , Edited by: Meyers , R.A. 9158 – 9172 . Heidelberg : Springer .
   Google Scholar
• Kari , J. 2011 . “ Snakes and Cellular Automata: Reductions and Inseparability Results ” . In CSR , Lecture Notes in Computer Science Edited by: Kulikov , A.S. and Vereshchagin , N.K. (Vol. 6651) , 223 – 232 . Berlin/Heidelberg : Springer .
   Google Scholar
• Kari , J. and Lukkarila , V. 2009 . “ Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata. Natural Computing Series ” . In Algorithmic Bioprocesses , Edited by: Condon , A. , Harel , D. , Kok , J.N. , Salomaa , A. and Winfree , E. 639 – 660 . Berlin and Heidelberg : Springer .
   Google Scholar
• Kari , J. and Ollinger , N. 2008 . “ Periodicity and Immortality in Reversible Computing ” . In MFCS , Lecture Notes in Computer Science Edited by: Ochmanski , E. and Tyszkiewicz , J. (Vol. 5162 , 419 – 430 . Berlin/Heidelberg : Springer .
   Google Scholar
• Kůrka , P. 1997 . Languages, Equicontinuity and Attractors in Cellular Automata . Ergodic Theory and Dynamical Systems , 17 ( 2 ) : 417 – 433 .
   Web of Science ®Google Scholar
• Lukkarila , V. 2009 . The 4-Way Deterministic Tiling Problem is Undecidable . Theoretical Computer Science , 410 ( 16 ) : 1516 – 1533 .
   Web of Science ®Google Scholar
• Lukkarila , V. 2010 . Sensitivity and Topological Mixing are Undecidable for Reversible One-dimensional Cellular Automata . Journal of Cellular Automata , 5 ( 3 ) : 241 – 272 .
   Web of Science ®Google Scholar
• Manzini , G. and Margara , L. 1999 . A Complete and Efficiently Computable Topological Classification of D-dimensional Linear Cellular Automata over Zm . Theoretical Computer Science , 221 ( 1–2 ) : 157 – 177 .
   Web of Science ®Google Scholar
• Moore , E. 1962 . Machine Models of Self-Reproduction . Proceedings of the Symposium in Applied Mathematics , 14 : 17 – 33 .
   Google Scholar
• Moreira , A. and Gajardo , A. 2010 . “ Time-Symmetric Cellular Automata ” . In JAC , Edited by: Kari , J. 180 – 190 . Turku Center for Computer Science .
   Google Scholar
• Myhill , J. 1963 . The Converse to Moore's Garden-of-Eden Theorem . Proceedings of the American Mathematical Society , 14 : 685 – 686 .
   Google Scholar
• Robinson , R.M. 1971 . Undecidability and Nonperiodicity for Tilings of the Plane . Inventiones Mathematicae , 12 : 177 – 209 .
   Web of Science ®Google Scholar
• Salo, V., ‘A Characterization of Cellular Automata Generated by Idempotents on the Full Shift,’ CoRR, abs/1206.0585
   Google Scholar
• Shereshevsky , M. 1993 . Expansiveness, Entropy and Polynomial Growth for Groups Acting on Subshifts by Automorphisms . Indagationes Mathematicae , 4 : 203 – 210 .
   Web of Science ®Google Scholar
• Sutner , K. 1989 . A Note on the Culik–Yu Classes . Complex Systems , 3 : 107 – 115 .
   Google Scholar
• Sutner , K. 1991 . De Bruijn Graphs and Linear Cellular Automata . Complex Systems , 4 : 19 – 30 .
   Google Scholar
• Turing , A.M. 1936 . On Computable Numbers, with an Application to the Entscheidungsproblem . Proceedings of the London Mathematical Society , 2 ( 42 ) : 230 – 265 .
   Google Scholar
• Wang , H. 1960 . Proving Theorems by Pattern Recognition I . Communications of the ACM , 3 : 220 – 234 .
   Web of Science ®Google Scholar