Cette thèse présente un algorithme qui élimine les racines carrées et les divisions dans des programmes sans boucles, utilisés dans des systèmes embarqués, tout en préservant la sémantique. L'élimination de ces opérations permet d'éviter les erreurs d'arrondis à l'exécution, ces erreurs d'arrondis pouvant entraîner un comportement complètement inattendu de la part du programme. Cette trans- formation respecte les contraintes du code embarqué, en particulier la nécessité pour le programme produit de s'exécuter en mémoire fixe. Cette transformation utilise deux algorithmes fondamentaux développés dans cette thèse. Le premier permet d'éliminer les racines carrées et les divisions des expressions booléennes contenant des comparaisons d'expressions arithmétiques. Le second est un algorithme qui résout un problème d'anti-unification particulier, que nous appelons anti-unification contrainte. Cette transformation de programme est définie et prouvée dans l'assistant de preuves PVS. Elle est aussi implantée comme une stratégie de ce système. L'anti-unification contrainte est aussi utilisée pour étendre la transformation à des programmes contenant des fonctions. Elle permet ainsi d'éliminer les racines carrées et les divisions de spécifications écrites en PVS. La robustesse de cette méthode est mise en valeur par un exemple conséquent: l'élimination des racines carrées et des divisions dans un programme de détection des conflits aériens.

Cette thèse s'intéresse à la modélisation de la syntaxe et de l'interface syntaxe-sémantique de la phrase, et explore la possibilité de contrôler au niveau des structures de dérivation la surgénération que produit le traitement des dépendances à distance par des types d'ordre supérieur. À cet effet, nous étudions la possibilité d'étendre le système de typage des Grammaires Catégorielles Abstraites avec les constructions de la somme disjointe, du produit cartésien et du produit dépendant, permettant d'étiqueter les catégories syntaxiques par des structures de traits. Nous prouvons dans un premier temps que le calcul résultant de cette extension bénéficie des propriétés de confluence et de normalisation, permettant d'identifier les termes beta-équivalents dans le formalisme grammatical. Nous réduisons de plus le même problème pour la beta-eta-équivalence à un ensemble d'hypothèse de départ. Dans un second temps, nous montrons comment cette introduction de structures de traits peut être appliquée au contrôle des dépendances à distances, à travers les exemples des contraintes de cas, des îlots d'extraction pour les mouvements explicites et implicites, et des extractions interrogatives multiples, et nous discutons de la pertinence de placer ces contrôles sur les structures de dérivation.

La thèse contribue à la compréhension de la nature, du rôle et des mécanismes de la polarisation dans les langages de programmation, en théorie de la preuve et dans les modèles catégoriels. La polarisation correspond à l'idée que la condition d'associativité de la composition peut être relâchée, comme on le montre à travers un résultat qui relie les duploïdes, notre modèle direct de la polarisation, aux adjonctions. En conséquence, la polarisation sous-tend de nombreux modèles du calcul, ce que l'on souligne encore en montrant comment les modèles par passage de continuation pour des opérateurs de contrôle délimité se décomposent en trois étapes fondamentales. Elle explique également des phénomènes de constructivité en théorie de la démonstration, ce que l'on illustre en donnant une interprétation selon le principe de la formule comme type à la polarisation en général et à une négation involutive en particulier. Notre approche est basée sur une représentation interactive des démonstrations et des programmes à base de termes (calcul L), qui met en évidence la structure des polarités. Celle-ci est basée sur la correspondance entre les machines abstraites et les calculs de séquents, et vise à synthétiser diverses directions : la modélisation du contrôle, de l'ordre d'évaluation et des effets dans les langages de programmation, la quête d'un lien entre la dualité catégorielle et les continuations, et l'approche interactive de la constructivité en théorie de la preuve. On introduit notre technique en supposant uniquement une connaissance élémentaire du λ-calcul simplement typé et de la réécriture.

Cette thèse d'HDR en anglais, présente l'essentiel de mes travaux de 1996 à 2005. Voir le résumé anglais pour plus de détails.

