Connection-Minimal Abduction in ℰℒ via Translation to FOL Extended Abstract Fajar Haifani1,2 , Patrick Koopmann3 , Sophie Tourret4,1 and Christoph Weidenbach1 1 Max-Planck-Institut für Informatik, Saarland Informatics Campus, 66123 Saarbrücken, Germany 2 Graduate School of Computer Science, 66123 Saarbrücken, Germany 3 Institute of Theoretical Computer Science, Technische Universität Dresden, 01062 Dresden, Germany 4 Université de Lorraine, CNRS, Inria, LORIA, Nancy, France Abduction is about finding extensions to a knowledge base that are sufficient to imply a given entailment. Specifically, in the context of description logics (DPs), we consider an ontology 𝒪 of background knowledge, an axiom 𝛼 s.t. 𝒪 ̸|= 𝛼 (called the observation), and we want to compute a suitable set ℋ of axioms called hypothesis such that 𝒪 ∪ ℋ |= 𝛼 [1]. Abduction as a reasoning problem has a long history [2] and has several applications: for example, it can be used to explain missing entailments of an ontology [3, 4, 5], to repair incomplete knowledge bases [6], and to provide possible explanations for unexpected observations [7]. We consider the special case of TBox abduction in the lightweight description logic ℰℒ, where the observation is an ℰℒ concept inclusion 𝐶1 ⊑ 𝐶2 and the background knowledge is an ℰℒ TBox 𝒯 . To avoid useless answers, abduction problems usually come with further restrictions on the solution space and/or minimality criteria that help sort the chaff from the grain. We argue that existing minimality notions suffer from certain limitations, and introduce connection minimality as a new notion that overcomes the limitations of earlier notions. Furthermore, we developed and evaluated a method to compute connection-minimal solutions in practice. Our criterion follows Occam’s razor by rejecting hypotheses that use concept inclusions unrelated to the problem at hand. To illustrate, consider the following TBox about relationships in academia: 𝒯a = { ∃employment.ResearchPosition ⊓ ∃qualification.Diploma ⊑ Researcher, ∃writes.ResearchPaper ⊑ Researcher, Doctor ⊑ ∃qualification.PhD, Professor ≡ Doctor ⊓ ∃employment.Chair, FundsProvider ⊑ ∃writes.GrantApplication }. The observation 𝛼a = Professor ⊑ Researcher does not follow from 𝒯a although it should. If we are only interested in subset minimal solutions, possible hypotheses to create the desired DL 2022: 35th International Workshop on Description Logics, August 7–10, 2022, Haifa, Israel $ fajar.haifani@mpi-inf.mpg.de (F. Haifani); patrick.koopmann@tu-dresden.de (P. Koopmann); sophie.tourret@inria.fr (S. Tourret); christoph.weidenbach@mpi-inf.mpg.de (C. Weidenbach)  0000-0001-5139-4503 (F. Haifani); 0000-0001-5999-2583 (P. Koopmann); 0000-0002-6070-796X (S. Tourret); 0000-0001-6002-0458 (C. Weidenbach) © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) entailment include the following ℋ1 = {PhD ⊑ Diploma, Chair ⊑ ResearchPosition} ℋ2 = {Doctor ⊑ FundsProvider, GrantApplication ⊑ ResearchPaper}. We argue that ℋ1 is preferable over ℋ2 , because ℋ2 is less linked to the observation. Indeed, for any two concepts 𝐷1 and 𝐷2 such that 𝒯a entails 𝐷1 ⊑ ∃writes.𝐷2 , a hypothesis {Doctor ⊑ 𝐷1 , 𝐷2 ⊑ ResearchPaper} could be created (consider for instance that 𝒯a additionally entails Poet ⊑ ∃writes.Poetry), since neither 𝐷1 nor 𝐷2 need to be connected to either Professor or Researcher. Our new minimality notion discards ℋ2 , and favors ℋ1 as connection-minimal. Intuitively, for an observation 𝐶1 ⊑ 𝐶2 , connection minimality only accepts those hypotheses which ensure that every CI in the hypothesis is connected to both 𝐶1 and 𝐶2 in 𝒯 . The definition of connection minimality is based on the following ideas: 1 Hypotheses for the abduction problem have to create a connection between 𝐶1 and 𝐶2 , in the form of a concept 𝐷 that satisfies 𝒯 ∪ ℋ |= 𝐶1 ⊑ 𝐷, 𝐷 ⊑ 𝐶2 . 2 To ensure that Occam’s razor is followed, we want this connection to be based on concepts 𝐷1 and 𝐷2 for which we already have 𝒯 |= 𝐶1 ⊑ 𝐷1 , 𝐷2 ⊑ 𝐶2 . 3 We additionally want to make sure that the connecting concepts are not more complex than necessary, and that ℋ only contains CIs that directly connect parts of 𝐷2 to parts of 𝐷1 by closely following their structure. We call 𝐷 a connecting concept: A concept 𝐷 connects 𝐶1 to 𝐶2 in 𝒯 if and only if 𝒯 |= 𝐶1 ⊑ 𝐷 and 𝒯 |= 𝐷 ⊑ 𝐶2 . Note that if 𝒯 |= 𝐶1 ⊑ 𝐶2 then both 𝐶1 and 𝐶2 are connecting concepts from 𝐶1 to 𝐶2 , and if 𝒯 ̸|= 𝐶1 ⊑ 𝐶2 , it means no concept connects them. In the above example, we would use 𝒯a |= 𝐶1 ⊑ 𝐷1 and 𝒯a |= 𝐷2 ⊑ 𝐶2 where 𝐷1 = ∃qualification.PhD ⊓ ∃employment.Chair 𝐷2 = ∃qualification.Diploma ⊓ ∃employment.ResearchPosition ⊓ Researcher from which we construct the hypothesis ℋ1 by linking the fillers of the existential restrictions. In the full paper, we define the connection between 𝐷1 and 𝐷2 formally using a relaxed notion of homomorphism between the description trees of 𝐷2 and 𝐷1 . We show that this notion of minimality is deeply connected with the generation of prime-implicates in first-order logic [8]. That is, using a translation scheme from abduction problems to first-order clauses, we are able to reconstruct the connection-minimal hypotheses using the prime implicates of the translation. In addition to soundness and completeness, we show a quadratic bound on the depth of the terms occurring in the prime implicates, which gives us a termination condition for our method, and ensures completeness for hypotheses that are both connection-minimal and subset-minimal. We implemented a prototype of our method consisting of two components: a Java component that takes care of preprocessing, translation into first-order logic, and construction of the hypotheses from prime implicates, and a first-order reasoning component that uses a modified version of the theorem prover SPASS [9] for the prime implicate generation. The prototype was evaluated on a set of ontologies from the medical domain for which we generated abduction problems in different ways, show-casing the practicality of our approach. The full paper has been accepted at IJCAR 2022 [10]. Acknowledgments: This work was supported by the Deutsche Forschungsgemeinschaft (DFG), Grant 389792660 within TRR 248. References [1] 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. [2] C. S. Peirce, Deduction, induction, and hypothesis, Popular science monthly 13 (1878) 470–482. [3] P. Koopmann, Two ways of explaining negative entailments in description logics using abduction, in: Informal Proceedings of the 2nd Workshop on Explainable Logic-Based Knowledge Representation (XLoKR-2021) co-located with the 18th international Confer- ence on Principles of Knowledge Representation and Reasoning (KR-2021), 2021. [4] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavicius, Explanations for negative query answers under existential rules, in: D. Calvanese, E. Erdem, M. Thielscher (Eds.), Proceedings of KR 2020, AAAI Press, 2020, pp. 223–232. URL: https://doi.org/10. 24963/kr.2020/23. doi:10.24963/kr.2020/23. [5] 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. [6] 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. [7] 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.), Advances and Trends in Artificial Intelligence. From Theory to Practice, Springer International Publishing, Cham, 2019, pp. 376–388. [8] P. Marquis, Extending abduction from propositional to first-order logic, in: P. Jorrand, J. Kelemen (Eds.), Fundamentals of Artificial Intelligence Research, International Workshop FAIR ’91, Smolenice, Czechoslovakia, September 8-13, 1991, Proceedings, volume 535 of Lecture Notes in Computer Science, Springer, 1991, pp. 141–155. URL: https://doi.org/10. 1007/3-540-54507-7_12. doi:10.1007/3-540-54507-7\_12. [9] C. Weidenbach, R. A. Schmidt, T. Hillenbrand, R. Rusev, D. Topic, System description: Spass Version 3.0, in: F. Pfenning (Ed.), Automated Deduction - CADE-21, 21st International Conference on Automated Deduction, Bremen, Germany, July 17-20, 2007, Proceedings, volume 4603 of Lecture Notes in Computer Science, Springer, 2007, pp. 514–520. URL: https: //doi.org/10.1007/978-3-540-73595-3_38. doi:10.1007/978-3-540-73595-3\_38. [10] F. Haifani, P. Koopmann, S. Tourret, C. Weidenbach, Connection-minimal abduction in ℰℒ via translation to fol, in: Proceedings of IJCAR 2022, Lecture Notes in Computer Science, Springer, 2022. To appear.