Coalescence in fully asynchronous elementary cellular automata

Jordina Francès de Mas 1, 2
2 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Cellular automata (CA) are discrete mathematical systems formed by a set of cells arranged in a regular fashion. Each of these cells is in a particular state and evolves according to a local rule depending on the state of the cells in its neighbourhood. In spite of their apparent simplicity, these dynamical systems are able to display a complex emerging behaviour, and the macroscopic structures they produce are not always predictable despite complete local knowledge. While studying the robustness of CA to the introduction of asynchronism in their updating scheme, a phenomenon called coalescence was observed for the first time: for some asynchronous CA, the application of the same local rule on any two di↵erent initial conditions following the same sequence of updates quickly led to the same non-trivial configuration. Afterwards, it was experimentally found that some CA would always coalesce whilst others would never coalesce, and that some of them exhibit a phase transition between a coalescing and non-coalescing behaviour. However, a formal explanation of non-trivial rapid coalescence has yet to be found, and this is the purpose of this project, where we try to characterise and explain this phenomenon both qualitatively and analytically. In particular, we analytically study trivial coalescence, find lower bounds for the coalescence time of ECA 154 and ECA 62, and give some first steps towards finding their upper bounds in order to prove that they have, respectively, quadratic and linear coalescence time.
Type de document :
Mémoires d'étudiants -- Hal-inria+
Cellular Automata and Lattice Gases [nlin.CG]. 2017
Liste complète des métadonnées

Littérature citée [54 références]  Voir  Masquer  Télécharger
Contributeur : Nazim Fatès <>
Soumis le : mercredi 1 novembre 2017 - 18:53:16
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : vendredi 2 février 2018 - 13:02:07


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


  • HAL Id : hal-01627454, version 1


Jordina Francès de Mas. Coalescence in fully asynchronous elementary cellular automata. Cellular Automata and Lattice Gases [nlin.CG]. 2017. 〈hal-01627454〉



Consultations de la notice


Téléchargements de fichiers