Laboratoire d'informatique de l'École polytechnique

GT Combi: «Génération aléatoires d'automates non-déterministes "intéressants"» par Julien David

Speaker: Julien David (LIPN)
Location: Salle Philippe Flajolet, bât. Alan Turing
Date: Mer. 14 déc. 2016, 11h00-12h00

Le prochain GT Combi du Plateau de Saclay aura lieu ce mercredi 14 décembre à 11h dans la salle Philippe Flajolet du LIX. Julien David (LIPN) nous parlera de «Génération aléatoires d’automates non-déterministes “intéressants”».

Résumé: Les automates finis sont le modèle de calcul le plus simple de la hiérarchie de Chomsky-Schützenberger. Ces machines à états finis reconnaissent les langages rationnels, appréciés pour leur propriétés de clôtures, souvent calculable en temps polynomial. Un automate déterministe (définition simplifiée pour ce résumé) est un automate pour lequel pour tout état, pour une action donnée, il existe au plus un état d’arrivée. Pour tout automate non-déterministe, il existe un automate déterministe qui reconnaît le même langage. L’opération permettant de calculer cet automate, appelée déterminisation, a un coût exponentiel dans le pire des cas. La génération aléatoire d’objets combinatoires est un outil puissant pour conduire des études expérimentales sur les propriétés moyennes et limites des objets engendrés, ainsi que sur les algorithmes qui s’y appliquent. Si plusieurs solutions efficaces existent pour engendrer des automates déterministes aléatoirement, la question même d’un modèle intéressant se pose pour les automates non-déterministes. Je proposerai donc un ensemble de modèles et une solution efficace pour ce problème. Aucun prérequis n’est nécessaire pour cet exposé.