A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton

DOI10.1007/978-3-319-44365-2_16zbMath1392.68274OpenAlexW2507569123MaRDI QIDQ4571178

Pedro Montealegre, Eric Goles Chacc

Publication date: 6 July 2018

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-44365-2_16

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Cellular automata (computational aspects) (68Q80)

Related Items (3)

Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata ⋮ Freezing sandpiles and Boolean threshold networks: equivalence and complexity ⋮ Sandpile toppling on Penrose tilings: identity and isotropic dynamics

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of the bootstraping percolation and other problems
• Computational complexity of threshold automata networks under different updating schemes
• Crossing information in two-dimensional sandpiles
• PSPACE-completeness of majority automata networks
• Decreasing energy functions as a tool for studying threshold networks
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• The computational complexity of sandpiles
• Universality of the chip-firing game
• The complexity of the majority rule on planar graphs
• SAND PILE AS A UNIVERSAL COMPUTER

This page was built for publication: A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton