Skip to Main content Skip to Navigation
New interface
Journal articles

Density Classification on Infinite Lattices and Trees

Ana Bušić 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 - ENS 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.
Complete list of metadata
Contributor : Nazim Fatès Connect in order to contact the contributor
Submitted on : Friday, December 13, 2013 - 5:15:48 PM
Last modification on : Thursday, March 17, 2022 - 10:08:43 AM

Links full text



Ana Bušić, Nazim Fatès, Irène Marcovici, Jean Mairesse. Density Classification on Infinite Lattices and Trees. Electronic Journal of Probability, 2013, 18 (51), pp.1-22. ⟨10.1214/EJP.v18-2325⟩. ⟨hal-00918583⟩



Record views