Amphithéâtre CTL
21 octobre 2009 - 14h00
Langages formels: quelques aspects quantitatifs (Phd Defense)
par Aldric Degorre de Vérimag
Résumé : Dans cette thèse nous présentons trois directions de recherche assez différentes concernant les aspects quantitatifs des langages formels.
La première étudie des problèmes d'ordonnancement avec à la fois des dépendances entre tâches à ordonnancer et des comportements infinis et imprévisibles: les flux de requêtes appartenant à un langage temporisé. Nous montrons, d'un côté, que même en se limitant à des flux de requêtes qui ne demandent pas plus de travail que le système peut en fournir, il est impossible de garantir une latence bornée dans un ordonnancement. De l'autre nous montrons que malgré cela, des stratégies d'ordonnancement à retard borné existent pour tout langage de tels flux.
La seconde s'intéresse aux oméga-langages définis en contraignant le coût moyen d'une exécution infinie sur un automate pondéré. Nous montrons que ces classes de langages sont incomparable avec celle des langages réguliers, ainsi qu'entre elles. Nous caractérisons la clôture booléenne des classes de langages à seuils simples en introduisant des coûts multidimensionnels, et nous donnons un algorithme permettant de décider du vide sur cette classe.
Enfin, dans la troisième, nous définissons le volume et l'entropie pour les langages temporisés réguliers. Nous donnons une formule récurrente pour calculer le volume et trois méthodes pour soit calculer, soit approximer l'entropie. Les deux premières utilisent des résultats d'analyse fonctionnelle et ramènent l'entropie au logarithme du rayon spectral d'un certain opérateur. La troisième consiste à discrétiser l'automate temporisé, y appliquer les méthodes déjà connues pour le cas discret et en déduire l'entropie du langage temporisé.
Jury composé de:
- Dominique Perrin, professeur à l'Université de Marne-la-Vallée, rapporteur
- Jean-François Raskin, professeur à l'Université Libre de Bruxelles, rapporteur
- Eugene Asarin, professeur à l'Université de Paris 7
- Paul Gastin, professeur à l'École Normale Supérieure de Cachan
- Claude Jard, professeur à l'École Normale Supérieure de Cachan
- Yassine Lakhnech, professeur à l'Université Joseph Fourier
- Oded Maler, directeur de recherches à Vérimag, directeur de thèse
