Home | << 1 >> |
![]() |
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 |