Edinburgh Research Explorer

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

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

Related Edinburgh Organisations

Open Access permissions

Open

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
Pages1707-1713
Number of pages7
ISBN (Electronic)978-0-9992411-2-7
DOIs
Publication statusPublished - 2018

Abstract

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.

ID: 74615575