Search

Abelian cellular automata (CAs) are CAs which are group endomorphisms of the full group shift when endowing the alphabet with an abelian group structure. A CA randomizes an initial probability measure if its iterated images have weak*-convergence towards the uniform Bernoulli measure (the Haar measure in this setting). We are interested in structural phenomena, i.e., randomization for a wide class of initial measures (under some mixing hypotheses). First, we prove that an abelian CA randomizes in Cesàro mean if and only if it has no soliton, i.e., a non-zero finite configuration whose time evolution remains bounded in space. This characterization generalizes previously known sufficient conditions for abelian CAs with scalar or commuting coefficients. Second, we exhibit examples of strong randomizers, i.e., abelian CAs randomizing in simple convergence; this is the first proof of this behaviour to our knowledge. We show, however, that no CA with commuting coefficients can be strongly randomizing. Finally, we show that some abelian CAs achieve partial randomization without being randomizing: the distribution of short finite words tends to the uniform distribution up to some threshold, but this convergence fails for larger words. Again this phenomenon cannot happen for abelian CAs with commuting coefficients. [ABSTRACT FROM AUTHOR]

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]

This paper concerns μ -limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial μ -random configuration. More precisely, we investigate the computational complexity of these sets and of related decision problems. Main results: first, μ -limit sets can have a Σ 3 0 -hard language, second, they can contain only α -complex configurations, third, any non-trivial property concerning them is at least Π 3 0 -hard. We prove complexity upper bounds, study restrictions of these questions to particular classes of CA, and different types of (non-)convergence of the measure of a word during the evolution. [ABSTRACT FROM AUTHOR]