Amphithéâtre CTL
21 October 2009 - 14h00
On Some Quantitative Aspects of Formal Languages (Phd Defense)
by Aldric Degorre from Vérimag
Abstract: In this thesis, we present three rather different research directions concerning with quantitative aspects of formal languages.
The first one studies scheduling problems having both dependencies between tasks and uncertain infinite behaviors: request streams belong to some timed language. We show, on one hand, that even restricting the study to request streams that do not require more work than the system can provide, it is not possible to guarantee schedules with bounded latency. On the other hand, we show that despite this, scheduling strategies with bounded backlog do exist for any language of such streams.
The second one considers omega-languages we defined by constraining the average cost of an infinite run on a weighted automaton. We show that these language classes are incomparable both to the class of regular languages and to each other. We characterize the boolean closure of the classes of single threshold languages by introducing multidimensional costs and we give an algorithm for deciding emptiness on this class.
Last, in the third one, we define volume and entropy for regular timed languages. We give a recurrent formula for computing volume, and three methods for either computing or approximating entropy. The two first ones use results from functional analysis and reduce the problem to that of finding the logarithm of the spectral radius of some operator. The third method consists in discretizing the timed automaton, applying methods already known for the discrete case and deduce the entropy of the timed language.
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
