PSPACE-completeness of majority automata networks

Eric Goles; Pedro Montealegre; Ville Salo; Ilkka Törmä

doi:10.1016/j.tcs.2015.09.014

PSPACE-completeness of majority automata networks

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

Faculty of Engineering and Science

Research output: Contribution to journal › Article › peer-review

16 Scopus citations

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.

Original language	English
Pages (from-to)	118-128
Number of pages	11
Journal	Theoretical Computer Science
Volume	609
DOIs	https://doi.org/10.1016/j.tcs.2015.09.014
State	Published - 4 Jan 2016

Keywords

Boolean network
Majority network
PSPACE
Prediction problem

Access to Document

10.1016/j.tcs.2015.09.014

Cite this

@article{8c8d480b09a043ecada02a16eadec480,

title = "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.",

keywords = "Boolean network, Majority network, PSPACE, Prediction problem",

author = "Eric Goles and Pedro Montealegre and Ville Salo and Ilkka T{\"o}rm{\"a}",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2016",

month = jan,

day = "4",

doi = "10.1016/j.tcs.2015.09.014",

language = "English",

volume = "609",

pages = "118--128",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - PSPACE-completeness of majority automata networks

AU - Goles, Eric

AU - Montealegre, Pedro

AU - Salo, Ville

AU - Törmä, Ilkka

PY - 2016/1/4

Y1 - 2016/1/4

N2 - 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.

AB - 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.

KW - Boolean network

KW - Majority network

KW - PSPACE

KW - Prediction problem

UR - http://www.scopus.com/inward/record.url?scp=84947343522&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2015.09.014

DO - 10.1016/j.tcs.2015.09.014

M3 - Article

AN - SCOPUS:84947343522

SN - 0304-3975

VL - 609

SP - 118

EP - 128

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

PSPACE-completeness of majority automata networks

Abstract

Keywords

Access to Document

Fingerprint

Cite this