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

摘要

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.