toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Record Links
Author (up) Concha-Vega, P.; Goles, E.; Montealegre, P.; Rios-Wilson, M doi  openurl
  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
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: