Density classification on infinite lattices and trees

Ana Bušić (INRIA & ÉNS)
Nazim Fatès (Inria & Nancy Université)
Jean Mairesse (Université Paris Diderot - Paris 7)
Irène Marcovici (Université Paris Diderot - Paris 7)


Consider an infinite graph with nodes initially labeled by independent Bernoullirandom 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 weback up with numerical simulations.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-22

Publication Date: April 24, 2013

DOI: 10.1214/EJP.v18-2325


  • Belitsky, Vladimir; Ferrari, Pablo A. Invariant measures and convergence properties for cellular automaton 184 and related processes. J. Stat. Phys. 118 (2005), no. 3-4, 589--623. MR2123649
  • A. Bušić, N. Fatès, J. Mairesse, and I. Marcovici. Density classification on infinite lattices and trees. In LATIN 2012, volume 7256 of LNCS, pages 109--120. Springer-Verlag, 2012.
  • Cox, J. T.; Durrett, R. Nonlinear voter models. Random walks, Brownian motion, and interacting particle systems, 189--201, Progr. Probab., 28, Birkhäuser Boston, Boston, MA, 1991. MR1146446
  • Dawson, D. A. Stable states of probabilistic cellular automata. Information and Control 34 (1977), no. 2, 93--106. MR0446758
  • R.L. Dobrushin, V.I. Kryukov, and A.L. Toom. Stochastic cellular systems: ergodicity, memory, morphogenesis. Nonlinear science. Manchester University Press, 1990.
  • Fatès, Nazim. Stochastic cellular automata solve the density classification problem with an arbitrary precision. 28th International Symposium on Theoretical Aspects of Computer Science, 284--295, LIPIcs. Leibniz Int. Proc. Inform., 9, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2011. MR2853436
  • Fontes, L. R.; Schonmann, R. H.; Sidoravicius, V. Stretched exponential fixation in stochastic Ising models at zero temperature. Comm. Math. Phys. 228 (2002), no. 3, 495--518. MR1918786
  • H. Fukś. Nondeterministic density classification with diffusive probabilistic cellular automata. Phys. Rev. E, 66, 2002.
  • Gács, Péter. A Toom rule that increases the thickness of sets. J. Statist. Phys. 59 (1990), no. 1-2, 171--193. MR1049966
  • Gács, Peter. Reliable cellular automata with self-organization. J. Statist. Phys. 103 (2001), no. 1-2, 45--267. MR1828729
  • P. Gács, G. Kurdyumov, and L. Levin. One-dimensional homogeneous media dissolving finite islands. Problems of Information Transmission, 14:92--96, 1978.
  • Gonzaga de Sá, Paula; Maes, Christian. The Gacs-Kurdyumov-Levin automaton revisited. J. Statist. Phys. 67 (1992), no. 3-4, 507--522. MR1171143
  • Gray, Lawrence F. A reader's guide to P. Gács's "positive rates'' paper: "Reliable cellular automata with self-organization'' [J. Statist. Phys. 103 (2001), no. 1-2, 45–267; MR1828729 (2002c:82058a)]. J. Statist. Phys. 103 (2001), no. 1-2, 1--44. MR1828728
  • Grimmett, Geoffrey. Percolation. Second edition. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 321. Springer-Verlag, Berlin, 1999. xiv+444 pp. ISBN: 3-540-64902-6 MR1707339
  • Howard, C. Douglas. Zero-temperature Ising spin dynamics on the homogeneous tree of degree three. J. Appl. Probab. 37 (2000), no. 3, 736--747. MR1782449
  • Kanoria, Yashodhan; Montanari, Andrea. Majority dynamics on trees and the dynamic cavity method. Ann. Appl. Probab. 21 (2011), no. 5, 1694--1748. MR2884049
  • Kari, Jarkko; Le Gloannec, Bastien. Modified traffic cellular automaton for the density classification task. Fund. Inform. 116 (2012), no. 1-4, 141--156. MR2977840
  • Kůrka, Petr. Cellular automata with vanishing particles. Fund. Inform. 58 (2003), no. 3-4, 203--221. MR2073077
  • M. Land and R. Belew. No perfect two-state cellular automata for density classification exists. Phys. Rev. Lett., 74:5148--5150, 1995.
  • Liggett, Thomas M. Interacting particle systems. Reprint of the 1985 original. Classics in Mathematics. Springer-Verlag, Berlin, 2005. xvi+496 pp. ISBN: 3-540-22617-6 MR2108619
  • Packard, Norman H. Adaptation toward the edge of chaos. Dynamic patterns in complex systems (Fort Lauderdale, FL, 1987), 293--301, World Sci. Publ., Teaneck, NJ, 1988. MR1037037
  • Park, Kihong. Ergodicity and mixing rate of one-dimensional cellular automata. Thesis (Ph.D.)–Boston University. ProQuest LLC, Ann Arbor, MI, 1997. 108 pp. ISBN: 978-0591-05272-5 MR2694652
  • Pippenger, Nicholas. Symmetry in self-correcting cellular automata. J. Comput. System Sci. 49 (1994), no. 1, 83--95. MR1284592
  • M. Schüle, T, Ott, and R. Stoop. Computing with probabilistic cellular automata. In Proceedings of the 19th International Conference on Artificial Neural Networks: Part II, ICANN '09, pages 525--533, 2009. Springer-Verlag.
  • Toom, A. L. Stable and attractive trajectories in multicomponent systems. Multicomponent random systems, pp. 549--575, Adv. Probab. Related Topics, 6, Dekker, New York, 1980. MR0599548

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.