Skip to Main content Skip to Navigation
Journal articles

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 metadata
Contributor : Pedro Montealegre Connect in order to contact the contributor
Submitted on : Friday, May 13, 2016 - 2:40:48 AM
Last modification on : Tuesday, October 12, 2021 - 5:20:39 PM

Links full text



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⟩



Record views