KR2022Proceedings of the 19th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning

Haifa, Israel. July 31–August 5, 2022.

Edited by
  1. Gabriele Kern-Isberner
  2. Gerhard Lakemeyer
  3. Thomas Meyer

ISSN: 2334-1033
ISBN: 978-1-956792-01-0

Sponsored by
Published by

Copyright © 2022 International Joint Conferences on Artificial Intelligence Organization

Finite Entailment of UCRPQs over ALC Ontologies

  1. Víctor Gutiérrez-Basulto(Cardiff University, UK)
  2. Albert Gutowski(University of Warsaw, Poland)
  3. Yazmín Ibáñez-García(Cardiff University, UK)
  4. Filip Murlak(University of Warsaw, Poland)
PDF
BibTeX
https://doi.org/10.24963/kr.2022/19

Keywords

  1. Description logics
  2. Ontology-based data access, integration, and exchange
  3. Applications of KR in databases

Abstract

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 union 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 entailment of UCRPQs. At the core of our decision procedure, there is a novel automata-based technique introducing a stratification of interpretations induced by the deterministic finite automaton underlying the input UCRPQ.