The Intrinsic Universality Problem of One-Dimensional Cellular Automata

1. J. Albert and K. Čulik II, A simple universal cellular automaton and its one-way and totalistic version, Complex Systems, 1(1987), no. 1, 1–16.

   MATH  MathSciNet  Google Scholar 

2. S. Amoroso and Y. N. Patt, Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures, J. Comput. System Sci., 6(1972), 448–464.

   MATH  MathSciNet  Google Scholar 

3. E. R. Banks, Universality in cellular automata, in Conference Record of 1970 Eleventh Annual Symposium on Switching and Automata Theory, pages 194–215, IEEE, 1970.

   Google Scholar 

4. K. Čulik II, J. K. Pachl, and S. Yu, On the limit sets of cellular automata,SIAM J. Comput., 18(1989), no. 4, 831–842.

   Article  MathSciNet  MATH  Google Scholar 

5. J. Kari, The nilpotency problem of one-dimensional cellular automata, SIAM J. Comput., 21(1992), 571–586.

   Article  MATH  MathSciNet  Google Scholar 

6. J. Kari, Reversibility and surjectivity problems of cellular automata, J. Comput. System Sci., 48(1994), 149–182.

   Article  MATH  MathSciNet  Google Scholar 

7. J. Kari, Rice’s theorem for the limit sets of cellular automata, Theoretical Computer Science, 127(1994), no. 2, 229–254.

   Article  MATH  MathSciNet  Google Scholar 

8. J. Mazoyer and I. Rapaport, Global fixed point attractors of circular cellular automata and periodic tilings of the plane: undecidability results, Discrete Math., 199(1999), 103–122.

   Article  MATH  MathSciNet  Google Scholar 

9. J. Mazoyer and I. Rapaport, Inducing an order on cellular automata by a grouping operation, Discrete Appl. Math., 218(1999), 177–196.

   Article  MathSciNet  Google Scholar 

10. N. Ollinger, Toward an algorithmic classification of cellular automata dynamics, 2001, LIP RR2001-10, http://www.ens-lyon.fr/LIP.

11. N. Ollinger, The quest for small universal cellular automata, in P. Widmayer, F. Triguero, R. Morales, M. Hennessy, S. Eidenbenz, and R. Conejo, editors, Automata, languages and programming (Málaga, Spain, 2002), volume 2380 of Lecture Notes in Computer Science, pages 318–329, Springer, Berlin, 2002.

    Chapter  Google Scholar 

12. R. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12(1971), 177–209.

    Google Scholar 

13. K. Sutner, Classifying circular cellular automata, Physica D, 45(1990), 386–395.

    Article  MATH  MathSciNet  Google Scholar 

Download references