Skip to Main content Skip to Navigation
Book sections

Cellular automata for the self-stabilisation of colourings and tilings

Abstract : 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).
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-02159155
Contributor : Nazim Fatès <>
Submitted on : Tuesday, November 26, 2019 - 4:05:18 PM
Last modification on : Thursday, March 5, 2020 - 3:28:11 PM

File

FMT-SelfCorrectingCA-RP2019-ha...
Files produced by the author(s)

Identifiers

Collections

Citation

Nazim 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), pp.121-136, 2019, ⟨10.1007/978-3-030-30806-3_10⟩. ⟨hal-02159155v2⟩

Share

Metrics

Record views

78

Files downloads

198