English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper concerns $\mu$-limit sets of cellular automata: sets ofconfigurations made of words whose probability to appear does not vanish withtime, starting from an initial $\mu$-random configuration. More precisely, weinvestigate the computational complexity of these sets and of related decisionproblems. Main results: first, $\mu$-limit sets can have a $\Sigma\_3^0$-hardlanguage, second, they can contain only $\alpha$-complex configurations, third,any non-trivial property concerning them is at least $\Pi\_3^0$-hard. We provecomplexity upper bounds, study restrictions of these questions to particularclasses of CA, and different types of (non-)convergence of the measure of aword during the evolution.

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