-limit sets of cellular automata from a computational complexity perspective

DOI10.1016/J.JCSS.2015.05.004MaRDI QIDQ494067zbMATHOpenAlexFDO

Authors Laurent Boyer, Martin Delacourt, Victor Poupet, Mathieu Sablik, Guillaume Theyssier

Publication date 31 August 2015

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.6730

zbMATH Keywords

computational complexitycellular automataarithmetical hierarchy\(\mu\)-limit setsRice theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80)

Abstract: 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 $Sigm{a}_3^0$-hard language, second, they can contain only $alpha$-complex configurations, third, any non-trivial property concerning them is at least $P{i}_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.

Recommendations

• Complexity of generic limit sets of cellular automata
• On the Limit Sets of Cellular Automata
• On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures
• Construction of \(\mu\)-limit sets of two-dimensional cellular automata
• On the limit set of some universal cellular automata
• Rice's theorem for \(\mu \)-limit sets of cellular automata
• Limit behaviour of -equicontinuous cellular automata
• Limit sets of stable cellular automata
• On the sofic limit sets of cellular automata
• Publication:4890460

Cites work

• scientific article; zbMATH DE number 4138816 (Why is no real title available?)
• scientific article; zbMATH DE number 4070371 (Why is no real title available?)
• scientific article; zbMATH DE number 2042127 (Why is no real title available?)
• A Search Algorithm for the Maximal Attractor of a Cellular Automaton
• An Introduction to Symbolic Dynamics and Coding
• Attractors in cellular automata
• Classical recursion theory. Vol. II
• Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
• Languages, equicontinuity and attractors in cellular automata
• Lexicographic compositions and de Bruijn sequences
• Limit sets of cellular automata associated to probability measures
• On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures
• On the sofic limit sets of cellular automata
• Rice's theorem for \(\mu \)-limit sets of cellular automata
• Rice's theorem for the limit sets of cellular automata
• The Nilpotency Problem of One-Dimensional Cellular Automata

Cited in

(13)

• Probability and algorithmics: a focus on some recent developments
• The complexity of limit languages of cellular automata: An example
• Construction of \(\mu\)-limit sets of two-dimensional cellular automata
• On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures
• Characterisation of limit measures of higher-dimensional cellular automata
• Cellular automata and bootstrap percolation
• Characterizing asymptotic randomization in abelian cellular automata
• Complexity of generic limit sets of cellular automata
• Computational aspects of cellular automata on countable sofic shifts
• Arithmetical complexity of the language of generic limit sets of cellular automata
• Cold dynamics in cellular automata: a tutorial
• Rice's theorem for \(\mu \)-limit sets of cellular automata
• Limit behaviour of \(\mu\)-equicontinuous cellular automata

This page was built for publication: \(\mu\)-limit sets of cellular automata from a computational complexity perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494067)