Séminaire Algorithmique : Solène Esnay (IMT, Univ. Toulouse 3) « Arithmetical Complexity of the Language of Generic Limit Sets of Cellular Automata »

Dynamical systems have various notions of attractor, and they characterize different asymptotic properties. Among them is the notion of generic attractor: a closed set that attracts most of the space in the topological sense, meaning its basin of attraction is comeager. The generic limit set is the smallest generic attractor and contained in all of them: all of the configurations in it are visited infinitely often or approached with arbitrary precision by a nonnegligible set of initial configurations.

In the context of (unidimensional) cellular automata, which are well-known and simple discrete dynamical systems, the generic limit set has an additional property: it is a subshift, that is, the set of all the configurations it contains can be entirely described by the alphabet of the automaton and a (possibly infinite) list of forbidden patterns that cannot appear. Cellular automata may still have complex generic limit sets in the arithmetical sense (Sigma 3 at worst), but some properties of the automaton (the existence of equicontinuity points) or of the generic limit set (minimality as an attractor or as a subshift, mixing properties) can lower that complexity.

This presentation is a detailed study of the complexity and structure of the attractor – and so, essentially, of the automaton as a consequence – as they are impacted by these various properties, in the same fashion as other articles do about other attractors (omega-limit set and mu-limit set).

This is a joint work with Alonso Nuñez and Ilkka Törmä.