P-completeness of Cellular Automaton Rule 110
From MaRDI portal
Publication:3613755
DOI10.1007/11786986_13zbMath1223.68072OpenAlexW1580526823MaRDI QIDQ3613755
Publication date: 12 March 2009
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11786986_13
Cellular automata (computational aspects) (68Q80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (33)
The Complexity of Small Universal Turing Machines: A Survey ⋮ Unraveling simplicity in elementary cellular automata ⋮ Universal Sleptsov net ⋮ On the complexity of two-dimensional signed majority cellular automata ⋮ Communication complexity and intrinsic universality in cellular automata ⋮ Four states are enough! ⋮ Abstract geometrical computation. IV: Small Turing universal signal machines ⋮ A simple P-complete problem and its language-theoretic representations ⋮ On the complex behavior of simple tag systems -- an experimental approach ⋮ Communication complexity meets cellular automata: necessary conditions for intrinsic universality ⋮ Building squares with optimal state complexity in restricted active self-assembly ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Computational Complexity of Spiking Neural P Systems ⋮ Distributed Multi-authority Attribute-Based Encryption Using Cellular Automata ⋮ Chaos emerged on the ‘edge of chaos’ ⋮ Tag systems and Collatz-like functions ⋮ Rule set design problems for oritatami systems ⋮ Parallel Computation Using Active Self-assembly ⋮ Parallel computation using active self-assembly ⋮ Topological chaos of universal elementary cellular automata rule ⋮ Bulking II: Classifications of cellular automata ⋮ A one-dimensional physically universal cellular automaton ⋮ Freezing sandpiles and Boolean threshold networks: equivalence and complexity ⋮ Elementary cellular automaton Rule 110 explained as a block substitution system. Rule 110 as a block substitution system ⋮ Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy ⋮ The complexity of small universal Turing machines: A survey ⋮ On the complexity of asynchronous freezing cellular automata ⋮ Average-Case Completeness in Tag Systems ⋮ Emulating cellular automata in chemical reaction-diffusion networks ⋮ The mirage of universality in cellular automata ⋮ On fungal automata ⋮ Freezing, Bounded-Change and Convergent Cellular Automata
This page was built for publication: P-completeness of Cellular Automaton Rule 110
