Computational complexity of threshold automata networks under different updating schemes
Goles
E
author
Montealegre
P
author
2014
English
Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the AND-OR rule (vertices take the AND or the OR logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs. (C) 2014 Elsevier B.V. All rights reserved.
Automata networks
Threshold functions
Computational complexity
Updating scheme
P-completeness
NC
NP-Hard
WOS:000347025300002
exported from refbase (show.php?record=434), last updated on Tue, 24 Feb 2015 19:06:15 -0300
text
files/434_Goles+Montealegre2014.pdf
10.1016/j.tcs.2014.09.010
Goles+Montealegre2014
Theoretical Computer Science
Theor. Comput. Sci.
2014
Elsevier Science Bv
continuing
periodical
academic journal
559
3
19
0304-3975