Academic literature on the topic 'Raisonnement automatisé'

Les contraintes arithmétiques sont largement utilisées dans les langages formels comme les expressions, les grammaires d'arbres et les chemins réguliers. Ces contraintes sont utilisées dans les modèles de contenu des types (XML Schemas) pour imposer des bornes sur le nombre d'occurrences de noeuds. Dans les langages de requêtes (XPath, XQuery), ces contraintes permettent de sélectionner les noeuds ayant un nombre limité de noeuds accessibles par une expression de chemin donnée. Les types et chemins étendus avec les contraintes de comptage constituent le prolongement naturel de leurs homologues sans comptage déjà considérés comme des constructions fondamentales dans les langages de programmation et les systèmes de type pour XML. Un des défis majeurs en programmation XML consiste à développer des techniques automatisées permettant d'assurer statiquement un typage correct et des optimisations de programmes manipulant les données XML. À cette fin, il est nécessaire de résoudre certaines tâches de raisonnement qui impliquent des constructions telles que les types et les expressions XPath avec des contraintes de comptage. Dans un futur proche, les compilateurs de programmes XML devront résoudre des problèmes de base tels que le sous-typage afin de s'assurer au moment de la compilation qu'un programme ne pourra jamais générer de documents non valides à l'exécution. Cette thèse étudie les logiques capables d'exprimer des contraintes de comptage sur les structures d'arbres. Il a été montré récemment que le μ-calcul sur les graphes, lorsqu'il est étendu à des contraintes de comptage portant exclusivement sur les noeuds successeurs immédiats est indécidable. Dans cette thèse, nous montrons que, sur les arbres finis, la logique avec contraintes de comptage est décidable en temps exponentiel. En outre, cette logique fournit des opérateurs de comptage selon des chemins plus généraux. En effet, la logique peut exprimer des contraintes numériques sur le nombre de noeuds descendants ou même ascendants. Nous présentons également des traductions linéaires d'expressions XPath et de types XML comportant des contraintes de comptage dans la logique.

La contribution principale de cette thèse est un système de preuve correct et complet pour les implications entre les prédicats inductifs, fréquemment rencontrées lors de la vérification des programmes qui utilisent des structures de données récursives allouées dynamiquement. Nous introduisons un système de preuve généralisé pour la logique du premier ordre et nous l'adaptons à la logique de séparation, car ceci est un cadre qui répond aux plusieurs difficultés posées par le raisonnement sur les tas alloués dynamiquement. La correction et la complétude sont assurées par quatre restrictions sémantiques et nous proposons également un semi-algorithme de recherche de preuves qui devient une procédure de décision pour le problème d'implication lorsque les restrictions sémantiques sont respectées.Ce raisonnement d'ordre supérieur sur les implications nécessite des procédures de décision de premier ordre pour la logique sous-jacente lors de l'application des règles d'inférence et lors de la recherche des preuves. Ainsi, nous fournissons deux procédures de décision pour la logique de séparation, en considérant le fragment sans quantificateurs et le fragment quantifié de façon Exists*Forall*, qui ont été intégrées dans le solveur SMT open source CVC4.Finalement, nous présentons une implémentation de notre système de preuve pour la logique de séparation, qui utilise ces procédures de décision. Étant donné des prédicats inductifs et une requête d'implication, un avertissement est émis lorsqu'une ou plusieurs restrictions sémantiques sont violées. Si l'implication est valide, la sortie est une preuve. Sinon, un ou plusieurs contre-exemples sont fournis<br>The main contribution of this thesis is a sound and complete proof system for entailments between inductive predicates, which are frequently encountered when verifying programs that work with dynamically allocated recursive data structures. We introduce a generalized proof system for first-order logic, and then adapt it to separation logic, a framework that addresses many of the difficulties posed by reasoning about dynamically allocated heaps. Soundness and completeness are ensured through four semantic restrictions and we also propose a proof-search semi-algorithm that becomes a decision procedure for the entailment problem when the semantic restrictions hold.This higher-order reasoning about entailments requires first-order decision procedures for the underlying logic when applying inference rules and during proof search. Thus, we provide two decision procedures for separation logic, considering the quantifier-free and the Exists*Forall*-quantified fragments, which were integrated in the open-source, DPLL(T)-based SMT solver CVC4.Finally, we also give an implementation of our proof system for separation logic, which uses these decision procedures. Given some inductive predicate definitions and an entailment query as input, a warning is issued when one or more semantic restrictions are violated. If the entailment is found to be valid, the output is a proof. Otherwise, one or more counterexamples are provided

Cette thèse porte sur le développement d'une méthode pour modéliser des systèmes complexes en utilisant des graphes de connaissances et des algorithmes de raisonnement automatisés. La méthode de modélisation a été appliquée aux maladies rares pour prédire leurs causes, depuis les niveaux génétique, cellulaire et physiologique jusqu'au niveau de l'organisme entier. Pour la création du graphe de connaissances, deux ontologies, GO et HPO, ont été utilisées. Étant donné qu'il n'existait pas de bases de données avec des relations entre ces ontologies, une méthode d'apprentissage automatique a été développée pour inférer des relations et appliquée aux ontologies GO et HPO. La thèse est complétée par une méthode d'apprentissage automatique pour inférer des effets délétères après une variation génétique appelée INDEL. Dans l'ensemble, le travail d'intelligence artificielle présenté dans cette thèse de doctorat aide les chercheurs à comprendre ce qui se passe dans le corps humain à différents niveaux d'abstraction, depuis l'apparition d'une variation génétique jusqu'au développement d'une maladie rare<br>This thesis is about the development of a method for modeling complex systems using knowledge graphs and automated reasoning algorithms. The modeling method was applied to rare diseases to predict their causes from the genetic to the cellular, physiological, and whole organism levels. For the creation of the knowledge graph, two ontologies, GO and HPO, were used. Since there were no databases with relationships between these ontologies, a machine learning method was developed to infer relationships and applied to both GO and HPO ontologies. The thesis is completed by a machine learning method to infer deleterious effects after a genetic variation called INDEL. Altogether, the artificial intelligence work presented in this doctoral thesis assists rare disease researchers in understanding what happens in the human body at various levels of abstraction, from the occurrence of a genetic variation to the development of a rare disease

Cette thèse aborde le défi de l'évaluation des formules logiques candidates, avec un accent particulier sur les axiomes, en combinant de manière synergique l'apprentissage automatique et le raisonnement symbolique. Cette approche innovante facilite la découverte automatique d'axiomes, principalement dans la phase d'évaluation des axiomes candidats générés. La recherche vise à résoudre le problème de la validation efficace et précise de ces candidats dans le contexte plus large de l'acquisition de connaissances sur le Web sémantique.Reconnaissant l'importance des heuristiques de génération existantes pour les axiomes candidats, cette recherche se concentre sur l'avancement de la phase d'évaluation de ces candidats. Notre approche consiste à utiliser ces candidats basés sur des heuristiques, puis à évaluer leur compatibilité et leur cohérence avec les bases de connaissances existantes. Le processus d'évaluation, qui nécessite généralement beaucoup de calculs, est révolutionné par le développement d'un modèle prédictif qui évalue efficacement l'adéquation de ces axiomes en tant que substitut du raisonnement traditionnel. Ce modèle innovant réduit considérablement les exigences en matière de calcul, en utilisant le raisonnement comme un "oracle" occasionnel pour classer les axiomes complexes lorsque cela est nécessaire.L'apprentissage actif joue un rôle essentiel dans ce cadre. Il permet à l'algorithme d'apprentissage automatique de sélectionner des données spécifiques pour l'apprentissage, améliorant ainsi son efficacité et sa précision avec un minimum de données étiquetées. La thèse démontre cette approche dans le contexte du Web sémantique, où le raisonneur joue le rôle d'"oracle" et où les nouveaux axiomes potentiels représentent des données non étiquetées.Cette recherche contribue de manière significative aux domaines du raisonnement automatique, du traitement du langage naturel et au-delà, en ouvrant de nouvelles possibilités dans des domaines tels que la bio-informatique et la preuve automatique de théorèmes. En mariant efficacement l'apprentissage automatique et le raisonnement symbolique, ces travaux ouvrent la voie à des processus de découverte de connaissances plus sophistiqués et autonomes, annonçant un changement de paradigme dans la manière dont nous abordons et exploitons la vaste étendue de données sur le web sémantique<br>This thesis addresses the challenge of evaluating candidate logical formulas, with a specific focus on axioms, by synergistically combining machine learning with symbolic reasoning. This innovative approach facilitates the automatic discovery of axioms, primarily in the evaluation phase of generated candidate axioms. The research aims to solve the issue of efficiently and accurately validating these candidates in the broader context of knowledge acquisition on the semantic Web.Recognizing the importance of existing generation heuristics for candidate axioms, this research focuses on advancing the evaluation phase of these candidates. Our approach involves utilizing these heuristic-based candidates and then evaluating their compatibility and consistency with existing knowledge bases. The evaluation process, which is typically computationally intensive, is revolutionized by developing a predictive model that effectively assesses the suitability of these axioms as a surrogate for traditional reasoning. This innovative model significantly reduces computational demands, employing reasoning as an occasional "oracle" to classify complex axioms where necessary.Active learning plays a pivotal role in this framework. It allows the machine learning algorithm to select specific data for learning, thereby improving its efficiency and accuracy with minimal labeled data. The thesis demonstrates this approach in the context of the semantic Web, where the reasoner acts as the "oracle," and the potential new axioms represent unlabeled data.This research contributes significantly to the fields of automated reasoning, natural language processing, and beyond, opening up new possibilities in areas like bioinformatics and automated theorem proving. By effectively marrying machine learning with symbolic reasoning, this work paves the way for more sophisticated and autonomous knowledge discovery processes, heralding a paradigm shift in how we approach and leverage the vast expanse of data on the semantic Web

Le diagnostic de pannes sur avions est caractérisé, notamment, par la présence éventuelle de plusieurs pannes à un moment donné et par la modification constante de l'état de l'avion au cours de son exploitation, due à l'arrivée de nouvelles pannes et aux actions de maintenance effectuées. Son amélioration permettrait de diminuer le nombre de déposes d'équipements injustifiées et donc de réduire les coûts de maintenance. Dans ce mémoire, l'auteur propose une méthode de diagnostic en ligne c'est-à-dire une méthode permettant, à tout moment, d'établir le diagnostic d'un système physique fonctionnant en continu (en particulier un avion) sur la base des informations disponibles à cet instant et de le réviser (et non pas le refaire) suite à l'arrivée de nouvelles informations. Ce raisonnement s'appuie essentiellement sur une connaissance profonde issue des ingénieurs de conception, à savoir l'architecture et le comportement du système physique en cas de panne. La méthode a été implémentée puis testée sur un sous-ensemble de l'Airbus A320.

