Stochastic cellular automata solutions to the density classification problem. When randomness helps computing

DOI10.1007/S00224-012-9386-3zbMath1286.68336OpenAlexW1013383594MaRDI QIDQ372972

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items (14)

Simply modified GKL density classifiers that reach consensus faster ⋮ Temporally Stochastic Cellular Automata: Classes and Dynamics ⋮ Lost in self-stabilization: a local process that aligns connected cells ⋮ Two-Dimensional Traffic Rules and the Density Classification Problem ⋮ Overview: PCA Models and Issues ⋮ The Density Classification Problem in the Context of Continuous Cellular Automata ⋮ Self-organisation in cellular automata with coalescent particles: qualitative and quantitative approaches ⋮ Affine continuous cellular automata solving the fixed-length density classification problem ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Remarks on the cellular automaton global synchronisation problem: deterministic versus stochastic models ⋮ CLOUDS IN THE BASINS OF FULLY ASYNCHRONOUS CELLULAR AUTOMATA ⋮ Density-conserving affine continuous cellular automata solving the relaxed density classification problem ⋮ Around probabilistic cellular automata ⋮ Autonomous population regulation using a multi-agent system in a prey-predator model that integrates cellular automata and the African buffalo optimization metaheuristic

Cites Work

• Unnamed Item
• Unnamed Item
• The Gacs-Kurdyumov-Levin automaton revisited
• Evolving cellular automata to perform computations: Mechanisms and impediments
• Fully asynchronous behavior of double-quiescent elementary cellular automata
• 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

This page was built for publication: Stochastic cellular automata solutions to the density classification problem. When randomness helps computing