Recherche

Thèmes de recherche

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

La quantification de propriétés parmi l'ensemble des AC, la recherche de comportements typiques
L'étude des comportements à long terme moyen d'AC fixés à travers la notion d'ensembles mu-limites.
Les relations de simulation intrinsèques au modèle et les propriétés d'universalités associées.
L'étude de sous-classe particulières des AC ayant des propriétés significatives, par exemple les AC multi-ensemblistes ou encore les AC persistants.

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

Julien Cervelle (Président),
Jean Mairesse (Rapporteur),
Enrico Formenti (Rapporteur),
Martin Kutrib (Examinateur),
Laurent Vuillon (directeur)
et Guillaume Theyssier (directeur).

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).

Construction of mu-limit sets.
With Martin Delacourt and Mathieu Sablik.
JAC 2010 [article en archives ouvertes]
Construction of Mu-limit Sets A mu-limit set is a subshift whose forbidden patterns are exactly those, whose probabilities tend to zero as time tends to infinity. In this article, for a given subshift in a large class of subshifts, we propose the construction of a cellular automaton which realizes this subshift as mu-limit set where mu is the uniform Bernoulli measure.
On Factor Universality in Symbolic Spaces.
With Guillaume Theyssier.
MFCS 2010 [article en archives ouvertes]
The study of factoring relations between subshifts or cellular automata is central in symbolic dynamics. Besides, a notion of intrinsic universality for cellular automata based on an operation of rescaling is receiving more and more attention in the literature. In this paper, we propose to study the factoring relation up to rescalings, and ask for the existence of universal objects for that simulation relation. In classical simulations of a system S by a system T , the simulation takes place on a specific subset of configurations of T depending on S (this is the case for intrinsic universality). Our setting, however, asks for every configurations of T to have a meaningful interpretation in S. Despite this strong requirement, we show that there exists a cellular automaton able to simulate any other in a large class containing arbitrarily complex ones. We also consider the case of subshifts and, using arguments from recursion theory, we give negative results about the existence of universal objects in some classes.
On Local Symmetries and Universality in Cellular Automata.
With Guillaume Theyssier.
STACS 2009 [article en archives ouvertes]
Cellular automata (CA) are dynamical systems defined by a finite local rule but they are studied for their global dynamics. They can exhibit a wide range of complex behaviours and a celebrated result is the existence of (intrinsically) universal CA, that is CA able to fully simulate any other CA. In this paper, we show that the asymptotic density of universal cellular automata is 1 in several families of CA defined by local symmetries. We extend results previously established for captive cellular automata in two significant ways. First, our results apply to well-known families of CA (e.g. the family of outer-totalistic CA containing the Game of Life) and, second, we obtain such density results with both increasing number of states and increasing neighbourhood. Moreover, thanks to universality-preserving encodings, we show that the universality problem remains undecidable in some of those families.
On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures.
With Guillaume Theyssier and Victor Poupet.
MFCS 2006 [article en archives ouvertes]
We study the notion of limit sets of cellular automata associated with probability measures (mu-limit sets). This notion was introduced by P. Kurka and A. Maass. It is a refinement of the classical notion of omega-limit sets dealing with the typical long term behavior of cellular automata. It focuses on the words whose probability of appearance does not tend to 0 as time tends to infinity (the persistent words). In this paper, we give a characterisation of the persistent language for non sensible cellular automata associated with Bernouilli measures. We also study the computational complexity of these languages. We show that the persistent language can be non-recursive. But our main result is that the set of quasi-nilpotent cellular automata (those with a single configuration in their mu-limit set) is neither recursively enumerable nor co-recursively enumerable.