We study the dynamical behavior of additive D-dimensional ( 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 , i.e., additive CA in which the alphabet is the cyclic group and the local rules are linear combinations with coefficients in . 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 , i.e., with the local rule defined by matrices with elements in which, in turn, strictly contains the class of linear CA over . In order to further emphasize that finite abelian groups are more expressive than we prove that, contrary to what happens in , 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 . Moreover, we provide a first characterization of strong transitivity for additive CA which we suspect to be true also for the general case.

Dynamical behavior of additive cellular automata over finite abelian groups

Margara, Luciano
2020

Abstract

We study the dynamical behavior of additive D-dimensional ( 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 , i.e., additive CA in which the alphabet is the cyclic group and the local rules are linear combinations with coefficients in . 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 , i.e., with the local rule defined by matrices with elements in which, in turn, strictly contains the class of linear CA over . In order to further emphasize that finite abelian groups are more expressive than we prove that, contrary to what happens in , 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 . Moreover, we provide a first characterization of strong transitivity for additive CA which we suspect to be true also for the general case.
2020
Dennunzio, Alberto; Formenti, Enrico; Grinberg, Darij; Margara, Luciano
File in questo prodotto:
Eventuali allegati, non sono esposti

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/11585/774754
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 7
social impact