-limit sets of cellular automata from a computational complexity perspective

DOI10.1016/J.JCSS.2015.05.004zbMATH Open1329.68178arXiv1309.6730OpenAlexW2095890038MaRDI QIDQ494067FDOQ494067

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)

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.

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

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 \(\mu\)-equicontinuous cellular automata
• Limit sets of stable cellular automata
• On the sofic limit sets of cellular automata
• Publication:4890460

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)

Cites Work

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

Cited In (13)

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