Computational complexity of threshold automata networks under different updating schemes

Eric Goles, Pedro Montealegre

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

18 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Páginas (desde-hasta)3-19
Número de páginas17
PublicaciónTheoretical Computer Science
Volumen559
N.ºC
DOI
EstadoPublicada - 2014

Huella

Profundice en los temas de investigación de 'Computational complexity of threshold automata networks under different updating schemes'. En conjunto forman una huella única.

Citar esto