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 / Dennunzio, Alberto; Formenti, Enrico; Grinberg, Darij; Margara, Luciano. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 843:(2020), pp. 45-56. [10.1016/j.tcs.2020.06.021]

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
Dynamical behavior of additive cellular automata over finite abelian groups / Dennunzio, Alberto; Formenti, Enrico; Grinberg, Darij; Margara, Luciano. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 843:(2020), pp. 45-56. [10.1016/j.tcs.2020.06.021]
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