On the Complexity of Sandpile Prediction Problems

DOI10.1016/j.entcs.2009.09.023zbMath1338.68188OpenAlexW2023776926MaRDI 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

zbMATH Keywords

cellular automatadiscrete dynamical systemscomplexity classesabelian sandpile modelgraph automataprediction tasks

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models ⋮ On the complexity of sandpile critical avalanches ⋮ Abelian Logic Gates

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

This page was built for publication: On the Complexity of Sandpile Prediction Problems