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 metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Nazim Fatès Connect in order to contact the contributor
Submitted on : Tuesday, November 26, 2019 - 4:05:18 PM
Last modification on : Friday, February 4, 2022 - 3:32:51 AM


Files produced by the author(s)



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⟩



Record views


Files downloads