Computing Issues of Asynchronous CA

• Autorzy: Dennunzio A. , Formenti E. , Manzoni L.
• Języki publikacji: EN

Abstrakty

EN

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., allowing a (specific family of) ACA to simulate any Turing machine on any input. We also consider the computational cost of such simulations. Finally, we deal with ACA equipped with peculiar updating sequences, namely those generated by random walks.

Słowa kluczowe

EN

Asynchronous Cellular Automata; turing machines; turing universality; computational complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 120, nr 2
• Strony: 165--180
• Opis fizyczny: Bibliogr. 31 poz., tab.

Twórcy

autor

Dennunzio A.

autor

Formenti E.

autor

Manzoni L.

• Universita degli Studi di Milano–Bicocca, Dipartimento di Informatica, Sistemistica e Comunicazione, Viale Sarca 336, 20126 Milano, Italy,

Bibliografia

• [1] L. Acerbi, A. Dennunzio, and E. Formenti, Shifting and lifting of cellular automata, CiE (S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, eds.), Lecture Notes in Computer Science, vol. 4497, Springer, 2007, pp. 1-10.
• [2] L. Acerbi, A. Dennunzio, and E. Formenti, Conservation of some dynamcal properties for operations on cellular automata, Theoretical Computer Science 410 (2009), 3685-3693.
• [3] P. Amar, G. Bernot, and V. Norris, Hsim: a simulation programme to study large assemblies of proteins, Journal of Biological Physics and Chemistry 4 (2004), 79-84.
• [4] A. Z. Broder and A. R. Karlin, Bounds on the cover time, J. Theoretical Probab 2 (1988), 101-120.
• [5] G. Cattaneo, A. Dennunzio, and F. Farina, A full cellular automaton to simulate predator-prey systems, ACRI (Samira El Yacoubi, Bastien Chopard, and Stefania Bandini, eds.), Lecture Notes in Computer Science, vol. 4173, Springer, 2006, pp. 446-451.
• [6] G. Cattaneo, A. Dennunzio, and F. Farina, A survey on transitivity in discrete time dynamical systems. Application to symbolic systems and related languages, RAIRO - Theoretical Informatics and Applications 40 (2006), 333-352.
• [7] G. Cattaneo, A. Dennunzio, E. Formenti, and J. Provillard, Non-uniform cellular automata, LATA (Adrian Horia Dediu, Armand-Mihai Ionescu, and Carlos Martín-Vide, eds.), Lecture Notes in Computer Science, vol. 5457, Springer, 2009, pp. 302-313.
• [8] G. Cattaneo, A. Dennunzio, and L. Margara, Chaotic subshifts and related languages applications to onedimensional cellular automata, Fundamenta Informaticae 52 (2002), 39-80.
• [9] G. Cattaneo, A. Dennunzio, and L. Margara, Solution of some conjectures about topological properties of linear cellular automata, Theoretical Computer Science 325 (2004), 249-271.
• [10] B. Chopard, Modelling physical systems by cellular automata, Handbook of Natural Computing: Theory, Experiments, and Applications (G. Rozenberg et al., ed.), Springer, 2012.
• [11] A. Dennunzio, From one-dimensional to two-dimensional cellular automata, Fundamenta Informaticae 115 (2012), 87-105.
• [12] A. Dennunzio, P. Di Lena, E. Formenti, and L. Margara, On the directional dynamics of additive cellular automata, Theoretical Computer Science 410 (2009), 4823-4833.
• [13] A. Dennunzio and E. Formenti, Decidable properties of 2d cellular automata, Developments in Language Theory (Masami Ito and Masafumi Toyama, eds.), Lecture Notes in Computer Science, vol. 5257, Springer, 2008, pp. 264-275.
• [14] A. Dennunzio, E. Formenti, and J. Provillard, Computational complexity of rule distributions of non-uniform cellular automata, LATA (Adrian Horia Dediu and Carlos Martín-Vide, eds.), Lecture Notes in Computer Science, vol. 7183, Springer, 2012, pp. 204-215.
• [15] A. Dennunzio, E. Formenti, and J. Provillard, Local rule distributions, language complexity and non-uniform cellular automata, Theoretical Computer Science (2012), In press.
• [16] A. Dennunzio, E. Formenti, and J. Provillard, Non-uniform cellular automata: Classes, dynamics, and decidability, Information and Computation 215 (2012), 32-46.
• [17] A. Dennunzio, P. Guillon, and B. Masson, Stable dynamics of sand automata, IFIP TCS (Giorgio Ausiello, Juhani Karhumäki, Giancarlo Mauri, and C.-H. Luke Ong, eds.), IFIP, vol. 273, Springer, 2008, pp. 157-169.
• [18] A. Dennunzio, P. Guillon, and B. Masson, Sand automata as cellular automata, Theoretical Computer Science 410 (2009), 3962-3974.
• [19] F. Farina and A. Dennunzio, A predator-prey cellular automaton with parasitic interactions and environmental effects, Fundamenta Informaticae 83 (2008), 337-353.
• [20] N. Fatès, M. Morvan, N. Schabanel, and E. Thierry, Fully asynchronous behaviour of double-quiescent elementary cellular automata, Theoretical Computer Science 362 (2006), 1-16.
• [21] J. E. Hopcroft and J. D. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979.
• [22] J. F. C. Kingman, Poisson processes, Oxford University Press, 1993.
• [23] P. Kůrka, E. Formenti, and A. Dennunzio, Asymptotic distribution of entry times in a cellular automaton with annihilating particles, Discrete Mathematics and Theoretical Computer Science AP (2012), 47-58.
• [24] J. Lee, S. Adachi, F. Peper, and S. Mashiko, Delay-insensitive computation in asynchronous cellular automata, J. Comput. Syst. Sci. 70 (2005), 201-220.
• [25] J. Lee, S. Adachi, F. Peper, and K. Morita, Asynchronous game of life, Physica D 194 (2004), 369-384.
• [26] K. Nakamura, Asynchronous cellular automata and their computational ability, Systems, Computers, Control 5 (1974), 58-66.
• [27] C. L. Nehaniv, Evolution in asynchronous cellular automata, Artificial Life VIII (2002), 65-73.
• [28] N. Ollinger, Universalities in cellular automata, Handbook of Natural Computing: Theory, Experiments, and Applications (G. Rozenberg et al., ed.), Springer, 2012.
• [29] D. Regnault, N. Schabanel, and E. Thierry, Progresses in the analysis of stochastic 2d cellular automata: A study of asynchronous 2d minority, Theoretical Computer Science 410 (2009), 4844-4855.
• [30] B. Schönfisch and A. de Roos, Synchronous and asynchronous updating in cellular automata, BioSystems 51 (1999), 123-143.
• [31] T. Worsch, A note on (intrinsically?) universal asynchronous cellular automata, Preprint, 2010