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].

Dynamical behavior of additive cellular automata over finite abelian groups

Dennunzio A.
;
Formenti E.
;
2020

Abstract

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.
Articolo in rivista - Articolo scientifico
Additive cellular automata; Cellular automata; Symbolic dynamics;
English
20-giu-2020
2020
843
45
56
none
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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/295303
Citazioni
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 7
Social impact