A1 Refereed original research article in a scientific journal
Modified Traffic Cellular Automaton for the Density Classification Task
Authors: Kari J, Le Gloannec B
Publisher: IOS PRESS
Publication year: 2012
Journal: Fundamenta Informaticae
Journal name in source: FUNDAMENTA INFORMATICAE
Journal acronym: FUND INFORM
Number in series: 1-4
Volume: 116
Issue: 1-4
First page : 141
Last page: 156
Number of pages: 16
ISSN: 0169-2968
DOI: https://doi.org/10.3233/FI-2012-675
Abstract
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.
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.
UTU Research Portal