L''usage d'un modèle causal dans le cadre de la supervision de processus se justifie si l'on considère que l’être humain appréhende de manière causale les phénomènes physiques. Souvent, la causalité nous permet de focaliser notre attention sur une partie ou sur un composant du système physique, sans avoir forcement recours à une description globale du type équationnel. Le travail de ce mémoire propose un formalisme de raisonnement basé sur une utilisation conjuguée de la causalité et des connaissances profondes s'exprimant sous forme d’équations mathématiques pour la supervision de processus complexes dont il est difficile voire impossible de fournir un modèle complet et précis par des approches classiques. Les constituants de base d'un processus sont des automates qualitatifs. Un automate qualitatif est un système dynamique élémentaire représentant la dynamique d'une variable du processus et les connaissances nécessaires pour raisonner à son propos. Un processus est représenté par deux niveaux de contraintes: un niveau d'influences sous-tendu par un réseau de causalité exprimant les interactions bipartites entre les automates qualitatifs, et le cas échéant, un niveau de contraintes globales spécifiant des relations entre plusieurs automates qualitatifs du processus. Pour représenter les connaissances nécessaires à l’interprétation des comportements, nous introduisons la notion de phase caractéristique qui exprime de façon géométrique les comportements significatifs stables du processus en regard des objectifs de supervision. Le formalisme présenté permet d'automatiser l'acquisition des connaissances sur les influences, de réaliser automatiquement la combinaison de plusieurs influences à partir de la description linguistique des relations causales, de prédire le comportement qualitatif des variables d'un processus, de fournir une interprétation géométrique des comportements d'un processus. L'ensemble des algorithmes proposés a été implémenté comme un moteur de raisonnement causal, appelé CA-EN (causal engine), en Lelisp sous Unix. CA-EN a été utilisé pour réaliser un module de raisonnement à base de modèles pour l'aide à la supervision d'un processus biotechnologique semi-continu pour la production de la protéine amylase. La généricité de ce moteur fait que l'on envisage de l'utiliser pour le diagnostic de turbines à gaz dans le cadre du projet européen Esprit Tiger.

La vérification formelle de programmes informatiques ou de systèmes dits critiques tels que dans le transport, l'énergie, etc, est essentielle pour garantir le bon fonctionnement de ces systèmes. Les méthodes de vérification employées s'appuient très fortement sur des procédés mathématiques et logiques permettant de raisonner de manière formelle sur le comportement de ces systèmes. Ces procédés définissent généralement les comportements sous forme de grands ensembles de contraintes logiques. L'approche par satisfaisabilité est une méthode largement utilisée pour vérifier ces contraintes et est un exemple de cas, où les solveurs SMT (satisfaisabilité modulo théories) sont fortement sollicités. Généralement, les solveurs SMT ne gèrent que la logique de premier ordre. Ils ne peuvent pas raisonner sur des expressions d'ordre supérieur, et ils ne peuvent généralement pas effectuer de preuves par induction. C'est regrettable, car la plupart des outils de vérification interactifs, qui utilisent les solveurs SMT, utilisent des langages d'ordre supérieur. L'objectif de cette thèse dans sa globalité est d'offrir des solutions pour améliorer les interactions entre solveur automatique et assistant de preuves. En particulier nous répondons à deux problématiques importantes permettant d'améliorer les usages de solveurs SMT au sein des assistants de preuves. Notre première contribution permet de réduire l'écart entre solveur et assistant de preuve en proposant une architecture adaptée pour la logique d'ordre supérieur. La seconde contribution permet d'améliorer les capacités de raisonnement des solveurs SMT pour les quantificateurs. Pour les deux approches développées nous apportons un ensemble d'évaluation sur des problèmes extraits pour la grande majorité de problèmes de formalisation. Les résultats obtenus lors de ces évaluations sont encourageants et montrent que les techniques développées dans cette thèse peuvent apporter de bonnes améliorations pour les solveurs SMT. Ce doctorat s'est effectué dans le cadre du projet ERC de J. Blanchette (Matryoshka), un ambitieux projet quinquennal qui vise à construire des prouveurs automatiques utiles pour la vérification interactive, et réduire l'écart entre les prouveurs interactifs et solveurs automatiques. L'un des objectifs concrets du projet est d'étendre les capacités de raisonnement des solveurs SMT vers l'ordre supérieur<br>Many applications, notably in the context of verification (for critical systems in transportation, energy, etc.), rely on checking the satisfiability of logic formulas. Satisfiability-modulo-theories (SMT) solvers handle large formulas in expressive languages with built-in and custom operators (e.g. arithmetic and data structure operators). These tools are built using a cooperation of a SAT (propositional satisfiability) solver to handle the Boolean structure of the formula and theory reasoners to tackle the atomic formulas (e.g. « x &gt; y+z » for the theory of arithmetic). Currently, SMT solvers only handle first-order logic. They cannot reason about higher-order expressions, and they generally cannot perform proofs by induction. This is unfortunate, because most interactive verification tools, which use SMT solvers as back-end reasoning engines, offer higher-order languages. This thesis offers solutions to improve interactions between automatic solvers and proof assistants. In particular, we answer two important issues allowing us to improve the use of SMT solvers within proof assistants. Our first contribution consists in providing a suitable architecture to SMT solvers for higher-order logic. The second contribution aims to improve quantifier reasoning inside SMT solvers. For both approaches, we developed a practical implementation and provide a concrete evaluation on a large collection of problems mostly coming from formalization problems. The results obtained during these evaluations are encouraging and show that the developed techniques can provide good improvements for SMT solvers.Many applications, notably in the context of verification (for critical systems in transportation, energy, etc.), rely on checking the satisfiability of logic formulas. Satisfiability-modulo-theories (SMT) solvers handle large formulas in expressive languages with built-in and custom operators (e.g. arithmetic and data structure operators). These tools are built using a cooperation of a SAT (propositional satisfiability) solver to handle the Boolean structure of the formula and theory reasoners to tackle the atomic formulas (e.g. « x &gt; y+z » for the theory of arithmetic). Currently, SMT solvers only handle first-order logic. They cannot reason about higher-order expressions, and they generally cannot perform proofs by induction. This is unfortunate, because most interactive verification tools, which use SMT solvers as back-end reasoning engines, offer higher-order languages. This thesis offers solutions to improve interactions between automatic solvers and proof assistants. In particular, we answer two important issues allowing us to improve the use of SMT solvers within proof assistants. Our first contribution consists in providing a suitable architecture to SMT solvers for higher-order logic. The second contribution aims to improve quantifier reasoning inside SMT solvers. For both approaches, we developed a practical implementation and provide a concrete evaluation on a large collection of problems mostly coming from formalization problems. The results obtained during these evaluations are encouraging and show that the developed techniques can provide good improvements for SMT solvers

