Modified Traffic Cellular Automaton for the Density Classification Task

: Kari J, Le Gloannec B

Publisher: IOS PRESS

: 2012

: Fundamenta Informaticae

: FUNDAMENTA INFORMATICAE

: FUND INFORM

: 1-4

: 116

: 1-4

: 141

: 156

: 16

: 0169-2968

DOI: https://doi.org/10.3233/FI-2012-675

The density classification task asks to design a cellular automaton that converges to the uniform configuration that corresponds to the state that is in majority in the initial configuration. We investigate connections of this problem to state-conserving cellular automata. We propose a modified traffic CA that washes out finite islands in the same way as the Gacs, Kurdyumov and Levin automaton, but is also guaranteed to converge to a uniform configuration on rings of odd size. We find experimentally several good classifiers that are close to state-conserving cellular automata, and we observe that the best performing known density classifier by Wolz and de Oliveira is only a simple swap away from a state-conserving automaton.