Concevoir et mettre en œuvre des méthodes pour la spécification, l'analyse et la vérification de logiciels et de systèmes sont les principaux moteurs des activités de recherche présentées dans ce manuscrit. Dans ce cadre, nos travaux se positionnent dans la catégorie dite des méthodes formelles appartenant à la communauté plus large du génie logiciel. A l'interface des travaux théoriques et applicatifs, notre objectif est de contribuer aux méthodes permettant d'assurer la correction et la sûreté des systèmes (fonctionnalité, sécurité, fiabilité, ...) en développant ou en améliorant des langages de spécification, des techniques et des outils permettant leur analyse formelle. Dans ce but, nous nous sommes attaché dans cette thèse à proposer et à étudier un cadre formel permettant la définition de politiques de sécurité et la vérification de leurs propriétés. A cet effet, nous avons proposé un cadre pour la spécification de politiques de sécurité basé sur une approche modulaire dans laquelle une politique est vue comme la composition d'un modèle de sécurité et d'une configuration. Nous avons investigué les possibilités offertes par de telles spécifications lorsque les modèles sont exprimés au moyen de contraintes du premier ordre et les configurations au moyen de programmes logiques. En particulier, nous avons proposé un algorithme permettant de transformer une politique exprimée dans un modèle donné vers une autre politique équivalente (au sens où elle engendre les mêmes autorisations) exprimée dans un autre modèle. Dans un second temps, nous nous sommes proposé de tenir compte des aspects dynamiques de la configuration d'une politique vue comme un état du système sur lequel la politique est mise en œuvre et où chaque action est associée à une procédure de modification des états. Nous avons proposé un langage formel simple pour spécifier séparément les systèmes et les politiques de sécurité puis avons donné une sémantique des spécifications exprimées dans ce cadre sous la forme de systèmes de réécriture. Nous nous sommes ensuite attachés à montrer que les systèmes de réécriture obtenus permettent l'étude de propriétés de sécurité. Dans une troisième partie, nous nous sommes focalisé sur les mécanismes permettant la mise en œuvre de politiques de sécurité dans les réseaux. Dans ce cadre, nous avons proposé une spécification des firewalls et de leurs compositions basée sur les automates d'arbres et les systèmes de réécriture puis avons montré en quoi ces spécifications nous permettent d'analyser de façon automatique les politiques de sécurité sous-jacentes.

Les questions <EM>"Qu'est-ce qu'une preuve?"</EM> et <EM>"Quand deux preuves sont-elles identiques?"</EM> sont fondamentales pour la théorie de la preuve. Mais pour la logique classique propositionnelle --- la logique la plus répandue --- nous n'avons pas encore de réponse satisfaisante. C'est embarrassant non seulement pour la théorie de la preuve, mais aussi pour l'informatique, où la logique classique joue un rôle majeur dans le raisonnement automatique et dans la programmation logique. De même, l'architecture des processeurs est fondée sur la logique classique. Tous les domaines dans lesquels la recherche de preuve est employée peuvent bénéficier d'une meilleure compréhension de la notion de preuve en logique classique, et le célèbre problème NP-vs-coNP peut être réduit à la question de savoir s'il existe une preuve courte (c'est-à-dire, de taille polynomiale) pour chaque tautologie booléenne. Normalement, les preuves sont étudiées comme des objets syntaxiques au sein de systèmes déductifs (par exemple, les tableaux, le calcul des séquents, la résolution, ...). Ici, nous prenons le point de vue que ces objets syntaxiques (également connus sous le nom d'arbres de preuve) doivent être considérés comme des représentations concrètes des objets abstraits que sont les preuves, et qu'un tel objet abstrait peut être représenté par un arbre en résolution ou dans le calcul des séquents. Le thème principal de ce travail est d'améliorer notre compréhension des objets abstraits que sont les preuves, et cela se fera sous trois angles différents, étudiés dans les trois parties de ce mémoire: l'algèbre abstraite (chapitre 2), la combinatoire (chapitres 3 et 4), et la complexité (chapitre 5).

Reliability in terms of functional properties from the safety-liveness spectrum is an indispensable requirement of low-level operating-system (OS) code. However, with evermore complex and thus less predictable hardware, quantitative and probabilistic guarantees become more and more important. Probabilistic model checking is one technique to automatically obtain these guarantees. First experiences with the automated quantitative analysis of low-level operating-system code confirm the expectation that the naive probabilistic model checking approach rapidly reaches its limits when increasing the numbers of processes. This paper reports on our work-in-progress to tackle the state explosion problem for low-level OS-code caused by the exponential blow-up of the model size when the number of processes grows. We studied the symmetry reduction approach and carried out our experiments with a simple test-and-test-and-set lock case study as a representative example for a wide range of protocols with natural inter-process dependencies and long-run properties. We quickly see a state-space explosion for scenarios where inter-process dependencies are insignificant. However, once inter-process dependencies dominate the picture models with hundred and more processes can be constructed and analysed.

