Directed Percolation arising in Stochastic Cellular Automata

Abstract : Cellular automata are both seen as a model of computation and as tools to model real life systems. Historically they were studied under synchronous dynamics where all the cells of the system are updated at each time step. Meanwhile the question of probabilistic dynamics emerges: on the one hand, to develop cellular automata which are capable of reliable computation even when some random errors occur; on the other hand, because synchronous dynamics is not a reasonable assumption to simulate real life systems. Among cellular automata a specific class was largely studied in synchronous dynamics : the elementary cellular automata (ECA). These are the "simplest" cellular automata. Nevertheless they exhibit complex behaviors and even Turing universality. Several studies have focused on this class under alpha-asynchronous dynamics where each cell has a probability alpha to be updated independently. It has been shown that some of these cellular automata exhibit interesting behavior such as phase transition when the asynchronicity rate alpha varies. Due to their richness of behavior, probabilistic cellular automata are also very hard to study. Almost nothing is known of their behavior. Understanding these "simple" rules is a key step to analyze more complex systems. We present here a coupling between oriented percolation and ECA 178 and confirms previous observations that percolation may arise in cellular automata. As a consequence this coupling shows that there is a positive probability that the ECA 178 does not reach a stable configuration with positive probability as soon as the initial configuration is not a stable configuration and alpha > 0.996. Experimentally, this result seems to stay true as soon as alpha > alpha_c where alpha_c is almost 0.5.
Type de document :
Pré-publication, Document de travail
RR2008-12. 12 pages. 2008
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger
Contributeur : Damien Regnault <>
Soumis le : mercredi 26 mars 2008 - 15:59:50
Dernière modification le : mardi 24 avril 2018 - 13:52:23
Document(s) archivé(s) le : vendredi 28 septembre 2012 - 11:45:29


Fichiers produits par l'(les) auteur(s)


  • HAL Id : ensl-00267169, version 1



Damien Regnault. Directed Percolation arising in Stochastic Cellular Automata. RR2008-12. 12 pages. 2008. 〈ensl-00267169〉



Consultations de la notice


Téléchargements de fichiers