A1 Refereed original research article in a scientific journal

PSPACE-completeness of majority automata networks




AuthorsEric Goles, Pedro Montealegre, Ville Salo, Ilkka Törmä

PublisherELSEVIER SCIENCE BV

Publication year2016

JournalTheoretical Computer Science

Journal name in sourceTHEORETICAL COMPUTER SCIENCE

Journal acronymTHEOR COMPUT SCI

Volume609

IssuePart 1

First page 118

Last page128

Number of pages11

ISSN0304-3975

eISSN1879-2294

DOIhttps://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 addresshttps://arxiv.org/abs/1501.03992(external)


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


Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





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