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 Kn, where K is the ring Z/mZ. 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 Kn,.

Dennunzio, A., Formenti, E., Grinberg, D., Margara, L. (2020). From linear to additive cellular automata. In International Colloquium on Automata, Languages, and Programming, ICALP 2020. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.ICALP.2020.125].

From linear to additive cellular automata

Dennunzio A.
;
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 Kn, where K is the ring Z/mZ. 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 Kn,.
paper
Cellular Automata; Decidability; Symbolic Dynamics
English
International Colloquium on Automata, Languages, and Programming, ICALP 2020
2020
International Colloquium on Automata, Languages, and Programming, ICALP 2020
9783959771382
2020
168
125
none
Dennunzio, A., Formenti, E., Grinberg, D., Margara, L. (2020). From linear to additive cellular automata. In International Colloquium on Automata, Languages, and Programming, ICALP 2020. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.ICALP.2020.125].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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