First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries
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.
Cite
Text
Barceló et al. "First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/236Markdown
[Barceló et al. "First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/barcelo2018ijcai-first/) doi:10.24963/IJCAI.2018/236BibTeX
@inproceedings{barcelo2018ijcai-first,
title = {{First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries}},
author = {Barceló, Pablo and Berger, Gerald and Lutz, Carsten and Pieris, Andreas},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {1707-1713},
doi = {10.24963/IJCAI.2018/236},
url = {https://mlanthology.org/ijcai/2018/barcelo2018ijcai-first/}
}