Stochastic Cellular Automata: Correlations : Decidability and Simulations

• Autorzy: Arrighi, P. , Schabanel, N. , Theyssier, G.
• Języki publikacji: EN

Abstrakty

EN

This paper introduces a simple formalism for dealing with deterministic, non-deterministic and stochastic cellular automata in an unified and composable manner. This formalism allows for local probabilistic correlations, a feature which is not present in usual definitions. We show that this feature allows for strictly more behaviors (for instance, number conserving stochastic cellular automata require these local probabilistic correlations). We also show that several problems which are deceptively simple in the usual definitions, become undecidable when we allow for local probabilistic correlations, even in dimension one. Armed with this formalism, we extend the notion of intrinsic simulation between deterministic cellular automata, to the non-deterministic and stochastic settings. Although the intrinsic simulation relation is shown to become undecidable in dimension two and higher, we provide explicit tools to prove or disprove the existence of such a simulation between any two given stochastic cellular automata. Those tools rely upon a characterization of equality of stochastic global maps, shown to be equivalent to the existence of a stochastic coupling between the random sources. We apply them to prove that there is no universal stochastic cellular automaton. Yet we provide stochastic cellular automata achieving optimal partial universality, as well as a universal non-deterministic cellular automaton.

Słowa kluczowe

EN

stochastic analysis; cellular automata; correlation; decidability; computer simulation; probability theory

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 126, nr 2-3
• Strony: 121--156
• Opis fizyczny: Bibliogr. 33 poz.

Twórcy

autor

Arrighi, P.

• Université de Grenoble (LIG, UMR 5217), France,
• Université de Lyon (LIP, UMR 5668), France

autor

Schabanel, N.

• CNRS, Université Paris Diderot (LIAFA, UMR 7089), France,
• Université de Lyon (IXXI), France

autor

Theyssier, G.

• CNRS, Université de Savoie (LAMA, UMR 5127), France,

Bibliografia

• [1] Arrighi, P., Fargetton, R., Nesme, V., Thierry, E.: Applying Causality Principles to the Axiomatization of Probabilistic Cellular Automata, CiE, 2011.
• [2] Arrighi, P., Grattage, J.: Intrinsically universal n-dimensional quantum cellular automata, J. of Computer and Systems Sciences, to appear., 2009.
• [3] Busic, A., Mairesse, J., Marcovici, I.: Probabilistic cellular automata, invariant measures, and perfect sampling, 2010, Pre-print arXiv:1010.3133.
• [4] Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups, Springer, 2010.
• [5] Delorme, M., Mazoyer, J., Ollinger, N., Theyssier, G.: Bulking I: An abstract theory of bulking, Theor. Comput. Sci., 412(30), 2011, 3866-3880.
• [6] Delorme, M., Mazoyer, J., Ollinger, N., Theyssier, G.: Bulking II: Classifications of cellular automata, Theor. Comput. Sci., 412(30), 2011, 3881-3905.
• [7] Durand, B., Formenti, E., Roka, Z.: Number-conserving cellular automata I: decidability, Theor. Comput. Sci., 1-3(299), 2003, 523-535.
• [8] Fates, N.: Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision, Proceedings of STACS, to appear in Lecture Notes in Computer Science, Springer, 2011.
• [9] Fates, N., Regnault, D., Schabanel, N., Thierry, E.: Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata, LATIN, 2006.
• [10] Finkel, O.: On Decidability Properties of One-Dimensional Cellular Automata, J. Cellular Automata, 6(2-3), 2011, 181-193.
• [11] Formenti, E., Grange, A.: Number conserving cellular automata II: dynamics, Theor. Comput. Sci., 1-3(304), 2003, 269-290.
• [12] Formenti, E., Kari, J., Taati, S.: The Most General Conservation Law for a Cellular Automaton, CSR, 2008.
• [13] Fuks, H.: Probabilistic cellular automata with conserved quantities, Nonlinearity, 17(4), 2004, 159-174.
• [14] Gacs, P.: Reliable cellular automata with self-organization, Journal of Statistical Physics, 103(1), 2001, 45-267.
• [15] Gimbert, H., Oualhadj, Y.: Probabilistic Automata on Finite Words: Decidable and Undecidable Problems, ICALP (2), 2010.
• [16] Hedlund, G. A.: Endormorphisms and automorphisms of the shift dynamical system, Mathematical Systems Theory, 3, 1969, 320-375.
• [17] Hodgson, B. R.: Decidabilite par automate fini, Annales Scientifiques de Mathématiques du Québec, 7(1), 19833, 39-57.
• [18] Kari, J.: Reversibility and Surjectivity Problems of Cellular Automata, J. Comput. Syst. Sci., 48(1), 1994, 149-182.
• [19] Kurka, P.: Topological and symbolic dynamics, Societe Mathematique de France, 2003.
• [20] Kuich, W., Vogler, H., Droste, M.: Handbook of Weighted Automata, Springer, 2009.
• [21] Kuske, D.: Theories of Automatic Structures and Their Complexity, CAI, 2009.
• [22] Maruoka, A., Kimura, M.: Condition for Injectivity of Global Maps for Tessellation Automata, Information and Control, 32, 1976, 158-162.
• [23] Ollinger, N.: Automates cellulaires : structures, Ph.D. Thesis, Ecole Normale Superieure de Lyon, 2002.
• [24] Ollinger, N.: The Quest for Small Universal Cellular Automata, ICALP, 2002.
• [25] Ollinger, N.: Universalities in cellular automata a (short) survey, JAC, 2008.
• [26] Ollinger, N., Richard, G.: Four states are enough!, Theor. Comput. Sci., 412(1-2), 2011, 22-32.
• [27] Pivato, M.: Ergodic Theory of Cellular Automata, in: Encyclopedia of Complexity and Systems Science, 2009, 2980-3015.
• [28] Rapaport, I.: Inducing an order on cellular automata by a grouping operation, Ph.D. Thesis, Ecole Normale Superieure de Lyon, 1998.
• [29] Regnault, D., Schabanel, N., Thierry, E.: Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority, Theoretical Computer Science, 410(47-49), 2009, 4844-4855.
• [30] Sutner, K.: Model Checking One-Dimensional Cellular Automata, J. Cellular Automata, 4(3), 2009, 213224.
• [31] Sutner, K.: Cellular Automata, Decidability and Phasespace, Fundam. Inform., 104(1-2), 2010, 141-160.
• [32] Theyssier, G.: Automates cellulaires : un modèle de complexités, Ph.D. Thesis, Ecole Normale Superieure de Lyon, 2005.
• [33] Toom, A.: Cellular automata with errors: Problems for students of probability, Topics in Contemporary Probability and Its Applications, 1995, 117-157.