toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Record Links
Author (up) 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
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: