Traditionally, consistency is the only criterion for the quality of a theory in logic-based approaches to reasoning about actions. This work goes beyond that and contributes to the meta-theory of actions by investigating what other properties a good domain description should satisfy. Having Propositional Dynamic Logic (PDL) as background, we state some meta-theoretical postulates <br />concerning this sore spot. When all postulates are satisfied, we call the action theory modular. We point out the problems that arise when the postulates about modularity are violated, and propose algorithmic checks that can help the designer of an action theory to overcome them. Besides being easier to understand and more elaboration tolerant in McCarthy's sense, modular theories<br />have interesting computational properties. Moreover, we also propose a framework for updating domain descriptions and show the importance modularity has in action theory change.

Sécurisation du Contrôle d'Accès dans les Bases de Données

Cette thèse s'inscrit dans l'étude de familles de graphes infinis de présentation finie, de leurs propriétés structurelles, ainsi que des comparaisons entre ces familles. Étant donné un alphabet fini Σ, un graphe infini étiqueté par Σ peut être caractérisé par un ensemble fini de relations binaires (Ra )a∈Σ sur un domaine dénombrable V quelconque. De multiples caractérisations finies de tels ensembles de relations existent, soit de façon explicite grâce à des systèmes de réécriture ou à divers formalismes de la théorie des automates, soit de façon implicite. Après un survol des principaux résultats existants, nous nous intéressons plus particulièrement à trois problèmes. Dans un premier temps, nous définissons trois familles de systèmes de réécriture de termes dont nous démontrons que la rela- tion de dérivation peut être représentée de façon finie. De ces résultats découlent plusieurs questions sur les familles de graphes infinis correspondantes. Dans un se- cond temps, nous étudions deux familles de graphes dont les ensembles de traces forment la famille des langages contextuels, à savoir les graphes rationnels et les graphes linéairement bornés. Nous nous intéressons en particulier au cas des langages contextuels déterministes, ainsi qu'à la comparaison structurelle de ces deux familles. Enfin, d'un point de vue plus proche du domaine de la vérifica- tion, nous proposons un algorithme de calcul des prédécesseurs pour une famille d'automates à pile d'ordre supérieur.

Depuis plusieurs années, de nombreuses recherches ont été menées autour du diagnostic. Cependant, il est impératif de se préoccuper dès la phase de conception d'un système des objectifs de diagnostic à atteindre. Aussi, de nombreux travaux se sont intéressés à analyser et à caractériser les propriétés de la diagnosticabilité d'un système. La diagnosticabilité est la propriété d'un système garantissant qu'il génère des observations permettant de détecter et discriminer les fautes en temps fini après leur occurrence.Le sujet de cette thèse porte sur les méthodes permettant d'établir les propriétés de la diagnosticabilité des systèmes à événements discrets dans le cadre distribué, sans construction du modèle global du système. Ce cadre est de première importance pour les applications réelles : systèmes naturellement distribués, systèmes trop complexes pour traiter leur modèle global, confidentialité des modèles locaux les uns par rapport aux autres. L'analyse de la diagnosticabilité de tels systèmes distribués se fonde sur des opérations de synchronisation des modèles locaux, par les observations et les communications. D'abord, nous étudions comment optimiser cette analyse de la diagnosticabilité en faisant abstraction de l'information nécessaire et suffisante à partir des objets locaux pour décider la diagnosticabilité globale. L'efficacité de l'algorithme peut être grandement améliorée par la synchronisation des objets locaux et abstraits en comparaison avec celle des objets locaux et non abstraits.Ensuite, nous proposons, dans le cadre distribué, l'algorithme de la diagnosticabilité de motifs d'événements particuliers a priori inobservables dans les systèmes. Ces motifs peuvent être simplement l'occurrence, brutale ou graduelle, d'une faute permanente ou transitoire, plusieurs occurrences d'une faute, plusieurs fautes en cascade, etc. Dans le cadre distribué, la reconnaissance du motif d'événements s'effectue d'abord progressivement dans un sous-système et ensuite la diagnosticabilité de ce motif peut être déterminée par la méthode abstraite et distribuée. Nous prouvons la correction et l'efficacité de notre algorithme à la fois en théorie et en pratique par la mise en œuvre de l'implémentation sur des exemples.Finalement, nous étudions le problème de la diagnosticabilité dans les systèmes distribués avec composants autonomes, où l'information observable est distribuée au lieu d'être centralisée comme jusqu'alors. En d'autres termes, chaque composant ne peut appréhender que ses propres événements observables. Nous donnons la définition de la diagnosticabilité conjointe. Et puis nous discutons de l'indécidabilité de diagnosticabilité conjointe dans le cas général, c'est à dire, les événements de communication ne sont pas observables, avant de proposer un algorithme pour tester sa condition suffisante. De plus, nous obtenons également un résultat de décidabilité et de l'algorithme lorsque les communications sont observables.

La bioinformatique nécessite l'analyse de grandes quantités de données. Avec l'apparition de nouvelles technologies permettant un séquençage à haut débit à bas coût, la puissance de calcul requise pour traiter les données a énormément augmenté.. Cette thèse examine la possibilité d'utiliser les processeurs graphiques (GPU) pour des applications de bioinformatique. Dans un premier temps, ce travail s'intéresse au calcul des structures secondaires d'ARN. Ce problème est en général calculé par programmation dynamique, avec un algorithme qui pose de sérieux problèmes pour un code GPU. Nous introduisons une nouvelle implémentation tuilée qui fait apparaitre une bonne localité mémoire, permettant ainsi un programme GPU très efficace. Cette modification permet également de vectoriser le code CPU et donc de faire une comparaison honnête des performances entre GPU et CPU. Dans un deuxième temps, ce travail aborde le problème d'alignements de séquences. Nous présentons une parallélisation GPU d'une méthode utilisant une indexation par graines. L' implémentation sur GPU n'étant pas efficace, nous nous tournons vers le développement d'une version CPU. Notre contribution principale est le développement d'un nouvel algorithme éliminant rapidement les nombreux alignements potentiels, basé sur le précalcul de portions de la matrice de programmation dynamique. Ce nouvel algorithme a conduit au développement d'un nouveau programme d'alignement très efficace. Notre travail fournit l'exemple de deux problèmes différents dont seulement un a pu être efficacement parallélisé sur GPU. Ces deux expériences nous permettent d'évaluer l'efficacité des GPU et leur place en bioinformatique.

Ce travail de thèse s'est consacré à la comparaison de l'anatomie et de la fonction cardiaques à partir d'images médicales. Une première partie se concentre sur l'anatomie cardiaque avec une étude statistique de l'architecture des bres musculaires du c÷ur à partir d'IRM de tenseur de di usion. Dans la deuxième partie est proposée une comparaison la fonction cardiaque de di érents patients ou du même patient a di érents instants par le recalage spatiotemporel de séquences 4D CT. La complexe organisation des bres musculaires cardiaques a un rôle très important dans le comportement électrique et mécanique du c÷ur. Pour étudier cette architecture des bres, nous avons proposé de nouveaux outils algorithmiques d'analyse statistique d'IRM de tenseurs de di usion. La nouveauté de cette approche est de réaliser cette analyse statistique directement sur les tenseurs de di usion l'a où la plupart des études statistiques se font sur des vecteurs ou angles d'orientation décrivant les directions des bres et des feuillets. La variabilité de l'orientation des bres et des feuillets est ensuite directement donnée par la matrice de covariance des tenseurs de di usion de laquelle sont extraites les variabilités des vecteurs propres. L'application de ces outils a une base de données d'IRM de tenseur de di usion de c÷urs de chiens acquis ex vivo a permis d'obtenir un atlas de l'architecture des bres mais aussi de révééler une cohérence de l'orientation des bres et une plus grande variabilité de l'orientation des feuillets. Ensuite, nous avons comparé l'atlas de c÷urs de chien à un c÷ur humain et un modèle synthétique couramment utilisé pour des simulations électromé- caniques ou l'analyse d'images cardiaques. Le c÷ur humain s'est révélé plus proche des c÷urs de chien au niveau de l'orientation des bres que de celle des feuillets. Le modèle synthétique quant à lui s'est montré trop simple pour décrire en détails la complexité de l'architecture des bres. L'acquisition de séquences d'images cardiaques permet d'observer le mouvement cardiaque et donc sa fonction. Nous avons proposé un nouvel algorithme de recalage nonlin éaire spatiotemporel de séquences d'images qui permet de comparer cette fonction cardiaque. Le recalage temporel assure la mise en correspondance d'instants physiologiques similaires. Le recalage spatial quant à lui doit assure une cohérence entre le mouvement des points physiques intra-séquence et leur mise en correspondance inter-séquence. Cette cohérence est assurée par les contraintes de trajectoires liant les transformations intras équences décrivant le mouvement cardiaque aux transformations inter-séquences décrivant les di érences anatomiques au cours du temps. Sous ces contraintes de trajectoires, le recalage spatial 4D est simpli é en un recalage multicanal 3D résolu avec une nouvelle version des Demons Di eomorphes Multicanaux. Cette méthode de recalage spatiotemporel est appliquée au recalage inter-sujet de séquences 4D CT pour évaluation. Comparée a d'autres techniques existantes, cette technique de recalage s'est révélée le meilleur compromis en terme de précision, de régularité spatiale et temporelle, mais aussi de temps de calcul. Un exemple d'application possible du recalage spatiotemporal est proposé avec la comparaison de l'anatomie et de la fonction cardiaques avant et après thérapie.

