Role Conjunctions in Expressive Description Logics
Birte Glimm and Yevgeny Kazakov
Abstract
We show that adding role conjunctions to the Description Logics (DLs) SHI and SHOIF causes a jump in the computational complexity of the standard reasoning tasks from ExpTime-complete to 2ExpTime-complete and from NExpTime-complete to N2ExpTime-hard respectively. We further show that this increase is due to a subtle interaction between inverse roles, role hierarchies, and role transitivity in the presence of role conjunctions and that for the DL SHQ a jump in the computational complexity cannot be observed.
Details
| Book Title |
LPAR |
| ISBN |
978−3−540−89438−4 |
| Pages |
391−405 |
| Publisher |
Springer |
| Series |
Lecture Notes in Computer Science |
| Volume |
5330 |
| Year |
2008 |
Links
Related pages
|
People |
|
|
Activities |