A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

PSPACE-completeness of majority automata networks



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

Kustantaja: ELSEVIER SCIENCE BV

Julkaisuvuosi: 2016

Journal: Theoretical Computer Science

Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE

Lehden akronyymi: THEOR COMPUT SCI

Vuosikerta: 609

Numero: Part 1

Aloitussivu: 118

Lopetussivu: 128

Sivujen määrä: 11

ISSN: 0304-3975

eISSN: 1879-2294

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

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

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


Tiivistelmä

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.


Ladattava julkaisu

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