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

arXiv: https://arxiv.org/abs/2011.09314 · HTML: https://mlsanity.com/paper/2011.09314/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2020.

## Built on by (most cited first, 1 of 1)

- [Query Rewriting with Disjunctive Existential Rules and Mappings](https://mlsanity.com/paper/2306.05973/) (2023)

## Abstract (arXiv)

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.