Conceptual Structure in Cellular Automata: The Density Classification Task

Manuel Marques-Pita1,2,3 and Luis M. Rocha1,3

1 School of Informatics, Indiana University, 919 East Tenth Street, Bloomington IN 47408, USA
2Portland State University
3FLAD Computational Biology Collaboratorium, Instituto Gulbenkian de Ciencia, Portugal

Citation: M. Marques-Pita and L.M. Rocha [2008]. "Conceptual Structure in Cellular Automata: The Density Classification Task". In: Artificial Life XI: Eleventh International Conference on the Simulation and Synthesis of Living Systems. S. Bullock, J. Noble, R. A. Watson, and M. A. Bedau (Eds.). MIT Press, pp. 390-397.

The pre-print is available in Adobe Acrobat (.pdf) format only. Due to mathematical notation and graphics, only the abstract is presented here. [BibTex]


The notion of conceptual structure in cellular automata (CA) rules that perform the density classification task (DCT) was introduced by Marques-Pita et al. (2006). Here we investigate the role of process-symmetry in CAs that solve the DCT, in particular the idea of conceptual similarity, which defines a novel search space for CA rules. We report on two new highest-performing process symmetric rules for the DCT.We further discuss how our results are relevant to understand, control, and design the collective computation performed by other networks of automata, such as those used to model, for example, living systems.

Keywords:Cellular Automata, Emergent Computation, Complex Networks, Artificial Life, Density Classification Task.

For the full paper please download the preprint in pdf

For more information contact Luis Rocha at Check the Web Design Credits, for due credit.
Last Modified: December 31, 2008