1. Pre-expansivity in cellular automata.
- Author
-
Gajardo, A., Nesme, V., and Theyssier, G.
- Subjects
- *
CELLULAR automata , *FREE groups - Abstract
We introduce the notion of pre-expansivity for cellular automata (CA): it is the property of being positively expansive on asymptotic pairs of configurations (i.e. configurations that differ in only finitely many positions). Pre-expansivity therefore lies between positive expansivity and pre-injectivity, two important notions of CA theory. We show that there exist one-dimensional pre-expansive CAs which are not positively expansive and they can be chosen reversible (while positive expansivity is impossible for reversible CAs). We provide both linear and non-linear examples. In the one-dimensional setting, we also show that pre-expansivity implies sensitivity to initial conditions in any direction. We show however that no two-dimensional Abelian CA can be pre-expansive. We also consider the finer notion of k -expansivity (positive expansivity over pairs of configurations with exactly k differences) and show examples of linear CA in dimension 2 and on the free group that are k -expansive depending on the value of k , whereas no (positively) expansive CA exists in this setting. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF