toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Record Links
Author (up) Formenti, E.; Goles, E.; Martin, B. pdf  doi
openurl 
  Title Computational Complexity of Avalanches in the Kadanoff Sandpile Model Type Journal Article
  Year 2012 Publication Fundamenta Informaticae Abbreviated Journal Fundam. Inform.  
  Volume 115 Issue 1 Pages 107-124  
  Keywords Kadanoff Sandpile Model; Bak Sandpile Model; Sandpiles Models; Complexity; Discrete Dynamical Systems; Self-Organized Criticality (SOC)  
  Abstract This paper investigates the avalanche problem AP for the Kadanoff sandpile model (KSPM). We prove that (a slight restriction of) AP is in NC1 in dimension one, leaving the general case open. Moreover, we prove that AP is P-complete in dimension two. The proof of this latter result is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with an initial sand distribution in KSPM. These results are also related to the known prediction problem for sandpiles which is in NC1 for one-dimensional sandpiles and P-complete for dimension 3 or higher. The computational complexity of the prediction problem remains open for the Bak's model of two-dimensional sandpiles.  
  Address [Formenti, Enrico] Univ Nice Sophia Antipolis, I3S, UMR CNRS 6070, F-06903 Sophia Antipolis, France, Email: enrico.formenti@unice.fr  
  Corporate Author Thesis  
  Publisher Ios Press Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0169-2968 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000302777200008 Approved no  
  Call Number UAI @ eduardo.moreno @ Serial 208  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: