A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom

Gerasimova, Olga, Kikot, Stanislav, Kurucz, Agi, Podolskii, Vladimir and Zakharyaschev, Michael (2020) A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom. Technical Report. International Joint Conferences on Artificial Intelligence Organization.

[img]
Preview
Text
2006.04167.pdf - Submitted Version

Download (611kB) | Preview
Official URL: https://arxiv.org/abs/2006.04167

Abstract / Description

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.

Item Type: Monograph (Technical Report)
Additional Information: ** From Crossref via Jisc Publications Router
Uncontrolled Keywords: artificial Intelligence (cs.AI); ontology-based data access; description logic; first-order rewritability; data complexity
Subjects: 000 Computer science, information & general works
Department: School of Computing and Digital Media
SWORD Depositor: Pub Router
Depositing User: Pub Router
Date Deposited: 11 Sep 2020 13:48
Last Modified: 11 Sep 2020 13:48
URI: http://repository.londonmet.ac.uk/id/eprint/6021

Downloads

Downloads per month over past year



Downloads each year

Actions (login required)

View Item View Item