On the Complexity of Sandpile Prediction Problems
From MaRDI portal
Publication:2811962
DOI10.1016/j.entcs.2009.09.023zbMath1338.68188MaRDI QIDQ2811962
Carolina Mejia, Juan Andrés Montoya
Publication date: 9 June 2016
Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.entcs.2009.09.023
cellular automata; discrete dynamical systems; complexity classes; abelian sandpile model; graph automata; prediction tasks
68Q80: Cellular automata (computational aspects)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Abelian Logic Gates, Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models, On the complexity of sandpile critical avalanches
Cites Work
- Unnamed Item
- Chip-firing games on directed graphs
- Chip-firing games on graphs
- On the sandpile group of regular trees
- The computational complexity of sandpiles
- The computational complexity of one-dimensional sandpiles
- Self-organized criticality
- Polynomial Bound for a Chip Firing Game on Graphs
- One-Input-Face MPCVP Is Hard for L, But in LogDCFL
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science