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.ICALP.2020.125
URN: urn:nbn:de:0030-drops-125321
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12532/
Go to the corresponding LIPIcs Volume Portal

Dennunzio, Alberto ; Formenti, Enrico ; Grinberg, Darij ; Margara, Luciano

From Linear to Additive Cellular Automata

pdf-format:
LIPIcs-ICALP-2020-125.pdf (0.5 MB)

Abstract

This paper proves the decidability of several important properties of additive cellular automata over finite abelian groups. First of all, we prove that equicontinuity and sensitivity to initial conditions are decidable for a nontrivial subclass of additive cellular automata, namely, the linear cellular automata over ?ⁿ, where ? is the ring ℤ/mℤ. The proof of this last result has required to prove a general result on the powers of matrices over a commutative ring which is of interest in its own.
Then, we extend the decidability result concerning sensitivity and equicontinuity to the whole class of additive cellular automata over a finite abelian group and for such a class we also prove the decidability of topological transitivity and all the properties (as, for instance, ergodicity) that are equivalent to it. Finally, a decidable characterization of injectivity and surjectivity for additive cellular automata over a finite abelian group is provided in terms of injectivity and surjectivity of an associated linear cellular automata over ?ⁿ.

BibTeX - Entry

@InProceedings{dennunzio_et_al:LIPIcs:2020:12532,
  author =	{Alberto Dennunzio and Enrico Formenti and Darij Grinberg and Luciano Margara},
  title =	{{From Linear to Additive Cellular Automata}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{125:1--125:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12532},
  URN =		{urn:nbn:de:0030-drops-125321},
  doi =		{10.4230/LIPIcs.ICALP.2020.125},
  annote =	{Keywords: Cellular Automata, Decidability, Symbolic Dynamics}
}

Keywords: Cellular Automata, Decidability, Symbolic Dynamics
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI