• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

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

P. 403-413.
Gerasimova O., Kikot S., Kurucz A., Podolskii V. V., Zakharyaschev M.

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.

В книге

Под науч. редакцией: D. Calvanese, M. Thielscher, E. Erdem. The International Joint Conference on Artificial Intelligence (IJCAI), 2020.