On the complexity of two-dimensional signed majority cellular automata

DOI10.1016/J.JCSS.2017.07.010MaRDI QIDQ2409572zbMATH OpenOpenAlexFDO

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

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) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Recommendations

• Majority-vote cellular automata, Ising dynamics, and P-completeness
• The complexity of the majority rule on planar graphs
• The complexity of the asynchronous prediction of the majority automata
• On local symmetries and universality in cellular automata
• PSPACE-completeness of majority automata networks

Cites work

• scientific article; zbMATH DE number 3141365 (Why is no real title available?)
• scientific article; zbMATH DE number 4085579 (Why is no real title available?)
• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Bulking I: An abstract theory of bulking
• Bulking II: Classifications of cellular automata
• Communication complexity and intrinsic universality in cellular automata
• Decreasing energy functions as a tool for studying threshold networks
• Four states are enough!
• Intrinsic universality in tile self-assembly requires cooperation
• Majority-vote cellular automata, Ising dynamics, and P-completeness
• Maximum period of 2-dimensional uniform neural networks
• On local symmetries and universality in cellular automata
• P-completeness of Cellular Automaton Rule 110
• Periodic behaviour of generalized threshold functions
• Planar and grid graph reachability problems
• Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority
• Quasilinear cellular automata
• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• The complexity of the bootstraping percolation and other problems
• The complexity of the majority rule on planar graphs
• Theory of computation.

Cited in

(14)

• Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models
• The Structure of Configurations in One-Dimensional Majority Cellular Automata: From Cell Stability to Configuration Periodicity
• \(\sigma\)-game, \(\sigma ^{+}\)-game and two-dimensional additive cellular automata
• Majority-vote cellular automata, Ising dynamics, and P-completeness
• Freezing sandpiles and Boolean threshold networks: equivalence and complexity
• The complexity of the majority rule on planar graphs
• scientific article; zbMATH DE number 1462667 (Why is no real title available?)
• The mirage of universality in cellular automata
• 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
• Eric Goles
• Three-dimensional rotation-symmetric number-conserving cellular automata
• Sandpile toppling on Penrose tilings: identity and isotropic dynamics

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

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