Des charrettes de la civilisation ancienne au Véhicule Utilitaire Sportif (VUS) actuels, la dépendance de l'homme pour les véhicules reste incontournable. Les avancements rapides des infrastructures de transport aujourd'hui, couplé au désir de voyager de plus en plus rapidement, conduisent à de graves problèmes de transport: accidents, pollution et embouteillages. Afin de réduire ces problèmes et augmenter la capacité de l'infrastructure actuelle, plusieurs approches ont été proposées. Les résultats se présentent, d'une part, sous forme de panneau à message variable qui affiche la situation du trafic aux conducteurs sur la route ; d' autre part, sous forme de dos d'âne pour la prévention des accidents en réduisant la vitesse des conducteurs dans les zones urbaines ; et enfin sous forme de décisions gouvernementale permettant de lutter contre la pollution en interdisant, les jours de forte pollution, l'accès au centre-ville pour les véhicules avec des numéros immatriculés pair ou impair. A la fin du XXe siècle, des efforts considérables sont apparus pour introduire l'intelligence dans les systèmes de transport. Afin de s'adapter à la complexité du système de transport, cela constitue un des facteurs déterminants pour une action durable et plus efficace. Au début, les initiatives se sont limitées au niveau de la télésurveillance sur les incidents de la circulation à l'aide de caméras pour en informer les utilisateurs via des panneaux à messages. Peu après, avec l'avènement de la communication sans fil, le monde a ouvert ses portes en direction de la recherche sur la communication inter-véhiculaires. Plus précisément, en permettant aux véhicules de détecter et de communiquer automatiquement sur les incidents de trafic avec d'autres véhicules on peut atteindre une connaissance étendue sur la situation de la circulation locale autour du conducteur. C'est un facteur très important pour l'installation efficace du Système des Transports Intelligent (STI). A l'heure actuelle, le principal défi est d'exploiter et utiliser efficacement la communication entre les véhicules afin de réduire, sinon éliminer complètement, les problèmes précités: accidents - par le biais de la sécurité active ; la pollution et les embouteillages - grâce à la fluidité du trafic et en guidant les conducteurs des transports à emprunter des itinéraires qui permettent d'économiser la consommation d'énergie et réduire les émissions. Cette thèse présente un élément important qui réalise le déploiement d'une STI à grande échelle: la communication entre les véhicules sur la route. Ce manuscrit est consacré au développement d'un algorithme de diffusion "Multi-Hop Vehicular Broadcast"(MHVB), en utilisant la localisation de véhicules pour permettre la communication entre les véhicules.

