First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries

Pablo Barceló, Gerald Berger, Carsten Lutz, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We focus on ontology-mediated queries (OMQs) based on (frontier-)guarded existential rules and (unions of) conjunctive queries, and we investigate the problem of FO-rewritability, i.e., whether an OMQ can be rewritten as a first-order query. We adopt two different approaches. The first approach employs standard two-way alternating parity tree automata. Although it does not lead to a tight complexity bound, it provides a transparent solution based on widely known tools. The second approach relies on a sophisticated automata model, known as cost automata. This allows us to show that our problem is 2EXPTIME-complete. In both approaches, we provide semantic characterizations of FO-rewritability that are of independent interest.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018
Subtitle of host publicationJuly 13-19, 2018, Stockholm, Sweden
PublisherInternational Joint Conferences on Artificial Intelligence Organization
Number of pages7
ISBN (Electronic)978-0-9992411-2-7
Publication statusPublished - 2018


Dive into the research topics of 'First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries'. Together they form a unique fingerprint.

Cite this