Stage Recherche M2 : Laboratoire SAMOVAR (Evry, Télécom SudParis)

Bonjour à tous

L'équipe Méthodes du laboratoire SAMOVAR propose cette année un stage recherche de niveau M2 et d'une durée d'environ 6 mois.

Problèmes d'identification d'états dans des automates
Walid Ben-Ameur, Natalia Kushik, Dimitri Watel

Mots-clefs : Automates, Graphes, Complexité algorithmique et paramétrée, Programmation mathématique, Conjecture de Cerný

Problèmes étudiés

Ce sujet de stage, fortement orienté recherche et pouvant être suivi d'une thèse de doctorat, s'intéresse à un problème de recherche de séquence particulière dans un automate à états fini. Un tel automate est constitué d'états et de transitions entre ces états. Chaque transition est associée à un symbole de lecture et un symbole observé. À chaque itération, la machine est dans un certain état s. Elle lit un symbole x sur une bande en entrée, utilise la transition quittant s ayant le symbole de lecture x et on observe alors le second symbole de cette transition.

Prenons, par exemple, l'automate suivant.

Si l'automate est dans l'état D et si la bande en entrée contient le mot 11001 alors en suivant les transitions, on se retrouve dans l'état A et on observe le mot 11110.

On s'intéresse dans ce stage à des mots de la bande en entrée permettant de donner des informations sur les états dans lequel l'automate s'est trouvé dans le passé, se trouve maintenant ou se trouvera dans le futur. Entre autres, on s'intéresse aux séquences synchronisantes et aux séquences distinctives. Un mot est synchronisant s'il permet de déterminer, à l'issue de la lecture du mot de la bande en entrée, dans quel état se trouve la machine, quel que soit l'état dans lequel elle se trouvait initialement. Par exemple, dans l'automate ci-dessus, le mot 111 est synchronisant car quel que soit l'état de départ, l'automate se retrouve dans l'état A. Un mot est distinctif s'il permet, à l'aide de l'observation associée, de dire dans quel état se trouvait la machine avant la lecture du mot. Par exemple, ci-dessus, le mot 111 est également distinctif. Car le mot observé sera différent selon qu'on est parti de l'état A (mot 111), B (mot 011), C (mot 101) ou D (mot 110).

Un objectif classique consiste, connaissant un automate, à trouver une séquence synchronisante/distinctive la plus courte possible.

Travail attendu pendant le stage

Ce stage est un stage exploratoire. Les méthodes classiques de la recherche opérationnelle n'ont été que peu ou pas du tout utilisées pour tenter de résoudre ces problèmes ou d'en prouver des propriétés théoriques. Il s'agira donc de travailler sur les problèmes susmentionnés ou des variantes de ces problèmes d'un point de vue recherche sur l'une ou plusieurs des pistes suivantes.

• complexité, approximabilité, complexité paramétrée
• modélisation et résolution par programmation mathématique
• étude de la Conjecture de Cerný (Il existe toujours une séquence synchronisante de taille au plus (n - 1)^2 dans un automate déterministe avec n états.)

Déroulement et détails pratiques

Le stage se déroulera dans l'enceinte de l'école Télécom SudParis, au 9 Rue Charles Fourier, 91000 Évry / 19 Place Marguerite Perey, 91120 Palaiseau. Le stagiaire sera accueilli au sein de l'équipe Méthodes du laboratoire SAMOVAR à l'un des 2 sites (Evry ou Palaiseau) selon sa convenance. Le niveau du stagiaire attendu est celui d'un BAC+5 avec des connaissances en informatique théorique et notamment en recherche opérationnelle. La durée du stage sera d'environ 6 mois.

Contacts :

Walid Ben-Ameur, Professeur de l'équipe Méthodes, Telecom SudParis, Bureau 4A 244 (Palaiseau)
Tél : +33 1 75 31 44 24 (Palaiseau) et +33 1 60 76 47 13 (Evry)
Mail : walid.benameur@telecom-sudparis.eu

Natalia Kushik, Maître de conférence de l'équipe Méthodes, Telecom SudParis, Bureau 4A 239 (Palaiseau)
Tél : +33 1 75 31 44 19
Mail : natalia.kushik@telecom-sudparis.eu

Dimitri Watel, Enseignant chercheur de l'équipe Méthodes, ENSIIE Bureau 119 (Evry)
Tél : +33 1 69 36 74 44
Mail : dimitri.watel@ensiie.fr