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

DOI10.1007/s00224-012-9386-3zbMath1286.68336MaRDI 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 process; density classification problem; models of spatially distributed computing; stochastic and probabilistic cellular automata

Mathematics Subject Classification ID

68Q80: Cellular automata (computational aspects)

37B15: Dynamical aspects of cellular automata

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

Overview: PCA Models and Issues, The Density Classification Problem in the Context of Continuous Cellular Automata, Temporally Stochastic Cellular Automata: Classes and Dynamics, Density-conserving affine continuous cellular automata solving the relaxed density classification problem, Around probabilistic cellular automata, Simply modified GKL density classifiers that reach consensus faster, Lost in self-stabilization: a local process that aligns connected cells, Autonomous population regulation using a multi-agent system in a prey-predator model that integrates cellular automata and the African buffalo optimization metaheuristic, Self-organisation in cellular automata with coalescent particles: qualitative and quantitative approaches, Two-Dimensional Traffic Rules and the Density Classification Problem

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