Regular Path Queries in Expressive Description Logics with Nominals

Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI 2009). 2009.

Reasoning over complex queries in the DLs underlying OWL 2 is of importance in several application domains. We provide decidability and (tight) upper bounds for the problem of checking entailment and containment of positive regular path queries under various combinations of constructs used in such expressive DLs; specifically: regular expressions and (safe) Booleans over roles, and allowing for the combination of any two constructs among inverse roles, qualified number restrictions, and nominals. Our results carry over also to the DLs of the SR family, and thus have a direct impact on OWL 2.

@inproceedings{IJCAI-2009,
   title = "Regular Path Queries in Expressive Description Logics with
Nominals",
   year = "2009",
   author = "Diego Calvanese and Thomas Eiter and Magdalena Ortiz",
   booktitle = "Proc. of the 21st Int. Joint Conf. on Artificial Intelligence
(IJCAI 2009)",
   pages = "714--720",
}