Paper Info
Title
Remarks on the cellular automaton global synchronisation problem: deterministic versus 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 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).
Year
DOI
Venue
2019
10.1007/s11047-018-9683-0
Natural Computing
Keywords
Field
DocType
Inverse problems,Synchronisation of complex systems,Stochastic cellular automata,SAT solvers
Cellular automaton,Discrete mathematics,Applied mathematics,Quadratic growth,Periodic boundary conditions,Inverse problem,Initial value problem,Stochastic modelling,Stochastic cellular automaton,Mathematics,Randomness
Journal
Volume
Issue
ISSN
18
3
1572-9796
Citations 
PageRank 
References 
1
0.35
10
Authors
1
Name
Order
Citations
PageRank
Nazim Fatès121225.31