PSPACE-completeness of majority automata networks

Abstract : We study the dynamics of majority automata networks when the vertices are updated according to a block sequential updating scheme. In particular, we show that the complexity of the problem of predicting an eventual state change in some vertex, given an initial configuration, is PSPACE-complete.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2016, 609, pp.118-128. 〈10.1016/j.tcs.2015.09.014〉
Liste complète des métadonnées

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

Lien texte intégral

Identifiants

Collections

Citation

Eric Goles Chacc, Pedro Montealegre, Ville Salo, Ilkka Törmä. PSPACE-completeness of majority automata networks. Theoretical Computer Science, Elsevier, 2016, 609, pp.118-128. 〈10.1016/j.tcs.2015.09.014〉. 〈hal-01315324〉

Partager

Métriques

Consultations de la notice

62