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.
|
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
Downloads per month over past year
Downloads each year
Actions (login required)
![]() |
View Item |