pith. sign in

arxiv: 2606.19197 · v2 · pith:AMT2ILF6new · submitted 2026-06-17 · 💻 cs.LO · cs.AI

The More the Merrier: Combining Properties for ABox Abduction under Repair Semantics in ELbot

Anselm Haak , Patrick Koopmann , Yasir Mahmood , Anni-Yasmin Turhan This is my paper

Pith reviewed 2026-06-26 18:56 UTC · model grok-4.3

classification 💻 cs.LO cs.AI
keywords abductionrepair semanticsEL_botABoxcomplexitydescription logicsbrave semanticsAR semantics
0
0 comments X

The pith

Requiring multiple properties on ABox abduction hypotheses in EL_bot does not increase complexity under repair semantics.

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

The paper studies ABox abduction under repair semantics in the description logic EL_bot, focusing on hypotheses that must satisfy several properties at once, such as signature restrictions combined with minimality in size or introduced conflicts. It also examines cases that add optimality criteria to these properties. The key finding is that the computational complexity for finding such combined hypotheses often stays the same as for single properties, under both brave and AR semantics. A reader would care because this means more constrained and application-relevant hypotheses can be generated without paying a higher computational price.

Core claim

For ABox abduction under repair semantics in EL_bot, the complexity of computing hypotheses that satisfy multiple properties or combine properties with optimality criteria remains unchanged from the single-property cases, for both brave and AR semantics.

What carries the argument

Repair semantics for ABox abduction, which enforces that hypotheses satisfy chosen combinations of properties such as signature-restrictions and minimality while restoring the missing entailment.

If this is right

  • Hypotheses meeting several criteria can be found with the same complexity as those meeting one criterion.
  • Both brave and AR repair semantics allow multiple properties without added cost.
  • Applications can select among more refined hypotheses without changing the underlying decision procedures.

Where Pith is reading between the lines

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

  • The same transfer might hold when further properties are added beyond those studied here.
  • If the transfer relies on the structure of EL_bot, similar results could be tested in nearby logics with repair semantics.

Load-bearing premise

Complexity results proven for single properties transfer directly to the setting where multiple properties are required simultaneously.

What would settle it

An explicit reduction proving that at least one specific combination of properties raises the complexity class beyond what holds for its individual components.

Figures

Figures reproduced from arXiv: 2606.19197 by Anni-Yasmin Turhan, Anselm Haak, Patrick Koopmann, Yasir Mahmood.

Figure 1
Figure 1. Figure 1: Complexity results for Existence (Left) and Verification (Right) problem under combination of properties. Each node contains a property and its complexity for brave (red) and AR (blue) semantics, highlighting our earlier results [17]. The edges represent the complexity when combining properties at the two end points, depicting our novel contributions. We recently proposed and investigated a range of desira… view at source ↗
read the original abstract

Abduction is a central approach to explain missing entailments from a knowledge base by providing a hypothesis, that would, if added to the knowledge base, make the missing entailment become true. Abduction under repair semantics has recently been investigated in detail, where several desirable properties and optimality criteria were considered, such as signature-restrictions and minimality in size and of introduced conflicts. Naturally, hypotheses that satisfy more than one of these properties or combine a property with an optimality criterion would be even more desirable for applications. So far, such hypotheses have not been investigated in the literature. In the present paper, we consider the ABox abduction problem for hypotheses satisfying more than one property or additional optimality criteria, for EL_bot under brave and AR semantics. Our main observation is that often requiring additional properties for hypotheses does not lead to an increase of complexity.

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

1 major / 2 minor

Summary. The paper studies ABox abduction under repair semantics in EL_bot, focusing on hypotheses that simultaneously satisfy multiple desirable properties (e.g., signature restrictions together with size or conflict minimality) or combine a property with an optimality criterion, under both brave and AR semantics. Its central observation is that imposing additional properties frequently does not raise the complexity of the decision problems beyond the bounds already known for the individual properties.

Significance. If the complexity-transfer claim holds, the result is useful: practitioners can request more constrained (hence more applicable) hypotheses without paying an extra computational price. The work fills a gap by systematically treating combinations that had not been examined before. No machine-checked proofs or reproducible code are mentioned.

major comments (1)
  1. [Complexity analysis sections] Complexity sections (presumably §4–§6): the main observation rests on the claim that single-property complexity bounds carry over verbatim to the multi-property setting. The manuscript cites the prior single-property results but supplies neither fresh hardness reductions for the combined problems nor explicit lemmas showing that the existing reductions remain valid when two or more properties are imposed simultaneously. Because this transfer step is load-bearing for the central claim, the absence of the argument is a major concern.
minor comments (2)
  1. Notation for the combined decision problems is introduced without a compact tabular overview; a single table listing each combination, its semantics, and the inherited complexity class would improve readability.
  2. The abstract states the observation in general terms; the introduction or conclusion should explicitly list the combinations for which the complexity stays the same and those (if any) for which it increases.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive report and for highlighting the need for clearer justification of the complexity-transfer argument. We address the major comment below and commit to revisions that make the reasoning explicit.

read point-by-point responses

  1. Referee: [Complexity analysis sections] Complexity sections (presumably §4–§6): the main observation rests on the claim that single-property complexity bounds carry over verbatim to the multi-property setting. The manuscript cites the prior single-property results but supplies neither fresh hardness reductions for the combined problems nor explicit lemmas showing that the existing reductions remain valid when two or more properties are imposed simultaneously. Because this transfer step is load-bearing for the central claim, the absence of the argument is a major concern.

    Authors: We agree that the transfer argument should be stated more explicitly. The upper-bound arguments in §§4–6 rely on the fact that the additional properties (signature restrictions, size minimality, conflict minimality) are checkable in polynomial time once a candidate hypothesis is generated by the single-property procedure; hence membership in the same complexity class is immediate. For hardness, each reduction constructed in the cited single-property papers already produces hypotheses that satisfy the extra properties under the semantics considered, so the same instances witness hardness for the combined problems. Nevertheless, the manuscript does not isolate these observations as separate lemmas. In the revised version we will insert, for each combination, a short lemma that records (i) why the upper bound carries over and (ii) why the existing hardness instances remain valid, thereby making the transfer step fully explicit. revision: yes

Circularity Check

0 steps flagged

Complexity transfer from single- to multi-property abduction relies on prior results treated as external

full rationale

The paper's central observation—that imposing multiple properties or optimality criteria on hypotheses does not increase complexity—is stated directly in the abstract and motivated by reference to 'recently investigated' single-property cases under repair semantics. No equations, fitted parameters, or self-definitional reductions appear in the provided text. The transfer of complexity bounds is presented as an observation rather than derived via new hardness proofs within this manuscript; prior single-property results are treated as independent external input. This constitutes at most a minor self-citation dependency that is not load-bearing for any definitional or predictive step inside the paper itself. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard description-logic semantics and prior complexity results for single-property abduction; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard ELbot semantics and repair-semantics definitions from prior literature
    Invoked implicitly when stating complexity results for brave and AR semantics.

pith-pipeline@v0.9.1-grok · 5688 in / 1035 out tokens · 17966 ms · 2026-06-26T18:56:41.144721+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

22 extracted references · 11 canonical work pages

  1. [1]

    Schlobach, R

    S. Schlobach, R. Cornet, Non-standard reasoning services for the debugging of description logic terminologies, in: Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence 2003, Morgan Kaufmann, 2003, pp. 355–362

    2003

  2. [2]

    Alrabbaa, S

    C. Alrabbaa, S. Borgwardt, T. Friese, A. Hirsch, N. Knieriemen, P. Koopmann, A. Kovtunova, A. Krüger, A. Popovic, I. S. R. Siahaan, Explaining reasoning results for OWL ontologies with Evee, in: P. Marquis, M. Ortiz, M. Pagnucco (Eds.), Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, KR 2024, Hanoi...

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

  3. [3]

    Koopmann, Explaining reasoning results for description logic ontologies (invited paper), in: A

    P. Koopmann, Explaining reasoning results for description logic ontologies (invited paper), in: A. Artale, M. Bienvenu, Y. Ibáñez-García, F. Murlak (Eds.), Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools, RW 2024, Bucharest, Romania, September 19-22, 2024 / RW 2025, Istanbul, Turkey, September 25-28, 2025, OASIcs, Schloss Dagstuhl - Le...

    work page doi:10.4230/oasics.rw.2024/2025.6 2024

  4. [4]

    Bienvenu, C

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

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

  5. [5]

    Bienvenu, C

    M. Bienvenu, C. Bourgaux, F. Goasdoué, Computing and explaining query answers over inconsis- tent DL-Lite knowledge bases, Journal of Artificial Intelligence Research 64 (2019) 563–644

    2019

  6. [6]

    2021/205

    T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for negative query answers under inconsistency-tolerant semantics, in: Proceedings of the Thirty-First International Joint Confer- ence on Artificial Intelligence, IJCAI-22, ijcai.org, 2022, pp. 2705–2711. doi: 10.24963/IJCAI. 2022/375

    work page doi:10.24963/ijcai 2022

  7. [7]

    Elsenbroich, O

    C. Elsenbroich, O. Kutz, U. Sattler, A case for abductive reasoning over ontologies, in: Proceedings of the OWLED’06 Workshop on OWL: Experiences and Directions, 2006. URL: http://ceur-ws.org/ Vol-216/submission_25.pdf

    2006

  8. [8]

    Klarman, U

    S. Klarman, U. Endriss, S. Schlobach, ABox abduction in the description logic 𝒜ℒ𝒞, Journal of Automated Reasoning 46 (2011) 43–80

    2011

  9. [9]

    Calvanese, M

    D. Calvanese, M. Ortiz, M. Simkus, G. Stefanoni, Reasoning about explanations for negative query answers in DL-Lite, J. Artif. Intell. Res. 48 (2013) 635–669. URL: https://doi.org/10.1613/jair.3870. doi:10.1613/jair.3870

    work page doi:10.1613/jair.3870 2013

  10. [10]

    J. Du, K. Wang, Y. Shen, Towards tractable and practical ABox abduction over inconsistent description logic ontologies, in: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, 2015, pp. 1489–1495. URL: https://doi.org/10.1609/aaai.v29i1.9393

    work page doi:10.1609/aaai.v29i1.9393 2015

  11. [11]

    İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavicius, Explanations for negative query answers under existential rules, in: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, AAAI Press, 2020, pp. 223–232. URL: https://doi.org/10.24963/kr.2020/23

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

  12. [12]

    P. Koopmann, Signature-based abduction with fresh individuals and complex concepts for de- scription logics, in: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, ijcai.org, 2021, pp. 1929–1935. URL: https://doi.org/10.24963/ijcai.2021/266

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

  13. [13]

    Obeid, Z

    M. Obeid, Z. Obeid, A. Moubaiddin, N. Obeid, Using description logic and ABox abduction to capture medical diagnosis, in: F. Wotawa, G. Friedrich, I. Pill, R. Koitz-Hristov, M. Ali (Eds.), From Theory to Practice — 32nd International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2019, Lecture Notes in...

    work page doi:10.1007/978-3-030-22999-3_33 2019

  14. [14]

    Wei-Kleiner, Z

    F. Wei-Kleiner, Z. Dragisic, P. Lambrix, Abduction framework for repairing incomplete ℰℒ ontologies: Complexity results and algorithms, in: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AAAI Press, 2014, pp. 1120–1127. URL: http://www.aaai.org/ ocs/index.php/AAAI/AAAI14/paper/view/8239

    2014

  15. [15]

    J. Du, H. Wan, H. Ma, Practical TBox abduction based on justification patterns, in: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017, pp. 1100–1106. URL: http: //aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14402

    2017

  16. [16]

    Haifani, P

    F. Haifani, P. Koopmann, S. Tourret, C. Weidenbach, Connection-minimal abduction in ℰℒ via translation to FOL, in: J. Blanchette, L. Kovács, D. Pattinson (Eds.), Proceedings of the 11th International Joint Conference on Automated Reasoning IJCAR 2022, volume 13385 ofLecture Notes in Computer Science, Springer, 2022, pp. 188–207. URL: https://doi.org/10.10...

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

  17. [17]

    A. Haak, P. Koopmann, Y. Mahmood, A.-Y. Turhan, Abox abduction for inconsistent knowledge bases under repair semantics, in: R. Wassermann, M.-L. Mugnier, F. Baader (Eds.), Proceedings of KR 2026, 2026. To appear

    2026

  18. [18]

    Baader, I

    F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduction to Description Logic, Cambridge University Press, 2017

    2017

  19. [19]

    Pippenger, Theories of computability, Cambridge University Press, 1997

    N. Pippenger, Theories of computability, Cambridge University Press, 1997

    1997

  20. [20]

    Bienvenu, R

    M. Bienvenu, R. Rosati, Tractable approximations of consistent query answering for robust ontology-based data access, in: F. Rossi (Ed.), IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, IJCAI/AAAI, 2013, pp. 775–781. URL: http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/...

    2013

  21. [21]

    Lembo, M

    D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant query answering in ontology-based data access, J. Web Semant. 33 (2015) 3–29. doi:10.1016/J.WEBSEM.2015.04. 002

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

  22. [22]

    𝐵1(𝑎)∈ ℛ

    Technical Appendix For constructions referenced in the main paper, we provide full proofs of the corresponding results here. The following example from our previous paper [17] will be useful in some of our reductions (e.g., when translating𝛴-restriction to conflict-confinement). Example 21.Let𝒦=⟨𝒯,𝒜⟩, where 𝒯={𝐴⊓𝐵⊑ ⊥, 𝐵⊓𝐶⊑ ⊥, 𝐶⊓𝐷⊑𝐴},and 𝒜={𝐵(𝑎), 𝐶(𝑎)}, an...