./..

In this article, written jointly with Enrico Formenti and Bruno Durand, we present a new approach to cellular automata (CA) classification based on algorithmic complexity. We construct a parameter κ which is based only on the transition table of CA and measures the "randomness" of evolutions; κ is better, in a certain sense, than any other parameter recursively definable on CA tables. We investigate the relations between the classical topological approach and ours one. Our parameter is compared with Langton's λ parameter: κ turns out to be theoretically better and also agrees with some practical evidences reported in literature. Finally, we propose a protocol to approximate κ and make experiments on CA dynamical behavior.

Even if written as published in may 2001, the last revision is dated from the 31st of March, 1999. Sometimes, it's a very long process to get an article published. It was submitted to numerous conferences before getting out as a journal papel: ISAAC'97, ICALP'98, MFCS'98, FCT'97, also as an internal research report... The various versions are too similar and do not deserve a separate presentation (or distribution).

The documents

Citing this publication

This article was published in Theoretical Computer Science, a top theoretical computer science-journal.

@Article{ddf01,
  author =   {Jean-Christophe Dubacq and Bruno Durand and Enrico Formenti},
  title =    {{Kolmogorov} complexity and cellular automata classification},
  journal =      {Theoretical Computer Science},
  year =     {2001},
  volume =   {259},
  number =   {1--2},
  pages =    {271--285},
  month =    may
}