Back to Search
Start Over
μ-Limit sets of cellular automata from a computational complexity perspective.
- Source :
-
Journal of Computer & System Sciences . Dec2015, Vol. 81 Issue 8, p1623-1647. 25p. - Publication Year :
- 2015
-
Abstract
- 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 Σ 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 81
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 109107465
- Full Text :
- https://doi.org/10.1016/j.jcss.2015.05.004