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

摘要

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 n×n matrices over L having the same characteristic polynomial, it holds that the set {A0,A1,A2,…} is finite if and only if the set {B0,B1,B2,…} is finite too.