Computational complexity of threshold automata networks under different updating schemes

Goles, E.; Montealegre, P

Abstract

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.

Más información

Título según WOS: Computational complexity of threshold automata networks under different updating schemes
Título según SCOPUS: Computational complexity of threshold automata networks under different updating schemes
Título de la Revista: THEORETICAL COMPUTER SCIENCE
Volumen: 559
Número: C
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2014
Página de inicio: 3
Página final: 19
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0304397514006756
DOI:

10.1016/j.tcs.2014.09.010

Notas: ISI, SCOPUS