Taille de la partie accessible d’un automate aléatoire

On tire au hasard un automate déterministe et complet avec n états en choisissant uniformément au hasard l’image de chaque transition. Si on place ensuite un état initial au hasard, on se rend compte que l’automate n’a que très peu de chances d’être accessible.

On va s’intéresser à la partie accessible d’un tel automate aléatoire, notamment pour des raisons algorithmiques liées à la génération aléatoire. En effet, on remarque facilement que deux automates accessibles de même taille m ≤ n ont la même probabilité d’être la partie accessible d’un automate aléatoire : tirer au sort l’automate et se restreindre à la partie accessible donne un générateur uniforme à taille fixée.

Il reste donc à étudier la variable aléatoire qui correspond à la taille de la partie accessible, ce qui sera présenté dans l’exposé. Cette étude s’avère être riche en conséquences : on valide un très efficace procédé de génération d’automates accessibles, on reformule de façon probabiliste un résultat de dénombrement sur les automates, et on a une méthode pour démontrer des propriétés statistiques sur les automates accessible en les étudiants sur les automates sans la contrainte d’accessibilité.

C’est un travail effectué en collaboration avec Arnaud Carayol.