toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Records Links
Author Formenti, E.; Goles, E.; Martin, B. pdf  doi
openurl 
  Title Computational Complexity of Avalanches in the Kadanoff Sandpile Model Type
  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  
  Call Number UAI @ eduardo.moreno @ Serial 208  
Permanent link to this record
 

 
Author Gajardo, A.; Goles, E. pdf  doi
openurl 
  Title Crossing information in two-dimensional Sandpiles Type
  Year 2006 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.  
  Volume 369 Issue 1-3 Pages 463-469  
  Keywords Sandpile; discrete dynamical system; cellular automata; calculability; complexity  
  Abstract We prove that in a two-dimensional Sandpile automaton, embedded in a regular infinite planar cellular space, it is impossible to cross information, if the bit of information is the presence (or absence) of an avalanche. This proves that it is impossible to embed arbitrary logical circuits in a Sandpile through quiescent configurations. Our result applies also for the non-planar neighborhood of Moore. Nevertheless, we also show that it is possible to compute logical circuits with a two-dimensional Sandpile, if a neighborhood of radius two is used in Z(2); crossing information becomes possible in that case, and we conclude that for this neighborhood the Sandpde is P-complete and Turing universal. (c) 2006 Elsevier B.V. All rights reserved.  
  Address Univ Adolfo Ibanez, Santiago, Chile, Email: anahi@ing-mat.udec.cl  
  Corporate Author Thesis  
  Publisher Elsevier Science Bv Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0304-3975 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000242765000035 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 34  
Permanent link to this record
 

 
Author Goles, E.; Tsompanas, M.A.; Adamatzky, A.; Tegelaar, M.; Wosten, H.A.B.; Martinez, G.J. doi  openurl
  Title Computational universality of fungal sandpile automata Type
  Year 2020 Publication Physics Letters A Abbreviated Journal Phys. Lett. A  
  Volume 384 Issue 22 Pages 8 pp  
  Keywords Fungi; Sandpile automata; Computational universality  
  Abstract Hyphae within the mycelia of the ascomycetous fungi are compartmentalised by septa. Each septum has a pore that allows for inter-compartmental and inter-hyphal streaming of cytosol and even organelles. The compartments, however, have special organelles, Woronin bodies, that can plug the pores. When the pores are blocked, no flow of cytoplasm takes place. Inspired by the controllable compartmentalisation within the mycelium of the ascomycetous fungi we designed two-dimensional fungal automata. A fungal automaton is a cellular automaton where communication between neighbouring cells can be blocked on demand. We demonstrate computational universality of the fungal automata by implementing sandpile cellular automata circuits there. We reduce the Monotone Circuit Value Problem to the Fungal Automaton Prediction Problem. We construct families of wires, cross-overs and gates to prove that the fungal automata are P-complete. (C) 2020 Elsevier B.V. All rights reserved.  
  Address [Goles, Eric; Tsompanas, Michail-Antisthenis; Adamatzky, Andrew; Martinez, Genaro J.] Univ West England, Unconvent Comp Lab, Bristol, Avon, England, Email: andrew.adamatzky@uwe.ac.uk  
  Corporate Author Thesis  
  Publisher Elsevier Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0375-9601 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000537033500017 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 1194  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: