Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 4 Décembre 2012

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

par Cyril Nicaud (LIGM, Paris-Est)

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

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr