Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

DL − Lite and Role Inclusions

Roman KontchakovContact Information and Michael ZakharyaschevContact Information

(3)  School of Computer Science and Information Systems, Birkbeck College London, UK
Abstract
We give a classification of the complexity of DL-Lite logics extended with role inclusion axioms. We show that the data complexity of instance checking becomes P-hard in the presence of functionality constraints, and coNP-hard if arbitrary number restrictions are allowed, even with primitive concept inclusions. The combined complexity of satisfiability in this case jumps to ExpTime. On the other side, the combined complexity for the logics without number restrictions depends only on the form of concept inclusions and can range from NLogSpace and P to NP; the data complexity for such logics stays in LogSpace.

Contact Information Roman Kontchakov

URL: http://www.dcs.bbk.ac.uk/~roman

Contact Information Michael Zakharyaschev

URL: http://www.dcs.bbk.ac.uk/~michael
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.110 • Server: mpweb17
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)