摘要
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%26apos;s if p %26lt; 1/2, and only 1%26apos;s if p %26gt; 1/2. We present solutions to the problem on the regular grids of dimension d, for any d %26gt;= 2, and on the regular infinite trees. For the bi-infinite line, we propose some candidates that we back up with numerical simulations.
- 出版日期2013-4-24
- 单位INRIA