Stochastic cellular automata solutions to the density classification problem. When randomness helps computing
DOI10.1007/S00224-012-9386-3zbMATH Open1286.68336OpenAlexW1013383594MaRDI QIDQ372972FDOQ372972
Authors: Nazim Fatès 
Publication date: 21 October 2013
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-012-9386-3
Recommendations
- Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision
- Solving two-dimensional density classification problem with two probabilistic cellular automata
- Solving the density classification problem with a large diffusion and small amplification cellular automaton
- Restricted density classification in one dimension
- Deterministic computing techniques for perfect density classification
stochastic processdensity classification problemmodels of spatially distributed computingstochastic and probabilistic cellular automata
Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)
Cites Work
- Evolving cellular automata to perform computations: Mechanisms and impediments
- Fully asynchronous behavior of double-quiescent elementary cellular automata
- The Gacs-Kurdyumov-Levin automaton revisited
- Some investigations about synchronization and density classification tasks in one-dimensional and two-dimensional cellular automata rule spaces
- Density classification on infinite lattices and trees
- A very effective density classifier two-dimensional cellular automaton with memory
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (28)
- Simply modified GKL density classifiers that reach consensus faster
- Remarks on the cellular automaton global synchronisation problem: deterministic versus stochastic models
- 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
- Overview: PCA models and issues
- Two-dimensional traffic rules and the density classification problem
- The HPP rule with memory and the density classification task
- Self-organisation in cellular automata with coalescent particles: qualitative and quantitative approaches
- Lost in self-stabilization: a local process that aligns connected cells
- Computational mechanisms for solving the density classification task by cellular automata
- On density determination with cellular automata: results, constructions and directions
- Efficient Solutions of the Density Classification Task in One-Dimensional Cellular Automata: Where Can They Be Found?
- Randomized Computation with Cellular Automata
- Around probabilistic cellular automata
- Density-conserving affine continuous cellular automata solving the relaxed density classification problem
- CLOUDS IN THE BASINS OF FULLY ASYNCHRONOUS CELLULAR AUTOMATA
- A note on skew-asynchronous cellular automata
- Asynchronous cellular systems that solve the parity problem
- Restricted density classification in one dimension
- Temporally Stochastic Cellular Automata: Classes and Dynamics
- 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 Solve the Density Classification Problem with an Arbitrary Precision
- Density classification on infinite lattices and trees
- A survey of cellular automata: types, dynamics, non-uniformity and applications
- Autonomous population regulation using a multi-agent system in a prey-predator model that integrates cellular automata and the African buffalo optimization metaheuristic
- The density classification problem in the context of continuous cellular automata
This page was built for publication: Stochastic cellular automata solutions to the density classification problem. When randomness helps computing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q372972)
