Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | Vol. 126, nr 2-3 | 121--156
Tytuł artykułu

Stochastic Cellular Automata: Correlations : Decidability and Simulations

Wybrane pełne teksty z tego czasopisma
Warianty tytułu
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.
Wydawca

Rocznik
Strony
121--156
Opis fizyczny
Bibliogr. 33 poz.
Twórcy
autor
  • Université de Grenoble (LIG, UMR 5217), France, pablo.arrighi@imag.fr
  • Université de Lyon (LIP, UMR 5668), France
  • CNRS, Université Paris Diderot (LIAFA, UMR 7089), France, schabanel@liafa.fr
  • Université de Lyon (IXXI), 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-4ef555f1-6d7d-4a87-8e45-cda96927be2a
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.