@inproceedings{ef5bd2cd0e7a4abaa2a26eb92a0b6d19,
title = "On the computational complexity of the freezing non-strict majority automata",
abstract = "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.",
author = "Eric Goles and Diego Maldonado and Pedro Montealegre and Nicolas Ollinger",
note = "Publisher Copyright: {\textcopyright} IFIP International Federation for Information Processing 2017.; 23rd IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2017 ; Conference date: 07-06-2017 Through 09-06-2017",
year = "2017",
doi = "10.1007/978-3-319-58631-1_9",
language = "English",
isbn = "9783319586304",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "109--119",
editor = "Alberto Dennunzio and Luca Manzoni and Porreca, {Antonio E.} and Enrico Formenti",
booktitle = "Cellular Automata and Discrete Complex Systems - 23rd IFIP WG 1.5 International Workshop, AUTOMATA 2017, Proceedings",
}