Publications de l'Institut Mathématique, Nouvelle SérieVol. 95[109], pp. 133–147 (2014)
|
|
Publications de l'Institut Mathématique, Nouvelle Série Vol. 95[109], pp. 133–147 (2014) |
|
|
ON THE COMPLEXITY OF (RESTRICTED) $\mathcal{ALCI}r$Milenko Mosurovic, Michael ZakharyaschevFaculty of Mathematics and Natural Science, University of Montenegro, Podgorica, Montenegro and Department of Computer Science and Information Systems, Birkbeck, University of London, U.K.,Abstract: We consider a new description logic $\mathcal{ALCI}r$ that extends $\mathcal{ALCI}$ with role inclusion axioms of the form $R \sqsubseteq Q R_1 \dots R_m$ satisfying a certain regularity condition. We prove that concept satisfiability with respect to RBoxes in this logic is \ExpTime-hard. We then define a restriction $\mathcal{ALCI}r^-$ of $\mathcal{ALCI}r$ and show that concept satisfiability with respect to RBoxes in $\mathcal{ALCI}r^-$ is \PSpace-complete. Classification (MSC2000): 68T27, 03B70, 68T30, 68W40, 68Q25 Full text of the article: (for faster download, first choose a mirror)
Electronic fulltext finalized on: 31 Mar 2014. This page was last modified: 2 Apr 2014.
© 2014 Mathematical Institute of the Serbian Academy of Science and Arts
|