toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Records Links
Author Goles, E.; Montealegre, P.; Rios-Wilson, M. doi  openurl
  Title On The Effects Of Firing Memory In The Dynamics Of Conjunctive Networks Type Journal Article
  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 no  
  Call Number UAI @ eduardo.moreno @ Serial 1183  
Permanent link to this record
 

 
Author Goles, E.; Montealegre, P. doi  openurl
  Title The complexity of the asynchronous prediction of the majority automata Type Journal Article
  Year 2020 Publication Information and Computation Abbreviated Journal Inform. Comput.  
  Volume to appear Issue Pages  
  Keywords Majority automata; Cellular automata; Prediction problem; Asynchronous updating; Computational complexity; Parallel algorithms; Bootstrap percolation; NP-Completeness  
  Abstract We consider the asynchronous prediction problem for some automaton as the one consisting in determining, given an initial configuration, if there exists a non-zero probability that some selected site changes its state, when the network is updated picking one site at a time uniformly at random. We show that for the majority automaton, the asynchronous prediction problem is in NC in the two-dimensional lattice with von Neumann neighborhood. Later, we show that in three or more dimensions the problem is NP-Complete.  
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0890-5401 ISBN Medium  
  Area Expedition Conference  
  Notes Approved no  
  Call Number UAI @ eduardo.moreno @ Serial 1124  
Permanent link to this record
 

 
Author Goles, E.; Montealegre, P.; Salo, V.; Torma, I. pdf  doi
openurl 
  Title PSPACE-completeness of majority automata networks Type Journal Article
  Year 2016 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.  
  Volume 609 Issue Pages 118-128  
  Keywords Boolean network; Majority network; Prediction problem; PSPACE  
  Abstract We study the dynamics of majority automata networks when the vertices are updated according to a block sequential updating scheme. In particular, we show that the complexity of the problem of predicting an eventual state change in some vertex, given an initial configuration, is PSPACE-complete. (C) 2015 Elsevier B.V. All rights reserved.  
  Address [Goles, Eric] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: eric.chacc@uai.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:000367488400009 Approved no  
  Call Number UAI @ eduardo.moreno @ Serial 572  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: