A study of stochastic 2D Minority CA : would wearing stripes be a fatality for snob people ?

Abstract : Cellular automata are usually associated with synchronous deterministic dynamics, and their asynchronous or stochastic versions have been far less studied although relevant for modeling purposes. The study of their asynchronous dynamics is all the more needed that their asynchronous behaviors are drastically different from their synchronous ones. This paper analyzes the dynamics of a two-dimensional cellular automaton, 2D Minority, under fully asynchronous dynamics, where only one random cell updates at each time step. This cellular automaton is of particular interest in computer science, biology or social science for instance, and already presents a rich variety of behaviors although the apparent simplicity of its transition rule. In particular, it captures some important features, like the emergence of striped patterns, which are common, according to experiments, to other important automata, such as Game of Life. In this paper, we present a mathematical analysis of the first steps and the last steps of the asynchronous dynamics of 2D Minority. Our results are based on the definition of an interaction energy and rely on the analysis of the dynamics of the borders between competing regions. Our results are a first step towards a complete analysis of this stochastic cellular automaton. Many questions remain open: in particular describing mathematically the middle part of the evolution of 2D Minority where many regions compete with each other, or defining similar parameters (energy, borders,...) for other automata (such as Game of Life) that present similarities with 2D Minority in their asynchronous behaviors.
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

Contributeur : Eric Thierry <>
Soumis le : mardi 10 avril 2007 - 16:18:57
Dernière modification le : mardi 16 janvier 2018 - 15:34:13
Document(s) archivé(s) le : mercredi 7 avril 2010 - 03:15:46


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


  • HAL Id : ensl-00140883, version 1



Eric Thierry, Damien Regnault, Nicolas Schabanel. A study of stochastic 2D Minority CA : would wearing stripes be a fatality for snob people ?. Research Report (RR) n°2007-16. 2007. 〈ensl-00140883〉



Consultations de la notice


Téléchargements de fichiers