EMIS ELibM Electronic Journals Publications de l'Institut Mathématique, Nouvelle Série
Vol. 95[109], pp. 133–147 (2014)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home


Pick a mirror



Milenko Mosurovic, Michael Zakharyaschev

Faculty 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
© 2014 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition