Langages formels : quelques aspects quantitatifs
Institution:
Université Joseph Fourier (Grenoble)Disciplines:
Directors:
Abstract EN:
Ln this thesis, we present three rather different research directions concerning with quantitative aspects of formai 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 su ch 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 tAis 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.
Abstract FR:
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 coat 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é.