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.

Dennunzio, A., Formenti, E., Grinberg, D., Margara, L. (2019). Additive cellular automata over finite abelian groups: Topological and measure theoretic properties. In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.MFCS.2019.68].

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

Dennunzio, A
;
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.
paper
Cellular automata; Complex systems; Symbolic dynamics;
Cellular automata; Complex systems; Symbolic dynamics
English
44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019
2019
44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019
9783959771177
2019
138
68
reserved
Dennunzio, A., Formenti, E., Grinberg, D., Margara, L. (2019). Additive cellular automata over finite abelian groups: Topological and measure theoretic properties. In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.MFCS.2019.68].
File in questo prodotto:
File Dimensione Formato  
LIPIcs-MFCS-2019-68.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 508.73 kB
Formato Adobe PDF
508.73 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/248345
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
Social impact