License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.12
URN: urn:nbn:de:0030-drops-127206
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12720/
Béaur, Pierre ;
Kari, Jarkko
Decidability in Group Shifts and Group Cellular Automata
Abstract
Many undecidable questions concerning cellular automata are known to be decidable when the cellular automaton has a suitable algebraic structure. Typical situations include linear cellular automata where the states come from a finite field or a finite commutative ring, and so-called additive cellular automata in the case the states come from a finite commutative group and the cellular automaton is a group homomorphism. In this paper we generalize the setup and consider so-called group cellular automata whose state set is any (possibly non-commutative) finite group and the cellular automaton is a group homomorphism. The configuration space may be any subshift that is a subgroup of the full shift and still many properties are decidable in any dimension of the cellular space. Decidable properties include injectivity, surjectivity, equicontinuity, sensitivity and nilpotency. Non-transitivity is semi-decidable. It also turns out that the the trace shift and the limit set can be effectively constructed, that injectivity always implies surjectivity, and that jointly periodic points are dense in the limit set. Our decidability proofs are based on developing algorithms to manipulate arbitrary group shifts, and viewing the set of space-time diagrams of group cellular automata as multidimensional group shifts.
BibTeX - Entry
@InProceedings{baur_et_al:LIPIcs:2020:12720,
author = {Pierre B{\'e}aur and Jarkko Kari},
title = {{Decidability in Group Shifts and Group Cellular Automata}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {12:1--12:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12720},
URN = {urn:nbn:de:0030-drops-127206},
doi = {10.4230/LIPIcs.MFCS.2020.12},
annote = {Keywords: group cellular automata, group shifts, symbolic dynamics, decidability}
}
|
Keywords: |
|
group cellular automata, group shifts, symbolic dynamics, decidability |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
