| Record |
Author  |
Goles, E.; Montealegre, P.; Salo, V.; Torma, I. |
| Title |
PSPACE-completeness of majority automata networks |
Type |
|
| Year |
2016 |
Publication |
Theoretical Computer Science |
Abbreviated Journal |
Theor. Comput. Sci. |
| Volume |
609 |
Issue |
|
Pages |
118-128 |
| Keywords |
Boolean network; Majority network; Prediction problem; PSPACE |
| 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. |
| Address |
[Goles, Eric] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: eric.chacc@uai.cl; |
| Corporate Author |
|
Thesis |
|
| Publisher |
Elsevier Science Bv |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0304-3975 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000367488400009 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
572 |
| Permanent link to this record |
