{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:37:38Z","timestamp":1723016258638},"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":"Aiming to understand the data complexity of answering conjunctive queries mediated by an axiom stating that a class is covered by the union of two other classes, we show that deciding their first-order rewritability is PSPACE-hard and obtain a number of sufficient conditions for membership in AC0, L, NL, and P. Our main result is a complete syntactic AC0\/NL\/P\/CONP tetrachotomy of path queries under the assumption that the covering classes are disjoint.<\/jats:p>","DOI":"10.24963\/kr.2020\/41","type":"proceedings-article","created":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T04:39:16Z","timestamp":1597898356000},"page":"403-413","source":"Crossref","is-referenced-by-count":1,"title":["A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom"],"prefix":"10.24963","author":[{"given":"Olga","family":"Gerasimova","sequence":"first","affiliation":[{"name":"National Research University Higher School of Economics, Moscow, Russia"}]},{"given":"Stanislav","family":"Kikot","sequence":"additional","affiliation":[{"name":"School of Computing and Digital Media, London Metropolitan University, U.K."}]},{"given":"Agi","family":"Kurucz","sequence":"additional","affiliation":[{"name":"Department of Informatics, King\u2019s College London, U.K."}]},{"given":"Vladimir","family":"Podolskii","sequence":"additional","affiliation":[{"name":"Steklov Mathematical Institute, Moscow, Russia"},{"name":"National Research University Higher School of Economics, Moscow, Russia"}]},{"given":"Michael","family":"Zakharyaschev","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Birkbeck, University of London, U.K."}]}],"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:38Z","timestamp":1604611118000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2020\/41"}},"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\/41","relation":{},"subject":[],"published":{"date-parts":[[2020,7]]}}}