Ensembles limites d’automates cellulaires associés à une mesure de probabilité

Martin Delacourt
Universidad de Chile
https://www.univ-orleans.fr/lifo/Members/delacourt/

Date(s) : 15/04/2014 iCal
11h00 - 12h00

Limit sets of cellular automata associated with a probability measure

μ-Limit Sets of Cellular Automata from a Computational Complexity Perspective

This talk 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.