Pre-expansivity in cellular automata (Q2306015): Difference between revisions

In this present paper, the authors work on cellular automata defined over a finitely generated group. The authors introduce a new dynamical property called pre-expansivity that both generalizes positive expansivity and refines pre-injectivity. They show that pre-expansivity is weaker than positive expansivity. Then the authors prove that abelian cellular automata are always predictable in logarithmic space complexity. Some preliminary results about pre-expansivity and \(k\)-expansivity are given. They show that the notions of \(k\)-expansivity, pre-expansivity and positive expansivity all differ and interact differently with properties of bijectivity and surjectivity. Then the authors present examples of pre-expansive CAs which are not positively expansive. The hierarchy of expansive-like properties is studied. By considering the free group, the authors prove that \(k\)-expansivity is possible for infinitely many values of \(k\) although positive expansivity is impossible. Finally, the authors study cellular automata on the lattice \(\mathbf{Z}^{n}\), with \(n\geq 2\). They prove that no abelian CA of dimension \(n\geq 2\) is pre-expansive. Also, they prove that the rule \(\oplus_2\) with von Neumann neighborhood in \(\mathbf{Z}^{2}\) is 1-expansive, 3-expansive but not \(2k\)-expansive for every \(k\in \mathbf{N}\). Some open questions concerning pre-expansivity and \(k\)-expansivity are presented.