This paper proves the decidability of several important properties of additive cellular automata over finite abelian groups. First of all, we prove that equicontinuity and sensitivity to initial conditions are decidable for a nontrivial subclass of additive cellular automata, namely, the linear cellular automata over ⁿ, where is the ring ℤ/mℤ. The proof of this last result has required to prove a general result on the powers of matrices over a commutative ring which is of interest in its own. Then, we extend the decidability result concerning sensitivity and equicontinuity to the whole class of additive cellular automata over a finite abelian group and for such a class we also prove the decidability of topological transitivity and all the properties (as, for instance, ergodicity) that are equivalent to it. Finally, a decidable characterization of injectivity and surjectivity for additive cellular automata over a finite abelian group is provided in terms of injectivity and surjectivity of an associated linear cellular automata over ⁿ.

Alberto Dennunzio, Enrico Formenti, Darij Grinberg, Luciano Margara (2020). From Linear to Additive Cellular Automata [10.4230/lipics.icalp.2020.125].

From Linear to Additive Cellular Automata

Luciano Margara
2020

Abstract

This paper proves the decidability of several important properties of additive cellular automata over finite abelian groups. First of all, we prove that equicontinuity and sensitivity to initial conditions are decidable for a nontrivial subclass of additive cellular automata, namely, the linear cellular automata over ⁿ, where is the ring ℤ/mℤ. The proof of this last result has required to prove a general result on the powers of matrices over a commutative ring which is of interest in its own. Then, we extend the decidability result concerning sensitivity and equicontinuity to the whole class of additive cellular automata over a finite abelian group and for such a class we also prove the decidability of topological transitivity and all the properties (as, for instance, ergodicity) that are equivalent to it. Finally, a decidable characterization of injectivity and surjectivity for additive cellular automata over a finite abelian group is provided in terms of injectivity and surjectivity of an associated linear cellular automata over ⁿ.
2020
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
1
13
Alberto Dennunzio, Enrico Formenti, Darij Grinberg, Luciano Margara (2020). From Linear to Additive Cellular Automata [10.4230/lipics.icalp.2020.125].
Alberto Dennunzio; Enrico Formenti; Darij Grinberg; Luciano Margara
File in questo prodotto:
File Dimensione Formato  
LIPIcs-ICALP-2020-125.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 515.71 kB
Formato Adobe PDF
515.71 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: https://hdl.handle.net/11585/763464
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact