Computational classification of cellular automata

References

• Adamatzky , A. 1994 . Identification of Cellular Automata , London : Taylor & Francis .
   Google Scholar
• Baldwin, J.T. (2002), ‘Computation Versus Simulation,’ http://www.math.uic.edu/jbaldwin/pub/cafom.ps , July 2002
   Google Scholar
• Baldwin , J.T. and Shelah , S. 2000 . On the Classifiability of Cellular Automata . Theoretical Computer Science , 230 ( 1–2 ) : 117 – 129 .
   Web of Science ®Google Scholar
• Barwise , J. and Keisler , J. , eds. 1977 . Handbook of Mathematical Logic , Number 90 in Studies in Logic and Foundations of Mathematics Amsterdam : Elsevier .
   Google Scholar
• Baumslag, G. (2009), ‘Magnus,’ http://caissny.org/
   Google Scholar
• Cook , M. 2004 . Universality in Elementary Cellular Automata . Complex Systems , 15 ( 1 ) : 1 – 40 .
   Google Scholar
• Culik , K. and Yu , S. 1988 . Undecidability of CA Classification Schemes . Complex Systems , 2 ( 2 ) : 177 – 190 .
   Google Scholar
• Durand-Lose , J. 2009 . “ Universality of Cellular Automata ” . In Encyclopedia of Complexity and System Science , Berlin : Springer .
   Google Scholar
• Epstein , D.B.A. , Cannon , J.W. , Holt , D.F. , Levy , S.V.F. , Patterson , M.S. and Thurston , W.P. 1992 . Word Processing in Groups , Burlington : Jones and Bartlett .
   Google Scholar
• Friedberg , R.M. 1957 . Two Recursively Enumerable Sets of Incomparable Degrees of Unsolvability . Proceedings of the National Academy of Sciences of the United States of America , 43 : 236 – 238 .
   PubMed Web of Science ®Google Scholar
• Griffor , E.R. , ed. 1999 . Handbook of Computability Theory, Vol. 140 of Studies in Logic , North-Holland .
   Google Scholar
• Hedlund , G.A. 1969 . Endomorphisms and Automorphisms of the Shift Dynamical System . Mathematical Systems Theory , 3 : 320 – 375 .
   Google Scholar
• Khoussainov , B. and Nerode , A. 1995 . “ Automatic Presentations of Structures ” . In LCC'94: International Workshop on Logical and Computational Complexity , 367 – 392 . London : Springer-Verlag .
   Google Scholar
• Khoussainov , B. and Rubin , S. 2003 . Automatic Structures: Overview and Future Directions . Journal of Automata, Languages and Combinatorics , 8 ( 2 ) : 287 – 301 .
   Google Scholar
• Kûrka , P. 1997 . Languages, Equicontinuity and Attractors in Cellular Automata . Ergodic Theory and Dynamical Systems , 17 : 417 – 433 .
   Web of Science ®Google Scholar
• Kûrka , P. 2003 . Topological and Symbolic Dynamics , Number 11 in Cours Spécialisés Paris : Societe Mathematique de France .
   Google Scholar
• Lerman , M. 1983 . Degrees of Unsolvability , Perspectives in Mathematical Logic Berlin : Springer .
   Google Scholar
• Li , W. and Packard , N. 1990 . The Structure of the Elementary Cellular Automata Rule Space . Complex Systems , 4 ( 3 ) : 281 – 297 .
   Google Scholar
• Li , W. , Packard , N. and Langton , C.G. 1990 . Transition Phenomena in CA Rule Space . Physica D , 45 ( 1-3 ) : 77 – 94 .
   Web of Science ®Google Scholar
• Muchnik , A.A. 1956 . On the Unsolvability of the Problem of Reducibility in the Theory of Algorithms . Doklady Academii Nauk SSSR , 108 : 194 – 197 .
   Google Scholar
