A1 Refereed original research article in a scientific journal
PSPACE-completeness of majority automata networks
Authors: Eric Goles, Pedro Montealegre, Ville Salo, Ilkka Törmä
Publisher: ELSEVIER SCIENCE BV
Publication year: 2016
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 609
Issue: Part 1
First page : 118
Last page: 128
Number of pages: 11
ISSN: 0304-3975
eISSN: 1879-2294
DOI: https://doi.org/10.1016/j.tcs.2015.09.014(external)
Web address : http://www.sciencedirect.com/science/article/pii/S0304397515008294?np=y(external)
Self-archived copy’s web address: https://arxiv.org/abs/1501.03992(external)
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.
Downloadable publication This is an electronic reprint of the original article. |