Restricted density classification in one dimension

DOI10.1007/978-3-662-47221-7_18MaRDI QIDQ5500627zbMATH OpenOpenAlexFDO

Authors Siamak Taati

Publication date 7 August 2015

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

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

zbMATH Keywords

cellular automatadensity classificationpercolationphase transitionspareness

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Cellular automata (computational aspects) (68Q80)

Abstract: The density classification task is to determine which of the symbols appearing in an array has the majority. A cellular automaton solving this task is required to converge to a uniform configuration with the majority symbol at each site. It is not known whether a one-dimensional cellular automaton with binary alphabet can classify all Bernoulli random configurations almost surely according to their densities. We show that any cellular automaton that washes out finite islands in linear time classifies all Bernoulli random configurations with parameters close to 0 or 1 almost surely correctly. The proof is a direct application of a "percolation" argument which goes back to Gacs (1986).

Recommendations

• Stochastic cellular automata solutions to the density classification problem. When randomness helps computing
• Modified traffic cellular automaton for the density classification task
• Solving two-dimensional density classification problem with two probabilistic cellular automata
• Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision
• Density classification on infinite lattices and trees

Cited in

(11)

• Convergence time and phase transition in a non-monotonic family of probabilistic cellular automata
• Modified traffic cellular automaton for the density classification task
• Density classification on infinite lattices and trees
• The HPP rule with memory and the density classification task
• Two-dimensional traffic rules and the density classification problem
• Stochastic cellular automata solutions to the density classification problem. When randomness helps computing
• Density classification on infinite lattices and trees
• ONE DIMENSIONAL nARY DENSITY CLASSIFICATION USING TWO CELLULAR AUTOMATON RULES
• Mining a class of decision problems for one-dimensional cellular automata
• Self-stabilisation of Cellular Automata on Tilings
• Simply modified GKL density classifiers that reach consensus faster

This page was built for publication: Restricted density classification in one dimension

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