CI²MA - Publicaciones | Prepublicaciones

Pre-Publicación 2016-06

Anahi Gajardo, Vincent Nesme, Guillaume Theyssier:

Pre-expansivity in cellular automata


We introduce the property of pre-expansivity for cellular automata (CA): it is the property of being expansive on asymptotic pairs of configurations (i.e. configurations that differ in only finitely many positions). Pre-expansivity therefore lies between 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. We show however that no bi-dimensional CA which is linear over an Abelian group can be pre-expansive. We also consider the finer notion of k-expansivity (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.

Descargar en formato PDF PDF

Esta prepublicacion dio origen a la(s) siguiente(s) publicación(es) definitiva(s):

Anahi GAJARDO, Vincent NESME, Guillaume THEYSSIER: Pre-expansivity in cellular automata. Theoretical Computer Science, vol. 816, pp. 37-66, (2020).