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

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 binary or multi-state systems with periodic boundary conditions. The examination of the problem raises two paradoxical observations: (a) despite the apparent simplicity of finding rules with good statistical results, there exist no perfect deterministic solutions to this problem, and (b) if we allow the use of randomness in the local rule, constructing " perfect " stochastic solutions is easy. To go further on the deterministic case, experimental work is carried out with SAT solvers to find the rules that achieve the synchronisation of the largest sets of initial conditions. 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.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01653631
Contributeur : Nazim Fatès <>
Soumis le : vendredi 1 décembre 2017 - 16:30:08
Dernière modification le : jeudi 11 janvier 2018 - 06:25:24

Fichier

article-GlobalSynchAC-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01653631, version 1

Collections

Citation

Nazim Fatès. Remarks on the cellular automaton global synchronisation problem – deterministic vs. stochastic models. 2017. 〈hal-01653631〉

Partager

Métriques

Consultations de la notice

70

Téléchargements de fichiers

13