Laboratoire : LIAFA, équipe Verif
Responsables : Eugene Asarin (Prof. P7)
Contacts : asarin@liafa.jussieu.fr
La dynamique symbolique considère les automates finis/langages réguliers comme systèmes dynamiques, et applique à ces systèmes des techniques mathématiques habituelles dans le domaine de systèmes dynamiques. Ce point de vue, complémentaire à la théorie de langages classique, permet de poser des nombreuses questions intéressantes et utiles (en particulier pour l’étude des codes) et y répondre. Ainsi la notion de l’entropie permet de mesurer la quantité de l’information dans un mot typique d’un langage régulier.
Les langages temporisés (étudiés depuis une quinzaine d’années) représentent les comportements de systèmes pour lesquels non seulement l'ordre d'événements, mais aussi les intervalles de temps entre ces événements sont importants. Un ensemble de comportements temporisés (langage), à la différence d’un langage classique, n’est plus un ensemble discret, il a une certaine « épaisseur », peut être vu comme une union des sous-ensembles de Rn. Dans une série de travaux récents [1] nous avons défini les notions de volume, et surtout de l’entropie de tels langages, des notions qui permettent d’évaluer la taille de langages temporisés et la quantité d’information dans leurs éléments. Le calcul de volume et de l’entropie s’appuie sur les équations de langages qui sont à leur tour transformées en équations intégrales, étudiées ensuite avec les méthodes d’analyse fonctionnelle.
Le but de ce stage consiste à appliquer l’approche de la dynamique symbolique aux langages réguliers temporisés en répondant à certaines parmi les questions suivantes :
· Comment associer un système dynamique à un langage (ou automate) temporisé ?
· Comment décrire les actions de semi-groupes R+ et S* ?
· Comment définir l’opérateur infinitésimal pour l’action de R+ ?
· Comment décrire un langage temporisé par des équations différentielles de langage ?
· Comment définir et calculer l’entropie d’un automate temporisé vu comme système dynamique ?
· Quels sont les liens de cette entropie avec l’entropie définie dans [1].
Si l’approche s’avère fructueuse, le stage peut être continué par une thèse.
Il serait préférable pour le candidat d’avoir suivi le cours sur la vérification des automates temporisés (2-8). Autres cours qui peuvent être utiles : 2-9, 2-16, 2-14. Certaines connaissances en algèbre linéaire et géométrie, analyse fonctionnelle, théorie ergodique seront utilisés lors de stage, mais il est tout à fait envisageable de les acquérir pendant le premier mois du travail.
[1] E. Asarin, A. Degorre, Volume and Entropy of Regular Timed Languages (2009) hal-00369812 (2 articles extraits de ce travail ont été publié à CONCUR’09 et FORMATS’09).