Computational Aspects of Asynchronous CA

Preprint English OPEN
Chandesris, Jérôme; Dennunzio, Alberto; Formenti, Enrico; Manzoni, Luca;
(2011)
  • Subject: Nonlinear Sciences - Cellular Automata and Lattice Gases | Computer Science - Formal Languages and Automata Theory
    arxiv: Nonlinear Sciences::Cellular Automata and Lattice Gases | Computer Science::Neural and Evolutionary Computation | Computer Science::Formal Languages and Automata Theory | Mathematics::Logic

This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are "universal", i.e.... View more
  • References (16)
    16 references, page 1 of 2

    1. Patrick Amar, Gilles Bernot, and Victor Norris. Hsim: a simulation programme to study large assemblies of proteins. Journal of Biological Physics and Chemistry, 4:79-84, 2004.

    2. B. Chopard. Modelling physical systems by cellular automata. In G. Rozenberg et al., editor, Handbook of Natural Computing: Theory, Experiments, and Applications. Springer, 2011. To appear.

    3. M. Cook. Universality in elementary cellular automata. Complex Systems, 15:1-40, 2004.

    4. M. Delorme and J. Mazoyer. Cellular automata as languages recognizers. In Marianne Delorme and Jacques Mazoyer, editors, Cellular Automata, Mathematics and Its Applications. Kluwer, Dordrecht, 1999.

    5. J.-C. Dubacq. How to simulate turing machines by invertible one dimensional cellular automata. IJFOCS, 6:395-402, 1995.

    6. N. Fatès, M. Morvan, N. Schabanel, and E. Thierry. Fully asynchronous behaviour of double-quiescent elementary cellular automata. Theoretical Computer Science, 362:1-16, 2006.

    7. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

    8. A. Ray Smith III. Simple computation-universal cellular spaces. Journal of the ACM, 18:339-353, 1971.

    9. J. Kari. Theory of cellular automata: A survey. Theoretical Computer Science, 334:3-33, 2005.

    10. J. F. C. Kingman. Poisson Processes. Oxford University Press, 1993.

  • Metrics
Share - Bookmark