On the Complexity of Description Logics with Modal Operators

eBibliothek Repositorium

 
 

On the Complexity of Description Logics with Modal Operators

Zur Kurzanzeige

dc.contributor.advisor Mijajlović, Žarko; Zakharyashchev, Michael
dc.contributor.author Mosurović, Milenko en_US
dc.date.accessioned 2009-12-03T12:14:27Z
dc.date.available 2009-12-03T12:14:27Z
dc.identifier.uri http://hdl.handle.net/123456789/192
dc.description.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. en
dc.description.provenance Made available in DSpace on 2009-12-03T12:14:27Z (GMT). No. of bitstreams: 1 phdMilenkoMosurovic.pdf: 3024129 bytes, checksum: c7800c50a26fbafa043310d2e0ff6661 (MD5) en
dc.publisher Belgrade en_US
dc.title On the Complexity of Description Logics with Modal Operators en_US
dc.title.alternative Složenost opisnih logika s modalnim operatorima sr
mf.subject.keywords description logics, complexity, modal logics
mf.contributor.committee Došen, Kosta; Vujošević, Slobodan

Dateien zu dieser Ressource

Dateien Größe Format Anzeige
phdMilenkoMosurovic.pdf 3.024Mb PDF Öffnen

Das Dokument erscheint in:

Zur Kurzanzeige