$\mu$-Limit Sets of Cellular Automata from a Computational Complexity Perspective

Autor:	Boyer, Laurent, Delacourt, Martin, Poupet, Victor, Sablik, Mathieu, Theyssier, Guillaume
Rok vydání:	2013
Předmět:	Computer Science - Discrete Mathematics Computer Science - Formal Languages and Automata Theory Nonlinear Sciences - Cellular Automata and Lattice Gases
Druh dokumentu:	Working Paper
Popis:	This paper concerns $\mu$-limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial $\mu$-random configuration. More precisely, we investigate the computational complexity of these sets and of related decision problems. Main results: first, $\mu$-limit sets can have a $\Sigma\_3^0$-hard language, second, they can contain only $\alpha$-complex configurations, third, any non-trivial property concerning them is at least $\Pi\_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. Comment: 41 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1309.6730 Zobrazit plný text záznamu View this record from Arxiv