PSPACE-completeness of majority automata networks



: Eric Goles, Pedro Montealegre, Ville Salo, Ilkka Törmä

Publisher: ELSEVIER SCIENCE BV

: 2016

: Theoretical Computer Science

: THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 609

: Part 1

: 118

: 128

: 11

: 0304-3975

: 1879-2294

DOI: https://doi.org/10.1016/j.tcs.2015.09.014

: http://www.sciencedirect.com/science/article/pii/S0304397515008294?np=y

: https://arxiv.org/abs/1501.03992


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. (C) 2015 Elsevier B.V. All rights reserved.


Last updated on 2024-26-11 at 20:44