Finite Entailment of UCRPQs over ALC Ontologies (Extended Abstract)

Víctor Gutiérrez-Basulto; Albert Gutowski; Yazmín Ibáñez-García; Filip Murlak

doi:10.24963/ijcai.2023/717

Finite Entailment of UCRPQs over ALC Ontologies (Extended Abstract)

Víctor Gutiérrez-Basulto, Albert Gutowski, Yazmín Ibáñez-García, Filip Murlak

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence

Sister Conferences Best Papers. Pages 6442-6446. https://doi.org/10.24963/ijcai.2023/717

PDF BibTeX

We investigate the problem of finite entailment of ontology-mediated queries. We consider the expressive query language, unions of conjunctive regular path queries (UCRPQs), extending the well-known class of unions of conjunctive queries, with regular expressions over roles. We look at ontologies formulated using the description logic ALC, and show a tight 2ExpTime upper bound for finite entailment of UCRPQs.

Keywords:

Sister Conferences Best Papers: Knowledge Representation and Reasoning