|
Abstract:
|
The results of this thesis are connected with papers of Wolter and Zakharyashchev in which various expressive and decidable description logics with epistemic, temporal, and dynamic operators are constructed, but the complexity of the satisfaction problem in these logics has remained unclear. The thesis consists of seven chapters. Chapter 1 and 5 contain the notions and properties which are used in other chapters. In Chapter 2 a fragment of the logic DIF, which is called D_1IF , is considered and new constructions and proofs for that logic are given. In Chapter 3 a fragment of the logic DIO, which is called D_1IO, is studied. In Chapter 4 by using the results from Chapter 2 and Chapter 3 NEXPTIME algorithm, which tests whether a structure simple quasi-world or not, is constructed and it is used in Chapter 7. In Chapters 6 and 7 it is shown that the modal description logics of Wolter and Zakharyashchev based on arbitrary frames are NEXPTIME-complete, no matter whether the underlying description logic is ALC, CI or C_1IQ. Moreover, it is shown that these logics based on S5-frames (for knowledge), and KD45-frames (for beliefs) are also NEXPTIME-complete. Finally, the following property is shown: the description logics of Wolter and Zakharyashchev based on N-frames (for time) are EXPSPACE-complete, no matter whether the underlying description logic is ALC_U, CI_U or C_1IQ_U. |