{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:50:35Z","timestamp":1762102235243},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.24963\/ijcai.2018\/236","type":"proceedings-article","created":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T05:49:10Z","timestamp":1530769750000},"page":"1707-1713","source":"Crossref","is-referenced-by-count":5,"title":["First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries"],"prefix":"10.24963","author":[{"given":"Pablo","family":"Barcel\u00f3","sequence":"first","affiliation":[{"name":"Millennium Institute for Foundational Research on Data"},{"name":"DCC, University of Chile"}]},{"given":"Gerald","family":"Berger","sequence":"additional","affiliation":[{"name":"Institute of Logic and Computation, TU Wien"}]},{"given":"Carsten","family":"Lutz","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Bremen"}]},{"given":"Andreas","family":"Pieris","sequence":"additional","affiliation":[{"name":"School of Informatics, University of Edinburgh"}]}],"member":"10584","event":{"number":"27","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2018","name":"Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}","start":{"date-parts":[[2018,7,13]]},"theme":"Artificial Intelligence","location":"Stockholm, Sweden","end":{"date-parts":[[2018,7,19]]}},"container-title":["Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T05:51:11Z","timestamp":1530769871000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2018\/236"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2018\/236","relation":{},"subject":[],"published":{"date-parts":[[2018,7]]}}}