|   | 
Details
   web
Records
Author Concha-Vega, P.; Goles, E.; Montealegre, P.; Rios-Wilson, M
Title On the Complexity of Stable and Biased Majority Type
Year 2022 Publication Mathematics Abbreviated Journal Mathematics
Volume 10 Issue 18 Pages 3408
Keywords cellular automata; majority rule; prediction problem
Abstract A majority automata is a two-state cellular automata, where each cell updates its state according to the most represented state in its neighborhood. A question that naturally arises in the study of these dynamical systems asks whether there exists an efficient algorithm that can be implemented in order to compute the state configuration reached by the system at a given time-step. This problem is called the prediction problem. In this work, we study the prediction problem for a more general setting in which the local functions can be different according to their behavior in tie cases. We define two types of local rules: the stable majority and biased majority. The first one remains invariant in tie cases, and the second one takes the value 1. We call this class the heterogeneous majority cellular automata (HMCA). For this latter class, we show that in one dimension, the prediction problem for HMCA is in NL as a consequence of the dynamics exhibiting a type of bounded change property, while in two or more dimensions, the problem is P-Complete as a consequence of the capability of the system of simulating Boolean circuits.
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 2227-7390 ISBN Medium
Area Expedition Conference
Notes WOS:000856736200001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1642
Permanent link to this record
 

 
Author Goles, E.; Montealegre, P.
Title The complexity of the asynchronous prediction of the majority automata Type
Year 2020 Publication Information and Computation Abbreviated Journal Inf. Comput.
Volume 274 Issue SI 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
Call Number UAI @ eduardo.moreno @ Serial 1124
Permanent link to this record
 

 
Author Goles, E.; Montealegre, P.; Rios-Wilson, M.
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
 

 
Author Goles, E.; Montealegre, P.; Salo, V.; Torma, I.
Title PSPACE-completeness of majority automata networks Type
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
Call Number UAI @ eduardo.moreno @ Serial 572
Permanent link to this record