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.2019.68
URN: urn:nbn:de:0030-drops-110126
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11012/
Dennunzio, Alberto ;
Formenti, Enrico ;
Grinberg, Darij ;
Margara, Luciano
Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties
Abstract
We study the dynamical behavior of D-dimensional (D >= 1) additive cellular automata where the alphabet is any finite abelian group. This class of discrete time dynamical systems is a generalization of the systems extensively studied by many authors among which one may list [Masanobu Ito et al., 1983; Giovanni Manzini and Luciano Margara, 1999; Giovanni Manzini and Luciano Margara, 1999; Jarkko Kari, 2000; Gianpiero Cattaneo et al., 2000; Gianpiero Cattaneo et al., 2004]. Our main contribution is the proof that topologically transitive additive cellular automata are ergodic. This result represents a solid bridge between the world of measure theory and that of topology theory and greatly extends previous results obtained in [Gianpiero Cattaneo et al., 2000; Giovanni Manzini and Luciano Margara, 1999] for linear CA over Z_m i.e. additive CA in which the alphabet is the cyclic group Z_m and the local rules are linear combinations with coefficients in Z_m. In our scenario, the alphabet is any finite abelian group and the global rule is any additive map. This class of CA strictly contains the class of linear CA over Z_m^n, i.e. , with the local rule defined by n x n matrices with elements in Z_m which, in turn, strictly contains the class of linear CA over Z_m. In order to further emphasize that finite abelian groups are more expressive than Z_m we prove that, contrary to what happens in Z_m, there exist additive CA over suitable finite abelian groups which are roots (with arbitrarily large indices) of the shift map.
As a consequence of our results, we have that, for additive CA, ergodic mixing, weak ergodic mixing, ergodicity, topological mixing, weak topological mixing, topological total transitivity and topological transitivity are all equivalent properties. As a corollary, we have that invertible transitive additive CA are isomorphic to Bernoulli shifts. Finally, we provide a first characterization of strong transitivity for additive CA which we suspect it might be true also for the general case.
BibTeX - Entry
@InProceedings{dennunzio_et_al:LIPIcs:2019:11012,
author = {Alberto Dennunzio and Enrico Formenti and Darij Grinberg and Luciano Margara},
title = {{Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {68:1--68:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-117-7},
ISSN = {1868-8969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11012},
URN = {urn:nbn:de:0030-drops-110126},
doi = {10.4230/LIPIcs.MFCS.2019.68},
annote = {Keywords: Cellular Automata, Symbolic Dynamics, Complex Systems}
}
|
Keywords: |
|
Cellular Automata, Symbolic Dynamics, Complex Systems |
|
Collection: |
|
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
20.08.2019 |
