Research map / Learning theory and algorithms / Combinatorial and search optimization
Knowledge-Base Degrees of Inconsistency: Complexity and Counting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Bound the knowledge-program graph treewidth and domain size | Fixed-domain non-entailment for Datalog queries · SROIQ or DLmin knowledge-bases | runtime: tower(2, |∆|O(k)) · |N(K) ∪ NP(P)| | Helped |
| Count projected anti-witnesses instead of all anti-witnesses | Fixed-domain non-entailment · Stratified, tight, normal, and disjunctive queries | counting complexity: one jump in the complexities | Hurt |
| Allow more expressive Datalog query classes | Fixed-domain non-entailment · Stratified, tight or normal, and disjunctive queries | decision complexity: ΣP2; ΣP3; ΣP4 | Hurt |
Closest papers by meaning
- Spectra of Cardinality Queries over Description Logic Knowledge Bases (AAAI 2025 · similarity 0.87)
- Consistent Query Answering over Existential Rules with Open and Closed Predicates (AAAI 2025 · similarity 0.87)
- Stable Model Semantics for Description Logic Terminologies (AAAI 2024 · similarity 0.86)
- A Variable Occurrence-Centric Framework for Inconsistency Handling (AAAI 2025 · similarity 0.85)
- Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases (AAAI 2025 · similarity 0.85)
- LogicCat: A Chain-of-Thought Text-to-SQL Benchmark for Complex Reasoning (AAAI 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.