ON THE COMPLEXITY OF (RESTRICTED) $\mathcal{ALCI}r$


Milenko Mosurović, Michael Zakharyaschev




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.