Two-dimensional traffic rules and the density classification problem

Nazim Fatès 1 Irène Marcovici 2 Siamak Taati 3
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
2 Probabilités et statistiques
IECL - Institut Élie Cartan de Lorraine
Abstract : The density classification problem is the computational problem of finding the majority in a given array of votes in a distributed fashion. It is known that no cellular automaton rule with binary alphabet can solve the density classification problem. On the other hand, it was shown that a probabilistic mixture of the traffic rule and the majority rule solves the one-dimensional problem correctly with a probability arbitrarily close to one. We investigate the possibility of a similar approach in two dimensions. We show that in two dimensions, the particle spacing problem, which is solved in one dimension by the traffic rule, has no cellular automaton solution. However, we propose exact and randomized solutions via interacting particle systems. We assess the performance of our models using numeric simulations.
Type de document :
Communication dans un congrès
Matthew Cook; Turlough Neary. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zürich, France. Springer, Lecture Notes in Computer Science, LNCS-9664, pp.135-148, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-39300-1_11〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01290290
Contributeur : Nazim Fatès <>
Soumis le : vendredi 1 avril 2016 - 22:47:23
Dernière modification le : jeudi 11 janvier 2018 - 06:26:22
Document(s) archivé(s) le : mercredi 9 novembre 2016 - 17:31:08

Fichiers

TwoDimensional-density-classif...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Pas de modification 4.0 International License

Identifiants

Citation

Nazim Fatès, Irène Marcovici, Siamak Taati. Two-dimensional traffic rules and the density classification problem. Matthew Cook; Turlough Neary. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zürich, France. Springer, Lecture Notes in Computer Science, LNCS-9664, pp.135-148, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-39300-1_11〉. 〈hal-01290290〉

Partager

Métriques

Consultations de la notice

511

Téléchargements de fichiers

61