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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-01315324
Contributor : Pedro Montealegre <>
Submitted on : Friday, May 13, 2016 - 2:40:48 AM
Last modification on : Tuesday, November 19, 2019 - 4:47:55 PM

Identifiers

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⟩

Share

Metrics

Record views

92