JCA HomeIssue Contents

Density Classification Quality of the Traffic-Majority Rules
Markus Redeker

The density classification task is a famous problem in the theory of cellular automata. It is unsolvable for deterministic automata, but recently solutions for stochastic cellular automata have been found. One of them is a set of stochastic transition rules depending on a parameter η, the traffic-majority rules.

Here I derive a simplified model for these cellular automata. It is valid for a subset of the initial configurations and uses random walks and generating functions. I compare its prediction with computer simulations and show that it expresses recognition quality and time correctly for a large range of η values.

Keywords: Density classification, majority rule, stochastic automata.

Full Text (IP)