Freezing sandpiles and Boolean threshold networks: equivalence and complexity

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

Mathematics Subject Classification ID

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)

A shape theorem for exploding sandpiles

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