Recherche

Thèmes de recherche

Mes travaux de recherche concernent principalement les automates cellulaires (AC) et impliquent plus particulièrement les notions suivantes:

Thèse

J'ai soutenu ma thèse qui s'intitule "Comportements Typiques dans les Automates Cellulaires" le 7 décembre 2010 devant un jury composé de

Le manuscrit (en français) regroupe ainsi une bonne partie des travaux que j'ai effectués ces dernières années.

Nous abordons les automates cellulaires (AC) en cherchant à dégager des informations quantitatives et en particulier à préciser les comportements répandus.
Nous étudions en guise de prélude des AC présentant une forte symmétrie de la règle locale (AC dits multi-ensemblistes). Les règles locales qui les définnissent ont la propriété de pouvoir être utilisées facilement pour différente tailles de voisinage, et nous exhibons des règles, pour chaque dimension, qui sont universelles pour une infinité de tailles.
Nous formalisons ensuite la notion de densité d'une propriété parmi l'ensemble des AC. En remarquant que les propriétés répandues sont liées aux propriétés des objets aléatoires au sens de Kolmogorov, et en utilisant divers outils combinatoires nous montrons la négligeabilité (au sens quantitatif) de propriétés non seulement syntaxiques (injectivité, surjectivité, présence d'états persistants ou envahissants), mais aussi dynamiques (nilpotence, certaines contraintes sur l'ensmble limites...). Et nous montrons à l'opposé que l'universalité intrinsèque , propriété qui semble à priori exigeante, est pour de nombreuses sous-familles une propriété très répandue.
En ce qui concerne le comportement typique à long terme d'un AC fixé, la mu-nipotence, que nous introduisons à partir de la notion d'ensembles mu-limites, permet de caractériser les AC convergeant presque toujours vers une configuration unique. Nous montrons que celle-ci n'est ni récursivement énumérable ni co-récursivement énumérable. Ceci montre que la difficulté calculatoire de la prédiction du comportement à long terme des AC n'est pas due à des ensembles de configurations négligeables. Nous exhibons aussi des ensembles mu-limites aux langages non récursifs.
Enfin nous montrons des résultats d'existence et de non-existence d'AC universels pour la relation de simulation dite surjective parmi certaines sous-familles.

Publications

Ce travail ainsi que d'autres résulats ont été publiés et présentés dans différentes conférences internationales (en anglais).