A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Modified Traffic Cellular Automaton for the Density Classification Task
Tekijät: Kari J, Le Gloannec B
Kustantaja: IOS PRESS
Julkaisuvuosi: 2012
Journal: Fundamenta Informaticae
Tietokannassa oleva lehden nimi: FUNDAMENTA INFORMATICAE
Lehden akronyymi: FUND INFORM
Numero sarjassa: 1-4
Vuosikerta: 116
Numero: 1-4
Aloitussivu: 141
Lopetussivu: 156
Sivujen määrä: 16
ISSN: 0169-2968
DOI: https://doi.org/10.3233/FI-2012-675
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali