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 [36, 43, 44, 40, 12, 11]. 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 [12, 43] for linear CA over ℤm i.e. additive CA in which the alphabet is the cyclic group ℤm and the local rules are linear combinations with coefficients in ℤ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 ℤnm, i.e., with the local rule defined by n × n matrices with elements in ℤm which, in turn, strictly contains the class of linear CA over ℤm. In order to further emphasize that finite abelian groups are more expressive than ℤm we prove that, contrary to what happens in ℤ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.

Additive cellular automata over finite abelian groups: Topological and measure theoretic properties

Margara L.
2019

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 [36, 43, 44, 40, 12, 11]. 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 [12, 43] for linear CA over ℤm i.e. additive CA in which the alphabet is the cyclic group ℤm and the local rules are linear combinations with coefficients in ℤ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 ℤnm, i.e., with the local rule defined by n × n matrices with elements in ℤm which, in turn, strictly contains the class of linear CA over ℤm. In order to further emphasize that finite abelian groups are more expressive than ℤm we prove that, contrary to what happens in ℤ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.
Leibniz International Proceedings in Informatics, LIPIcs
1
15
Dennunzio A.; Formenti E.; Grinberg D.; Margara L.
File in questo prodotto:
File Dimensione Formato  
LIPIcs-MFCS-2019-68.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 512.12 kB
Formato Adobe PDF
512.12 kB Adobe PDF Visualizza/Apri

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: http://hdl.handle.net/11585/713281
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact