pith. machine review for the scientific record. sign in

arxiv: 2605.01341 · v1 · submitted 2026-05-02 · 💻 cs.LO · cs.AI

Recognition: unknown

ABox Abduction for Inconsistent Knowledge Bases under Repair Semantics

Anselm Haak , Patrick Koopmann , Yasir Mahmood , Anni-Yasmin Turhan
Authors on Pith no claims yet

Pith reviewed 2026-05-09 18:25 UTC · model grok-4.3

classification 💻 cs.LO cs.AI
keywords ABox abductionrepair semanticsinconsistent knowledge basesDL-LiteEL_botdescription logicscomputational complexity
0
0 comments X

The pith

ABox abduction for inconsistent knowledge bases admits defined notions and full complexity classifications under repair semantics in DL-Lite and EL_bot.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines suitable notions of ABox abduction when a knowledge base is inconsistent due to erroneous data, relying on repair semantics to enable meaningful reasoning about what would entail a given fact. It introduces usefulness criteria to steer the search toward hypotheses that support diagnosis, explainability, and repair tasks. The authors then analyze multiple variants of the abduction problem and deliver a complete complexity landscape for the lightweight description logics DL-Lite and EL_bot. A reader would care because inconsistent data is common in practice, and these results clarify when efficient methods exist for generating useful explanations or repairs.

Core claim

By applying established repair semantics to inconsistent knowledge bases, ABox abduction problems become well-defined, usefulness criteria can guide hypothesis selection for practical applications, and the computational complexity of the resulting problems can be fully classified across variants for DL-Lite and EL_bot.

What carries the argument

ABox abduction operators under repair semantics, equipped with usefulness criteria for hypotheses, that operate on inconsistent knowledge bases in lightweight description logics.

If this is right

  • Some abduction variants remain tractable while others become NP-hard or higher under the chosen repair semantics.
  • The complexity results directly determine which variants can be used in time-critical diagnosis or repair tools.
  • Useful hypotheses can be computed without first restoring full consistency to the knowledge base.
  • Different repair semantics yield different complexity trade-offs that practitioners can select according to their needs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The complexity map could inform the choice of repair semantics in deployed systems that must handle noisy data streams.
  • Similar analyses might be attempted for more expressive description logics to identify the boundary where problems become undecidable.
  • Empirical testing on real inconsistent datasets could reveal whether the usefulness criteria produce explanations that domain experts accept.

Load-bearing premise

The selected repair semantics and usefulness criteria for hypotheses match the requirements of diagnosis, explainability, and repair applications.

What would settle it

An algorithm that solves an ABox abduction variant in polynomial time when the paper classifies it as NP-hard under one of the repair semantics for DL-Lite.

read the original abstract

Given a knowledge base (KB) with a non-entailed fact, the ABox abduction problem asks for possible extensions of the KB that would entail this fact. This problem has many applications, ranging from diagnosis to explainability and repair. ABox abduction has been well-investigated for consistent KBs and classical semantics, but little is known for the case of inconsistent KBs, which can be caused by erroneous data. In this paper we define suitable notions of abduction in this setting and propose criteria that guide abduction towards "useful" hypotheses. To regain meaningful reasoning in the presence of inconsistencies, we use well-established repair semantics. We provide a comprehensive landscape of the complexity of ABox abduction under repair semantics, treating different variants of the abduction problem for the light-weight description logics DL-Lite and EL_bot.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript defines notions of ABox abduction for inconsistent knowledge bases under repair semantics, introduces usefulness criteria for hypotheses, and provides a complexity landscape for multiple variants of the abduction problem in the lightweight description logics DL-Lite and EL_bot.

Significance. If the stated complexity results hold, the work fills a notable gap by extending abduction to inconsistent KBs, which is directly relevant to diagnosis, explainability, and repair tasks. The focus on DL-Lite and EL_bot together with standard complexity reductions is appropriate and yields a useful classification; the explicit proposal of usefulness criteria is a constructive addition.

minor comments (2)
  1. [Abstract] The abstract would be strengthened by briefly naming the concrete variants of the abduction problem (e.g., minimal vs. useful hypotheses) that receive complexity results.
  2. [Introduction] An early illustrative example showing an inconsistent KB, a repair, and a resulting hypothesis would improve readability before the formal definitions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, the recognition that our work fills a gap in extending ABox abduction to inconsistent knowledge bases, and the recommendation to accept the manuscript. The focus on DL-Lite and EL_bot with repair semantics and usefulness criteria is indeed central to the contribution.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper first defines suitable notions of ABox abduction for inconsistent KBs under repair semantics and proposes usefulness criteria for hypotheses. It then derives a complexity classification for variants of the problem in DL-Lite and EL_bot. These results are obtained via standard complexity-theoretic reductions and algorithms applied to the newly defined problems. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the central claims rest on independent reductions from known problems rather than on any internal renaming or ansatz smuggled from prior author work. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard semantics of DL-Lite and EL_bot plus the definition of repair semantics taken from prior literature; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Repair semantics restore consistency by minimal changes to the ABox
    Invoked to regain meaningful reasoning when the KB is inconsistent
  • standard math Standard entailment and consistency notions for DL-Lite and EL_bot
    Background for defining abduction variants

pith-pipeline@v0.9.0 · 5442 in / 1082 out tokens · 30621 ms · 2026-05-09T18:25:06.203168+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 12 canonical work pages

  1. [1]

    1 Christian Alrabbaa, Stefan Borgwardt, Tom Friese, Anke Hirsch, Nina Knieriemen, Patrick Koopmann, Alisa Kovtunova, Antonio Krüger, Alexej Popovic, and Ida S. R. Siahaan. Explaining reasoning results for OWL ontologies with Evee. In Pierre Marquis, Magdalena Ortiz, and Maurice Pagnucco, editors, Proceedings of the 21st International Conference on Princip...

    2024

  2. [2]

    2 Franz Baader, Ian Horrocks, Carsten Lutz, and Ulrike Sattler.An Introduction to Description Logic

    URL: https://doi.org/10.24963/kr.2024/67, doi:10.24963/KR.2024/67. 2 Franz Baader, Ian Horrocks, Carsten Lutz, and Ulrike Sattler.An Introduction to Description Logic. Cambridge University Press,

    work page doi:10.24963/kr.2024/67 2024

  3. [3]

    Optimal ABox repair w.r.t

    3 Franz Baader, Patrick Koopmann, Francesco Kriegel, and Adrian Nuradiansyah. Optimal ABox repair w.r.t. staticEL TBoxes: From quantified ABoxes back to ABoxes. InThe Semantic Web – 19th International Conference, ESWC 2022, volume 13261 ofLecture Notes in Computer Science, pages 130–146. Springer,

    2022

  4. [4]

    Inconsistency-tolerant querying of description logic knowledge bases

    4 Meghyn Bienvenu and Camille Bourgaux. Inconsistency-tolerant querying of description logic knowledge bases. InReasoning Web: Logical Foundation of Knowledge Graph Construction and Query Answering — 12th International Summer School 2016, volume 9885 ofLecture Notes in Computer Science, pages 156–202. Springer, 2016.doi:10.1007/978-3-319-49493-7\_5. 5 Meg...

    work page doi:10.1007/978-3-319-49493-7 2016

  5. [5]

    Abductive reasoning in a paraconsistent framework

    6 Meghyn Bienvenu, Katsumi Inoue, and Daniil Kozhemiachenko. Abductive reasoning in a paraconsistent framework. In Pierre Marquis, Magdalena Ortiz, and Maurice Pagnucco, editors,Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, KR 2024,

    2024

  6. [6]

    Abductive Reasoning in a Paraconsistent Framework

    URL: https://doi.org/10.24963/kr.2024/13,doi:10.24963/KR.2024/13. 7 Meghyn Bienvenu and Quentin Maniere. Data complexity of querying description logic knowledge bases under cost-based semantics. InProceedings of the Annual AAAI Conference on Artificial Intelligence, Singapore, Singapore,

    work page doi:10.24963/kr.2024/13 2024

  7. [7]

    URL: https://hal.science/hal-05360907

    AAAI Press. URL: https://hal.science/hal-05360907. 8 Meghyn Bienvenu and Riccardo Rosati. Tractable approximations of consistent query answering for robust ontology-based data access. In Francesca Rossi, editor,IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pages 775–781. IJ...

    2013

  8. [8]

    Explanations for negative query answers under existential rules

    10 ˙Ismail ˙Ilkan Ceylan, Thomas Lukasiewicz, Enrico Malizia, Cristian Molinaro, and Andrius Vaicenavicius. Explanations for negative query answers under existential rules. InProceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, pages 223–232. AAAI Press,

    2020

  9. [9]

    11 Jianfeng Du, Hai Wan, and Huaguan Ma

    URL: https://doi.org/10.24963/kr.2020/23. 11 Jianfeng Du, Hai Wan, and Huaguan Ma. Practical TBox abduction based on justification patterns. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pages 1100–1106,

    work page doi:10.24963/kr.2020/23 2020

  10. [10]

    URL: https://doi.org/10.1609/aaai.v29i1

    work page doi:10.1609/aaai.v29i1

  11. [11]

    14 Fajar Haifani, Patrick Koopmann, Sophie Tourret, and Christoph Weidenbach

    URL: http://ceur-ws.org/V ol-216/submission_25.pdf. 14 Fajar Haifani, Patrick Koopmann, Sophie Tourret, and Christoph Weidenbach. Connection-minimal abduction inEL via translation to FOL. InProceedings of the 11th International Joint Conference on Automated Reasoning IJCAR 2022, volume 13385 ofLecture Notes in Computer Science, pages 188–207. Springer,

    2022

  12. [12]

    15 Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva

    URL: https://doi.org/10.1007/978-3-031-10769-6_12. 15 Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva. Abduction-based explanations for machine learning models. InProceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1511–1519,

    work page doi:10.1007/978-3-031-10769-6_12

  13. [13]

    Signature-based abduction with fresh individuals and complex concepts for description logics

    17 Patrick Koopmann. Signature-based abduction with fresh individuals and complex concepts for description logics. InProceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pages 1929–1935. ijcai.org,

    1929

  14. [14]

    18 Patrick Koopmann, Warren Del-Pinto, Sophie Tourret, and Renate A

    URL: https://doi.org/10.24963/ijcai.2021/266. 18 Patrick Koopmann, Warren Del-Pinto, Sophie Tourret, and Renate A. Schmidt. Signature-based abduction for expressive description logics. InProceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, pages 592–602. AAAI Press,

    work page doi:10.24963/ijcai.2021/266 2021

  15. [15]

    19 Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo

    URL: https://doi.org/10.24963/kr.2020/59. 19 Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Inconsistency-tolerant query answering in ontology-based data access.J. Web Semant., 33:3–29,

    work page doi:10.24963/kr.2020/59 2020

  16. [16]

    20 Paolo Liberatore

    doi:10.1016/J.WEBSEM.2015.04.002. 20 Paolo Liberatore. Redundancy in logic I: CNF propositional formulae.Artif. Intell., 163(2):203–232,

    work page doi:10.1016/j.websem.2015.04.002 2015

  17. [17]

    21 Thomas Lukasiewicz, Enrico Malizia, and Cristian Molinaro

    URL: https://doi.org/10.1016/j.artint.2004.11.002,doi:10.1016/J.ARTINT.2004.11.002. 21 Thomas Lukasiewicz, Enrico Malizia, and Cristian Molinaro. Explanations for negative query answers under inconsistency-tolerant semantics. InProceedings of the Thirty-First International Joint Confer- ence on Artificial Intelligence, IJCAI-22, pages 2705–2711. ijcai.org,

    work page doi:10.1016/j.artint.2004.11.002 2004

  18. [18]

    2022/168

    doi:10.24963/IJCAI. 2022/375. 22 Frederick Maier, Yue Ma, and Pascal Hitzler. Paraconsistent OWL and related logics.Semantic Web, 4(4):395–427, 2013.doi:10.3233/SW-2012-0066. 23CS Peirce. Deduction, induction and hypothesis: Popular science monthly, v

    work page doi:10.24963/ijcai 2022

  19. [19]

    On the complexity of dealing with inconsistency in description logic ontologies

    25 Riccardo Rosati. On the complexity of dealing with inconsistency in description logic ontologies. In Toby Walsh, editor,IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artifi- cial Intelligence, pages 1057–1062. IJCAI/AAAI,

    2011

  20. [20]

    26 Stefan Schlobach and Ronald Cornet

    doi:10.5591/978-1-57735-516-8/ IJCAI11-181. 26 Stefan Schlobach and Ronald Cornet. Non-standard reasoning services for the debugging of description logic terminologies. InProceedings of the Eighteenth International Joint Conference on Artificial Intelligence 2003, pages 355–362. Morgan Kaufmann,

    work page doi:10.5591/978-1-57735-516-8/ 2003