Title | ||
---|---|---|
An efficiently computable characterization of stability and instability for linear cellular automata |
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 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. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1016/j.jcss.2021.06.001 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
Cellular automata,Linear cellular automata,Decidability,Complex systems | Journal | 122 |
ISSN | Citations | PageRank |
0022-0000 | 0 | 0.34 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
alberto dennunzio | 1 | 318 | 38.17 |
Enrico Formenti | 2 | 400 | 45.55 |
darij grinberg | 3 | 13 | 3.65 |
Luciano Margara | 4 | 367 | 46.16 |