Martin Delacourt
Universidad de Chile
https://www.univ-orleans.fr/lifo/Members/delacourt/
Date(s) : 15/04/2014 iCal
11 h 00 min - 12 h 00 min
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 Σ03-hard language, second, they can contain only 𝛼-complex configurations, third, any non-trivial property concerning them is at least Π03-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.
https://hal.archives-ouvertes.fr/hal-00866094v2/
Séminaire IMDB du LIF : http://www.lif.univ-mrs.fr/evenements/id/76
Catégories