Two-dimensional traffic rules and the density classification problem

DOI10.1007/978-3-319-39300-1_11MaRDI QIDQ3186480zbMATH OpenOpenAlexFDO

Authors Nazim Fatès, Irène Marcovici, Siamak Taati

Publication date 10 August 2016

Published in Cellular Automata and Discrete Complex Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.04402

zbMATH Keywords

density classification probleminteracting particle systemsspacing problem

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Abstract: 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.

Recommendations

• Solving two-dimensional density classification problem with two probabilistic cellular automata
• Density classification quality of the traffic-majority rules
• An exact solution to the two-dimensional arbitrary-threshold density classification problem
• Stochastic cellular automata solutions to the density classification problem. When randomness helps computing
• Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision

Cites work

• Around probabilistic cellular automata
• Density classification on infinite lattices and trees
• Invariant measures and convergence properties for cellular automaton 184 and related processes
• Modified traffic cellular automaton for the density classification task
• On density determination with cellular automata: results, constructions and directions
• Restricted density classification in one dimension
• Solving two-dimensional density classification problem with two probabilistic cellular automata
• Stochastic cellular automata solutions to the density classification problem. When randomness helps computing
• Two-dimensional traffic rules and the density classification problem

Cited in

(9)

• Density classification quality of the traffic-majority rules
• Modified traffic cellular automaton for the density classification task
• Density classification on infinite lattices and trees
• scientific article; zbMATH DE number 6611489 (Why is no real title available?)
• Performance of the majority voting rule in solving the density classification problem in high dimensions
• Two-dimensional traffic rules and the density classification problem
• An exact solution to the two-dimensional arbitrary-threshold density classification problem
• Density classification on infinite lattices and trees
• The density classification problem in the context of continuous cellular automata

This page was built for publication: Two-dimensional traffic rules and the density classification problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3186480)