Tractable Responsibility Measures for Ontology-Mediated Query Answering

Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade · 2025

Read Tractable Responsibility Measures for Ontology-Mediated Query Answering by Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-23191.txt.

Description

When a database plus background knowledge answers a question, responsibility scores say how much each fact contributed. Meghyn Bienvenu, Diego Figueira and Pierre Lafourcade study how hard those scores are to compute in this knowledge-backed setting. They focus on new Shapley-inspired scores, built as weighted sums over the smallest fact sets that still yield the answer. Building on database results, they show the scores stay computable in reasonable time for queries rewritable as simple database queries.

The picture flips when the knowledge can express reachability. In the harder combined view, the problem is already intractable for simple questions when the language allows joining facts. The same holds for unions of well-behaved joined questions, even without any background knowledge. On the bright side, for common lightweight languages they carve out neatly structured question classes where the scores stay efficiently computable.

Catalog record

CREATORMeghyn Bienvenu, Diego Figueira, Pierre Lafourcade
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-23191

Browse the full library · About the Tower of Babel