Skip to Main content Skip to Navigation
New interface
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 : Monday, May 9, 2022 - 1:10:01 PM

Links full text



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



Record views