2013/09/26 by Laurent Boyer, Boyer, Laurent, Martin Delacourt +7
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #cs.DM #cs.FL #nlin.CG #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1309.6730
41 pages
openalex publication_date 2013/09/26 · arxiv created 2015/06/22 · arxiv updated 2015/06/23 · openalex created_date 2022/10/07 · openalex updated_date 2026/07/28
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 Σ_30-hard language, second, they can contain only α-complex configurations, third, any non-trivial property concerning them is at least Π_30-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.