Search

International audience; One of the factors that is hindering the adoption of nonmonotonic description logics in applications is performance. Even when monotonic and nonmonotonic inferences have the same asymptotic complexity, the implementation of nonmonotonic reasoning may be significantly slower. This happens also with the family of nonmonotonic logics DLN.In this work we address this issue by introducing two optimizations for reasoning in DLN. The first optimization, called optimistic evaluation, aims at exploiting incremental reasoning in a better way. The second is a module extractor for DLN, that has the purpose of focusing reasoning on a relevant subset of the knowledge base. The proposed optimization iterates the module extractor that, unlike classical module extractors, is not idempotent, in general.We prove that the proposed optimizations are correct and complete, and assess them through extensive experiments. Our results prove that optimized DLN reasoning is often compatible with interactive query answering, which brings nonmonotonic description logics closer to practical applications.

Nominal schemas have been proposed as an extension to Description Logics (DL), the knowledge representation paradigm underlying the Web Ontology Language (OWL). They provide for a very tight integration of DL and rules. Nominal schemas can be understood as syntactic sugar on top of OWL. However, this naive perspective leads to inefficient reasoning procedures. In order to develop an efficient reasoning procedure for the language ${\mathcal {E}\mathcal {L}\mathcal {V}^{++}}$, which results from extending the OWL profile language OWL EL with nominal schemas, we propose a transformation from ${\mathcal {E}\mathcal {L}\mathcal {V}^{++}}$ ontologies into Datalog-like rule programs that can be used for satisfiability checking and assertion retrieval. The use of this transformation enables the use of powerful Datalog engines to solve reasoning tasks over ${\mathcal {E}\mathcal {L}\mathcal {V}^{++}}$ ontologies. We implement and then evaluate our approach on several real-world, data-intensive ontologies, and find that it can outperform state-of-the-art reasoners such as Konclude and ELK. As a lesser side result we also provide a self-contained description of a rule-based algorithm for ${\mathcal {E}\mathcal {L}^{++}}$, which does not require a normal form transformation.

Ontology-mediated query answering (OMQA) is a promising approach to data access and integration that has been actively studied in the knowledge representation and database communities for more than a decade. The vast majority of work on OMQA focuses on conjunctive queries, whereas more expressive queries that feature counting or other forms of aggregation remain largely unexplored. In this thesis, we introduce a general form of counting conjunctive query (CCQ), relate it to previous proposals, and study the complexity of answering such queries in the presence of ontologies expressed in the description logic ALCHI or its sublogics. As the general case of CCQ answering is intractable and often of high complexity over such ontologies, we consider two practically relevant restrictions, namely rooted CCQs and Boolean atomic CCQs, for which we establish improved complexity bounds., La réponse à des requêtes en présence d'ontologies est une approche prometteuse pour l'intégration et l'accès aux données qui a été activement étudiée ces quinze dernières années. La grande majorité des travaux dans ce domaine se concentre sur les requêtes conjonctives, alors que des requêtes plus expressives, qui offrent des fonctionnalités de comptage ou d'autres formes d'agrégation demeurent largement inexplorées. Dans cette thèse, nous introduisons une forme unifiée de requêtes de comptage, nous la relions à celles déjà existantes, et étudions la complexité du problème consistant à répondre à ces requêtes en présence d'ontologies exprimées dans la logique de description ALCHI ou l'une de ses sous-logiques. Dans la mesure où la complexité de ce problème dans le cas général est inaccessible en pratique et parfois très élevée sur de telles ontologies, nous considérons également deux restrictions sur ces requêtes: l'enracinement et l'atomicité, pour lesquelles nous établissons de meilleurs résultats en terme de complexité.

In the Semantic Web era, Linked Open Data (LOD) is its most successful implementation, which currently contains billions of RDF (Resource Data Framework) triples derived from multiple, distributed, heterogeneous sources. The role of a general semantic schema, represented as an ontology, is essential to ensure the correctness and consistency in LOD and make it possible to infer implicit knowledge by reasoning. The growth of LOD creates an opportunity for the discovery of ontological knowledge from its raw RDF data itself to enrich relevant knowledge bases. In this work, we aim at discovering schema-level knowledge in the form of axioms encoded in OWL (Ontology Web Language) from RDF data. The approaches to automated generation of the axioms from recorded RDF facts on the Web may be regarded as a case of inductive reasoning and ontology learning. The instances, represented by RDF triples, play the role of specific observations, from which axioms can be extracted by generalization.Based on the insight that discovering new knowledge is essentially an evolutionary process, whereby hypotheses are generated by some heuristic mechanism and then tested against the available evidence, so that only the best hypotheses survive, we propose a model applying Grammatical Evolution, one type of evolutionary algorithm, to mine OWL axioms from an RDF data repository. In addition, we specialize the model for the specific problem of learning OWL class disjointness axioms, along with the experiments performed on DBpedia, one of the prominent examples of LOD. Furthermore, we use different axiom scoring functions based on possibility theory, which are well-suited to the open world assumption scenario of LOD, to evaluate the quality of discovered axioms. Specifically, we proposed a set of measures to build objective functions based on single-objective and multi-objective models, respectively. Finally, in order to validate it, the performance of our approach is evaluated against subjective and objective benchmarks, and is also compared to the main state-of-the-art systems.; À l'ère du Web Sémantique, les données liées ouvertes (LOD) en sort l'implémentation la plus réussie qui contient actuellement des milliards de triplets RDF (Resource Data Framework) dérivés de sources multiples, distribuées et hétérogènes. Le rôle d'un schéma sémantique général, représenté comme une ontologie, est essentiel pour assurer l'exactitude et la cohérence du LOD et permettre d'inférer des connaissances implicites par le raisonnement. La croissance du LOD a créé une opportunité pour la découverte de connaissances ontologiques à partir de ses données RDF brutes elles-mêmes pour enrichir les bases de connaissances pertinentes. Dans ce travail, nous visons à découvrir des connaissances au niveau des schémas sous forme d'axiomes encodés en OWL (Ontology Web Language) à partir de données RDF. Les approches de génération automatisée d'axiomes à partir de faits RDF enregistrés sur le Web peuvent être considérées comme un cas de raisonnement inductif et d'apprentissage d'ontologie. Les instances, représentées par des triplets RDF, jouent le rôle d'observations spécifiques, dont les axiomes peuvent être extraits par généralisation.Partant du principe que la découverte de nouvelles connaissances est essentiellement un processus évolutif, dans lequel les hypothèses sont générées par un mécanisme heuristique puis testées par rapport à l'évidence disponible, de sorte que seules les meilleures hypothèses survivent, nous proposons un modèle appliquant l'évolution grammaticale, un type d'algorithme évolutionnaire, pour extraire les axiomes OWL d'un référentiel de données RDF. En outre, nous spécialisons le modèle pour le problème spécifique d'apprentissage d'axiomes de disjonction de classes OWL, ainsi que pour les expériences effectuées sur DBpedia, l'un des exemples les plus proéminents du LOD.De plus, nous utilisons différentes fonctions de notation des axiomes basées sur la théorie des possibilités, qui sont bien adaptées au scénario d'hypothèse du monde ouvert du LOD, pour évaluer la qualité des axiomes découverts. Plus précisément, nous avons proposé un ensemble de mesures pour construire des fonctions objectif basées respectivement sur des modèles à objectif unique et multi-objectifs.Enfin, afin de la valider, la performance de notre approche est évaluée par rapport à des benchmarks, subjectif et objectif, et est également comparée aux principaux systèmes de l'état de l'art.

In this paper, we explore the issue of inconsistency handling over prioritized knowledge bases (KBs), which consist of an ontology, a set of facts, and a priority relation between conflicting facts. In the database setting, a closely related scenario has been studied and led to the definition of three different notions of optimal repairs (global, Pareto, and completion) of a prioritized inconsistent database. After transferring the notions of globally-, Pareto- and completion-optimal repairs to our setting, we study the data complexity of the core reasoning tasks: query entailment under inconsistency-tolerant semantics based upon optimal repairs, existence of a unique optimal repair, and enumeration of all optimal repairs. Our results provide a nearly complete picture of the data complexity of these tasks for ontologies formulated in common DL-Lite dialects. The second contribution of our work is to clarify the relationship between optimal repairs and different notions of extensions for (set-based) argumentation frameworks. Among our results, we show that Pareto-optimal repairs correspond precisely to stable extensions (and often also to preferred extensions), and we propose a novel semantics for prioritized KBs which is inspired by grounded extensions and enjoys favourable computational properties. Our study also yields some results of independent interest concerning preference-based argumentation frameworks., 27 pages. To appear in the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020) without the appendix

International audience; This chapter considers the notion of a formal ontology, which is a conceptual vocabulary equipped with a logical semantics. Three families of knowledge representation and reasoning formalisms that put ontologies at the core of any knowledge base are presented, namely: description logics, conceptual graphs and existen-tial rules. We present the main knowledge constructs and dialects of these families, as well as the main reasoning problems with their complexity. We highlight the relationships between these families and compare them from an expressivity viewpoint.

International audience; In this work we describe preferential Description Logics of typicality, a nonmonotonic extension of standard Description Logics by means of a typicality operator T allowing to extend a knowledge base with inclusions of the form T(C) ⊑ D, whose intuitive meaning is that “normally/typically Cs are also Ds”. This extension is based on a minimal model semantics corresponding to a notion of rational closure, built upon preferential models. We recall the basic concepts underlying preferential Description Logics. We also present two extensions of the preferential semantics: on the one hand, we consider probabilistic extensions, based on a distributed semantics that is suitable for tackling the problem of commonsense concept combination, on the other hand, we consider other strengthening of the rational closure semantics and construction to avoid the so called “blocking of property inheritance problem”.

International audience; This paper provides a concise overview of the literature on inconsistency handling for ontology-mediated query answering, a topic which has grown into an active area of research over the last decade. The focus of this survey is on the case where errors are localized in the data (i.e., the ontology is deemed reliable) and where inconsistency-tolerant semantics are employed with the aim of obtaining meaningful information from inconsistent knowledge bases.

This paper presents a method for verifying graph transformation programs written in Small-t\(\mathcal ALC\), an imperative language which allows expressing graph properties and graph transformations in \(\mathcal ALCQI\) description logic. We aim at reasoning not only about the local effect when applying a transformation rule on a matched subgraph but also about the global impact on the whole input graph when applying a set of rules. Using \(\mathcal ALCQI\) assertional and terminological formulae to formalize directed labeled graphs, Small-t\(\mathcal ALC\) allows specifying local properties on individual nodes and edges as well as global properties on sets of nodes and edges. Our previous work focuses on verifying local properties of the graph. In this paper, we propose a static analyzer at terminological level that intertwines with a static analyzer at assertional level to infer global properties of the transformed graph.

Data interlinking is a critical task for widening and enhancing linked open data. One way to tackle data interlinking is to use link keys, which generalise keys to the case of two RDF datasets described using different ontologies. Link keys specify pairs of properties to compare for finding same-as links between instances of two classes of two different datasets. Hence, they can be used for finding links. Link keys can also be considered as logical axioms just like keys, ontologies and ontology alignments. We introduce the logic ALC+LK extending the description logic ALC with link keys. It may be used to reason and infer entailed link keys that may be more useful for a particular data interlinking task. We show that link key entailment can be reduced to consistency checking without introducing the negation of link keys. For deciding the consistency of an ALC+LK ontology, we introduce a new tableau-based algorithm. Contrary to the classical ones, the completion rules concerning link keys apply to pairs of individuals not directly related. We show that this algorithm is sound, complete and always terminates.

International audience; Stream-based reasoning systems process data stemming from different sources that are received over time. In this kind of applications, reasoning needs to cope with the temporal dimension and should be resilient against inconsistencies in the data. Motivated by such settings, this paper addresses the problem of handling inconsistent data in a temporal version of ontology-mediated query answering. We consider a recently proposed temporal query language that combines conjunctive queries with operators of propositional linear temporal logic (LTL), and consider these under three inconsistency-tolerant semantics that have been introduced for querying inconsistent description logic knowledge bases. We investigate their complexity for temporal EL ⊥ and DL-LiteR knowledge bases. In particular, we consider two different cases, depending on the presence of negations in the query. Furthermore, we complete the complexity picture for the consistent case. We also provide two approaches toward practical algorithms for inconsistency-tolerant temporal query answering.

https://dblp.uni-trier.de/db/conf/frocos/frocos2019.html; International audience; This book constitutes the proceedings of the 12th International Symposium on Frontiers of Combining Systems, FroCoS 2019, held in London, UK, in September 2019, colocated with the 28th International Conference on Automated Reasoning with Analytic Tableaux and Related Methods, TABLEAUX 2019. The 20 papers presented were carefully reviewed and selected from 30 submissions. They present research on the development of techniques and methods for the combination and integration of formal systems, their modularization and analysis. The papers are organized in the following topical sections: automated theorem proving and model building, combinations of systems, constraint solving, description logics, interactive theorem proving, modal and epistemic logics, and rewriting and unification.

In the Semantic Web context, OWL ontologies represent explicit domain knowledge based on the conceptualization of domains of interest while the corresponding assertional knowledge is given by RDF data referring to them. In this thesis, based on ideas derived from ILP, we aim at discovering hidden knowledge patterns in the form of multi-relational association rules by exploiting the evidence coming from the assertional data of ontological knowledge bases. Specifically, discovered rules are coded in SWRL to be easily integrated within the ontology, thus enriching its expressive power and augmenting the assertional knowledge that can be derived. Two algorithms applied to populated ontological knowledge bases are proposed for finding rules with a high inductive power: (i) level-wise generated-and-test algorithm and (ii) evolutionary algorithm. We performed experiments on publicly available ontologies, validating the performances of our approach and comparing them with the main state-of-the-art systems. In addition, we carry out a comparison of popular asymmetric metrics, originally proposed for scoring association rules, as building blocks for a fitness function for evolutionary algorithm to select metrics that are suitable with data semantics. In order to improve the system performance, we proposed to build an algorithm to compute metrics instead of querying via SPARQL-DL.; Dans le contexte du Web sémantique, les ontologies OWL représentent des connaissances explicites sur un domaine sur la base d'une conceptualisation des domaines d'intérêt, tandis que la connaissance correspondante sur les individus est donnée par les données RDF qui s'y réfèrent. Dans cette thèse, sur la base d'idées dérivées de l'ILP, nous visons à découvrir des motifs de connaissance cachés sous la forme de règles d'association multi-relationnelles en exploitant l'évidence provenant des assertions contenues dans les bases de connaissances ontologiques. Plus précisément, les règles découvertes sont codées en SWRL pour être facilement intégrées dans l'ontologie, enrichissant ainsi son pouvoir expressif et augmentant les connaissances sur les individus (assertions) qui en peuvent être dérivées. Deux algorithmes appliqués aux bases de connaissances ontologiques peuplées sont proposés pour trouver des règles à forte puissance inductive : (i) un algorithme de génération et test par niveaux et (ii) un algorithme évolutif. Nous avons effectué des expériences sur des ontologies accessibles au public, validant les performances de notre approche et les comparant avec les principaux systèmes de l'état de l'art. En outre, nous effectuons une comparaison des métriques asymétriques les plus répandues, proposées à l'origine pour la notation de règles d'association, comme éléments constitutifs d'une fonction de fitness pour l'algorithme évolutif afin de sélectionner les métriques qui conviennent à la sémantique des données. Afin d'améliorer les performances du système, nous avons proposé de construire un algorithme pour calculer les métriques au lieu d'interroger viaSPARQL-DL.

International audience; In this paper, we place ourselves in the Ontology Based Data Access (OBDA) setting and investigate reasoning with inconsistent existential rules knowledge bases. We use the notion of inconsistency measures on sets of facts to rank and filter repairs. We propose a generic framework to answer queries by using the best repairs and study productivity and properties of such a framework.

International audience; Real-world applications using fuzzy ontologies are increasing in the last years, but the problem of fuzzy ontology learning has not received a lot of attention. While most of the previous approaches focus on the problem of learning fuzzy subclass axioms, we focus on learning fuzzy datatypes. In particular, we describe the Datil system, an implementation using unsupervised clustering algorithms to automatically obtain fuzzy datatypes from different input formats. We also illustrate the practical usefulness with an application: semantic lifestyle profiling.

International audience; We carry out a comparison of popular asymmetric metrics, originally proposed for scoring association rules, as building blocks for a fitness function for evolutionary inductive programming. In particular, we use them to score candidate multi-relational association rules in an evolutionary approach to the enrichment of populated knowledge bases in the context of the Semantic Web. The evolutionary algorithm searches for hidden knowledge patterns, in the form of SWRL rules, in assertional data, while exploiting the deductive capabilities of ontologies. Our methodology is to compare the number of generated rules and total predictions when the metrics are used to compute the fitness function of the evolutionary algorithm. This comparison, which has been carried out on three publicly available ontologies, is a crucial step towards the selection of suitable metrics to score multi-relational association rules that are generated from ontologies.

International audience; Providing a mechanism for modeling and reasoning about the dynamics of geographic spatio-temporal objects is a challenge issue and main problem due to the complex characteristics describing these objects. A spatio-temporal geographical entity is defined as a set composed by spatial, temporal and semantic (thematic) dimensions, of which various types of relationships can be specified. Changes in the state of each component are the result of geographic events and processes that may occur. Remotely sensed images provide measurements and observations that can be used for the interpretation of dynamic spatio-temporal objects. The observed proprieties are used to classify geographic objects and monitor change that occurs in such object. The intended paper focuses to model the dynamics of spatio-temporal object from a remote sensing observation viewpoint. Dynamic, here, is represented in term of events such as reduction and expansion, split and merging, etc. and in term of geographic processes such as deforestation and urbanization. To achieve this purpose, we exploit the description logic extended to a semantic spatio-temporal concrete domain as a mechanism for semantic-spatio-temporal reasoning and dynamic representation.

International audience; In the Semantic Web context, OWL ontologies represent the conceptualization of domains of interest while the corresponding assertional knowledge is given by RDF data referring to them. Because of its open, distributed, and collaborative nature, such knowledge can be incomplete, noisy, and sometimes inconsistent. By exploiting the evidence coming from the assertional data, we aim at discovering hidden knowledge patterns in the form of multi-relational association rules while taking advantage of the intensional knowledge available in ontological knowledge bases. An evolutionary search method applied to populated ontological knowledge bases is proposed for finding rules with a high inductive power. The proposed method, EDMAR, uses problem-aware genetic operators, echoing the refinement operators of ILP, and takes the intensional knowledge into account, which allows it to restrict and guide the search. Discovered rules are coded in SWRL, and as such they can be straightforwardly integrated within the ontology, thus enriching its expressive power and augmenting the assertional knowledge that can be derived. Additionally , discovered rules may also suggest new axioms to be added to the ontology. We performed experiments on publicly available ontologies, validating the performances of our approach and comparing them with the main state-of-the-art systems.

Earth Observation data is of great interest for a wide spectrum of scientific domain applications. An enhanced access to remote sensing images for domain experts thus represents a great advance since it allows users to interpret remote sensing images based on their domain expert knowledge. However, such an advantage can also turn into a major limitation if this knowledge is not formalized, and thus is difficult for it to be shared with and understood by other users. In this context, knowledge representation techniques such as ontologies should play a major role in the future of remote sensing applications. We implemented an ontology-based prototype to automatically classify Landsat images based on explicit spectral rules. The ontology is designed in a very modular way in order to achieve a generic and versatile representation of concepts we think of utmost importance in remote sensing. The prototype was tested on four subsets of Landsat images and the results confirmed the potential of ontologies to formalize expert knowledge and classify remote sensing images. HighlightsAn ontology to classify Landsat images based on spectral rules is proposed.The ontology is composed of three knowledge representation types.Image pixels are assigned to semantic classes by a description logic reasoner.Ontologies are useful to formalize remote sensing expert-knowledge.

International audience; We propose a novel approach to ontology authoring that is centered on semantics rather than on syntax. Instead of writing axioms formalizing a domain, the expert is invited to explore the possible worlds of her ontology, and to eliminate those that do not conform to her knowledge. Each elimination generates an axiom that is automatically derived from the explored situation. We have implemented the approach in prototype PEW (Possible World Explorer), and conducted a user study comparing it to Protégé. The results show that more axioms are produced with PEW, without making more errors. More importantly, the produced ontologies are more complete, and hence more deductively powerful, because more negative constraints are expressed.

International audience; Repair-based techniques are a standard way of dealing with inconsistency in the context of ontology-based data access where several inconsistency-tolerant semantics have been mainly proposed for lightweight description logics. In this paper we present a generic transformation from knowledge bases expressed within existential rules formalism into an ASP program. We propose different strategies for this transformation, and highlight the ones for which answer sets of the generated program correspond to various kinds of repairs used in inconsistency-tolerant inferences.

gmati2016a; International audience; Link keys allow for generating links across data sets expressed in different ontologies. But they can also be thought of as axioms in a description logic. As such, they can contribute to infer ABox axioms, such as links, or terminological axioms and other link keys. Yet, no reasoning support exists for link keys. Here we extend the tableau method designed for ALC to take link keys into account. We show how this extension enables combining link keys with terminological reasoning with and without ABox and TBox and generate non trivial link keys.

International audience; Circumscription is a paradigm of non-monotonic logic meant to formalize the common-sense understanding that, among competing theories that represent phenomena equally well, the one with the fewest “abnormal” assumptions should be selected. Several papers have considered ways of adding circumscription to Description Logics. One of the proposals with good computational properties is Grounded Circumscription, introduced by Sengupta, Krishnadi and Hitzler in 2011. Our paper builds on their general idea, but identifies some problems with the original semantics definition, which gives rise to counter-intuitive consequences and renders the proposed tableau algorithm incorrect. We give an example that makes the problem explicit and propose a modification of the semantics that remedies this issue. On the algorithmic side, we show that a big part of the reasoning can actually be transferred to standard Description Logics, for which tools and results already exist.

International audience; Formal ontologies are explicitly representation of domain knowledge. Ontology change management should ensure maintaining its consistency, so that its users can continue to cooperate and understand each other. This paper presents a meta-conceptual modeling approach for change modeling in the domain of applied ontology. This modeling approach makes use a mathematical structure to model ontologies and its changes in order to make possible the qualification of changes regarding its consistency. Actually, the paper focuses on the meta-conceptual modeling approach inspired by Guarino's formal ontology building process.

The problem of querying description logic knowledge bases using database-style queries (in particular, conjunctive queries) has been a major focus of recent description logic research. An important issue that arises in this context is how to handle the case in which the data is inconsistent with the ontology. Indeed, since in classical logic an inconsistent logical theory implies every formula, inconsistency-tolerant semantics are needed to obtain meaningful answers. This thesis aims to develop methods for dealing with inconsistent description logic knowledge bases using three natural semantics (AR, IAR, and brave) previously proposed in the literature and that rely on the notion of a repair, which is an inclusion-maximal subset of the data consistent with the ontology. In our framework, these three semantics are used conjointly to identify answers with different levels of confidence. In addition to developing efficient algorithms for query answering over inconsistent DL-Lite knowledge bases, we address three problems that should support the adoption of this framework: (i) query result explanation, to help the user to understand why a given answer was (not) obtained under one of the three semantics, (ii) query-driven repairing, to exploit user feedback about errors or omissions in the query results to improve the data quality, and (iii) preferred repair semantics, to take into account the reliability of the data. For each of these three topics, we developed a formal framework, analyzed the complexity of the relevant reasoning problems, and proposed and implemented algorithms, which we empirically studied over an inconsistent DL-Lite benchmark we built. Our results indicate that even if the problems related to dealing with inconsistent DL-Lite knowledge bases are theoretically hard, they can often be solved efficiently in practice by using tractable approximations and features of modern SAT solvers., Interroger des bases de connaissances avec des requêtes conjonctives a été une préoccupation majeure de la recherche récente en logique de description. Une question importante qui se pose dans ce contexte est la gestion de données incohérentes avec l'ontologie. En effet, une théorie logique incohérente impliquant toute formule sous la sémantique classique, l'utilisation de sémantiques tolérantes aux incohérences est nécessaire pour obtenir des réponses pertinentes. Le but de cette thèse est de développer des méthodes pour gérer des bases de connaissances incohérentes en utilisant trois sémantiques naturelles (AR, IAR et brave) proposées dans la littérature et qui reposent sur la notion de réparation, définie comme un sous-ensemble maximal des données cohérent avec l'ontologie. Nous utilisons ces trois sémantiques conjointement pour identifier les réponses associées à différents niveaux de confiance. En plus de développer des algorithmes efficaces pour interroger des bases de connaissances DL-Lite incohérentes, nous abordons trois problèmes : (i) l'explication des résultats des requêtes, pour aider l'utilisateur à comprendre pourquoi une réponse est (ou n'est pas) obtenue sous une des trois sémantiques, (ii) la réparation des données guidée par les requêtes, pour améliorer la qualité des données en capitalisant sur les retours des utilisateurs sur les résultats de la requête, et (iii) la définition de variantes des sémantiques à l'aide de réparations préférées pour prendre en compte la fiabilité des données. Pour chacune de ces trois questions, nous développons un cadre formel, analysons la complexité des problèmes de raisonnement associés, et proposons et mettons en œuvre des algorithmes, qui sont étudiés empiriquement sur un jeu de bases de connaissance DL-Lite incohérentes que nous avons construit. Nos résultats indiquent que même si les problèmes à traiter sont théoriquement durs, ils peuvent souvent être résolus efficacement dans la pratique en utilisant des approximations et des fonctionnalités des SAT solveurs modernes.

The increase of textual sources over the Web offers an opportunity for knowledge extraction and knowledge base creation. Recently, several research works on this topic have appeared or intensified. They generally highlight that to extract relevant and precise information from text, it is necessary to define a collaboration between linguistic approaches, e.g., to extract certain concepts regarding named entities, temporal and spatial aspects, and methods originating from the field of semantics' processing. Moreover, successful approaches also need to qualify and quantify the uncertainty present in the text. Finally, in order to be relevant in the context of the Web, the linguistic processing need to be consider several sources in different languages. This PhD thesis tackles this problematic in its entirety since our contributions cover the extraction, representation of uncertain knowledge as well as the visualization of generated graphs and their querying. This research work has been conducted within a CIFRE funding involving the Laboratoire d'Informatique Gaspard Monge (LIGM) of the Université Paris-Est Marne la Vallée and the GEOLSemantics start-up. It was leveraging from years of accumulated experience in natural language processing (GeolSemantics) and semantics processing (LIGM).In this context, our contributions are the following:- the integration of a qualifation of different forms of uncertainty, based on ontology processing, within the knowledge extraction processing,- the quantification of uncertainties based on a set of heuristics,- a representation, using RDF graphs, of the extracted knowledge and their uncertainties,- an evaluation and an analysis of the results obtained using our approach, La multiplication de sources textuelles sur le Web offre un champ pour l'extraction de connaissances depuis des textes et à la création de bases de connaissances. Dernièrement, de nombreux travaux dans ce domaine sont apparus ou se sont intensifiés. De ce fait, il est nécessaire de faire collaborer des approches linguistiques, pour extraire certains concepts relatifs aux entités nommées, aspects temporels et spatiaux, à des méthodes issues des traitements sémantiques afin de faire ressortir la pertinence et la précision de l'information véhiculée. Cependant, les imperfections liées au langage naturel doivent être gérées de manière efficace. Pour ce faire, nous proposons une méthode pour qualifier et quantifier l'incertitude des différentes portions des textes analysés. Enfin, pour présenter un intérêt à l'échelle du Web, les traitements linguistiques doivent être multisources et interlingue. Cette thèse s'inscrit dans la globalité de cette problématique, c'est-à-dire que nos contributions couvrent aussi bien les aspects extraction et représentation de connaissances incertaines que la visualisation des graphes générés et leur interrogation. Les travaux de recherche se sont déroulés dans le cadre d'une bourse CIFRE impliquant le Laboratoire d'Informatique Gaspard Monge (LIGM) de l'Université Paris-Est Marne la Vallée et la société GEOLSemantics. Nous nous appuyons sur une expérience cumulée de plusieurs années dans le monde de la linguistique (GEOLSemantics) et de la sémantique (LIGM).Dans ce contexte, nos contributions sont les suivantes :- participation au développement du système d'extraction de connaissances de GEOLSemantics, en particulier : (1) le développement d'une ontologie expressive pour la représentation des connaissances, (2) le développement d'un module de mise en cohérence, (3) le développement d'un outil visualisation graphique.- l'intégration de la qualification de différentes formes d'incertitude, au sein du processus d'extraction de connaissances à partir d'un texte,- la quantification des différentes formes d'incertitude identifiées ;- une représentation, à l'aide de graphes RDF, des connaissances et des incertitudes associées ;- une méthode d'interrogation SPARQL intégrant les différentes formes d'incertitude ;- une évaluation et une analyse des résultats obtenus avec notre approche

International audience; This paper intends to describe the application ontology of the SaaS version of the decision statistical mapping and geomarketing software Cartes & Données (C & D): CD7 Online. Specified in OWL DL, the CD7 ontology was conceived for automation of semantic annotation of CD7 Online user data to help users better understand their data and make better selection and representation choices when building maps.

International audience; Around the world, land cover changes occur due to natural and anthropogenic factors. In many cases, the consequences of anthropogenic interventions are unexpected. In order for scientists and policy makers to identify land cover change processes of interest, it is necessary suitable tools for early and efficient analysis of land cover data. In our research, we present a data model that makes use of semantic web technologies to manage a hierarchical structure of land cover types. Using this approach, it is possible to manage the land cover information at different levels of abstraction. In our research, we use a Change Vector Analysis approach to represent the land cover change. The number and semantics of the axes in the resulting multidimensional space depend on the level of abstraction decided by the researcher and can be modified on the fly. Using this approach, it is possible to detect processes allowing the researcher to have quantitative change measurements. In this work, we present our research using data from the CORINE land cover program, corresponding to the years 1990, 2000 and 2006. As our study area, we have selected ten countries in Eastern Europe, that became members of the EU between 2005 and 2007. Our results suggest that our method is efficient, reliable and scalable.

This thesis investigates the dynamics of beliefs and uncertainty management in DL-Lite, one of the most important lightweight description logics. The first part of the thesis concerns the problem of han- dling uncertainty in DL-Lite. First, we propose an extension of the main fragments of DL-Lite to deal with the uncertainty associated with axioms using a possibility theory framework without additional ex- tra computational costs. We then study the revision of possibilistic DL-Lite bases when a new piece of information is available. Lastly, we propose a min-based assertional merging operator when assertions of ABox are provided by several sources of information having different levels of priority. The second part of the thesis concerns the problem of inconsistency handling in flat and prioritized DL-Lite knowledge bases. We first propose how to reason from a flat DL-Lite knowledge base, with a multiple ABox, which can be either issued from multiple information sources or resulted from revising DL-Lite knowledge bases. This is done by introducing the notions of modifiers and inference strategies. The combination of modifiers plus inference strategies can be mapped out in order to provide a principled and exhaustive list of techniques for inconsistency management. We then give an approach based on selecting multiple repairs using a cardinality-based criterion, and we identified suitable strategies for handling inconsistency in the prioritized case. Lastly, we perform a comparative analysis, followed by experimental studies, of the proposed inconsistency handling techniques. A tool for representing and reasoning in possibilistic DL-Lite framework is implemented.; Cette thèse étudie la dynamique des croyances et la gestion de l’incertitude dans DL-Lite, une des plus importantes familles des logiques de description légères. La première partie de la thèse porte sur la gestion de l’incertitude dans DL-Lite. En premier lieu, nous avons proposé une extension des prin- cipaux fragments de DL-Lite pour faire face à l’incertitude associée aux axiomes en utilisant le cadre de la théorie des possibilités. Cette extension est réalisée sans engendrer des coûts calculatoires sup- plémentaires. Nous avons étudié ensuite la révision des bases DL-Lite possibilistes en présence d’une nouvelle information. Enfin, nous avons proposé un opérateur de fusion lorsque les assertions de ABox sont fournies par plusieurs sources d’information ayant différents niveaux de priorité. La deuxième partie de la thèse traite le problème de la gestion d’incohérence dans les bases de connaissances DL-Lite. Nous avons étudié, tout d’abord, comment raisonner à partir d’une base DL-Lite standard avec des ABox mul- tiples en introduisant les notions de modificateurs et de stratégies d’inférence. La combinaison des mod- ificateurs et de stratégies d’inférence fournit une liste exhaustive des principales techniques de gestion de l’incohérence. Nous avons proposé ensuite une approche, basée sur un critère de cardinalité, de sélection des réparations, et nous avons identifié les stratégies appropriées pour la gestion de l’incohérence pour les bases DL-Lite stratifiées. Enfin, nous avons effectué une analyse comparative, suivie par des études expérimentales, des différentes techniques de gestion d’incohérence proposées. Finalement, un outil de représentation et de raisonnement à partir des bases DL-Lite possibiliste est réalisé.

Part 10: Information Technology: Ontologies; International audience; A real world of objects (individuals) is represented by a set of assertions written with respect to defined syntax and semantics of description logic (formal language). These assertions should be consistent with the ontology axioms described as terminology of knowledge. The axioms and the assertions represent ontology about a particular domain. A real world is a possible world if all the assertions and the axioms over its set of individuals, are consistent. It is possible then to query the possible world by specific assertions (as instance checking) to determine if they are consistent with it or not. However, ontology can contain vague concepts which means the knowledge about them is imprecise and then query answering will not possible due to the open world assumption if the necessary information is incomplete (it is currently absent). A concept description can be very exact (crisp concept) or exact (fuzzy concept) if its knowledge is complete, otherwise it is inexact (vague concept) if its knowledge is incomplete. In this paper we propose a vagueness theory based on the definition of truth gaps as ontology assertions to express the vague concepts in Ontology Web Language (OWL2) (which is based on the description logic SROIQ(D)) and an extension of the Tableau algorithm for reasoning over imprecise ontologies.

International audience; Formal ontology provides axiomatizations of domain independent principles which, among other applications,can be used to identify modeling errors within a knowledge base. The Ontoclean methodology is probably the best-known illustration of this strategy, but its cost in terms of manual work is often considered dissuasive. This article investigates the applicability of such debugging strategies to Description Logics knowledge bases, showing that even a partial and shallow analysis rapidly performed with a top-level ontology can reveal the presence of violations of common sense, and that the bottleneck, if there is one, may instead reside in the resolution of the resulting inconsistency or incoherence.

In this paper we provide a semantic reconstruction of rational closure. We first consider rational closure as defined by Lehman and Magidor [33] for propositional logic, and we provide a semantic characterization based on a minimal models mechanism on rational models. Then we extend the whole formalism and semantics to Description Logics, by focusing our attention to the standard ALC : we first naturally adapt to Description Logics Lehman and Magidor's propositional rational closure, starting from an extension of ALC with a typicality operator T that selects the most typical instances of a concept C (hence T ( C ) stands for typical C). Then, for the Description Logics, we define a minimal model semantics for the logic ALC and we show that it provides a semantic characterization for the rational closure of a Knowledge base. We consider both the rational closure of the TBox and the rational closure of the ABox.

This thesis investigates the dynamics of beliefs and uncertainty management in DL-Lite, one of the most important lightweight description logics. The first part of the thesis concerns the problem of han- dling uncertainty in DL-Lite. First, we propose an extension of the main fragments of DL-Lite to deal with the uncertainty associated with axioms using a possibility theory framework without additional ex- tra computational costs. We then study the revision of possibilistic DL-Lite bases when a new piece of information is available. Lastly, we propose a min-based assertional merging operator when assertions of ABox are provided by several sources of information having different levels of priority. The second part of the thesis concerns the problem of inconsistency handling in flat and prioritized DL-Lite knowledge bases. We first propose how to reason from a flat DL-Lite knowledge base, with a multiple ABox, which can be either issued from multiple information sources or resulted from revising DL-Lite knowledge bases. This is done by introducing the notions of modifiers and inference strategies. The combination of modifiers plus inference strategies can be mapped out in order to provide a principled and exhaustive list of techniques for inconsistency management. We then give an approach based on selecting multiple repairs using a cardinality-based criterion, and we identified suitable strategies for handling inconsistency in the prioritized case. Lastly, we perform a comparative analysis, followed by experimental studies, of the proposed inconsistency handling techniques. A tool for representing and reasoning in possibilistic DL-Lite framework is implemented., Cette thèse étudie la dynamique des croyances et la gestion de l’incertitude dans DL-Lite, une des plus importantes familles des logiques de description légères. La première partie de la thèse porte sur la gestion de l’incertitude dans DL-Lite. En premier lieu, nous avons proposé une extension des prin- cipaux fragments de DL-Lite pour faire face à l’incertitude associée aux axiomes en utilisant le cadre de la théorie des possibilités. Cette extension est réalisée sans engendrer des coûts calculatoires sup- plémentaires. Nous avons étudié ensuite la révision des bases DL-Lite possibilistes en présence d’une nouvelle information. Enfin, nous avons proposé un opérateur de fusion lorsque les assertions de ABox sont fournies par plusieurs sources d’information ayant différents niveaux de priorité. La deuxième partie de la thèse traite le problème de la gestion d’incohérence dans les bases de connaissances DL-Lite. Nous avons étudié, tout d’abord, comment raisonner à partir d’une base DL-Lite standard avec des ABox mul- tiples en introduisant les notions de modificateurs et de stratégies d’inférence. La combinaison des mod- ificateurs et de stratégies d’inférence fournit une liste exhaustive des principales techniques de gestion de l’incohérence. Nous avons proposé ensuite une approche, basée sur un critère de cardinalité, de sélection des réparations, et nous avons identifié les stratégies appropriées pour la gestion de l’incohérence pour les bases DL-Lite stratifiées. Enfin, nous avons effectué une analyse comparative, suivie par des études expérimentales, des différentes techniques de gestion d’incohérence proposées. Finalement, un outil de représentation et de raisonnement à partir des bases DL-Lite possibiliste est réalisé.

International audience; In image interpretation and computer vision, spatial relations between objects and spatial reasoning are of prime importance for recognition and interpretation tasks. Quantitative representations of spatial knowledge have been proposed in the literature. In the Artificial Intelligence community, logical formalisms such as ontologies have also been proposed for spatial knowledge representation and reasoning, and a challenging and open problem consists in bridging the gap between these ontological representations and the quantitative ones used in image interpretation. In this paper, we propose a new description logic, named ALC(F), dedicated to spatial reasoning for image understanding. Our logic relies on the family of description logics equipped with concrete domains, a widely accepted way to integrate quantitative and qualitative qualities of real world objects in the conceptual domain, in which we have integrated mathematical morphological operators as predicates. Merging description logics with mathematical morphology enables us to provide new mechanisms to derive useful concrete representations of spatial concepts and new qualitative and quantitative spatial reasoning tools. It also enables imprecision and uncertainty of spatial knowledge to be taken into account through the fuzzy representation of spatial relations. We illustrate the benefits of our formalism on a model-guided cerebral image interpretation task.

Several researchers have developed properties that ensure compatibility of a concept similarityor dissimilarity measure with the formal semantics of Description Logics. While these authors havehighlighted the relevance of the triangle inequality, none of their proposed dissimilarity measuressatisfy it. In this work we present several dissimilarity measures with this property: first, a simpledissimilarity measure, based on description trees for the lightweight Description LogicEL; second, ageneral framework based on concept relaxations; third, an instantiation of the general framework usingdilation operators from mathematical morphology, exploiting the link between Hausdorff distanceand dilations using balls of the ground distance as structuring elements. A comparison between thesedefinitions and their properties is provided as well.

International audience; Retrieving and composing individuals' capabilities are the matter of several research fields, like competence-based management, human resources management, enterprise knowledge management systems, knowledge representation systems, etc. This talk focuses on capability representation, discovery and composition in heterogeneous, and possibly distributed, knowledge representation environments. A driving motivation of this work is to provide a contribution to the satisfaction of the need for retrieving individualswho may carry out actions, as well as the need for retrieving individuals who, when putting their competences together, may carry out actions. We outline some formal capability description languages , and we propose approaches and algorithms for capability management, discovery and composition. In addition, we outline how our proposals are implemented in a mediator-based prototype system under a service oriented architecture and a Peer-to-Peer architecture.

International audience; The processing of complex data is admittedly among the major concerns of knowledge discovery from data (KDD). Indeed, a major part of the data worth analyzing is stored in relational databases and, since recently, on the Web of Data. This clearly underscores the need for Entity-Relationship and RDF compliant data mining (DM) tools. We are studying an approach to the underlying multi-relational data mining (MRDM) problem, which relies on formal concept analysis (FCA) as a framework for clustering and classification. Our relational concept analysis (RCA) extends FCA to the processing of multi-relational datasets, i.e., with multiple sorts of individuals, each provided with its own set of attributes, and relationships among those. Given such a dataset, RCA constructs a set of concept lattices, one per object sort, through an iterative analysis process that is bound towards a fixed-point. In doing that, it abstracts the links between objects into attributes akin to role restrictions from description logics (DLs). We address here key aspects of the iterative calculation such as evolution in data description along the iterations and process termination. We describe implementations of RCA and list applications to problems from software and knowledge engineering.

[Departement_IRSTEA]Ecotechnologies [TR1_IRSTEA]MOTIVE; International audience; This paper proposes an operational approach to (1) formalize, in Description Logics (DL), the topological relations between simple regions and (2) automatically check whether a set of relations is consistent. The solution allows for the use of traditional DL reasoners (Pellet, Fact++, etc.) to check the consistency of relations and detect the sources of error. The solution does not require any specific extension of the DL or reasoner. The authors demonstrate how to apply this approach with Protégé and Fact++. Different spatial relations in agricultural and environmental applications are also provided to illustrate the possible uses of our method.

One way of comparing knowledge representation formalisms that has attracted attention recently is in terms of representational succinctness, i.e., we can ask whether one of the formalisms allows for a more 'economical' encoding of information than the other. Proving that one logic is more succinct than another becomes harder when the underlying semantics is stronger. We propose to use Formula Size Games (as put forward by Adler and lmmerman (2003) [1], but we present them as games for one player, called Spoiler), games that are played on two sets of models, and that directly link the length of a play in which Spoiler wins the game with the size of a formula, i.e., a formula that is true in the first set of models but false in all models of the second set. Using formula size games, we prove the following succinctness results for m-dimensional modal logic, where one has a set I = {i(1),..., i(m)} of indices for m modalities: (1) on general Kripke models (and also on binary trees), a definition [for all(Gamma)]phi = Lambda(i is an element of Gamma) [i]phi (with Gamma subset of I) makes the resulting logic exponentially more succinct for m > 1; (2) several modal logics use such abbreviations [for all(Gamma)]phi, e.g., in description logics the construct corresponds to adding role disjunctions, and an epistemic interpretation of it is 'everybody in Gamma knows'. Indeed, we show that on epistemic models (i.e., S-5-models), the logic with [for all(Gamma)]phi becomes more succinct for m > 3; (3) the results for the logic with 'everybody knows' also hold for a logic with 'somebody knows', and (4) on epistemic models, Public Announcement Logic is exponentially more succinct than epistemic logic, if m > 3. The latter settles an open problem raised by Lutz (2006) [18]. 2013 Elsevier B.V. All rights reserved.

International audience; In this paper, we present an ongoing work aiming to improve content based image retrieval performance with the help of logical concept analysis. Domain semantic is formalized and used instead of classical CBIR visual features. This is being applied to comicbooks using Sewelis.

This Habilitation thesis outlines my research activities carried out as an Associate Professor at Univ. Paris-Sud and Inria Saclay Île-de-France. During this period, from 2003 to early 2012, my work was - and still is - at the interface between Knowledge Representation and Databases. I have mainly focused on ontology-based data management using the Semantic Web data models promoted by W3C: the Resource Description Framework (RDF) and the Web Ontology Language (OWL). In particular, my work has covered (i) the design, (ii) the optimization, and (iii) the decentralization of ontology-based data management techniques in these data models. This thesis briefly reports on the results obtained along these lines of research.

International audience; This paper proposes an Ontology-driven and Community-based Web Services (OCWS) framework which aims at automating discovery, composition and execution of web services. The purpose is to validate and to execute a user's request built from the composition of a set of OCWS descriptions and a set of user constraints. The defined framework separates clearly the OCWS external descriptions from internal realistic implementations of e-services. It identifies three levels: the knowledge level, the community level and e-services level and uses different participant agents deployed in a distributed architecture. First, the reasoner agent uses a description logic extended for actions in order to reason about: (i) consistency of the pre-conditions and post-conditions of OCWS descriptions and the user constraints with ontologies semantics, (ii) consistency of the workflow matching assertions and the execution dependency graph. Then the execution plan model is generated automatically to be run by the composer agents using the dynamic execution plan algorithm (DEPA), according to the workflow matching and the established execution order. The community composer agents invoke the appropriate e-services and ensure that the non functional constraints are satisfied. DEPA algorithm works dynamically without a priori information about e-services states and has interesting properties such as taking into account the non-determinism of e-services and reducing the search space.

Webrieflyoutlineourresearchactivity,startedinthe90s,inthefieldofnon-classicallogics.Inparticular,wedescribeour activity on the use of non-classical logics for knowledge representation and on proof methods for non-monotonic and conditional logics.

The original publication is available at www.springerlink.com; International audience; Retrieving and composing individuals' capabilities are the matter of several research fields, like competence-based management, human resources management, enterprise knowledge management systems, knowledge representation systems, etc. This work focuses on capability representation, discovery and composition in heterogeneous, and possibly distributed, knowledge representation environments. We define a capability representation language in Description Logics, and we propose approaches and algorithms for capability management and discovery. In addition, we outline how our proposals are implemented in a mediator-based prototype system.

International audience; Recently the usefulness of Concept Abduction, a novel non-monotonic inference service for Description Logics (DLs), has been argued in the context of ontology-based applications such as semantic matchmaking and resource retrieval. Based on tableau calculus, a method has been proposed to realize this reasoning task in ALN, a description logic that supports simple cardinality restrictionsas well as other basic constructors. However, in many ontology-based systems, the representation of ontology would require expressive formalisms for capturing domain-specific constraints, this language is not sufficient. In order to increase the applicability of the abductive reasoning method in such contexts, we would like to present in the scope of this paper an extension of the tableaux-based algorithm for dealing with concepts represented inALCQ, the description logic that extends ALN with full concept negation and quantified number restrictions.

We extend the Description Logic ALC with a "typicality" operator T that allows us to reason about the prototypical properties and inheritance with exceptions. The resulting logic is called ALC + T. The typicality operator is intended to select the "most normal" or "most typical" instances of a concept. In our framework, knowledge bases may then contain, in addition to ordinary ABoxes and TBoxes, subsumption relations of the form "T(C) is subsumed by P", expressing that typical C-members have the property P. The semantics of a typicality operator is defined by a set of postulates that are strongly related to Kraus-Lehmann-Magidor axioms of preferential logic P. We first show that T enjoys a simple semantics provided by ordinary structures equipped with a preference relation. This allows us to obtain a modal interpretation of the typicality operator. We show that the satisfiability of anALC+Tknowledge base is decidable and it is precisely EXPTIME. We then present a tableau calculus for deciding satisfiability of ALC + T knowledge bases. Our calculus gives a (suboptimal) nondeterministic-exponential time decision procedure for ALC + T. We finally discuss how to extend ALC + T in order to infer defeasible properties of (explicit or implicit) individuals. We propose two alternatives: (i) a nonmonotonic completion of a knowledge base; (ii) a "minimal model" semantics for ALC + T whose intuition is that minimal models are those that maximise typical instances of concepts.

zimmermann2008b; International audience; In the context of the Semantic Web or semantic peer to peer systems, many ontologies may exist and be developed independently. Ontology alignments help integrating, mediating or reasoning with a system of networked ontologies. Though different formalisms have already been defined to reason with such systems, they do not consider ontology alignments as first class objects designed by third party ontology matching systems. Correspondences between ontologies are often asserted from an external point of view encompassing both ontologies. We study consistency checking in a network of aligned ontologies represented in Integrated Distributed Description Logics (IDDL). This formalism treats local knowledge (ontologies) and global knowledge (inter-ontology semantic relations, i.e., alignments) separately by distinguishing local interpretations and global interpretation so that local systems do not need to directly connect to each other. We consequently devise a correct and complete algorithm which, although being far from tractable, has interesting properties: it is independent from the local logics expressing ontologies by encapsulating local reasoners. This shows that consistency of a IDDL system is decidable whenever consistency of the local logics is decidable. Moreover, the expressiveness of local logics does not need to be known as long as local reasoners can handle at least ALC.

International audience; Relational Concept Analysis (RCA) facilitates the discovery of new abstractions in data descriptions including relations. A model driven approach for RCA implementation makes possible to deal with most input data (models) simply by configuring the transformation for the chosen input data type (metamodel). Until now, we only applied this approach to one-level models (mainly class models). In this paper we study RCA applied to bi-levels models, which mix elements and meta-elements (class-instance models, e.g. OWL models). We propose a model hybridisation approach to tackle the encoding problems and we provide a case study showing the results obtained on OWL models.