|   | 
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.
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