On the complexity of two-dimensional signed majority cellular automata

DOI10.1016/j.jcss.2017.07.010zbMath1378.68116OpenAlexW2597319246MaRDI QIDQ2409572

Guillaume Theyssier, Eric Goles Chacc, Pedro Montealegre, Kévin Perrot

Publication date: 11 October 2017

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

Full work available at URL: https://doi.org/10.1016/j.jcss.2017.07.010

zbMATH Keywords

computational complexitycellular automata dynamicsintrinsic universalmajority cellular automatasigned two-dimensional latticeTuring universal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15)

Related Items

Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models ⋮ Two-dimensional rotation-symmetric number-conserving cellular automata ⋮ On the complexity of the stability problem of binary freezing totalistic cellular automata ⋮ The complexity of the asynchronous prediction of the majority automata ⋮ Unnamed Item ⋮ Freezing sandpiles and Boolean threshold networks: equivalence and complexity ⋮ Eric Goles ⋮ The mirage of universality in cellular automata ⋮ Sandpile toppling on Penrose tilings: identity and isotropic dynamics

Cites Work

• The complexity of the bootstraping percolation and other problems
• Bulking I: An abstract theory of bulking
• Bulking II: Classifications of cellular automata
• Communication complexity and intrinsic universality in cellular automata
• Four states are enough!
• Planar and grid graph reachability problems
• Quasilinear cellular automata
• Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority
• Decreasing energy functions as a tool for studying threshold networks
• Periodic behaviour of generalized threshold functions
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• The complexity of the majority rule on planar graphs
• Theory of computation.
• P-completeness of Cellular Automaton Rule 110
• Maximum period of 2-dimensional uniform neural networks
• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• Intrinsic universality in tile self-assembly requires cooperation
• On Local Symmetries and Universality in Cellular Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of two-dimensional signed majority cellular automata