Remarks on the cellular automaton global synchronisation problem – deterministic vs. stochastic models

Nazim Fatès 1
1 MOCQUA - Designing the Future of Computational Models
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In the global synchronisation problem, one is asked to find a cellular automaton which has the property that every initial condition evolves into a homogeneous blinking state. We study this simple inverse problem for the case of one-dimensional systems with periodic boundary conditions. Two paradoxical observations are made: (a) despite the apparent simplicity of finding rules with good statistical results, there exist no perfect deterministic solutions to this problem, (b) if we allow the use of randomness in the local rule, constructing ``perfect" stochastic solutions is easy. For the stochastic case, we give some rules for which the mean time of synchronisation varies quadratically with the number of cells and ask if this result can be improved. To explore more deeply the deterministic rules, we code our problem as a SAT problem and USE SAT solvers to find rules that synchronise a large set of initial conditions (in appendix).
Type de document :
Article dans une revue
Natural Computing, Springer Verlag, In press, 〈10.1007/s11047-018-9683-0〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01653631
Contributeur : Nazim Fatès <>
Soumis le : lundi 9 avril 2018 - 18:04:23
Dernière modification le : vendredi 9 novembre 2018 - 01:09:55

Fichier

hal-CA-globalSynchProblem-Fate...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Nazim Fatès. Remarks on the cellular automaton global synchronisation problem – deterministic vs. stochastic models. Natural Computing, Springer Verlag, In press, 〈10.1007/s11047-018-9683-0〉. 〈hal-01653631v2〉

Partager

Métriques

Consultations de la notice

170

Téléchargements de fichiers

42