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.

Preview

Text 2006.04167.pdf - Submitted Version Download (611kB) | Preview

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:	30 Nov 2020 09:21
URI:	https://repository.londonmet.ac.uk/id/eprint/6021

Downloads

Actions (login required)

View Item