Density Classification on Infinite Lattices and Trees

Ana Busic 1, 2, 3 Nazim Fatès 4 Irène Marcovici 5 Jean Mairesse 5
3 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
4 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : Consider an infinite graph with nodes initially labeled by independent Bernoulli random variables of parameter p. We address the density classification problem, that is, we want to design a (probabilistic or deterministic)cellular automaton or a finite-range interacting particle system that evolves on this graph and decides whether p is smaller or larger than 1/2. Precisely, the trajectories should converge to the uniform configuration with only 0's if p<1/2, and only 1's if p>1/2. We present solutions to the problem on the regular grids of dimension d, for any d>1, and on the regular infinite trees. For the bi-infinite line, we propose some candidates that we back up with numerical simulations.
Type de document :
Article dans une revue
Electronic Journal of Probability, Institute of Mathematical Statistics (IMS), 2013, 18 (51), pp.1-22. 〈10.1214/EJP.v18-2325〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00918583
Contributeur : Nazim Fatès <>
Soumis le : vendredi 13 décembre 2013 - 17:15:48
Dernière modification le : mardi 17 avril 2018 - 11:34:32

Lien texte intégral

Identifiants

Collections

Citation

Ana Busic, Nazim Fatès, Irène Marcovici, Jean Mairesse. Density Classification on Infinite Lattices and Trees. Electronic Journal of Probability, Institute of Mathematical Statistics (IMS), 2013, 18 (51), pp.1-22. 〈10.1214/EJP.v18-2325〉. 〈hal-00918583〉

Partager

Métriques

Consultations de la notice

431