Freezing sandpiles and Boolean threshold networks: equivalence and complexity
From MaRDI portal
Publication:2020018
DOI10.1016/j.aam.2020.102161zbMath1505.68027arXiv2101.04204OpenAlexW3121017816MaRDI QIDQ2020018
Pedro Montealegre, Eric Goles Chacc, Kévin Perrot
Publication date: 23 April 2021
Published in: Advances in Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2101.04204
Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- The computational complexity of pattern formation
- Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
- The computational complexity of sandpiles
- Universality of the chip-firing game
- Universality in freezing cellular automata
- On the computational complexity of the freezing non-strict majority automata
- Sandpile models and lattices: a comprehensive survey
- The complexity of the majority rule on planar graphs
- On the complexity of two-dimensional signed majority cellular automata
- P-completeness of Cellular Automaton Rule 110
- A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton
- How Hard is it to Predict Sandpiles on Lattices? A Survey
- Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models
This page was built for publication: Freezing sandpiles and Boolean threshold networks: equivalence and complexity
