{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T07:00:00Z","timestamp":1762326000513,"version":"build-2065373602"},"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":[[2025,11]]},"abstract":"<jats:p>Recent work on quantitative approaches to explaining query\n\nanswers employs responsibility measures to assign scores to\n\nfacts in order to quantify their respective contributions\n\nto obtaining a given answer. In this paper, we study the\n\ncomplexity of computing such responsibility scores in the\n\nsetting of ontology-mediated query answering, focusing on a\n\nvery recently introduced family of Shapley-value-based\n\nresponsibility measures defined in terms of weighted sums\n\nof minimal supports (WSMS). By exploiting results from the\n\ndatabase setting, we can show that such measures enjoy\n\npolynomial data complexity for classes of ontology-mediated\n\nqueries that are first-order-rewritable, whereas the\n\nproblem becomes #P-hard when the ontology language can\n\nencode reachability queries (via axioms like \u2203R.A \u2291 A). To\n\nbetter understand the tractability frontier, we next\n\nexplore the combined complexity of WSMS computation. We\n\nprove that intractability applies already to atomic queries\n\nif the ontology language supports conjunction, as well as\n\nto unions of \u2018well-behaved\u2019 conjunctive queries, even in\n\nthe absence of an ontology. By contrast, our study yields\n\npositive results for common DL-Lite dialects: by means of\n\ncareful analysis, we identify classes of structurally\n\nrestricted conjunctive queries (which intuitively disallow\n\nundesirable interactions between query atoms) that admit\n\ntractable WSMS computation.<\/jats:p>","DOI":"10.24963\/kr.2025\/16","type":"proceedings-article","created":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:10:44Z","timestamp":1762323044000},"page":"154-163","source":"Crossref","is-referenced-by-count":0,"title":["Tractable Responsibility Measures for Ontology-Mediated Query Answering"],"prefix":"10.24963","author":[{"given":"Meghyn","family":"Bienvenu","sequence":"first","affiliation":[{"name":"Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800"}]},{"given":"Diego","family":"Figueira","sequence":"additional","affiliation":[{"name":"Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800"}]},{"given":"Pierre","family":"Lafourcade","sequence":"additional","affiliation":[{"name":"Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800"}]}],"member":"10584","event":{"name":"22nd International Conference on Principles of Knowledge Representation and Reasoning {KR-2025}","theme":"Artificial Intelligence","location":"Melbourne, Australia","acronym":"KR-2025","number":"22","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Academic College of Tel-Aviv","European Association for Artificial Intelligence","National Science Foundation"],"start":{"date-parts":[[2025,11,11]]},"end":{"date-parts":[[2025,11,17]]}},"container-title":["Proceedings of the TwentySecond International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:10:57Z","timestamp":1762323057000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2025\/16"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2025,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2025\/16","relation":{},"subject":[],"published":{"date-parts":[[2025,11]]}}}