Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision

DOI10.4230/LIPICS.STACS.2011.284MaRDI QIDQ3113693zbMATH OpenOpenAlexFDO

Authors Nazim Fatès

Publication date 23 January 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_31ed.html

zbMATH Keywords

stochastic processdensity classification problemmodels of spatially distributed computingstochastic and probabilistic cellular automata

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Cellular automata (computational aspects) (68Q80)

Recommendations

• Stochastic cellular automata solutions to the density classification problem. When randomness helps computing
• The density classification problem in the context of continuous cellular automata
• Solving the density classification problem with a large diffusion and small amplification cellular automaton
• Solving two-dimensional density classification problem with two probabilistic cellular automata
• Computational mechanisms for solving the density classification task by cellular automata
• Affine continuous cellular automata solving the fixed-length density classification problem
• On density determination with cellular automata: results, constructions and directions
• scientific article; zbMATH DE number 5679760
• Efficient Solutions of the Density Classification Task in One-Dimensional Cellular Automata: Where Can They Be Found?

Cited in

(22)

• Solving the density classification problem with a large diffusion and small amplification cellular automaton
• Solving the parity problem in one-dimensional cellular automata
• Solving two-dimensional density classification problem with two probabilistic cellular automata
• Two-dimensional traffic rules and the density classification problem
• Lost in self-stabilization
• On density determination with cellular automata: results, constructions and directions
• Performance of the majority voting rule in solving the density classification problem in high dimensions
• Efficient Solutions of the Density Classification Task in One-Dimensional Cellular Automata: Where Can They Be Found?
• scientific article; zbMATH DE number 5679760 (Why is no real title available?)
• An Analytical Formulation for Cellular Automata (CA) Based Solution of Density Classification Task (DCT)
• Probabilistic Cellular Automata, Invariant Measures, and Perfect Sampling
• A sequential solution to the density classification task using an intermediate alphabet
• Density-conserving affine continuous cellular automata solving the relaxed density classification problem
• Restricted density classification in one dimension
• Deterministic computing techniques for perfect density classification
• An exact solution to the two-dimensional arbitrary-threshold density classification problem
• Affine continuous cellular automata solving the fixed-length density classification problem
• Stochastic cellular automata solutions to the density classification problem. When randomness helps computing
• Two-dimensional affine continuous cellular automata solving the relaxed density classification problem
• Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations
• The density classification problem in the context of continuous cellular automata
• Pattern classification with temporally stochastic cellular automata

This page was built for publication: Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision

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