Towards More Useful Description Logics of Time, Change and Context

Abstract

Description Logics (DLs) are a family of logic-based formalisms for the representation of and reasoning about knowledge. Classical DLs are fragments of first-order logic and therefore aim at capturing static knowledge. Alas, the lack of means of DLs to capture dynamic aspects of knowledge has been often criticized because many important DL applications depend on this kind of knowledge. As a reaction to this shortcoming of DLs, two-dimensional extensions of DLs with capabilities to represent and reason about dynamic knowledge were introduced. We further, in this thesis, the understanding and utility of two-dimensional DLs. We particularly focus on identifying two-dimensional DLs providing the right expressive power to model more accurately temporal and contextual aspects of knowledge required by certain DL applications, or providing better computational properties than other possible alternatives. We pursue three lines of research: we study branching-time temporal DLs that emerge from the combination of classical DLs with the classical temporal logics CTL* and CTL; we study description logics of change that emerge from the combination of classical DLs with the modal logic S5; we study description logics of context that emerge from the combination of classical DLs with multi-modal logics. We investigate temporal and contextual DLs based on the classical DL ALC and on members of the EL-family of DLs. Our main technical contributions are algorithms for satisfiability and subsumption, and (mostly) tight complexity bounds.