Tampere University of Technology

TUTCRIS Research Portal

Exploratory analysis of spatiotemporal patterns of cellular automata by clustering compressibility

Research output: Contribution to journalArticleScientificpeer-review

Details

Original languageEnglish
Article number026103
JournalPhysical Review E
Volume81
Issue number2
DOIs
Publication statusPublished - 8 Feb 2010
Externally publishedYes
Publication typeA1 Journal article-refereed

Abstract

In this paper we study the classification of spatiotemporal pattern of one-dimensional cellular automata (CA) whereas the classification comprises CA rules including their initial conditions. We propose an exploratory analysis method based on the normalized compression distance (NCD) of spatiotemporal patterns which is used as dissimilarity measure for a hierarchical clustering. Our approach is different with respect to the following points. First, the classification of spatiotemporal pattern is comparative because the NCD evaluates explicitly the difference of compressibility among two objects, e.g., strings corresponding to spatiotemporal patterns. This is in contrast to all other measures applied so far in a similar context because they are essentially univariate. Second, Kolmogorov complexity, which underlies the NCD, was used in the classification of CA with respect to their spatiotemporal pattern. Third, our method is semiautomatic allowing us to investigate hundreds or thousands of CA rules or initial conditions simultaneously to gain insights into their organizational structure. Our numerical results are not only plausible confirming previous classification attempts but also shed light on the intricate influence of random initial conditions on the classification results.