2026-07-23T17:33:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6978 2024-03-06T10:39:14Z ddc:004 open_access

On the Synchronisation Problem over Cellular Automata Richard, Gaétan cellular automata dynamical systems aperiodic tiling synchronisation Cellular automata are a discrete, synchronous, and uniform dynamical system that give rise to a wide range of dynamical behaviours. In this paper, we investigate whether this system can achieve synchronisation. We study the cases of classical bi-infinite configurations, periodic configurations, and periodic configurations of prime period. In the two former cases, we prove that only a "degenerated" form of synchronisation - there exists a fix-point - is possible. In the latter case, we give an explicit construction of a cellular automaton for which any periodic configuration of prime period eventually converges to cycle of two uniform configurations. Our construction is based upon sophisticated tools: aperiodic NW-deterministic tilings and partitioned intervals. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gaétan Richard 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.54 urn:nbn:de:0030-drops-69780 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.54 eng https://creativecommons.org/licenses/by/3.0/legalcode