Search

International audience; We address the problem of handling inconsistency in uncertain knowledge bases that are specified in the lightweight fragments of Description Logics DL-Lite. More specifically, we assume that the TBox component is coherent, stable and fully reliable. However, the ABox component may be inconsistent with respect to the TBox, partially preordered and uncertain. Uncertainty is encoded in the framework of possibility theory. In this context, we propose an extension of standard possibilistic DL-Lite. We represent the ABox as a symbolic weighted base, where the weights attached to the assertions are ordered according to a strict partial order. We define a tractable method for computing a single possibilistic repair for a partially preordered weighted ABox. The idea is to consider the possibilistic compatible bases of such an ABox, which intuitively encode all the possible extensions of a partial order, and compute the possibilistic repair of each compatible base. We then compute the intersection of all these possibilistic repairs to obtain a single repair for the initial ABox. We also provide an equivalent characterization by introducing the notion of π-accepted assertions. This ensures that the computation of the partially preordered possibilistic repair can be achieved in polynomial time in DL-Lite.

In the view of my philosophical position ‘nominal conceptualism’, cognitive/knowledge agents, who are in some way aware of expressing the world based on their mental concepts, deal with their linguistic and/or symbolic expressions. In this paper I rely on nominal concep- tualism to logically characterise agents’ concept-based descriptions of the world and analyse a undamental logical system for conception representation.

We present a new synthesis framework based on the on-the-fly DFA construction for LTL over finite traces (LTLf ). Extant approaches rely heavily on the construction of the complete DFA w.r.t. the input LTLf formula, whose size can be doubly exponential to the size of the formula in the worst case. Under those approaches, the synthesis cannot be conducted unless the whole DFA is completely constructed, which is not only inefficient but also not scalable in practice. Indeed, the DFA construction is the main bottleneck of LTLf synthesis in prior work. To mitigate this challenge, we follow two steps in this paper: Firstly, we present several light-weight pre-processing techniques such that the synthesis result can be obtained even without DFA construction; Secondly, we propose to achieve the synthesis together with the on-the-fly DFA construction such that the synthesis result can be obtained before constructing the whole DFA. The on-the-fly DFA construction is implemented using the SAT-based techniques for automata generation. We compared our new approach with the traditional ones on extensive LTLf synthesis benchmarks. Experimental results showed that the pre-processing techniques have a significant advantage on the synthesis performance in terms of scalability, and the on-the-fly synthesis is able to complement extant approaches on both realizable and unrealizable cases.

The past 25 years have seen many attempts to introduce defeasible-reasoning capabilities into a description logic setting. Many, if not most, of these attempts are based on preferential extensions of description logics, with a significant number of these, in turn, following the so-called KLM approach to defeasible reasoning initially advocated for propositional logic by Kraus, Lehmann, and Magidor. Each of these attempts has its own aim of investigating particular constructions and variants of the (KLM-style) preferential approach. Here our aim is to provide a comprehensive study of the formal foundations of preferential defeasible reasoning for description logics in the KLM tradition. We start by investigating a notion of defeasible subsumption in the spirit of defeasible conditionals as studied by Kraus, Lehmann, and Magidor in the propositional case. In particular, we consider a natural and intuitive semantics for defeasible subsumption, and we investigate KLM-style syntactic properties for both preferential and rational subsumption. Our contribution includes two representation results linking our semantic constructions to the set of preferential and rational properties considered. Besides showing that our semantics is appropriate, these results pave the way for more effective decision procedures for defeasible reasoning in description logics. Indeed, we also analyse the problem of non-monotonic reasoning in description logics at the level of entailment and present an algorithm for the computation of rational closure of a defeasible knowledge base. Importantly, our algorithm relies completely on classical entailment and shows that the computational complexity of reasoning over defeasible knowledge bases is no worse than that of reasoning in the underlying classical DL ALC .

Ontology-based data management (OBDM) is a powerful knowledge-oriented paradigm for managing data spread over multiple heterogeneous sources. In OBDM, the data sources of an information system are handled through the reconciled view provided by an ontology, i.e., the conceptualization of the underlying domain of interest expressed in some formal language. In any information systems where the basic knowledge resides in data sources, it is of paramount importance to specify the acceptable states of such information. Usually, this is done via integrity constraints, i.e., requirements that the data must satisfy formally expressed in some specific language. However, while the semantics of integrity constraints are clear in the context of databases, the presence of inferred information, typical of OBDM systems, considerably complicates the matter. In this paper, we establish a novel framework for integrity constraints in the OBDM scenarios, based on the notion of knowledge state of the information system. For integrity constraints in this framework, we define a language based on epistemic logic, and study decidability and complexity of both checking satisfaction and performing different forms of static analysis on them.

Lehmann and Magidor's rational closure is acknowledged as a landmark in the field of non-monotonic logics and it has also been re-formulated in the context of Description Logics (DLs). We show here how to model a rational form of entailment for expressive DLs, such as SROIQ, providing a novel reasoning procedure that compiles a nonmonotone DL knowledge base into a description logic program (dl-program).

We introduce a nonmonotonic procedure for preferential Description Logics in order to reason about typicality by taking probabilities of exceptions into account. We consider an extension, called ALC + T R P , of the logic of typicality ALC + T R by inclusions of the form T ( C ) ⊑ p D with probability p, whose intuitive meaning is that “all the typical Cs are Ds, and the probability that a C is not a D is 1 − p ”. We consider a notion of extension of an ABox containing only some typicality assertions, then we equip each extension with a probability. We then restrict entailment of a query F to those extensions whose probabilities belong to a given and fixed range. We propose a decision procedure for reasoning in ALC + T R P and we exploit it to show that entailment is ExpTime -complete as for the underlying ALC .

A study of query answering in prioritized ontological knowledge bases (KBs) has received attention in recent years. While several semantics of query answering have been proposed and their complexity is rather well-understood, the problem of explaining inconsistency-tolerant query answers has paid less attention. Explaining query answers permits users to understand not only what is entailed or not entailed by an inconsistent description logic DL-LiteR KBs in the presence of priority, but also why.We, therefore, concern with the use of argumentation frameworks to allow users tobetter understand explanation techniques of querying answers over inconsistent DLLiteRKBs in the presence of priority. More specifically, we propose a new variantof Dung’s argumentation frameworks, which corresponds to a given inconsistent DLLiteRKB. We clarify a close relation between preferred subtheories adopted in suchprioritized DL-LiteR setting and acceptable semantics of the corresponding argumentationframework. The significant result paves the way for applying algorithms andproof theories to establish preferred subtheories inferences in prioritized DL-LiteRKBs.

In this paper we study instance-level update in DL-LiteA , a well-known description logic that influenced the OWL 2 QL standard. Instance-level update regards insertions and deletions in the ABox of an ontology. In particular we focus on formula-based approaches to instance-level update. We show that DL-LiteA , which is well-known for enjoying first-order rewritability of query answering, enjoys a first-order rewritability property also for instance-level update. That is, every update can be reformulated into a set of insertion and deletion instructions computable through a non-recursive Datalog program with negation. Such a program is readily translatable into a first-order query over the ABox considered as a database, and hence into SQL. By exploiting this result, we implement an update component for DL-LiteA-based systems and perform some experiments showing that the approach works in practice. This work was partly supported by the EU within the H2020 Programme under the grant agreement 834228 (ERC Advanced Grant WhiteMech), the grant agreement 952215 (TAILOR), and the grant agreement 825333 (MOSAICrOWN). Moreover, it is partly supported by Ministerio de Economia, Industria y Competitividad under the grant agreement TIN2017-87610-R (REMEDiAL), by the Generalitat de Catalunya under the grant agreement 2017-SGR-1749, and by Regione Lombardia within the Call Hub Ricerca e Innovazione under the grant agreement 1175328 (WATCHMAN).

In Ontology-Based Data Access (OBDA), a domain ontology is linked to the data sources of an organization in order to query, integrate and manage data through the concepts and relations of the domain of interest, thus abstracting from the technical details of the data layer implementation. While the great majority of contributions in OBDA in the last decade have been concerned with the issue of computing the answers of queries expressed over the ontology, recent papers address a different problem, namely the one of providing suitable abstractions of data services, i.e., characterizing or explaining the semantics of queries over the sources in terms of queries over the domain ontology. Current works on this subject are based on expressing abstractions in terms of unions of conjunctive queries (UCQs) over the ontology. In this paper we advocate the use of a non-monotonic language for this task. As a first contribution, we present a simple extension of UCQs with non-monotonic features, and show that non-monotonicity provides more expressive power in characterizing the semantics of data services. A second contribution is to prove that, similarly to the case of monotonic abstractions, depending on the expressive power of the languages used to specify the various components of the OBDA system, there are cases where neither perfect nor approximated abstractions exist for a given data service. As a third contribution, we single out interesting special cases where the existence of abstractions is guaranteed, and we present algorithms for computing such abstractions in these cases.

Serializable and incremental semantic reasoners make it easier to reason on a mobile device with limited resources, as they allow the reuse of previous inferences computed by another device without starting from scratch. This paper describes an extension of the fuzzy ontology reasoner fuzzyDL to make it the first serializable and incremental semantic reasoner. We empirically show that the size of the serialized files is smaller than in another serializable semantic reasoner (JFact), and that there is a significant decrease in the reasoning time.

In this paper we present results to the problem of an adequate and compact symbolic representation of morphological features of anatomical structures that serve as surgical landmarks for automated assistance in endoscopic surgery using the General Formal Ontology (GFO) as a formal framework. For this purpose, we employed a translation from this first-order logic representation to a more compact description logic based formalism with the associated benefits, such as the availability of decidable reasoning procedures, for the purpose of automated landmark recognition in a hybrid symbolic/subsymbolic AI approach.

Issue title: Special Issue on the 30th Italian Conference on Computational Logic: CILC 2015Guest editors: Marco Maratea, Viviana Mascardi, Davide Ancona and Alberto Pettorossi; International audience; We explore the extension of the notion of rational closure to logics lacking the finite model property, considering the logic SHIQ. We provide a semantic characterization of rational closure in SHIQ in terms of a preferential semantics, based on a finite rank characterization of minimal models. We show that the rational closure of a KB can be computed in EXPTIME based on a polynomial encoding of the rational extension of SHIQ into entailment in SHIQ. We discuss the extension of rational closure to more expressive description logics.

Fuzzy DL-Lite has been studied as a means to answer queries w.r.t. vague or imprecise knowledge and facts. Existing approaches consider only the Zadeh semantics or are limited to precise terminological knowledge, where only facts are graded. We study the problem of answering conjunctive queries over fuzzy DL-Lite\(_R\) ontologies which allow also graded axioms, and whose semantics is based on mathematical fuzzy logic. We show that for the Godel t-norm, the degree of an answer is computable through repeated calls to a classical query answering engine. For non-idempotent t-norms, we show the difficulty in dealing with degrees, and provide some partial solutions.

Personal data provides important business value, for example, in the personalization of services. In addition, companies are moving toward new business models, in which products and services are offered without charge to users, but in exchange for targeted advertising revenue. New privacy regulations require organizations to explicitly state their data practices in privacy policies, including which data types will be collected. By consenting to data collections described in a policy, the user acknowledges that he or she is granting the company the authorizations needed to access their data. When data practices change, a new version of the policy is released. This release can occur a few times a year, when requirements are rapidly changing for the collection and processing of personal data. Furthermore, the user may change his or her privacy consent by opting in or out of the policy. We propose a formal framework to support companies and users in their understanding of policies evolution under consent regime that supports both retroactive and non-retroactive consent and consent revocation. Preliminary results include an ontology for policy evolution, expressed in Description Logic, that can be used to formalize consent and data collection logs and then query for which data types can be legally accessed.

This paper develops a formal framework, founded on description logics, to assist decision making in relation to the manufacturing operation and control in modern enterprises that stand to benefit from the transition to Industry 4.0. The objective is to provide sophisticated support to individuals making decisions in the area of production operations management and in particular, production scheduling and material requirements planning. Using this framework, this paper demonstrates an approach to encode the domain knowledge of human experts managing the production as sets of formal rules. These rules can be implemented in an intelligent system that can assist and empower human experts, reducing difficulty when making decisions in complex manufacturing environments.

A significant portion of information that is nowa-days collected in enterprises and organizations resides in text documents, and thus is inherently unstructured. Turning it into a structured form is the aim of information extraction (IE). Depending on the approach followed, the output of an IE process can fill forms or populate relational tables, or can be presented through an ontology. This last approach is particularly interesting, since ontologies may facilitate the integration with other corporate and external data, and enable data management and governance at an abstract, conceptual level, as in Ontology-based Data Access (OBDA). To this aim, OBDA uses declarative mappings that specify the relation between the ontology and the database to be accessed. In OBDA, however, only mappings towards relational databases have been so far considered, and how to declaratively relate the ontology to unstructured sources is still unexplored. By leveraging the study on document spanners for IE, in this paper we propose a new framework that allows to map text documents to ontologies, in the spirit of the OBDA approach. We then investigate the problem of answering conjunctive queries (CQs) in our framework, and show that, if the ontology is specified in the lightweight Description Logic DL-LiteR, the problem can be solved by reformulating the user query into a new spanner. Interestingly, both the spanners used in the mapping and the one computed by the rewriting algorithm have the same expressiveness, and CQ answering in this case is polynomial in data complexity.

International audience; We propose a method to construct asymmetric metrics for evaluating the quality of multi-relational association rules coded in the form of SWRL rules. These metrics are derived from metrics for scoring association rules. We use each constructed metric as a fitness function for evolutionary inductive programming employed to discover hidden knowledge patterns (represented in SWRL) from assertional data of ontological knowledge bases. This new knowledge can be integrated easily within the ontology to enrich it. In addition, we also carry out a search for the best metric to score candidate multi-relational association rules in the evolutionary approach by experiment. We performed experiments on three publicly available ontologies validating the performances of our approach and comparing them with the main state-of-the-art systems.

Ontologies in real-world applications are typically dynamic entities that are frequently modified when new knowledge needs to be added or when existing knowledge is no longer considered valid. Logical errors inevitably occur when ontologies are modified. To effectively identify the problematic axioms that are responsible for these logical errors, an optimization strategy based on the clash sequence strategy is proposed for debugging the incoherent terminologies in dynamic environments. The clash sequence strategy is used to identify the clash set from an incoherent terminology, and then the debugging work can be performed on the identified clash set than on the entire terminology. A heuristic strategy is also proposed to reuse the results of the previous debugging and to provide information for the next debugging. The experiment results show that the proposed debugging approach based on clash sequences can achieve a significant improvement especially for large-scale ontologies in many cases.

We propose a new family of abstract argumentation frameworks which we refer to as generalized (identified through the acronym GenAF), due to its ability of adapting to different representation languages. GenAFs are formalized upon an unspecified representation language L but enriched with some inner structure which allows relating formulæ from the underlying knowledge base with primitive elements of arguments. The well-known Dung's standard semantics are adapted to construct the GenAF’s reasoning machinery. As an application, we reify the GenAF’s abstract language for arguments with the basic ALC flexibility of the presented formalism and a way of applying argumentation for reasoning over inconsistent ontologies. Finally, a detailed study is performed on the matter of argumentation rationality. The GenAF when concretized into a generalized argumentation system (GenAS) is studied under specific conditions which turn it into a standard logic-based argumentation system. This brings the opportunity to verify the scope of widely accepted postulates for logic-based argumentation to control the well behavior of the GenAS and to relate it to other argumentation systems. Fil: Moguillansky, Martin Oscar. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Bahía Blanca. Instituto de Ciencias e Ingeniería de la Computación. Universidad Nacional del Sur. Departamento de Ciencias e Ingeniería de la Computación. Instituto de Ciencias e Ingeniería de la Computación; Argentina Fil: Simari, Guillermo Ricardo. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Bahía Blanca. Instituto de Ciencias e Ingeniería de la Computación. Universidad Nacional del Sur. Departamento de Ciencias e Ingeniería de la Computación. Instituto de Ciencias e Ingeniería de la Computación; Argentina

The increasing popularity of the Semantic Web drove to a widespread adoption of Description Logics (DLs) for modeling real world domains. To help the diffusion of DLs, a large number of reasoning algorithms have been developed. Usually these algorithms are implemented in procedural languages such as Java or C++. Most of the reasoners exploit the tableau algorithm which features non-determinism, that is not easily handled by those languages. Prolog directly manages non-determinism, thus is a good candidate for dealing with the tableau’s non-deterministic expansion rules. We present TRILL, for “Tableau Reasoner for descrIption Logics in proLog”, that implements a tableau algorithm and is able to return explanations for queries and their corresponding probability, and TRILL P , for “TRILL powered by Pinpointing formulas”, which is able to compute a Boolean formula representing the set of explanations for a query. Reasoning on real world domains also requires the capability of managing probabilistic and uncertain information. We show how TRILL and TRILL P can be used to compute the probability of queries to knowledge bases following DISPONTE semantics. Experiments comparing these with other systems show the feasibility of the approach.

General Concept Inclusion (GCI) absorption algorithms have shown to play an important role in classical Description Logic (DL) reasoners. They allow to transform GCIs into simpler forms to which we may apply specialised inference rules, returning important performance gains. In this work, we develop the first absorption algorithm for fuzzy DLs, implement it in the fuzzyDL reasoner and evaluate it extensively over both classical and fuzzy ontologies. The results show that our algorithm improves the performance of the reasoner significantly.

We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL 2 QL : the succinctness problem for first-order rewritings of ontology-mediated queries (OMQs) and the complexity problem for OMQ answering. We classify OMQs according to the shape of their conjunctive queries (treewidth, the number of leaves) and the existential depth of their ontologies. For each of these classes, we determine the combined complexity of OMQ answering and whether all OMQs in the class have polynomial-size first-order, positive existential, and nonrecursive datalog rewritings. We obtain the succinctness results using hypergraph programs, a new computational model for Boolean functions, which makes it possible to connect the size of OMQ rewritings and circuit complexity.

The Internet of Things is a natural continuity of the Ambient Intelligence where smart and ambient environments are built by integrating a large number of interconnected smart objects with heterogeneous capabilities abstracted as software services. The aim is to design cross-domain applications that compose and select most relevant services, which best match user requirements and closely meet the specified quality-of-service level. However, semantic description and representation of such smart devices, including their hosted services and their provided real world data, is still a challenging issue. Semantic Web technologies are seen as a promising tool for this purpose. Indeed, applying these technologies in the Internet of Things enables smart objects to efficiently share their data, exchange their services and cooperate to better satisfy both functional and non-functional user requirements. In this paper, we propose a new semantic model for smart objects description and users request resolution using ontological techniques combined with description logics. Such a model facilitates intelligent functions, including reasoning over service data and semantic interoperability enabling among devices. A case study for smart environment monitoring has been proposed to illustrate the effectiveness and usability of our approach.

In this paper, a novel approach using Description Logic (DL) based inference rules, for ontology matching is presented. Alignment concerns ontology concepts, with the application of similarity measures to perform concepts and instances relationship alignments. Moreover, external knowledge, in the form of WordNet dictionary is then used to solve usual matching problems encountered with synonyms, polesemy, homonyms, etc. Illustrative examples are then presented to support the developed approach.

Reasoning and change over inconsistent ontologies (i-ont(s)) is of utmost relevance in sciences like medicine and law. Argumentation may be an appropriate formalism to cope with both problems: (reasoning) through an argumentation framework (AF) constructed from the i-ont, and (change) by handling the dynamics of its arguments. We propose a new family of abstract AFs referred as generalized (GenAF), due to its ability of adapting to different representation languages. Afterwards, we propose a possible instantiation of the GenAF?s abstract language for arguments to the basic ALC description logic for reasoning over i-onts. For dynamics of arguments, a revision operation modifies the graph of arguments in an AF for provoking the argumentation semantics to accept an argument. Thus, revising an ALC-GenAF would introduce a novel methodology for handling evolution of i-onts. To such end, we propose a revision operation by relying upon classic belief revision theory, although contrary to it, consistency restoration is avoided in order to handle evolution with inconsistency tolerance. Fil: Moguillansky, Martin Oscar. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Bahía Blanca; Argentina. Universidad Nacional del Sur. Departamento de Ciencia e Ingeniería de la Computación. Laboratorio de Investigación y Desarrollo en Inteligencia Artificial; Argentina

3D models of transportation objects like a road, bridge, underpass, etc. are required in many domains including military training, land development, etc. While remote sensed images and LiDaR data can be used to create approximate 3D representations, detailed 3D representations are difficult to create automatically. Instead, interactive tools are used with rather laborious effort. For example, the top commercial interactive model generator we tried required 94 parameters in all for different bridge types. In this paper, we take a different path.We automatically derive these parameter values from GIS (Geographic Information Systems) data, which normally contains detailed information of these objects, but often only implicitly. The framework presented here transforms GIS data into a knowledge base consisting of assertions. Spatial/numeric relations are handled through plug-ins called property extractors whose results get added to the knowledge base, used by a reasoning engine to infer object properties. A number of properties have to be extracted from images, and are dependent on the accuracy of computer vision methods. While a comprehensive property extractor mechanism is work in progress, . a prototype implementation illustrates our framework for bridges with GIS data from the real world. To the best of our knowledge, our framework is the first to integrate knowledge inference and uncertainty for extracting landscape object properties by fusing facts from multi-modal GIS data sources., Computer Graphics and Visual Computing (CGVC), Visualization III and VR, 153, 161, Pedro Eid Maroun, Sudhir Mudur, and Tiberiu Popa, CCS Concepts: Computing methodologies --> Computer graphics; Description logics; Reasoning about belief and knowledge

The recent tendency in analysis and design of information systems is that the emphasis is placed on the documents that are ubiquitous around information systems and organizations. The proliferation of computer literacy led to the general use of electronic documents. To understand the anticipated behaviour of information systems and the actual operation of an organization, the analysis of documents plays increasingly an important role. The behaviour of information systems can be interpreted in a framework of Enterprise Architecture and its models that are contained in it. Certain parts and entirety of various types of documents are connected to business processes, tasks, roles, and actors within an organization. The tracking of life cycle of documents and representing the complex relationships are essential at both analysis and operation time. We propose a theoretical framework that makes use of previous results of modelling and well-founded mathematical techniques. The basic idea is that the very flexible mathematical structure, the hypergraph, provides a sound groundwork on which a formal structure can be built up through mapping the essential concept, construction, components, and constituents of information systems. Thus, the representations of models for information systems that mapped onto a hypergraph can be analysed by either using more traditional tools as logic and inference rules or by a set of tools belonging to data science later. The paper describes the mapping of the important concepts onto hypergraphs as documents, processes in cases, their models and some rules for verification and validation; the hypergraph description can be interpreted as a concept hypergraph to be subjected for logical reasoning.

We propose a nonmonotonic Description Logic of typicality able to account for the phenomenon of combining prototypical concepts, an open problem in the fields of AI and cognitive modelling. Our logic extends the logic of typicality \(\mathcal {ALC}+\mathbf{T}_\mathbf{R}\), based on the notion of rational closure, by inclusions \(p \ {::} \ \mathbf{T}(C) \sqsubseteq D\) (“we have probability p that typical Cs are Ds”), coming from the distributed semantics of probabilistic Description Logics. Additionally, it embeds a set of cognitive heuristics for concept combination. We show that the complexity of reasoning in our logic is ExpTime-complete as in \(\mathcal {ALC}\).

This paper presents a simplification of one of the TRIZ methods, the Substance-Field Analysis (SFA). Applying TRIZ methods is often time consuming and therefore a barrier to its application in the industry. Our research group strives to simplify TRIZ methods to make their use more widespread. This SFA simplification was obtained during the implementation of a computer aided SFA. This implementation implies an ontological phase, which leads to the translation of the SFA terminological and conditional knowledge in a computer language. In addition to their operational interest, the chosen computer languages (Description Logics and First Order Logic) have formal interest for the SFA. The complexity of the application of SFA has regularly been reported by the TRIZ community. The SFA terminology suffers from a lack of normalization and the 76 Standards deployment is an empirical process. We propose a clarification of the Substance-Field Modeling terminology and a systematic process for deploying the 76 Standards. Thanks to Description Logics, the SFA terminology is formalized in an automatically consistency checked model and First Order Logic ensures the systematization of the 76 Standards deployment.

International audience; Concepts such as near, far, south of, etc., are by its own nature vague. However, they are quite common in human language. In the case of historical records, these concepts are often the only source of information regarding the position of ancient places whose exact location has been lost. In our research, we use digitized written records from Upper Mesopotamia (2000BC) from the HIGEOMES project. Our goal is to provide better understanding of the location of places, based on the analysis of spatial statements. In our approach, we analyse cardinal statements between places with known location. Using this information we construct a probabilistic function representing the vagueness of cardinal statements. For each place with unknown position, we combine multiple vague statements using our probabilistic function in order to limit the possible search area. At this point, our results look promising. In the near future, and thanks to new data, such as proximity statements as provided by the HIGEOMES project, we expect to improve our results.

The World Wide Web contains large amounts of data, and in most cases this data has no explicit structure. The lack of structure makes it difficult for automated agents to understand and use such data. A step towards a more structured World Wide Web is the Semantic Web, which aims at introducing semantics to data on the World Wide Web. One of the key technologies in this endeavour are ontologies, which provide a means for modeling a domain of interest and are used for search and integration of data. In recent years many ontologies have been developed. To be able to use multiple ontologies it is necessary to align them, i.e., find inter-ontology relationships. However, developing and aligning ontologies is not an easy task and it is often the case that ontologies and their alignments are incorrect and incomplete. This can be a problem for semantically-enabled applications. Incorrect and incomplete ontologies and alignments directly influence the quality of the results of such applications, as wrong results can be returned and correct results can be missed. This thesis focuses on the problem of completing ontologies and ontology networks. The contributions of the thesis are threefold. First, we address the issue of completing the is-a structure and alignment in ontologies and ontology networks. We have formalized the problem of completing the is-a structure in ontologies as an abductive reasoning problem and developed algorithms as well as systems for dealing with the problem. With respect to the completion of alignments, we have studied system performance in the Ontology Alignment Evaluation Initiative, a yearly evaluation campaign for ontology alignment systems. We have also addressed the scalability of ontology matching, which is one of the current challenges, by developing an approach for reducing the search space when generating the alignment.Second, high quality completion requires user involvement. As users' time and effort are a limited resource we address the issue of limiting and facilitating user interaction in the completion process. We have conducted a broad study of state-of-the-art ontology alignment systems and identified different issues related to the process. We have also conducted experiments to assess the impact of user errors in the completion process. While the completion of ontologies and ontology networks can be done at any point in the life-cycle of ontologies and ontology networks, some of the issues can be addressed already in the development phase. The third contribution of the thesis addresses this by introducing ontology completion and ontology alignment into an existing ontology development methodology.

Lipids are a major class of biomolecule and potentially the most varied by structure, function, and origin. As the development of highthroughput techniques for analysis of genes and proteins has given rise to the new fields of genomics and proteomics, the development of highthroughput techniques for lipids has given rise to lipidomics. The great increases in volumes of data being produced require new methods of processing and automated analysis, but lipidomics face a great problem in characterisation due to their highly varied structures. The task of assigning identified lipids within classification schemes has traditionally fallen to human experts, but this approach will not scale with the volumes of data being produced and leads to increased likelihood of error. Recently, automated software has been produced to classify all molecules, including lipids, but it remains to be seen whether it will be taken up by the community. The increase in volume of data also necessitates the automation of more tasks usually performed by humans beyond classification. Ontologies have been used for modelling in the life sciences, most notably with the Gene Ontology, and are noted for their ability to formally capture the meaning of the domain of interest in a machine readable way, unlike with human prose, due to formal syntax and semantics. This further permits machine reasoning, where a program can interpret the ontology and draw additional inferences - a form of interpretation usually reserved for humans. In the present work a study of the Protein Data Bank’s (PDB’s) small molecule dictionary is performed, identifying resolved lipids by means of cross-reference with external sources of lipidomic data and classification. Furthermore, the consistency of classification of these external data sources is analysed. In order to permit a reasoner to make inferences about relations between entries in data sources, a chemical relation ontology based on the International Chemical Identifier iv (InChI) is developed. For correct functioning of the chemical relation ontology, the reasoning power of the underlying ontologies was extended. The extensions to the ontologies lead to an interesting novel form of logical rule for use with ontologies, and its properties and implementation are demonstrated and discussed. The present work aims to demonstrate the usefulness of ontologies to data intensive pursuits beyond their ability to model domains. The chemical relation ontology and associated work on rules show that ontologically aware modelling of opaque or difficult to understand data can lead to the inference of information usually reserved for human experts, and the study of the PDB’s small-molecule dictionary and of the consistency of the lipid data sources shows the utility of integrating data from external sources by logical, ontological means, and also the capability detecting inconsistency between and within data sources.

International audience; In this paper, we propose an original way of enriching description logics with abduction reasoning services. Under the aegis of set and lattice theories, we put together ingredients from mathematical morphology, description logics, and formal concept analysis. We propose computing the best explanations of an observation through algebraic erosion over the concept lattice of a background theory that is efficiently constructed using tools from formal concept analysis. We show that the defined operators are sound and complete and satisfy important rationality postulates of abductive reasoning. As a typical illustration, we consider a scene understanding problem. In fact, scene understanding can benefit from prior structural knowledge represented as an ontology and the reasoning tools of description logics. We formulate model based scene understanding as an abductive reasoning process. A scene is viewed as an observation and the interpretation is defined as the best explanation, considering the terminological knowledge part of a description logic about the scene context. This explanation is obtained from morphological operators applied on the corresponding concept lattice.

The philosophical, logical, and terminological junctions between Description Logics (DLs) and Modal Logic (ML) are important because they can support the formal analysis of modal notions of ‘possibility’ and ‘necessity’ through the lens of DLs. This paper introduces functional contingents in order to (i) structurally and terminologically analyse ‘functional possibility’ and ‘functional necessity’ in DL world descriptions and (ii) logically and terminologically annotate DL world descriptions based on functional contingents. The most significant contributions of this research are the logical characterisation and terminological analysis of functional contingents in DL world descriptions. The ultimate goal is to investigate how modal operators can – logically and terminologically – be expressed within DL world descriptions.

The Web Ontology Language (OWL) is a family of description logic based ontology languages for the Semantic Web and gives well defined meaning to web accessible information and services. The study of inconsistency-tolerant reasoning with description logic knowledge bases is especially important for the Semantic Web since knowledge is not always prefect within it. An important challenge is strengthening the inference power of inconsistency-tolerant reasoning because it is normally impossible for paraconsistent logics to obey all important properties of inference together. This paper presents a non-classical DL called quasi-classical description logic (QCDL) to tolerate inconsistency in OWL DL which is a most important sublanguage of OWL supporting those users who want the maximum expressiveness while retaining computational completeness (i.e., all conclusions are guaranteed to be computable) and decidability (i.e., all computations terminate in finite time). Instead of blocking those inference rules, we validate them conditionally and partially, under which more useful information can still be inferred when inconsistency occurs. This new non-classical DL possesses several important properties as well as its paraconsistency in DL, but it does not bring any extra complexity in worst case. Finally, a transformation-based algorithm is proposed to reduce reasoning problems in QCDL to those in DL so that existing OWL DL reasoners can be used to implement inconsistency-tolerant reasoning. Based on this algorithm, a prototype OWL DL paraconsistent reasoner called PROSE is implemented. Preliminary experiments shows that PROSE produces more intuitive results for inconsistent knowledge bases than other systems in general. We would like to thank the anonymous reviewers for their critical comments which helped us to substantially improve the paper. We also thank Yue Ma, Guilin Qi and Kewen Wang for helpful comments and discussions. This work is partly supported by the project of Research Foundation Flanders (FWO) under grant G.0489.10N, Vienna PhD School of informatics and the program of the National Natural Science Foundation of China (NSFC) under grant 60973003.

This book illustrates how to use description logic-based formalisms to their full potential in the creation, indexing, and reuse of multimedia semantics. To do so, it introduces researchers to multimedia semantics by providing an in-depth review of state-of-the-art standards, technologies, ontologies, and software tools. It draws attention to the importance of formal grounding in the knowledge representation of multimedia objects, the potential of multimedia reasoning in intelligent multimedia applications, and presents both theoretical discussions and best practices in multimedia ontology engineering.

International audience; In this paper we propose a non-monotonic extension of the Description Logic ALC for reasoning about prototypical properties and inheritance with exceptions. The resulting logic, called ALC + T-min, is built upon a previously introduced (monotonic) logic ALC + T that is obtained by adding a typicality operator T to ALC. The operator T is intended to select the "most normal" or "most typical" instances of a concept, so that knowledge bases may contain subsumption relations of the form T(C) subset of D ("T(C) is subsumed by D"), expressing that typical C-members are instances of concept D. From a knowledge representation point of view, the monotonic logic ALC + T is too weak to perform inheritance reasoning. In ALC + T-min, in order to perform non-monotonic inferences, we define a "minimal model" semantics over ALC + T. The intuition is that preferred or minimal models are those that maximize typical instances of concepts. By means of ALC + T-min we are able to infer defeasible properties of (explicit or implicit) individuals. We also present a tableau calculus for deciding ALC + T-min entailment that allows to give a complexity upper bound for the logic, namely that query entailment is in co-NExp(NP)

Finite model reasoning in UML class diagrams is an important task for assessing the quality of the analysis phase in the development of software applications in which it is assumed that the number of objects of the domain is finite. In this paper, we show how to encode finite model reasoning in UML class diagrams as a constraint satisfaction problem (CSP), exploiting techniques developed in description logics. In doing so we set up and solve an intermediate CSP problem to deal with the explosion of "class combinations" arising in the encoding. To solve the resulting CSP problems we rely on the use of off-the-shelf tools for constraint modeling and programming. As a result, we obtain, to the best of our knowledge, the first implemented system that performs finite model reasoning on UML class diagrams.

According to the last years the use of domain ontologies has increased considerably. In Logic Circuits, we can used the ontologies not only for educational purposes but also for interrogating the domain knowledge represented in an ontology. As well as means to verify the design of a circuit considering the manufacturer specification (offering) and the client view point (requiring). This approach allows the reuse of previously constructed circuits in different contexts.

We investigate on the possibility of transforming concepts in Description Logics into relational databases and queries in such a way that subsumption between the original concepts can be decided as query answering over a database. For the positive results, we show a translation of ALN -concepts into pairs (database, query) such that, in order to decide Subsumption CD one evaluates the query resulting from the translation of D over the database resulting from C. For the negative results, we show that no compilation is possible for expressive Description Logics.

Answering queries over an incomplete database w.r.t. a set of constraints is an important computational task with applications in fields as diverse as information integration and metadata management in the semantic Web. Description Logics (DLs) are constraint languages that have been extensively studied with the goal of providing useful modeling constructs while keeping the query answering problem decidable. For many DLs, query answering under constraints can be solved via query rewriting: given a conjunctive query Q and a set of DL constraints T , the query Q can be transformed into a datalog query Q T that takes into account the semantic consequences of T ; then, to obtain answers to Q w.r.t. T and some (arbitrary) database instance A , one can simply evaluate Q T over A using existing (deductive) database technology, without taking T into account. In this paper, we present a novel query rewriting algorithm that handles constraints modeled in the DL ELHIO ¬ and use it to show that answering conjunctive queries in this setting is PTime -complete w.r.t. data complexity. Our algorithm deals with various description logics of the EL and DL-Lite families and is worst-case optimal w.r.t. data complexity for all of them.

Ontologies play a crucial role in the development of the Semantic Web as a means for defining shared terms in web resources. They are formulated in web ontology languages, which are based on expressive description logics. Significant research efforts in the semantic web community are recently directed towards representing and reasoning with uncertainty and vagueness in ontologies for the Semantic Web. In this paper, we give an overview of approaches in this context to managing probabilistic uncertainty, possibilistic uncertainty, and vagueness in expressive description logics for the Semantic Web. © 2008 Elsevier B.V. All rights reserved.

We focus on the aspect of sensing in reasoning about actions under qualitative and probabilistic uncertainty. We first define the action language E for reasoning about actions with sensing, which has a semantics based on the autoepistemic description logic ALCK NF , and which is given a formal semantics via a system of deterministic transitions between epistemic states. As an important feature, the main computational tasks in E can be done in linear and quadratic time. We then introduce the action language E + for reasoning about actions with sensing under qualitative and probabilistic uncertainty, which is an extension of E by actions with nondeterministic and probabilistic effects, and which is given a formal semantics in a system of deterministic, nondeterministic, and probabilistic transitions between epistemic states. We also define the notion of a belief graph, which represents the belief state of an agent after a sequence of deterministic, nondeterministic, and probabilistic actions, and which compactly represents a set of unnormalized probability distributions. Using belief graphs, we then introduce the notion of a conditional plan and its goodness for reasoning about actions under qualitative and probabilistic uncertainty. We formulate the problems of optimal and threshold conditional planning under qualitative and probabilistic uncertainty, and show that they are both uncomputable in general. We then give two algorithms for conditional planning in our framework. The first one is always sound, and it is also complete for the special case in which the relevant transitions between epistemic states are cycle-free. The second algorithm is a sound and complete solution to the problem of finite-horizon conditional planning in our framework. Under suitable assumptions, it computes every optimal finite-horizon conditional plan in polynomial time. We also describe an application of our formalism in a robotic-soccer scenario, which underlines its usefulness in realistic applications.

Description logics (DLs) are a family of logics for representing structured knowledge which have proved to be very useful as ontology languages. Classical DLs are not suitable to rep- resent vague pieces of information. The attempts to achieve a solution have led to the birth of fuzzy DLs and rough DLs. In this work, we provide a simple solution to join these two formalisms and define a fuzzy rough DL. This logic is more general than other related approaches, including tight and loose fuzzy rough approximations and being independent of the fuzzy logic operators considered. We show the usefulness of our approach by pre- senting some uses case, and we also describe how to extend two reasoning algorithms for fuzzy DLs, which are implemented in the fuzzy DL reasoners FUZZYDL and DELOREAN.

View-based query answering is the problem of answering a query based only on the precomputed answers to a set of views. While this problem has been widely investigated in databases, it is largely unexplored in the context of Description Logic ontologies. Differently from traditional databases, Description Logics may express several forms of incomplete information, and this poses challenging problems in characterizing the semantics of views. In this paper, we first present a general framework for view-based query answering, where we address the above semantical problems by providing two notions of view-based query answering over ontologies, all based on the idea that the precomputed answers to views are the certain answers to the corresponding queries. We also relate such notions to privacy-aware access to ontologies. Then, we provide decidability results, algorithms, and data complexity characterizations for view-based query answering in several Description Logics, ranging from those with limited modeling capability to highly expressive ones.

In description logic (DL), ABoxes are used for describing the state of affairs in an application domain. We consider the problem of updating ABoxes when the state changes, assuming that update information is described at an atomic level, i.e., in terms of possibly negated ABox assertions that involve only atomic concepts and roles. We analyze such basic ABox updates in several standard DLs, in particular addressing questions of expressibility and succinctness: can updated ABoxes always be expressed in the DL in which the original ABox was formulated and, if so, what is the size of the updated ABox? It turns out that DLs have to include nominals and the ‘@’ constructor of hybrid logic for updated ABoxes to be expressible, and that this still holds when updated ABoxes are approximated. Moreover, the size of updated ABoxes is exponential in the role depth of the original ABox and the size of the update. We also show that this situation improves when updated ABoxes are allowed to contain additional auxiliary symbols. Then, DLs only need to include nominals for updated ABoxes to exist, and the size of updated ABoxes is polynomial in the size of both the original ABox and the update.

Competence management calls for automated knowledge-based services in order to take full advantage from the know-how of a company. This paper presents an integrated semantic-based knowledge management system providing decision support services for several activities typical of competence management, including core competence evaluation, human resources allocation, training programs planning. Knowledge resources are represented according to the formalism of Description Logics, which also allows for inference services crucial for the implemented solutions. We present the various features of our approach, which exploit advanced non-standard reasoning services from Description Logics, specifically developed to support knowledge management.

Molodtsov initiated the concept of soft set theory, which can be used as a generic mathematical tool for dealing with uncertainty. Description Logics (DLs) are a family of knowledge representation languages which can be used to represent the terminological knowledge of an application domain in a structured and formally well-understood way. Nowadays, properties and semantics of ontology constructs mainly are determined by DLs. In this paper we investigate semantic operations of multiple standard soft sets by using domain ontologies (i.e., DL intensional knowledge bases). Concretely, we give some semantic operations such as complement, restricted difference, extended union, restricted intersection, restricted union, extended intersection, AND, and OR for (multiple) standard soft sets from a semantic point of view. Especially, we also present an approach to deal with conflict from a semantic point of view when we define these semantic operations. Moreover, the basic properties and implementation methods of these semantic operations under conflict are also presented and discussed.