CATS, standing for Comenius Abduction Team Solver, is an ABox abduction solver for description logics that allows the users to choose among multiple abduction algorithms. The solver integrates the JFact reasoner as a black-box, thanks to which it handles expressivity up to ℛℐ (OWL 2). It handles inputs and outputs via OWL API and it ofers a command line, GUI, and API interface. Abduction [1] is a type of hypothetical inference aiming to explain an observation using the background knowledge of the problem domain. We specifically deal with ABox abduction [ 2]: Given a finite set of ABox assertions Abd (hypotheses), a knowledge base and an ABox assertion (observation), an ABox abduction problem is a pair = (, ) and a solution of (explanation) is a finite set of ABox assertions ℰ ⊆ Abd such that ∪ ℰ |= . We also require explanations to have standard properties [2] such as minimality. In our work, can include any concept or role assertion (possibly multiple ones), which may involve even complex concepts and negated roles. To prevent an infinite hypothesis space, Abd consists of only atomic (concept and role) assertions and their complements involving any named individuals from or . In the following example, we define an ABox abduction problem = ( , ) to determine the potential causes of John's toothache.
known to be incomplete [
CATS1 is a freely available software written in Java, using the OWL API [
To solve ABox abduction in a complete way, MHS and the algorithms derived from it require to run
repeated knowledge base consistency checks. Additionally, after each successful consistency check, the
algorithms need to obtain the ABox assertions that are satisfied in a model of the knowledge base to
navigate the search for explanations in the hypothesis space [
While consistency checking is a standard task for any DL reasoner, model extraction is not. Not
all DL reasoners need to construct a model (or its suficient representation) to check knowledge base
consistency. But for instance, tableau-based DL reasoners [
CATS currently uses a modified version of the JFact reasoner 2 [
CATS supports any OWL 2 [17] ontology as the background knowledge of an abduction problem. It currently implements the abduction algorithms listed above. The option to choose from diferent algorithms can be utilised in multiple ways. Firstly, CATS may be used to empirically compare their performance. Secondly, the user can choose an algorithm that is most suitable for their needs, as each algorithm has an advantage over the others in specific situations. For example, when the user wants to obtain any set of explanations quickly, it is best to use MXP. When all explanations are required, diferent algorithms are necessary. MHS-MXP can be very eficient if we limit the hypothesis space to atomic assertions only. If negations are included, it is better to use MHS or HST.
The solver also provides various options for configuring the abduction problem, such as the maximal length of the explanations found, the maximal duration of solving, or limiting what symbols or axioms the explanations can include.
By default, CATS is a command-line application that uses structured text files as its inputs. Let us show an example of CATS’s input using the problem from the introduction:
2https://github.com/boborova3/jfact 3https://owlcs.github.io/owlapi/apidocs_4/org/semanticweb/owlapi/reasoner/knowledgeexploration/ OWLKnowledgeExplorerReasoner.html -f: files/toothache_ontology.owl -o: Prefix: pref: <http://www.semanticweb.org/janbo/ontologies/2024/4/ untitled-ontology-10#> Class: pref:Toothache
Individual: pref:john Types: pref:Toothache -alg: MHS-MXP was processed into toothache_ontology.owl. For readability, is split into three lines, but in a proper input file, it would have to be in one. To compute explanations, MHS-MXP will be used. This example can be run using command java -jar cats.jar <relative path to the input file>. Subsequently, we obtain an output: 1; 1; 0,05; {{DentalTrauma(john)}} 2; 2; 0,05; {{Cavity(john),DrankColdDrink(john)},
{SensitiveTeeth(john),DrankColdDrink(john)}} 0,08 The last output line contains the total running time. Other lines are in the form: <length n>;<number of explanations>;<tree level completion time>; {<found explanations of the length n>}. As we can see, with MHS-MXP, we found all explanations ℰ1–ℰ3 in 0.08 seconds. Because this is a small example, we cannot demonstrate the diferences between the algorithms in time eficiency. We would get the same result using MHS, HST and HST-MXP. The only diference is in MXP, which could not find ℰ3.
CATS can be also used via a graphical interface in the DL Abduction App4 [18], which can be seen in Figure 1. Another way of utilising the solver is by integrating it directly into Java code through the DL Abduction API5 [18]. This library allows developers to work with the solver through abstract interfaces, without the need to know how it functions internally.
Our main future goal is to extend CATS with more well-known abduction algorithms, such as HS-DAG
[
In the future, we would like to conduct a comparative evaluation of the algorithms, taking advantage of
the fact that they all share the same code-base and modular architecture. However, further considerations
are needed in regard to what test cases and methodology to use. Some works [
We were sponsored by the Slovak Republic under the grant no. APVV-19-0220 (ORBIS) and by the EU under the H2020 grant no. 952215 (TAILOR). J. Boborová was supported by a DL student grant. J. Kloc was supported by an extraordinary scholarship awarded by Comenius University in Bratislava, Faculty of Mathematics, Physics and Informatics, and by a DL student grant. [15] E. Sirin, B. Parsia, B. Cuenca Grau, A. Kalyanpur, Y. Katz, Pellet: A practical OWL-DL reasoner,
Journal of Web Semantics 5 (2007) 51–53. [16] F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider (Eds.), The Description
Logic Handbook: Theory, Implementation, and Applications, Cambridge University Press, 2003. [17] B. Cuenca Grau, I. Horrocks, B. Motik, B. Parsia, P. Patel-Schneider, U. Sattler, OWL 2: The next step for OWL, J. Web Semant. 6 (2008) 309–322. [18] J. Kloc, M. Homola, J. Pukancová, DL abduction API v2 and GUI interface (Extended abstract), in: Proceedings of the 36th International Workshop on Description Logics (DL 2023), Rhodes, Greece, September 2–4, 2023, volume 3515 of CEUR-WS, 2023. [19] I. Pill, T. Quaritsch, RC-Tree: A variant avoiding all the redundancy in Reiter’s minimal hitting set algorithm, in: 2015 IEEE International Symposium on Software Reliability Engineering Workshops, ISSRE Workshops, Gaithersburg, MD, USA, November 2-5, 2015, IEEE Computer Society, 2015, pp. 78–84. [20] U. Junker, QuickXplain: Preferred explanations and relaxations for over-constrained problems, in: Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, San Jose, California, US, AAAI Press, 2004, pp. 167–172. [21] J. Du, G. Qi, Y. Shen, J. Z. Pan, Towards practical ABox abduction in large description logic ontologies, Int. J. Semantic Web Inf. Syst. 8 (2012) 1–33.