Exploratory analysis of spatiotemporal patterns of cellular automata by clustering compressibility

Frank Emmert-Streib

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


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.
Original languageEnglish
Article number026103
Pages (from-to)x1-y1
Number of pages1
JournalPhysical Review E
Issue number2
Publication statusPublished - 08 Feb 2010

ASJC Scopus subject areas

  • Statistics and Probability
  • Condensed Matter Physics
  • Statistical and Nonlinear Physics


Dive into the research topics of 'Exploratory analysis of spatiotemporal patterns of cellular automata by clustering compressibility'. Together they form a unique fingerprint.

Cite this