Le raisonnement epistémique joue un rôle en théorie de la concurrence de plusieurs manières distinctes mais complémentaires; cette thèse en décrit trois. La première, et presque certainement la moins explorée jusqu'à présent, est l'idée d'utiliser les modalités épistémiques comme éléments d'un langage de programmation. La programmation logique émergea sous le slogan <> et dans le paradigme de la programmation concurrente par contraintes, le lien est manifeste de manière très claire. Dans la première partie de cette thèse, nous explorons le rôle des modalités épistémiques, ainsi que celui des modalités spatiales qui leur sont étroitement liées, en tant que partie intégrante du langage de programmation et non simplement en tant que partie du meta-langage du raisonnement à propos des protocoles. La partie suivante explore une variante de la logique épistémique dynamique adaptée aux systèmes de transitions étiquetés. Contrairement à la partie précédente, on serait tenté de croire que tout ce qu'on pouvait dire à ce sujet a déjà été dit. Cependant, le nouvel ingrédient que nous proposons est un lien étroit entre la logique épistémique et la logique de Hennessy-Milner, cette dernière étant \emph{la} logique des systèmes de transitions étiquetés. Plus précisement, nous proposons une axiomatisation et une preuve d'un théorème de complétude faible, ce qui est conforme au principe général qu'on utilise pour des logiques telles que la logique dynamique mais nécessite des adaptations non triviales. La dernière partie de la thèse se concentre sur l'étude d'agents en interaction dans les processus concurents. Nous présentons une sémantique des jeux pour l'interaction d'agents qui rend manifeste le rôle de la connaissance et du flux d'information dans les interactions entre agents, et qui permet de contrôler l'information disponible aux agents en interaction. Nous utilisons les processus comme support de jeu et définissons des stratégies pour les agents de telle sorte que deux agents qui interagissent conformément à leurs stratégies respectives déterminent l'exécution du processus, rempla{\c}cant ainsi l'ordonnanceur traditionnel. Nous démontrons que des restrictions différentes sur les stratégies réprésentent des quantités d'information différentes disponibles à l'ordonnanceur. Ces restrictions sur les stratégies ont un aspect épistémique explicite, et nous présentons une logique modale pour les stratégies et une caractérisation logique de plusieurs restrictions possibles sur les stratégies. Ces trois approches d'analyse et de représentation de l'information épistémique en théorie de la concurrence apportent une nouvelle manière de comprendre la connaissance des agents dans des processus conncurrents, ce qui est vital dans le monde d'aujourd'hui, dans lequel les systèmes distribués composés de multiples agents sont omniprésents.

Le document traite du raisonnement sur les processus. Les chapitres principaux sont: - Équivalences comportementales : caractérisation logique, axiomatisation et congruence - Inspections et équivalences intensionnelles - Calculs avec localités

Les travaux en modélisation déclarative sont assez nombreux. Il est désormais nécessaire de mettre en place des méthodes générales basées sur celles déjà étudiées et de proposer des outils pour le développement de modeleurs déclaratifs. Nous proposons un nouveau formalisme basé sur les ensembles flous. Ce formalisme apparaît d'une part comme une synthèse et une unification des travaux existants et d'autre part apporte des éléments nouveaux comme la logique floue, la gestion linguistique de la négation. Nous étudions particulièrement le type de propriété le plus simple : la propriété élémentaire. A partir d'une propriété de base, d'un opérateur flou et d'un modificateur, nous mettons en place une méthode pour déterminer la sémantique d'une propriété élémentaire. Nous proposons aussi un traitement original de sa négation. Plutôt que d'utiliser la négation logique habituelle, nous nous intéressons à une gestion se basant sur des notions linguistiques. Enfin, nous présentons des solutions de traitement pour les autres propriétés. Cependant, ces solutions ne sont pas encore vraiment satisfaisantes. La plupart des projets en modélisation déclarative mettent en oeuvre des techniques similaires. A partir de ces travaux et du formalisme flou, nous développons le projet CordiFormes, une plate-forme de programmation visant à faciliter la mise en oeuvre de futurs modeleurs déclaratifs. Ses caractéristiques sont la simplicité, la souplesse de programmation, l'efficacité, l'extensibilité, la réutilisabilité et le prototypage rapide du modeleur. CordiFormes propose des outils sur trois niveaux : le noyau comportant toutes les structures et algorithmes de base, la couche interface proposant dialogues et composants d'interface et, enfin, la couche application pour produire rapidement un premier modeleur. Trois applications permettent de valider le formalisme et les outils de la plate-forme.