• Neary , R. and Woods , D. 2006a . “ On the Time Complexity of 2-Tag Systems and Small Universal Turing Machines ” . In FOCS , 439 – 448 . Washington : IEEE Computer Society .
   Google Scholar
• Neary , R. and Woods , D. 2006b . Small Fast Universal Turing Machines . Theoretical Computer Science , 362 ( 1-3 ) : 171 – 195 .
   Web of Science ®Google Scholar
• Perrin , D. and Pin , J.-E. 2004 . Infinite Words, Vol. 141 of Pure and Applied Mathematics , Amsterdam : Elsevier .
   Google Scholar
• Rogers , H. 1967 . Theory of Recursive Functions and Effective Computability , New York : McGraw Hill .
   Google Scholar
• Safra , S. 1988 . “ On the Complexity of ω-Automata ” . In Proceedings of the 29th FOCS , 319 – 327 . Washington : IEEE Computer Society Press .
   Google Scholar
• Shoenfield , J.R. 1967 . Mathematical Logic , Boston : Addison Wesley .
   Google Scholar
• Soare , R.I. 1972 . The Friedberg-Muchnik Theorem Re-examined . Canadian Journal of Mathematics , 24 : 1070 – 1078 .
   Web of Science ®Google Scholar
• Soare , R.I. 1987 . Recursively Enumerable Sets and Degrees , Perspectives in Mathematical Logic Berlin : Springer .
   Google Scholar
• Sutner , K. 1991 . De Bruijn Graphs and Linear Cellular Automata . Complex Systems , 5 ( 1 ) : 19 – 30 .
   Google Scholar
• Sutner , K. 1995 . On the Computational Complexity of Finite Cellular Automata . Journal of Computer and System Sciences , 50 ( 1 ) : 87 – 97 .
   Web of Science ®Google Scholar
• Sutner , K. 1997 . Linear Cellular Automata and Fischer Automata . Parallel Computing , 23 ( 11 ) : 1613 – 1634 .
   Web of Science ®Google Scholar
• Sutner , K. 2002 . Cellular Automata and Intermediate Reachability Problems . Fundamenta Informaticae , 52 ( 1-3 ) : 249 – 256 .
   Web of Science ®Google Scholar
• Sutner , K. 2003 . Cellular Automata and Intermediate Degrees . Theoretical Computer Science , 296 : 365 – 375 .
   Web of Science ®Google Scholar
• Sutner , K. 2004 . The Complexity of Reversible Cellular Automata . Theoretical Computer Science , 325 ( 2 ) : 317 – 328 .
   Web of Science ®Google Scholar
• Sutner , K. 2010 . Cellular Automata . Decidability and Phasespace. Fundamenta Informaticae , 140 : 1 – 20 .
   Google Scholar
• von Neumann , J. 1966 . “ Theory of Self-Reproducing Automata ” . In Essays on Cellular Automata , Champaign : University of Illinois Press .
   Google Scholar
• Vorhees , B. 1996 . Computational Analysis of One-Dimensional Cellular Automata , Singapore : World Scientific .
   Google Scholar
• Wang , H. 1993 . Popular Lectures on Mathematical Logic , New York : Dover .
   Google Scholar
• Weihrauch , K. 2000 . Computable Analysis , EATCS Monographs Berlin : Springer .
   Google Scholar
• Wolfram , S. 1984 . Computation Theory of Cellular Automata . Communications in Mathematical Physics , 96 ( 1 ) : 15 – 57 .
   Web of Science ®Google Scholar
• Wolfram , S. 1985 . Twenty Problems in the Theory of Cellular Automata . Physica Scripta , T9 : 170 – 183 .
   Web of Science ®Google Scholar
• Wolfram , S. 2002 . A New Kind of Science , Champaign, IL : Wolfram Media .
   Google Scholar
• Wuensche , A. 1999 . Classifying Cellular Automata Automatically . Complexity , 4 ( 3 ) : 47 – 66 .
   Google Scholar