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ä

Facultad de Ingeniería y Ciencias

Producción científica: Contribución a una revista › Artículo › revisión exhaustiva

20 Citas (Scopus)

Resumen

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.

Idioma original	Inglés
Páginas (desde-hasta)	118-128
Número de páginas	11
Publicación	Theoretical Computer Science
Volumen	609
DOI	https://doi.org/10.1016/j.tcs.2015.09.014
Estado	Publicada - 4 ene 2016

Acceder al documento

10.1016/j.tcs.2015.09.014

Citar esto

@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 - https://www.scopus.com/pages/publications/84947343522

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

Resumen

Acceder al documento

Huella

Citar esto