One Dimensional ary Density Classification Using Two Cellular Automaton Rules
arXiv:adap-org/9810006 · doi:10.1142/S0129183199000681
Abstract
Suppose each site on a one-dimensional chain with periodic boundary condition may take on any one of the states , can you find out the most frequently occurring state using cellular automaton? Here, we prove that while the above density classification task cannot be resolved by a single cellular automaton, this task can be performed efficiently by applying two cellular automaton rules in succession.
arXiv commentRevtex, 4 pages, uses amsfonts
References in corpus (2)
Cited by in corpus (6)
- Parity Problem With A Cellular Automaton Solution
- Sensitivity to noise and ergodicity of an assembly line of cellular automata that classifies density
- Strictly local one-dimensional topological quantum error correction with symmetry-constrained cellular automata
- Explorations of ternary cellular automata and ternary density classification problems
- Deterministic Computing Mechanism for Perfect Density Classification
- Finding The Sign Of A Function Value By Binary Cellular Automaton