Geodesic
On the Complexity of (Restricted) $\mathcal{ALCI}r$
Publications de l'Institut Mathématique, _N_S_95 (2014) no. 109, p. 133

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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 : 68T27 03B70 68T30 68W40 68Q25 
@article{PIM_2014_N_S_95_109_a9,
     author = {Milenko Mosurovi\'c and Michael Zakharyaschev},
     title = {On the {Complexity} of {(Restricted)} $\mathcal{ALCI}r$},
     journal = {Publications de l'Institut Math\'ematique},
     pages = {133 },
     publisher = {mathdoc},
     volume = {_N_S_95},
     number = {109},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PIM_2014_N_S_95_109_a9/}
}
TY  - JOUR
AU  - Milenko Mosurović
AU  - Michael Zakharyaschev
TI  - On the Complexity of (Restricted) $\mathcal{ALCI}r$
JO  - Publications de l'Institut Mathématique
PY  - 2014
SP  - 133 
VL  - _N_S_95
IS  - 109
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PIM_2014_N_S_95_109_a9/
LA  - en
ID  - PIM_2014_N_S_95_109_a9
ER  - 
%0 Journal Article
%A Milenko Mosurović
%A Michael Zakharyaschev
%T On the Complexity of (Restricted) $\mathcal{ALCI}r$
%J Publications de l'Institut Mathématique
%D 2014
%P 133 
%V _N_S_95
%N 109
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PIM_2014_N_S_95_109_a9/
%G en
%F PIM_2014_N_S_95_109_a9
Milenko Mosurović; Michael Zakharyaschev. On the Complexity of (Restricted) $\mathcal{ALCI}r$. Publications de l'Institut Mathématique, _N_S_95 (2014) no. 109, p. 133 . http://geodesic.mathdoc.fr/item/PIM_2014_N_S_95_109_a9/