Cellular Automata for the Self-stabilisation of Colourings and Tilings
Cellular Automata for the Self-stabilisation of Colourings and Tilings
复制标题
用于着色和平铺自稳定的元胞自动机
DOI：
10.1007/978-3-030-30806-3_10
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Siamak Taati
中科院分区：
文献类型：
--
作者：
Nazim Fatès;Irène Marcovici;Siamak Taati
我们研究了自稳定问题，如Dijkstra在1970年代引入的，在细胞自动机稳定墨水着色的背景下，也就是说，在无限网格上用不同的颜色着色，这样相邻的细胞就有不同的颜色。假设由于某种原因（例如，噪声、以前的使用、对手的篡改），有效着色中有限数量的单元格的颜色被修改，从而引入错误。是否有可能仅借助局部规则就将系统重置为有效的着色？换句话说，是否存在一个元胞自动机，从有效着色的任何有限扰动开始，总是在有限多个步骤中达到有效着色？我们讨论了不同颜色数量的情况，并提出了一些确定性和概率规则来解决这一问题。我们还解释了为什么这种情况更微妙。最后，我们对这个问题的更一般的设置提出了一些见解，从k-着色传递到其他平铺（有限类型的子移位）。
We examine the problem of self-stabilisation, as introduced by Dijkstra in the 1970’s, in the context of cellular automata stabilising onk-colourings, that is, on infinite grids which are coloured withkdistinct 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 validk-colouring are modified, thus introducing errors. Is it possible to reset the system into a validk-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 validk-colouring, would always reach a validk-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. We also explain why the caseis more delicate. Finally, we propose some insights on the more general setting of this problem, passing fromk-colourings to other tilings (subshifts of finite type).