Cet article, écrit conjointement avec Enrico Formenti et Bruno Durand, présente une approche nouvelle de la classification des automates cellulaires (AC) fondée sur la complexité de Kolmogorov. Nous construisons un paramètre κ qui est basé seulement sur la table de transition des AC et mesure le « caractère aléatoire » des évolutions. κ est meilleur, dans un certain sens, que n'importe quel autre paramètre calculable défini uniquement par la table de transition des AC. Nous avons aussi examiné les relations entre l'approche classique (topologique) et la notre. Notre paramètre a été aussi comparé au paramètre λ de Langton : le notre est plus fondé théoriquement, et s'accorde aussi avec des constatations expérimentales déjà publiées. Finalement, nous proposons aussi un protocole d'approximation de κ et d'expérimentation sur le comportement dynamique des AC.
Même s'il est marqué comme publié en mai 2001, la dernière révision est datée du 31 mars 1999. Parfois, c'est long, le processus éditorial... Je note aussi qu'il a été soumis a de très nombreuses conférences avant de paraître (directement en journal): ISAAC'97, ICALP'98, MFCS'98, FCT'97, en tant que rapport de recherche interne... Les différentes versions sont trop proches les unes des autres pour que j'ai jugé utile de les garder ou les présenter.
Les documents
Citer cette publication
Cet article a été publié dans Theoretical Computer Science, revue très sérieuse d'informatique théorique.
@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
}