On the computational complexity of the freezing non-strict majority automata

Eric Goles, Diego Maldonado, Pedro Montealegre, Nicolas Ollinger

Producción científica: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

8 Citas (Scopus)

Resumen

Consider a two dimensional lattice with the von Neumann neighborhood such that each site has a value belonging to {0, 1} which changes state following a freezing non-strict majority rule, i.e., sites at state 1 remain unchanged and those at 0 change iff two or more of it neighbors are at state 1.We study the complexity of the decision problem consisting in to decide whether an arbitrary site initially in state 0 will change to state 1. We show that the problem in the class NC proving a characterization of the maximal sets of stable sites as the tri-connected components.

Idioma originalInglés
Título de la publicación alojadaCellular Automata and Discrete Complex Systems - 23rd IFIP WG 1.5 International Workshop, AUTOMATA 2017, Proceedings
EditoresAlberto Dennunzio, Luca Manzoni, Antonio E. Porreca, Enrico Formenti
EditorialSpringer Verlag
Páginas109-119
Número de páginas11
ISBN (versión impresa)9783319586304
DOI
EstadoPublicada - 2017
Evento23rd IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2017 - Milan, Italia
Duración: 7 jun. 20179 jun. 2017

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen10248 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia23rd IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2017
País/TerritorioItalia
CiudadMilan
Período7/06/179/06/17

Huella

Profundice en los temas de investigación de 'On the computational complexity of the freezing non-strict majority automata'. En conjunto forman una huella única.

Citar esto