Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.54
URN: urn:nbn:de:0030-drops-69780
URL: https://drops.dagstuhl.de/opus/volltexte/2017/6978/
Richard, Gaétan
On the Synchronisation Problem over Cellular Automata
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{richard:LIPIcs:2017:6978,
author = {Ga{\'e}tan Richard},
title = {{On the Synchronisation Problem over Cellular Automata}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {54:1--54:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-028-6},
ISSN = {1868-8969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6978},
URN = {urn:nbn:de:0030-drops-69780},
doi = {10.4230/LIPIcs.STACS.2017.54},
annote = {Keywords: cellular automata, dynamical systems, aperiodic tiling, synchronisation}
}
| Keywords: | cellular automata, dynamical systems, aperiodic tiling, synchronisation | |
| Seminar: | 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 06.03.2017 |
