%0 Conference Proceedings
%T Two-dimensional traffic rules and the density classification problem
%+ Theoretical adverse computations, and safety (CARTE)
%+ Institut Élie Cartan de Lorraine (IECL)
%+ Department of Mathematics (University of Groningen)
%A Fatès, Nazim
%A Marcovici, Irène
%A Taati, Siamak
%Z Part 2: Regular Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Zürich, France
%Y Matthew Cook
%Y Turlough Neary
%I Springer
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-9664
%P 135-148
%8 2016-06-15
%D 2016
%Z 1604.04402
%R 10.1007/978-3-319-39300-1_11
%Z Nonlinear Sciences [physics]/Cellular Automata and Lattice Gases [nlin.CG]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-01290290/document
%2 https://inria.hal.science/hal-01290290/file/TwoDimensional-density-classif.pdf
%L hal-01290290
%U https://inria.hal.science/hal-01290290
%~ CNRS
%~ INRIA
%~ IECN
%~ INSMI
%~ INRIA_TEST
%~ INRIA-LORRAINE
%~ LORIA2
%~ INRIA-NANCY-GRAND-EST
%~ TESTALAIN1
%~ IFIP-LNCS
%~ IFIP
%~ UNIV-LORRAINE
%~ INRIA2
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ TDS-MACS
%~ LORIA
%~ LORIA-FM
%~ IFIP-LNCS-9664
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA
%~ IECLPS