PSPACE-completeness of majority automata networks
PSPACE.pdf (247.3Kb)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.
General note
Artículo de publicación ISI
Patrocinador
CONICYT-Becas Chile
72130083
FONDECYT
1140090
ECOS
C12E05
Basal project
PFB-03
Centro de Modelamiento Matematico
CNRS
UMI 2807
Universidad de Chile
Academy of Finland
131558
Identifier
URI: https://repositorio.uchile.cl/handle/2250/136835
DOI: DOI: 10.1016/j.tcs.2015.09.014
Quote Item
Theoretical Computer Science Volumen: 609 Páginas: 118-128 Subdivisión: 1 Jan 2016
Collections
The following license files are associated with this item:
Except where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 Chile