Non-monotonic Description Logics Based on Predicate Minimization

Abstract

Description Logics (DLs) are a family of formalisms, often seen as decidable fragments of first-order logic, tailored for representing and reasoning about knowledge pertaining to a domain of interest. Over the past decades, their increasing adoption as the underlying formalism for, e.g., the Semantic Web and medical ontologies has drawn attention to the challenge of reconciling the open-world assumption, which underlies the classical, monotonic semantics of DLs, and the closed-world assumption that characterizes many non-monotonic formalisms. This has motivated extensive research into formalisms that extend DLs with non-monotonic capabilities. Among these approaches, a prominent one is that of circumscribed DLs, i.e., DLs with the semantics of McCarthy’s circumscription. At its core, circumscription is based on predicate minimization, selecting from the models of a first-order theory only those in which the extension of certain predicates is minimal. Adding non-monotonic capabilities to DLs is challenging, as the delicate balance between expressiveness and computational cost is readily compromised, and circumscription is no exception. In this thesis, we investigate various non-monotonic semantics for DLs based on predicate minimization and closely related to circumscription, with the aim of providing useful formalisms for knowledge representation and reasoning. Through a fine-grained analysis of different modes of predicate minimization, we enhance the current understanding of its impact in several DLs and refine the boundaries of decidability, most notably in the setting where all predicates are minimized. We begin by providing complexity bounds for circumscribed DLs. We show that the pure case in which allpredicates are minimized easily leads to undecidability and role minimization is a key source of computational difficulty, even in basic settings. In contrast, we provide decidability results under the assumption that none of the roles are minimized. Aiming at regaining decidability while preserving the expressiveness of circumscription, we introduce pointwise circumscribed DLs, based on a restricted form of predicate minimization. We present decidability results for pointwise circumscribed fragments that are otherwise undecidable under full circumscription. By identifing a large class of ontologies in which pointwise circumscription and circumscription coincide, we show that decidability can be regained in circumscribed DLs if natural acyclicity conditions are imposed, similar to those imposed in medical ontologies, e.g., SnomedCT.We present Equilibrium Description Logics (EDLs), i.e. DLs with the stable model semantics of Quantified Equilibrium Logic, and provide complexity results for EDLs. Similarly to circumscription, EDLs suffer the negative consequences of role minimization. To mitigate the complexity, we take inspiration from pointwise circumscription and introduce pointwise EDLs. We establish a translation from (pointwise) EDLs into (pointwise) circumscription, inheriting decidability results from pointwise circumscribed DLs. Finally, we exploit the stable model semantics of EDLs in the context of DL terminologies, finite collections of possibly recursive concept definitions. We show that the semantics of EDLs overcomes the limitations of previously proposed semantics and does not exhibit any increase in the computational costs compared to reasoning under the classical semantics.