Review Comment:
The article proposes methods for computing abductive explanations for single observations and for multiple observations, respectively, in ABox abduction with arbitrary description logics. The basic idea for computing an abductive explanation for a given observation is that, an abduction explanation can be computed from a hitting set of the collection of all ABox encoding models of the union of the ontology (TBox+ABox) and the given observation by negating every assertion in the hitting set. Based on this idea, the article proposes a hitting set tree algorithm for computing abductive explanations with bounded cardinality for single observations. To handle multiple observations, the article also proposes two methods, where one (the reductionbased method) is based on a reduction to a problem about a single observation, the other (the combinationbased method) is based on combining abductive explanations for respective single observations. Some experiments on three small ontologies were conducted to show the running statistics for computing single observations and to show the comparison results about the two methods for multiple observations.
In general, the originality is partially good, but the significance of the results and the quality of writing need to be improved much. More details about these statements are shown below.
Originality:
(1) The basis idea for handling single observations based on hitting set trees is new compared with related work, though it has been unofficially published in the DL 2016 workshop.
(2) The algorithm for computing abductive explanations with bounded cardinality for single observations is new, but more justifications for its technical advantages need to be provided. See more details in the following review comments on significance.
(3) The combinationbased method for handling multiple observations is rather straightforward and has only been mentioned without details nor empirical evaluation in previous work on ABox abduction. The article provides empirical results on this method.
(4) The reductionbased method for handling multiple observations is new compared with related work, but more justifications for its technical advantages need to be provided. See more details in the following review comments on significance.
Significance of the results:
(1) The basis idea for handling single observations based on hitting set trees works for arbitrary description logics that have corresponding reasoners. However, the feasibility of a method implementing this idea is only partially demonstrated by three small ontologies (one having <300 axioms and the other two having <50 axioms). The feasibility needs to be further clarified by larger ontologies, such as those ones with up to millions of axioms created by the LUBM generator, which have been used in experiments conducted by related work [7,8].
(2) The computation of abductive explanations with bounded cardinality is a special problem setting different from traditional ones. It is unclear what this setting results in with respective to the computational complexity. In particular, it is unclear whether this setting results in intractability for tractable description logics. According to Figure 1, the execution time for computing all abductive explanations with cardinality<=5 is already extremely long (>1,000,000s) for LUBM with only 46 axioms. This result actually means that the proposed algorithm (Algorithm 1) is not practical or even infeasible for large ontologies. According to Table 3, which shows that the algorithm only computes 20 abductive explanations in more than 1,000,000 seconds, I conjecture that the proposed algorithm has much room to improve its efficiency and scalability. As a word, the proposed algorithm or even the proposed problem setting may not be sufficiently reasonable, especially in term of scaling to large ontologies.
(3) An empirical comparison study on the two methods for handling multiple observations is provided in the article. The comparison results show that the new reductionbased method is not necessary more efficient than the straightforward combinationbased method. This raises a question about the advantages of the proposed reductionbased method. In fact, the reductionbased method increases the expressivity of the observations by introducing nominals. It is unclear whether this reduction increases the computational complexity of the abduction problem for description logics without nominals. More theoretical statements on comparing the two methods are needed to clarify the pros and cons of the two methods.
Quality of writing:
The writing is generally good but still has a number of issues. The main issues are listed below. There are also relatively minor issues on wording, which need to be checked by authors.
(1) Different methods on ABox abduction actually have different problem settings. These differences should be clarified during the discussion of related work.
(2) A_nR_n used in Definition 5 is an abnormal representation for function symbols. A function symbol should be short and has only subscripts at tail.
(3) The function TA(K) declared in the article is nondeterminate. A normal function should be determinate; i.e., it should return a unique result for any input. In this sense, it is inappropriate to declare TA as a function. Instead, we can say that the symbol TA stands for the ABox encoding of something.
(4) In Definition 9, {\neg M M\in\mathcal{M}} represents only one set but not a collection of sets.
(5) In the implementation section (Section 6), the term “loops” is used without definition. Moreover, it is unclear why authors say that forbidding loops significantly reduce the search space.
(6) Table 2 and Table 3 report the statistics other than the parameters.
(7) In many places the execution time is said to be high or low. This wording is wrong as the execution time is often said to be long or short.
