Self-stabilisation of cellular automata on tilings

Given a finite set of local constraints, we seek a cellular automaton (i.e.,a local and uniform algorithm) that self-stabilises on the configurations thatsatisfy these constraints. More precisely, starting from a finite perturbationof a valid configuration, the cellular automaton must eventually fall back intothe space of valid configurations where it remains still. We allow the cellularautomaton to use extra symbols, but in that case, the extra symbols can alsoappear in the initial finite perturbation. For several classes of localconstraints (e.g., $k$-colourings with $k\neq 3$, and North-East deterministicconstraints), we provide efficient self-stabilising cellular automata with orwithout additional symbols that wash out finite perturbations in linear orquadratic time, but also show that there are examples of local constraints forwhich the self-stabilisation problem is inherently hard. We note that theoptimal self-stabilisation speed is the same for all local constraints that areisomorphic to one another. We also consider probabilistic cellular automatarules and show that in some cases, the use of randomness simplifies theproblem. In the deterministic case, we show that if finite perturbations arecorrected in linear time, then the cellular automaton self-stabilises evenstarting from a random perturbation of a valid configuration, that is, whenerrors in the initial configuration occur independently with a sufficiently lowdensity.Comment: 56 pages, 28 figure