%0 Conference Proceedings
%T On the Computational Complexity of the Freezing Non-strict Majority Automata
%+ Universidad Adolfo Ibáñez [Santiago]
%+ LE STUDIUM (LE STUDIUM)
%+ Laboratoire d'Informatique Fondamentale d'Orléans (LIFO)
%A Goles, Eric
%A Maldonado, Diego
%A Montealegre, Pedro
%A Ollinger, Nicolas
%Z Part 2: Regular Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Milan, Italy
%Y Alberto Dennunzio
%Y Enrico Formenti
%Y Luca Manzoni
%Y Antonio E. Porreca
%I Springer International Publishing
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-10248
%P 109-119
%8 2017-06-07
%D 2017
%R 10.1007/978-3-319-58631-1_9
%Z Computer Science [cs]Conference papers
%X 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 $\mathbf{NC}$ proving a characterization of the maximal sets of stable sites as the tri-connected components.
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-01656355/document
%2 https://inria.hal.science/hal-01656355/file/447449_1_En_9_Chapter.pdf
%L hal-01656355
%U https://inria.hal.science/hal-01656355
%~ INSERM
%~ IRD
%~ CEA
%~ BRGM
%~ CNRS
%~ UNIV-ORLEANS
%~ IRSTEA
%~ INRA
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA
%~ AGREENIUM
%~ IFIP-LNCS-10248
%~ INSA-GROUPE
%~ INSA-CVL
%~ INRAE