PSPACE-completeness of majority automata networks

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

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

9 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 originalInglés
Páginas (desde-hasta)118-128
Número de páginas11
PublicaciónTheoretical Computer Science
Volumen609
DOI
EstadoPublicada - 4 ene. 2016

Huella

Profundice en los temas de investigación de 'PSPACE-completeness of majority automata networks'. En conjunto forman una huella única.

Citar esto