On the Computational Complexity of the Freezing Non-strict Majority Automata - Inserm - Institut national de la santé et de la recherche médicale Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

On the Computational Complexity of the Freezing Non-strict Majority Automata

Résumé

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.
Fichier principal
Vignette du fichier
447449_1_En_9_Chapter.pdf (272.22 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01656355 , version 1 (05-12-2017)

Licence

Paternité

Identifiants

Citer

Eric Goles, Diego Maldonado, Pedro Montealegre, Nicolas Ollinger. On the Computational Complexity of the Freezing Non-strict Majority Automata. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. pp.109-119, ⟨10.1007/978-3-319-58631-1_9⟩. ⟨hal-01656355⟩
232 Consultations
99 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More