On the complexity of (restricted) AlCIr
Milenko Mosurović, Michael Zakharyaschev · Publications de l Institut Mathematique · 2014
We consider a new description logic ALCIr that extends ALCI with role inclusion axioms of the form R ? QR1 . . .Rm 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 ALCIr? of ALCIr and show that concept satisfiability with respect to RBoxes in ALCIr? is PSpace-complete.