Automata on timed structures
Automate sur les structures temporisée
Résumé
Digital system are now part of our society. They are used in a wide range of domainsand in particular they have to handle delicate tasks. Already used in domainssuch as transportation, surgery or economy, we speak now of using digital systemsfor social or political matters : electronic vote, selection algorithms, electoralprofilingdots For task handled by algorithm, the responsibility is moved from theexecutioner to the designer, developer and tester of those algorithms. It is alsothe responsibility of computer scientists who study those algorithms to proposereliable techniques of verification which will be applicable in the design, thedevelopment or the testing phase. Formal verification methods provide mathematicaltools to prevent executions error in all phases. Among them, fault-diagnosis consiston the construction of a diagnoser based on a formal model of the system we aim tocheck. The diagnoser runs in parallel with the real system and emit a warning anytime it detect a dangerous behavior. For systems modeled by timed automata, it isnot always possible to construct a timed automaton to diagnose it. Indeed timed automata,introduce in the nineties by cite{AD94} and widely studied and used since to modeltimed systems, are not determinizable. A machine, more powerful than a timed automaton,can still be used to construct the diagnoser of a timed automaton as it is done incite{Tripakis02}. This thesis work aim at constructing a diagnoser for any one-clocktimed automata. This diagnoser is constructed with the help of a machine more powerfulthan timed automata, following the idea of cite{Tripakis02}. Part~I of this thesisintroduce a formal framework for the modeling of quantitative systems and the study oftheir determinization. In this framework we introduce automata on timed structures,the model used to construct the diagnoser. Part~II study the determinization problemof automata on timed structures, and particularly the one of timed automatadeterminization in this framework. Part~III illustrate how automata on timed structurescan be used to construct in a generic way a diagnoser for one clock timed automata.This technique is implemented in a tool, DOTA , and is compared to the technique usedin cite{Tripakis02}.
Les systèmes digitaux jouent un rôle croissant dans le bon fonctionnement de notre société.Au delà de la grande diversité de leur domaines d'utilisations, on confie aujourd'hui destâches importantes à des algorithmes. Déjà largement utilisés dans des domaines aussi délicatque le transport, la chirurgie ou l'économie, il est aujourd'hui de plus en plus question defaire de la place aux systèmes digitaux dans les domaines sociaux et politiques :vote électronique, algorithmes de sélection, profilage électoraldotsPour les tâches confiées à des algorithmes, la responsabilité est déplacées de l'exécutantvers les concepteurs, développeurs et testeurs de ces algorithmes. Il incombe aussi auxchercheurs qui étudient ces algorithmes de proposer des techniques de vérifications fiablequi pourront être utilisées à tous les niveaux : conception, développement et test.Les méthodes de vérifications formelles donnent des outils mathématiques pourprévenir des erreurs à chaque niveaux. Parmi elle, le diagnostic d'erreur consiste en lacréation d'un diagnostiqueur basé sur un modèle formel du système à vérifier.Le diagnostiqueur est exécuté en parallèle du système qu'il doit surveiller et prévientun contrôleur si il détecte un comportement dangereux du système.Pour les systèmes modélisés par des automates temporisés, il n'est pas toujours possiblede construire un diagnostiqueur sous la forme d'un autre automate temporisé. En effetles automates temporisés, introduits par cite{AD94} dans les années 90 et largementétudiés et utilisés depuis pour modéliser des systèmes avec contraintes temporelles,ne sont pas déterminisable. Une machine plus puissante qu'un automate temporisé peutcependant être utilisée pour construire le diagnostiqueur d'un automate temporisé commele montre cite{Tripakis02}. L'aboutissement de ce travail de thèse est la constructionautomatique d'un diagnostiqueur pour les automates temporisés à une horloge.Ce diagnostiqueur, dans le même esprit que celui de cite{Tripakis02}, est une machineplus puissante qu'un automate temporisé. La partie~I du manuscrit introduit un cadreformel pour ce type de machine et plus généralement pour la modélisation et ladéterminisation de systèmes quantitatifs. Y est introduit le modèle des automates surstructures temporisés, qui apporte un nouveau point de vue sur la manière de modéliserles systèmes avec variables quantitatives. La partie~II étudie le problème de ladéterminisation des automates sur structures temporises, et plus spécifiquement celuides automates temporisés qui peuvent se traduire dans ce cadre nouveau cadre formel.La partie~III montre comment utiliser les automates sur structure temporisés pourconstruire de manière générique un diagnostiqueur pour les automate temporisés à unehorloge. Cette technique est implémentée dans un outils, DOTA , et comparée à lamachine construite par cite{Tripakis02}.
Origine : Version validée par le jury (STAR)
Loading...