Cellular automata for the self-stabilisation of colourings and tilings - Archive ouverte HAL Access content directly
Book Sections Year : 2019

Cellular automata for the self-stabilisation of colourings and tilings

(1, 2) , (3, 1) , (4)


We examine the problem of self-stabilisation, as introduced by Dijkstra in the 1970's, in the context of cellular automata stabilising on k-colourings, that is, on infinite grids which are coloured with k distinct colours in such a way that adjacent cells have different colours. Suppose that for whatever reason (e.g., noise, previous usage, tampering by an adversary), the colours of a finite number of cells in a valid k-colouring are modified, thus introducing errors. Is it possible to reset the system into a valid k-colouring with only the help of a local rule? In other words, is there a cellular automaton which, starting from any finite perturbation of a valid k-colouring, would always reach a valid k-colouring in finitely many steps? We discuss the different cases depending on the number of colours, and propose some deterministic and probabilistic rules which solve the problem for k = 3. We also explain why the case k = 3 is more delicate. Finally, we propose some insights on the more general setting of this problem, passing from k-colourings to other tilings (subshifts of finite type).
Fichier principal
Vignette du fichier
FMT-SelfCorrectingCA-RP2019-hal (1).pdf (391.57 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-02159155 , version 1 (18-06-2019)
hal-02159155 , version 2 (26-11-2019)



Nazim A. Fatès, Irène Marcovici, Siamak Taati. Cellular automata for the self-stabilisation of colourings and tilings. Proceedings of RP 2019 (International Conference on Reachability Problems), Springer, pp.121-136, 2019, ⟨10.1007/978-3-030-30806-3_10⟩. ⟨hal-02159155v2⟩
131 View
319 Download



Gmail Facebook Twitter LinkedIn More