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 $\mathbf{NC}$ proving a characterization of the maximal sets of stable sites as the tri-connected components.
Type de document :
Communication dans un congrès
Alberto Dennunzio; Enrico Formenti; Luca Manzoni; Antonio E. Porreca. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10248, pp.109-119, 2017, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-58631-1_9〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01656355
Contributeur : Hal Ifip <>
Soumis le : mardi 5 décembre 2017 - 15:42:20
Dernière modification le : jeudi 7 décembre 2017 - 10:07:06

Fichier

 Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Eric Goles, Diego Maldonado, Pedro Montealegre, Nicolas Ollinger. On the Computational Complexity of the Freezing Non-strict Majority Automata. Alberto Dennunzio; Enrico Formenti; Luca Manzoni; Antonio E. Porreca. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10248, pp.109-119, 2017, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-58631-1_9〉. 〈hal-01656355〉

Partager

Métriques

Consultations de la notice

23