\(\mu\)-limit sets of cellular automata from a computational complexity perspective
From MaRDI portal
Publication:494067
DOI10.1016/j.jcss.2015.05.004zbMath1329.68178arXiv1309.6730OpenAlexW2095890038MaRDI QIDQ494067
Mathieu Sablik, Guillaume Theyssier, Martin Delacourt, Victor Poupet, Laurent Boyer
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
Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80)
Related Items
Cellular automata and bootstrap percolation ⋮ Characterisation of limit measures of higher-dimensional cellular automata ⋮ Cold dynamics in cellular automata: a tutorial ⋮ Arithmetical complexity of the language of generic limit sets of cellular automata ⋮ Probability and algorithmics: a focus on some recent developments ⋮ Characterizing asymptotic randomization in abelian cellular automata
Cites Work
- Lexicographic compositions and de Bruijn sequences
- Classical recursion theory. Vol. II
- Rice's theorem for the limit sets of cellular automata
- Rice’s Theorem for μ-Limit Sets of Cellular Automata
- A Search Algorithm for the Maximal Attractor of a Cellular Automaton
- Attractors in cellular automata
- The Nilpotency Problem of One-Dimensional Cellular Automata
- Languages, equicontinuity and attractors in cellular automata
- On the sofic limit sets of cellular automata
- An Introduction to Symbolic Dynamics and Coding
- Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
- On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures
- Limit sets of cellular automata associated to probability measures
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: \(\mu\)-limit sets of cellular automata from a computational complexity perspective