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.
infoannote | LPAR 2008, To appear |
year | 2008 |
links
BibTeX
Download (pdf)
related pages
|