Les récents progrès réalisés en matière de communication (réseaux hauts débits, normalisation des protocoles et des architectures à objets répartis, explosion de l'internet) conduisent à l'apparition de systèmes de gestion de données et services largement répartis. Les données sont produites à la demande ou de manière continue au travers de divers dispositifs statiques ou mobiles. Cette thèse présente une approche pour l'évaluation de requêtes dites hybrides car intégrant différents aspects des données mobiles, continues, cachées rencontrées dans des environnements dynamiques. Notre approche consiste à représenter une telle requête comme une coordination de services comprenant des services de données et de calcul. Une telle coordination est définie par le flux de la requête et ceux d'opérateurs sur les données (e.g. join, select, union). Un flux de requête représente une expression construite avec les opérateurs de notre modèle de données. Ce flux est construit par un algorithme de ré-écriture à partir de la requête spécifiée dans notre langage de requête HSQL Les flux dit opérateurs composent des services de calcul afin de permettre l'évaluation d'un opérateur particulier. Le processeur de requêtes basées sur les services hybrides que nous avons développé met en mise en œuvre et valide nos propositions.

Soit un langage composé par tous les mots d'une longueur donnée $n$. Un cycle de de Bruijn d'ordre $n$ est un mot cyclique tel que tous les mots du langage apparaissent exactement une fois comme facteurs de ce cycle. Un algorithme pour construire le cycle de de Bruijn lexicographiquement minimal est dû à Fredricksen et Maiorana, il utilise les mots de Lyndon du langage. Cette thèse étudie comment généraliser le concept de cycles de de Bruijn pour un langage composé par un sous-ensemble de mots de longueur $n$, en particulier les langages de tous les mots de longueur $n$ sans facteurs dans une liste de facteurs interdits. Premièrement, nous étudions le cas des mots sans le facteur 11. Nous fournissons de nouvelles preuves de l'algorithme de Fredricksen et Maiorana qui nous permettent de prolonger ce resultat au cas des mots sans le facteur $1^i$ pour n'importe quel $i$. Nous caractérisons pour quels langages de mots de longueur $n$ existe un cycle de de Bruijn, et nous étudions également quelques propriétés de la dynamique symbolique de ces langages, en particulier des langages définis par des facteurs interdits. Pour ces genres de langages, nous présentons un algorithme pour produire un cycle de de Bruijn, en utilisant les mots de Lyndon du langage. Ces résultats utilisent la notion du graphe de de Bruijn et réduit le problème à construire un cycle eulérien dans ce graphe. Nous étudions le problème de la construction du cycle minimal dans un langage avec des facteurs interdits en employant le graphe de de Bruijn. Nous étudions deux algorithmes, un algorithme glouton simple et efficace qui fonctionne avec quelques familles de langages, et un algorithme plus complexe qui résout ce problème pour n'importe quel graphe eulérien.

De nombreux outils ont été développés pour faire évoluer au cours du temps une application et/ou sa plate-forme d'exécution en fonction de l'apparition de nouveaux besoins. Dans le cadre de Java, ils se présentent souvent sous la forme de nouveaux compilateurs manipulant un langage Java enrichi, de chargeurs de classes évolués qui modifient le code compilé de l'application afin d'ajouter à celle-ci de nouvelles propriétés, ou encore de machines virtuelles spécialisées. Cependant ces différents outils sont diffcilement combinables entre eux et/ou réutilisables en dehors de leur contexte. C'est pourquoi nous proposons, dans le cadre de Java, une machine virtuelle ouverte et entièrement écrite en Java pour conserver la portabilité, capable d'évoluer au cours du temps. Elle dispose d'une architecture à composants qui s'inspire le plus fidèlement possible de la spécification de Sun Microsystems. Un composant de Corosol est une abstraction des unités fonctionnelles d'une machine virtuelle (comme le chargeur de classes ou les fils d'exécution), mais aussi des unités de stockage (comme le tas ou la pile d'exécution) et de tous les mécanismes internes liés à l'exécution (comme la résolution dynamique de méthodes). L'architecture de Corosol est décrite par des interfaces, qui spécifient les services des composants mais aussi comment ils s'intègrent dans Corosol et communiquent entre eux. Une implantation par défaut est fournie pour chaque composant. L'implantation de chaque composant peut être choisie avant le démarrage de Corosol par simple paramétrage. Cependant, l'originalité principale de notre machine virtuelle est une puissante interface d'introspection. Elle permet d'une part à l'application de consulter à tout instant les caractéristiques de sa plate-forme d'exécution afin de pouvoir s'y adapter. D'autre part, elle autorise l'application qui s'exécute à créer des composants pour la machine virtuelle à partir d'objets qui lui sont propres, et à changer les composants existants par les nouveaux, à n'importe quel moment. Notre travail a principalement consisté à définir et implanter cette interface d'introspection.