{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T17:01:19Z","timestamp":1762102879616},"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":[[2020,7]]},"abstract":"<jats:p>We study the relative expressiveness of ontology-mediated queries (OMQs) formulated in the expressive Description Logic ALCHOIF extended with closed predicates. In particular, we present a polynomial-time translation from OMQs into Datalog with negation under the stable model semantics, the formalism that underlies Answer Set Programming. This is a novel and non-trivial result: the considered OMQs are not only non-monotonic but also feature a tricky combination of nominals, inverse roles, and role functionality. We start with atomic queries and then lift our approach to a large class of first-order queries where quantification is \u201cguarded\u201d by closed predicates. Our translation is based on a characterization of the query answering problem via integer programming, and a specially crafted program in Datalog with negation that finds solutions to dynamically generated systems of integer inequalities. As an important by-product of our translation, we get that the query answering problem is co-NP-complete in data complexity for the considered class of OMQs. Thus, answering these OMQs in the presence of closed predicates is not harder than answering them in the standard setting. This is not obvious as closed predicates are known to increase data complexity for some existing ontology languages.<\/jats:p>","DOI":"10.24963\/kr.2020\/44","type":"proceedings-article","created":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T04:39:16Z","timestamp":1597898356000},"page":"434-444","source":"Crossref","is-referenced-by-count":0,"title":["Datalog Rewritability and Data Complexity of ALCHOIF with Closed Predicates"],"prefix":"10.24963","author":[{"given":"Tomasz","family":"Gogacz","sequence":"first","affiliation":[{"name":"University of Warsaw"}]},{"given":"Sanja","family":"Lukumbuzya","sequence":"additional","affiliation":[{"name":"TU Wien"}]},{"given":"Magdalena","family":"Ortiz","sequence":"additional","affiliation":[{"name":"TU Wien"}]},{"given":"Mantas","family":"\u0160imkus","sequence":"additional","affiliation":[{"name":"TU Wien"}]}],"member":"10584","event":{"number":"17","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Association for Logic Programming","Center for Perspicuous Computing","European Association for Artificial Intelligence","Ontopic - The Virtual Knowledge Graph Company"],"acronym":"KR-2020","name":"17th International Conference on Principles of Knowledge Representation and Reasoning {KR-2020}","start":{"date-parts":[[2020,9,12]]},"theme":"Artificial Intelligence","location":"Rhodes, Greece","end":{"date-parts":[[2020,9,18]]}},"container-title":["Proceedings of the Seventeenth International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T21:18:39Z","timestamp":1604611119000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2020\/44"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2020,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2020\/44","relation":{},"subject":[],"published":{"date-parts":[[2020,7]]}}}