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

A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom

  1. Olga Gerasimova(National Research University Higher School of Economics, Moscow, Russia)
  2. Stanislav Kikot(School of Computing and Digital Media, London Metropolitan University, U.K.)
  3. Agi Kurucz(Department of Informatics, King’s College London, U.K.)
  4. Vladimir Podolskii(Steklov Mathematical Institute, Moscow, Russia, National Research University Higher School of Economics, Moscow, Russia)
  5. Michael Zakharyaschev(Department of Computer Science, Birkbeck, University of London, U.K.)
PDF
BibTeX
https://doi.org/10.24963/kr.2020/41

Keywords

  1. Computational aspects of knowledge representation-General
  2. Description logics-General
  3. Ontology-based data access, integration, and exchange-General

Abstract

Aiming to understand the data complexity of answering conjunctive queries mediated by an axiom stating that a class is covered by the union of two other classes, we show that deciding their first-order rewritability is PSPACE-hard and obtain a number of sufficient conditions for membership in AC0, L, NL, and P. Our main result is a complete syntactic AC0/NL/P/CONP tetrachotomy of path queries under the assumption that the covering classes are disjoint.