• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Modified Traffic Cellular Automaton for the Density Classification Task

Jarkko Kari, Bastien Le Gloannec, Modified Traffic Cellular Automaton for the Density Classification Task. Fundamenta Informaticae 116(1-4), 141–156, 2012.

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.

BibTeX entry:

@ARTICLE{jKaLe12a,
  title = {Modified Traffic Cellular Automaton for the Density Classification Task},
  author = {Kari, Jarkko and Le Gloannec, Bastien},
  journal = {Fundamenta Informaticae},
  volume = {116},
  number = {1-4},
  pages = {141–156},
  year = {2012},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication