Rencontres autour des Automates Cellulaires Probabilistes
Organisateurs : Jean Mairesse et Irène Marcovici (LIAFA, Université Paris Diderot - Paris 7)
Avec le soutien de l'ANR MAGNUM.
L'objectif de ces journées est de rassembler la communauté française (cotés informatique, mathématiques discrètes, probabilités) travaillant sur les ACP, en abordant les deux aspects : modèles synchrones où les transitions sont probabilistes, et modèles déterministes itérés à partir de configurations initiales aléatoires.
Déjeuner (buffet dans la même salle)
Pause
Pause
Déjeuner (buffet dans la même salle)
Jeudi 10 janvier 2013
Le comportement asymptotique d'un automate cellulaire itéré sur une configuration tirée suivant une mesure de probabilité initiale est bien décrit par sa mesure limite dans une certaine topologie. Quels ensembles de mesures peuvent être ainsi obtenus, partant d'une mesure simple, comme ensembles de valeurs d'adhérence ? Nous avons d'abord des contraintes nécessaires en termes de calculabilité. Ajoutant à notre alphabet des états auxiliaires de calcul pour simuler des machines de Turing de manière contrôlée, nous parvenons à obtenir effectivement tous ces ensembles sous une hypothèse de connexité supplémentaire. Les corollaires intéressants incluent un résultat d'indécidabilité (théorème de Rice) sur les mesures limite d'un automate cellulaire.
Probabilistic Cellular Automata are CA whose updating rule is stochastic. They can be considered as Markov stochastic process or more precisely interacting particle systems whose dynamical evolution is a discrete-time one. Their specificity lies in the synchronous evolution. We will concentrate on a special class of reversible dynamics (detailed balance holds) coming from the parallelisation of the Ising Gibbs sampler. The main questions we address are : what is the influence of the synchronous updating scheme on the stationary measures, how are the dynamics for a finite family of interacting entities related to the one with infinitely-many interacting elements.
We introduce a class of interacting particle systems with Glauber-like dynamics in which the creation/destruction of a particle can occur only if the configuration satisfies some local constraints. These models, known as Kinetically Constrained Models (KCM), are currently used in physics to model liquid/glass transition. We will explain the connection among the anomalous glassy dynamics of KCM's and the properties of properly devised bootstrap percolation-like cellular automata. We will in particular discuss a KCM which undergoes at a critical density an ergodicity breaking transition corresponding to the percolation transition of the corresponding bootstrap-like automaton.
En 1952, Turing propose un mécanisme pour expliquer la formation d'organes différenciés à
partir d'un ensemble homogène de cellules [1]. Ce mécanisme fait intervenir des interactions simples
entre cellules à l'aide de substances "abstraites", les morphogènes, qui activent ou inhibent
leur propre synthèse et se diffusent aux cellules voisines. Turing montre que ce modèle permet d'observer
une "brisure de symétrie", à savoir que partant d'un état global statistiquement
homogène, d'infimes différences microscopiques sont amplifiées jusqu'à produire un motif stable,
observable au niveau macroscopique.
Nous cherchons à identifier de tels phénomènes au niveau des automates cellulaires déterministes
et stochastiques. Quelles sont les règles qui permettent d'observer ces brisures de symétrie ?
Quels sont les types de bruit (asynchronisme, transitions aléatoires, défauts de topologie)
qui peuvent produire ou modifier ces phénomènes ? Comment analyser de tels systèmes ?
C'est ce que nous proposons d'examiner dans une étude préliminaire qui n'est qu'une préparation
à un travail plus approfondi.
[1] The Chemical basis of morphogenesis, Phil. Trans. R. Soc. Lond. B 14 August 1952 vol. 237 no. 641 37-72
Nous considérons une classe d'automates cellulaires possédant une propriété d'érosion, comme par exemple le modèle de la majorité nord-est-centre de Toom. Les automates cellulaires probabilistes qui résultent d'une perturbation stochastique de ceux-ci présentent une transition de phase. En effet, lorsque le bruit est suffisamment faible, il existe plusieurs mesures stationnaires. Dans ce régime de faible bruit, nous étudions la convergence vers l'un des équilibres extrémaux et la décroissance des corrélations.
La biologie s'intéresse de plus en plus aux systèmes dynamiques discrets pour simuler des phénomènes naturels à base de modèles simples. Mais la robustesse de ces modèles est-elle bien prise en compte ? A titre d'exemple, nous présentons un modèle ergodique d'automate cellulaire de gaz sur réseau simulant un essaim de particules. En décrivant la dynamique sous forme de comportements métastables, nous montrons que leur observation est fortement influencée sur des longs temps de simulation par la définition de la grille cellulaire considérée.
Vendredi 11 janvier 2013
A faulty cellular automata is a special case of a probabilistic cellular automata: each cell of a faulty automaton behaves like a deterministic one randomly perturbed by some random noise. We will discuss several approaches to implementing stable computations in the framework of faulty automata. We will survey the techniques proposed by Andrei Toom and Peter Gacs, their advantages and limits.
Les automates cellulaires stochastiques ou non-déterministes sont souvent étudiés à travers des exemples ou aspects particuliers (alpha-asynchronisme, automates bruités, transitions locales probabilistes, etc). Nous proposons au contraire de formaliser les automates cellulaires stochastiques ou non-déterministes dans un modèle général qui se prête à une étude systématique. Partant de là nous abordons deux problématiques importantes largement développées dans la théorie des automates cellulaires déterministes : les simulations et l'universalité intrinsèque d'une part, la décidabilité des propriétés globales en fonction des descriptions locales d'autre part.
Dans cet exposé, nous présenterons la dynamique asynchrone où à chaque pas de temps, un sous-ensemble de cellules choisies aléatoirement sont mises à jour selon la règle de l'automate, les autres cellules ne changent pas d'état. Nous récapitulerons les résultats obtenus sur cette dynamique et démontrerons l'existence d'une transition de phase dans un automate cellulaire asynchrone en dimension 1.
Un animal dirigé A sur le réseau carré est une partie de N^2 contenant l'origine 0, et telle que chaque point de A peut-être atteint depuis 0 en restant à l'intérieur de A, uniquement par des pas (0,1) ou (1,0). Le cardinal de A s'appelle l'aire de A, et l'ensemble des sommets de N^2 que l'on peut ajouter à A sans lui faire perdre sa qualité d'animal dirigé (AD), s'appelle le périmètre de A. On s'intéresse a la question du calcul de la série génératrice G(x, y) des AD sur réseau carré selon l'aire et le périmètre. Il s'agit d'une question centrale dans l'étude des AD, très directement liée au problème de la percolation dirigée, pour laquelle le seuil critique, qui est sup {p : G( p,1-p)=1}, est inconnu (alors qu'il existe de nombreuses méthodes pour calculer G(x,1)). Dans cet exposé, nous montrons l'équivalence entre le calcul de G et le calcul d'une solution à un système quadratique dont les inconnues sont des matrices (équations relativement proches de celles apparaissant pour le TASEP). Incapable de résoudre ce problème, nous montrons que des matrices infinies obtenues comme point fixe d'un système de type "système de réécriture", sont "solutions naturelles" de ce problème quadratique. Trouver un vecteur propre pour l'une d'elle, devrait permettre de calculer G...