Some Investigations About Synchronization and Density Classification Tasks in One-dimensional and Two-dimensional Cellular Automata Rule Spaces

The study of computational aspects of cellular automata (CA) is a recurrent theme being that the investigation of specific tasks to be solved by CA rules a common and widely-known approach. We investigated two of the most-studied computational tasks: synchronization (ST) and density classification (...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in theoretical computer science 2009-10, Vol.252, p.121-142
Main Authors: Oliveira, Gina M.B., Martins, Luiz G.A., de Carvalho, Laura B., Fynn, Enrique
Format: Article
Language:English
Subjects:
Cellular Automata
Density Classification Task
Evolutionary Algorithms
Synchronization Task
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The study of computational aspects of cellular automata (CA) is a recurrent theme being that the investigation of specific tasks to be solved by CA rules a common and widely-known approach. We investigated two of the most-studied computational tasks: synchronization (ST) and density classification (DCT). Different specifications of CA rule space were analyzed for both tasks: one-dimensional rules with radius 1 and 2, and two-dimensional rules with von Neumann and Moore neighborhoods. We also analyzed different lattice sizes when trying to execute these tasks. Several evolutionary experiments were performed to characterize ST and DCT on these different scenarios. Some interesting results have been occurred from these experiments as the adequacy of the tasks to be solved in two-dimensional spaces instead of 1D even using rules with the same length and the dependency to the parity of the lattice size related to good rules for DCT in 1D and 2D spaces.
ISSN:1571-0661
1571-0661
DOI:10.1016/j.entcs.2009.09.018