We study the dynamical behavior of additive D-dimensional (D≥1) 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 [38,44,41]. Among our major contributions, there is the proof that topologically transitive additive D-dimensional cellular automata over a finite abelian group are ergodic. This result represents a solid bridge between the world of measure theory and that of topology and greatly extends previous results obtained in [12,44] for linear CA over Z/mZ, i.e., additive CA in which the alphabet is the cyclic group Z/mZ and the local rules are linear combinations with coefficients in Z/mZ. 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/mZ)n, i.e., with the local rule defined by n×n matrices with elements in Z/mZ which, in turn, strictly contains the class of linear CA over Z/mZ. In order to further emphasize that finite abelian groups are more expressive than Z/mZ we prove that, contrary to what happens in Z/mZ, there exist additive CA over suitable finite abelian groups which are roots (with arbitrarily large indices) of the shift map. As a relevant consequence of our results, we have that, for additive D-dimensional CA over a finite abelian group, 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 see that invertible transitive additive CA are isomorphic to Bernoulli shifts. Furthermore, we prove that surjectivity implies openness for additive D-dimensional CA over a finite abelian group. Hence, we get that topological transitivity is equivalent to the well-known Devaney notion of chaos when D=1. Moreover, we provide a first characterization of strong transitivity for additive CA which we suspect to be true also for the general case.
Dennunzio, A., Formenti, E., Grinberg, D., & Margara, L. (2020). Dynamical behavior of additive cellular automata over finite abelian groups. THEORETICAL COMPUTER SCIENCE, 843, 45-56 [10.1016/j.tcs.2020.06.021].
|Citazione:||Dennunzio, A., Formenti, E., Grinberg, D., & Margara, L. (2020). Dynamical behavior of additive cellular automata over finite abelian groups. THEORETICAL COMPUTER SCIENCE, 843, 45-56 [10.1016/j.tcs.2020.06.021].|
|Tipo:||Articolo in rivista - Articolo scientifico|
|Carattere della pubblicazione:||Scientifica|
|Presenza di un coautore afferente ad Istituzioni straniere:||Si|
|Titolo:||Dynamical behavior of additive cellular automata over finite abelian groups|
|Autori:||Dennunzio, A; Formenti, E; Grinberg, D; Margara, L|
DENNUNZIO, ALBERTO (Corresponding)
FORMENTI, ENRICO (Corresponding)
|Data di pubblicazione:||2020|
|Rivista:||THEORETICAL COMPUTER SCIENCE|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/j.tcs.2020.06.021|
|Appare nelle tipologie:||01 - Articolo su rivista|