Modified Traffic Cellular Automaton for the Density Classification Task

• Autorzy: Kari J. , Le Gloannec B.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

cellular automata; density classification; traffic CA

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 141--156
• Opis fizyczny: Bibliogr. 11 poz., rys., tab.

Twórcy

autor

Kari J.

autor

Le Gloannec B.

• Department of Mathematics, FI-20014 University of Turku Turku Finland,

Bibliografia

• [1] Gacs, P., Kurdyumov, G., Levin, L.: One-dimensional homogenuous media dissolving finite islands, Problems of Inf. Transm, 14(3), 1978, 92-96.
• [2] Juille, H., Pollack, J. B.: Coevolving the Ideal Trainer: Application to the Discovery of Cellular Automata Rules, Genetic Programming 1998: Proceedings of the Third Annual Conference (J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, R. Riolo, Eds.), Morgan Kaufmann, University of Wisconsin, Madison, Wisconsin, USA, 1998.
• [3] Kari, J.: Theory of cellular automata: A survey, Theor. Comput. Sci., 334(1-3), 2005, 3-33.
• [4] Kůrka, P.: Cellular automata with vanishing particles, Fundam. Inform., 58(2003), 2003, 203-221.
• [5] Land, M., Belew, R.: No perfect two-state cellular automata for density classification exists, Physical Review Letters, 74(25), 1995, 5148-5150.
• [6] Le Gloannec, B.: Around Kari's traffic cellular automaton for the density classification, Project report, ENS Lyon, France, 2009.
• [7] Levin, L. A.: Self-stabilization of circular arrays of automata, Theor. Comput. Sci., 235(1), 2000, 143-144.
• [8] Mitchell, M., Crutchfield, J., Hraber, P.: Evolving cellular automata to perform computations: Mechanisms and impediments, Physica D, 75(1-3), 1994, 361-391.
• [9] de Oliveira, P. P. B., Bortot, J. C., Oliveira, G. M. B.: The best currently known class of dynamically equivalent cellular automata rules for density classification, Neurocomputing, 70(1-3), 2006, 35-43.
• [10] de Sa, P., Maes, C.: The Gacs-Kurdyumov-Levin automaton revisited, Journal of Statistical Physics, 67(3), 1992, 507-522.
• [11] Wolz, D., de Oliveira, P. P. B.: Very Effective Evolutionary Techniques for Searching Cellular Automata Rule Spaces, J. Cellular Automata, 3(4), 2008, 289-312.