Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics
Meghyn Bienvenu, Quentin Manière · 2025
Read Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics by Meghyn Bienvenu, Quentin Manière (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-2511-07095.txt.
Description
Meghyn Bienvenu and Quentin Manière analyze the computational cost of answering questions over inconsistent knowledge bases written in description logics. Under cost-based semantics, each interpretation is charged for the weighted axioms and assertions it violates, and certain or possible answers are read off from interpretations of optimal or bounded cost. Earlier work covered only logics between two modest classes, leaving prominent DL-Lite dialects unexamined.
Extending the analysis to logics with inverse roles and role inclusions, the authors sharpen several lower bounds and pin down the precise complexity of certain answers under optimal cost. No nontrivial upper bound was known there before. Surprisingly, for one DL-Lite family with a fixed cost bound, instance-query certain answers and conjunctive-query possible answers admit first-order rewriting, the lowest possible data complexity, against the intractability found elsewhere.
Catalog record
| CREATOR | Meghyn Bienvenu, Quentin Manière |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-07095