We provide an efficiently computable characterization of two important properties describing stable and unstable complex behaviours as equicontinuity and sensitivity to the initial conditions for one-dimensional linear cellular automata (LCA) over (Z/mZ)^n. We stress that the setting of LCA over (Z/mZ)^n with n>1 is more expressive, it gives rise to much more complex dynamics, and it is more difficult to deal with than the already investigated case n=1. Indeed, in order to get our result we need to prove a nontrivial result of abstract algebra: if K is any finite commutative ring and L is any K-algebra, then for every pair A, B of nxn matrices over L having the same characteristic polynomial, it holds that the set {A^0,A^1,A^2,...} is finite if and only if the set {B^0,B^1,B^2,...} is finite too.

An efficiently computable characterization of stability and instability for linear cellular automata

Margara, Luciano
2021

Abstract

We provide an efficiently computable characterization of two important properties describing stable and unstable complex behaviours as equicontinuity and sensitivity to the initial conditions for one-dimensional linear cellular automata (LCA) over (Z/mZ)^n. We stress that the setting of LCA over (Z/mZ)^n with n>1 is more expressive, it gives rise to much more complex dynamics, and it is more difficult to deal with than the already investigated case n=1. Indeed, in order to get our result we need to prove a nontrivial result of abstract algebra: if K is any finite commutative ring and L is any K-algebra, then for every pair A, B of nxn matrices over L having the same characteristic polynomial, it holds that the set {A^0,A^1,A^2,...} is finite if and only if the set {B^0,B^1,B^2,...} is finite too.
2021
Dennunzio, Alberto; Formenti, Enrico; Grinberg, Darij; Margara, Luciano
File in questo prodotto:
File Dimensione Formato  
revised.pdf

accesso aperto

Tipo: Postprint
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione 338.79 kB
Formato Adobe PDF
338.79 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/827095
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 3
social impact