On the complexity of sandpile prediction problems

DOI10.1016/J.ENTCS.2009.09.023MaRDI QIDQ2811962zbMATH OpenOpenAlexFDO

Authors Carolina Mejía, J. Andres 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

abelian sandpile modelcellular automatacomplexity classesdiscrete dynamical systemsgraph automataprediction tasks

Mathematics Subject Classification ID

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

Recommendations

• How hard is it to predict sandpiles on lattices? A survey
• The computational complexity of one-dimensional sandpiles
• New Computational Paradigms
• The computational complexity of sandpiles
• Freezing sandpiles and Boolean threshold networks: equivalence and complexity

Cites work

• Chip-firing games on directed graphs
• Chip-firing games on graphs
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 1059167 (Why is no real title available?)
• On the sandpile group of regular trees
• One-Input-Face MPCVP Is Hard for L, But in LogDCFL
• Polynomial Bound for a Chip Firing Game on Graphs
• Self-organized criticality
• The computational complexity of one-dimensional sandpiles
• The computational complexity of sandpiles

Cited in

(11)

• Freezing sandpiles and Boolean threshold networks: equivalence and complexity
• The computational complexity of one-dimensional sandpiles
• Modelling the LLL Algorithm by Sandpiles
• Sandpile prediction on a tree in near linear time
• How hard is it to predict sandpiles on lattices? A survey
• Abelian logic gates
• On the complexity of sandpile critical avalanches
• Computational Complexity of the Avalanche Problem on One Dimensional Kadanoff Sandpiles
• New Computational Paradigms
• Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models
• Prediction of large events in directed sandpiles

This page was built for publication: On the complexity of sandpile prediction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811962)