Description Logics (DLs) excel at representing structured knowledge in several application domains, but fall very short when it comes to reasoning about their numeric aspects. We consider the expressive DL ALCHOIQ with closed predicates and extend it with features ranging over user-specified finite numeric intervals, feature assertions, and local additive constraints on feature values. We illustrate the power of this language for describing problems that involve ontological and numeric reasoning and study reasoning problems that go beyond satisfiability, such as finding models that minimize some costs. We show that these additional numeric modeling and reasoning capabilities can be accommodated by extending a standard reasoning technique for ALCHOIQ using linear inequalities, and the extension does not necessarily increase the worst-case computational cost.

Reasoning with minimal models has always been at the core of many knowledge representation techniques, but we still have only a limited understanding of this problem in Description Logics (DLs). Minimization of some selected predicates---letting the remaining predicates vary or be fixed, as proposed in circumscription---has been explored and exhibits high complexity. The case of `pure' minimal models, where the extension of all predicates must be minimal, has remained largely uncharted. We address this problem in popular DLs and obtain surprisingly negative results: concept satisfiability in minimal models is undecidable already for EL. This undecidability also extends to a very restricted fragment of tuple-generating dependencies. To regain decidability, we impose acyclicity conditions on the TBox that bring the worst-case complexity below double exponential time and allow us to establish a connection with the recently studied pointwise circumscription; we also derive results in data complexity. We conclude with a brief excursion to the DL-Lite family, where a positive result was known for DL-Lite_core, but our investigation establishes ExpSpace-hardness already for its extension DL-Lite_horn.

This paper studies a stable model semantics for Description Logic (DL) knowledge bases (KBs) and for (possibly cyclic) terminologies, ultimately showing that terminologies under the proposed semantics can be equipped with effective reasoning algorithms. The semantics is derived using Quantified Equilibrium Logic, and---in contrast to the usual semantics of DLs based on classical logic---supports default negation and allows to combine the open-world and the closed-world assumptions in a natural way. Towards understanding the computational properties of this and related formalisms, we show a strong undecidability result that applies not only to KBs under the stable model semantics, but also to the more basic setting of minimal model reasoning. Specifically, we show that concept satisfiability in minimal models of an ALCIO KB is undecidable. We then turn our attention to (possibly cyclic) DL terminologies, where ontological axioms are limited to definitions of concept names in terms of complex concepts. This restriction still yields a very rich setting. We show that standard reasoning problems, like concept satisfiability and subsumption, are ExpTime-complete for terminologies expressed in ALCI under the stable model semantics.

Recently, Equilibrium Description Logics (EDLs) have been suggested as a promising new approach to Description Logics (DLs) with non-monotonic default negation. However, a deeper understanding of EDLs in terms of computational complexity and relations to other formalisms is still missing. Motivated by this, in this paper we investigate the computational complexity of reasoning in EDLs both in the case of expressive DLs like ALCIO and lightweight DLs in the EL and DL-Lite families. We establish a translation on EDLs into DLs with circumscription, introducing an extension of circumscribed DLs where a further set of axioms is attached to circumscribed KBs to filter out unintended minimal models. Such translation not only applies in the case of classical circumscription but can be extended to the recently introduced pointwise circumscribed DLs. We introduce pointwise EDLs where the single global minimality check on models is replaced by local minimality checks at the single domain elements in the style of pointwise circumscription. We provide preliminary results on the computational complexity of reasoning in pointwise EDLs. In particular, via the translation into pointwise circumscription, we inherit the decidability results of pointwise circumscribed DLs. Furthermore, we show that for a large class of acyclic ontologies EDLs and pointwise EDLs accept the same set of stable models. To this aim, we identify a class of ontologies where circumscription and pointwise circumscription accept the same set of minimal models, providing new decidability results for circumscribed DLs even in the presence of minimized and fixed roles.

Circumscription is one of the most powerful ways to extend Description Logics (DLs) with non-monotonic reasoning features, albeit with huge computational costs and undecidability in many cases. In this paper, we introduce pointwise circumscription for DLs, which is not only intuitive in terms of knowledge representation, but also provides a sound approximation of classic circumscription and has reduced computational complexity. Our main idea is to replace the second-order quantification step of classic circumscription with a series of (pointwise) local checks on all domain elements and their immediate neighbourhood. Our main positive results are for ontologies in DLs ALCIO and ALCI: we prove that for TBoxes of modal depth 1 (i.e. without nesting of existential or universal quantifiers) standard reasoning problems under pointwise circumscription are (co)NExpTime-complete and ExpTime-complete, respectively. The restriction of modal depth still yields a large class of ontologies useful in practice, and it is further justified by a strong undecidability result for pointwise circumscription with general TBoxes in ALCIO.