Computational complexity of threshold automata networks under different updating schemes

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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2014, 559, pp.3-19. 〈10.1016/j.tcs.2014.09.010〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01315323
Contributeur : Pedro Montealegre <>
Soumis le : vendredi 13 mai 2016 - 02:21:17
Dernière modification le : jeudi 17 mai 2018 - 12:52:03

Identifiants

Collections

Citation

Eric Goles Chacc, Pedro Montealegre. Computational complexity of threshold automata networks under different updating schemes. Theoretical Computer Science, Elsevier, 2014, 559, pp.3-19. 〈10.1016/j.tcs.2014.09.010〉. 〈hal-01315323〉

Partager

Métriques

Consultations de la notice

45