Cette these presente une approche originale de certains problemes d'ordonnancement en maintenance aeronautique. L'approche utilisee est basee sur un systeme de raisonnement temporel specifie en clauses de horn: le calcul d'evenements. Ce systeme definit des concepts tres generaux sur le temps et le changement (evenements, periodes, propositions temporelles), qui permettent de representer des actions. On presente un systeme qui elabore une representation appropriee d'un ensemble d'actions, en utilisant des connaissances formalisees sur le domaine technique specifique. Les connaissances utilisees sont de divers types: il peut s'agir: de connaissances semantiques, sur les termes qui sont utilises pour decrire des actions dans le domaine specifique; de connaissances dites pragmatiques, qui indiquent comment utiliser le contexte de l'action pour en preciser la description; de connaissances geometriques ou fonctionnelles simples sur les composants d'un avion. La representation des actions ainsi elaborees permet de mettre en uvre des inferences dont les resultats sont utiles dans un processus d'ordonnancement. En particulier, un ensemble de clauses permet de detecter et d'identifier des incoherences locales (bugs) dans un plan d'actions. A titre d'application, on presente un programme qui resout un probleme de sequencement: il s'agit de contraindre temporellement un ensemble desordonne d'actions, afin de garantir qu'aucun bug ne se produira a l'execution de ces actions. Une maquette de ce programme a ete mise en uvre dans un langage de programmation logique avec contraintes (prolog iii)

Les systèmes automatisés de production (SAP) représentent une classe importante des systèmes industriels qui sont de plus en plus complexes vue le grand nombre d’interaction et d’interconnexion entre leurs différents composants. En conséquence, ils sont plus sensibles aux dysfonctionnements dont les conséquences peuvent être importantes en termes de productivité, de sécurité et de qualité de production. Un défi majeur est alors de développer une approche intelligente qui peut être utilisée pour le diagnostic de ces systèmes afin de garantir leurs suretés de fonctionnement. Dans le cadre de cette thèse, nous nous intéressons seulement au diagnostic des SAP ayant une dynamique discrète. Nous présentons dans le premier chapitre ces systèmes, les dysfonctionnements possibles et la terminologie du diagnostic utilisée. Ensuite, nous présentons un état de l’art de différentes méthodes et approches existantes et aussi une synthèse de ces méthodes. Cette synthèse nous a motivé de choisir une approche à base de donnée qui s’appuie sur une technique d’apprentissage automatique, qui est le raisonnement à partir de cas (RàPC). Pour cela, nous avons présenté dans le deuxième chapitre un état de l’art sur l’apprentissage automatique et ses différentes méthodes en mettant l’accent essentiellement sur le RàPC et ses utilisations pour le diagnostic des systèmes industriels. Cette étude nous a permis de proposer dans le chapitre 3 une approche d’aide au diagnostic qui se base sur le RàPC. Cette approche s’appuie sur une phase hors ligne et une phase en ligne. La phase hors ligne permet de définir un format de représentation de cas et de construire une base de cas normaux (BCN) et une base de cas défaillants (BCD) à partir d’une base de données d’historique. La phase en ligne permet d’aider les opérateurs humains de surveillance à la prise de la décision du diagnostic la plus adéquate. Les résultats des expérimentations sur un système de tri de caisses ont présentés les piliers de cette approche qui résident au niveau du format de représentation de cas proposé et au niveau de la base de cas utilisé. Pour résoudre ces problèmes et améliorer les résultats, un nouveau format de représentation de cas est proposé dans le chapitre 4. Selon ce format et à partir des données issues du système simulé après son émulation en mode normal et fautif, les cas de la base de cas initiale sont construits. Ensuite, une phase de raisonnement et d’apprentissage incrémental est présentée. Cette phase permet non seulement le diagnostic du système surveillé mais aussi d’enrichir la base de cas suite à l’apparition des nouveaux comportements inconnus. Les expérimentations présentées dans le chapitre 5 sur « le plateau tournant » qui est un sous système du système « tri de caisses » ont permis de montrer l’amélioration des résultats et aussi d’évaluer et de comparer les performances de l’approche proposée vis-à-vis certaines approches d’apprentissage automatique et vis-à-vis une approche à base de modèle pour le diagnostic du plateau tournant<br>Automated production systems (APS) represents an important class of industrial systems that are increasingly complex given the large number of interactions and interconnections between their different components. As a result, they are more susceptible to malfunctions, whose consequences can be significant in terms of productivity, safety and quality of production. A major challenge is to develop an intelligent approach that can be used to diagnose these systems to ensure their operational safety. In this thesis, we are only interested in the diagnosis of APS with discrete dynamics. We present in the first chapter these systems, the possible malfunctions and the used terminology for the diagnosis. Then, we present a state of the art of the existing methods for the diagnosis of this class of systems and also a synthesis of these methods. This synthesis motivated us to choose a data-based approach that relies on a machine learning technique, which is Case-Based Reasoning (CBR). For this reason, we presented in the second chapter a state of the art on machine learning and its different methods with a focus mainly on the CBR and its uses for the diagnosis of industrial systems. This study allowed us to propose in Chapter 3 a Case Based Decision Support System for the diagnosis of APS. This system is based on an online block and an offline block. The Offline block is used to define a case representation format and to build a Normal Case Base (NCB) and a Faulty Case Base (FCB) from a historical database. The online block helps human operators of monitoring to make the most appropriate diagnosis decision. The experiments results perform on a sorting system presented the pillars of this approach, which reside in the proposed case representation format and in the used case base. To solve these problems and improve the results, a new case representation format is proposed in chapter 4. According to this format and from the data acquired from the simulated system after its emulation in normal and faulty mode, cases of the initial case base are build. Then, a reasoning and incremental learning phase is presented. This phase allows the system diagnosis and the enrichment of the case base following the appearance of new unknown behaviors. The experiments presented in Chapter 5 and perform on the 'turntable' which is a subsystem of the 'sorting system” allowed to show the improvement of the results and also to evaluate and compare the performances of the proposed approach with some automatic learning approaches and with a model-based approach to turntable diagnosis