KR2020Proceedings of the 17th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning

Rhodes, Greece. September 12-18, 2020.

Edited by
  1. Diego Calvanese
  2. Esra Erdem
  3. Michael Thielscher

ISSN: 2334-1033
ISBN: 978-0-9992411-7-2

Sponsored by
Published by

Copyright © 2020 International Joint Conferences on Artificial Intelligence Organization

On Finite Entailment of Non-Local Queries in Description Logics

  1. Tomasz Gogacz(University of Warsaw)
  2. Víctor Gutiérrez-Basulto(Cardiff University)
  3. Albert Gutowski(University of Warsaw)
  4. Yazmín Ibáñez-García(Cardiff University)
  5. Filip Murlak(University of Warsaw)
PDF
BibTeX
DOI 10.24963/kr.2020/43

Keywords

  1. Description logics-General
  2. Ontology-based data access, integration, and exchange-General

Abstract

We study the problem of finite entailment of ontology-mediated queries. Going beyond local queries, we allow transitive closure over roles. We focus on ontologies formulated in the description logics ALCOI and ALCOQ, extended with transitive closure. For both logics, we show 2EXPTIME upper bounds for finite entailment of unions of conjunctive queries with transitive closure. We also provide a matching lower bound by showing that finite entailment of conjunctive queries with transitive closure in ALC is 2EXPTIME-hard