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 Goles, E.; Lobos, F.; Ruz, G.A.; Sene, S. doi  openurl
  Title Attractor landscapes in Boolean networks with firing memory: a theoretical study applied to genetic networks Type
  Year 2020 Publication Natural Computing Abbreviated Journal Nat. Comput.  
  Volume 19 Issue 2 Pages 295-319  
  Keywords Discrete dynamical systems; Boolean networks; Biological network modeling  
  Abstract In this paper we study the dynamical behavior of Boolean networks with firing memory, namely Boolean networks whose vertices are updated synchronously depending on their proper Boolean local transition functions so that each vertex remains at its firing state a finite number of steps. We prove in particular that these networks have the same computational power than the classical ones, i.e. any Boolean network with firing memory composed of m vertices can be simulated by a Boolean network by adding vertices. We also prove general results on specific classes of networks. For instance, we show that the existence of at least one delay greater than 1 in disjunctive networks makes such networks have only fixed points as attractors. Moreover, for arbitrary networks composed of two vertices, we characterize the delay phase space, i.e. the delay values such that networks admits limit cycles or fixed points. Finally, we analyze two classical biological models by introducing delays: the model of the immune control of the lambda\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda $$\end{document}-phage and that of the genetic control of the floral morphogenesis of the plant Arabidopsis thaliana.  
  Address [Goles, Eric; Lobos, Fabiola; Ruz, Gonzalo A.] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: eric.chacc@uai.cl;  
  Corporate Author Thesis  
  Publisher Springer Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 1567-7818 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000531210800001 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 1139  
Permanent link to this record
 

 
Author Goles, E.; Montealegre, P.; Rios-Wilson, M. doi  openurl
  Title On The Effects Of Firing Memory In The Dynamics Of Conjunctive Networks Type
  Year 2020 Publication Discrete And Continuous Dynamical Systems Abbreviated Journal Discret. Contin. Dyn. Syst.  
  Volume 40 Issue 10 Pages 5765-5793  
  Keywords Discrete dynamical systems; boolean network; firing memory; conjunctive networks; prediction problem; and PSPACE  
  Abstract A boolean network is a map F : {0, 1}(n) -> {0, 1}(n) that defines a discrete dynamical system by the subsequent iterations of F. Nevertheless, it is thought that this definition is not always reliable in the context of applications, especially in biology. Concerning this issue, models based in the concept of adding asynchronicity to the dynamics were propose. Particularly, we are interested in a approach based in the concept of delay. We focus in a specific type of delay called firing memory and it effects in the dynamics of symmetric (non-directed) conjunctive networks. We find, in the caseis in which the implementation of the delay is not uniform, that all the complexity of the dynamics is somehow encapsulated in the component in which the delay has effect. Thus, we show, in the homogeneous case, that it is possible to exhibit attractors of non-polynomial period. In addition, we study the prediction problem consisting in, given an initial condition, determinate if a fixed coordinate will eventually change its state. We find again that in the non-homogeneous case all the complexity is determined by the component that is affected by the delay and we conclude in the homogeneous case that this problem is PSPACE-complete.  
  Address [Goles, Eric; Montealegre, Pedro] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Diagonal Torres 2650, Santiago, Chile, Email: eric.chacc@uai.cl;  
  Corporate Author Thesis  
  Publisher Amer Inst Mathematical Sciences-Aims Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 1078-0947 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000545661800006 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 1183  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: