We characterize the expressive power of description logic (DL) TBoxes, both for expressive DLs such as ALC and ALCQIO and lightweight DLs such as DL-Lite and EL. Our characterizations are relative to first-order logic, based on a wide range of semantic notions such as bisimulation, equisimulation, disjoint union, and direct product. We exemplify the use of the characterizations by a first study of the following novel family of decision problems: given a TBox T formulated in one DL, decide whether T can be equivalently rewritten as a TBox in der fragment L' of L.

Uncertainty and vagueness are pervasive phenomena in real-life knowledge. They are supported in extended description logics that adapt classical description logics to deal with numerical probabilities or fuzzy truth degrees. While the two concepts are distinguished for good reasons, they combine in the notion of probably, which is ultimately a fuzzy qualification of probabilities. Here, we develop existing propositional logics of fuzzy probability into a full-blown description logic, and we show decidability of several variants of this logic under Lukasiewicz semantics. We obtain these results in a novel generic framework of fuzzy coalgebraic logic; this enables us to extend our results to logics that combine crisp ingredients including standard crisp roles and crisp numerical probabilities with fuzzy roles and fuzzy probabilities.

We study the problem of dealing with inconsistency in Description Logic (DL) ontologies. We consider inconsistency-tolerant semantics recently proposed in the literature, called AR-semantics and CAR-semantics, which are based on repairing (i.e., modifying) in a minimal way the extensional knowledge (ABox) while keeping the intensional knowledge (TBox) untouched. We study instance checking and conjunctive query entailment under the above inconsistency-tolerant semantics for a wide spectrum of DLs, ranging from tractable ones (EL) to very expressive ones (SHIQ), showing that reasoning under the above semantics is inherently intractable, even for very simple DLs. To the aim of overcoming such a high computational complexity of reasoning, we study sound approximations of the above semantics. Surprisingly, our computational analysis shows that reasoning under the approximated semantics is intractable even for tractable DLs. Finally, we identify suitable language restrictions of such DLs allowing for tractable reasoning under inconsistency-tolerant semantics.

As more and more application areas require higher scalability, the study of fragments of expressive The high computational complexity of the expressive DLs with better computational properties has become an Description Logics (DLs) that underlie the important area of research. OWL standard has motivated the study of their Horn fragments of DLs, which are obtained by restricting Horn fragments, which are usually tractable in data the syntax of a DL in such a way that disjunction is not complexity and can also have lower combined complexity, expressible, were first considered in [Hustadt et al., 2005] particularly for query answering. In this paper as expressive fragments with tractable data complexity (see we provide algorithms for answering conjunctive also [Krötzsch et al., 2007]). It was later identified that they 2-way regular path queries (2CRPQs), a nontrivial can also exhibit lower combined complexity when it comes generalization of plain conjunctive queries, to query answering. Indeed, answering conjunctive queries in the Horn fragments of the DLs SHOIQ and (CQs), a kind of database-inspired queries that have become SROIQ underlying OWL 1 and OWL 2. We show the standard for querying DLs, is in ExpTime for the Horn that the combined complexity of the problem is ExpTime-complete fragment of the prominent SHIQ [Eiter et al., 2008], while it for Horn-SHOIQ and 2ExpTimecomplete is already 2ExpTime-hard for quite restricted (non Horn) fragments for the more expressive Horn-SROIQ, of SHIQ, like ALCI [Lutz, 2008] and SH [Eiter et but is PTime-complete in data complexity for both.

We study uniform interpolation and forgetting in the description logic ALC. Our main results are model-theoretic characterizations of uniform interpolants and their existence in terms of bisimulations, tight complexity bounds for deciding the existence of uniform interpolants, an approach to computing interpolants when they exist, and tight bounds on their size. We use a mix of model-theoretic and automata-theoretic methods that, as a by-product, also provides charachterizations of, and decision procedures for, conservative extensions.

We study a decidable fixpoint extension of temporal description logics. To this end we employ and extend decidability results obtained for various temporally first-order monodic extensions of (first-order) description logics. Using these techniques we obtain decidability and tight complexity results for various fixpoint extensions of temporal description logics.

Defeasible inheritance networks are a non-monotonic framework that deals with hierarchical knowledge. On the other hand, rational closure is acknowledged as a landmark of the preferential approach. We will combine these two approaches and define a new non-monotonic closure operation for propositional knowledge bases that combines the advantages of both. Then we redefine such a procedure for Description Logics, a family of logics well-suited to model structured information. In both cases we will provide a simple reasoning method that is build on top of the classical entailment relation.

Query containment has been studied extensively in KR and databases, for different kinds of query languages and domain constraints. We address the longstanding open problem of containment under expressive description logic (DL) constraints for two-way regular path queries (2RPQs) and their conjunctions, which generalize conjunctive queries with the ability to express regular navigation. We show that, surprisingly, functionality constraints alone make containment of 2RPQs already ExpTime-hard. By employing automata-theoretic techniques, we also provide a matching upper bound that extends to very expressive DL constraints. For conjunctive 2RPQs we prove a further exponential jump in complexity, and provide again a matching upper bound for expressive DLs. Our techniques provide also a solution to the problem of query entailment over DL knowledge bases in which individuals in the ABox may be related through regular role-paths.

The automata-based approach is based on translating a knowledge base (KB) whose satisfiability is to be checked In this work we describe the theoretical foundations into some variant of automata on infinite trees that accepts and the implementation of a new automata-based tree-shaped models of the KB, and checking such an automaton technique for reasoning over expressive Description for non-emptiness. This approach is powerful and flexible. Logics that is worst-case optimal and lends itself It is acknowledged that it provides a very robust basis to an efficient implementation. In order to show for showing worst-case optimal complexity upper bounds, the feasibility of the approach, we have realized a and has been applied for a wide range of expressive DLs working prototype of a reasoner based upon these and reasoning services (cf.

Uncertainty is unavoidable when modeling most application domains. In medicine, for example, symptoms (such as pain, dizziness, or nausea) are always subjective, and hence imprecise and incomparable. Additionally, concepts and their relationships may be inexpressible in a crisp, clear-cut manner. We extend the description logic ALC with multi-valued semantics based on lattices that can handle uncertainty on concepts as well as on the axioms of the ontology. We introduce reasoning methods for this logic w.r.t. general concept inclusions and show that the complexity of reasoning is not increased by this new semantics.