In abduction, we are given a KB as background knowledge, in combination with a set of facts (the observation) that cannot be deduced from the background knowledge. We are then looking for the missing piece in the background knowledge (the hypothesis) that is needed to make the observation logically entailed [12]. This form of reasoning has many applications: 1) it can be used to explain why something cannot be deduced [6,7], to supplement services explaining positive entailments such as justi cations [22,4,15] and proofs [1,2], 2) it can be used for diagnosis tasks, giving the hypothesis as possible explanation for an unexpected observation [19], and 3) it can be used in KB repair to give hints on how to x missing entailments [23]. There is a variety of research on abduction with description logics. Based on the shape of the hypothesis, one distinguishes between concept abduction [5], TBox abduction [10,23], ABox abduction [8,7,21,20,6,11,9,14,16] and KB abduction [18,12]. We focus on a variant called signature-based ABox abduction de ned as follows, where by at ABox, we refer to an ABox that does not use complex concepts. De nition 1. Let L be a DL, and denote for an ABox A by sig(A) the concept and role names in A, and by size(A) its size. An L abduction problem is then given by a triple A = hK; ; i with K an L KB of background knowledge, an L ABox called the observation, and NC [ NR a signature of abducibles; and asks whether there exists a hypothesis for A, i.e. an L ABox H satisfying If we require H additionally to be at, we speak of a at abduction problem. A size-restricted ( at) L abduction problem is a tuple A = hK; ; ; ni s.t. A0 = hK; ; i is a ( at) L abduction problem and n is a number encoded in binary. A hypothesis for A is then an L ABox H which is a hypothesis for A0 and additionally satis es size(H) n.
A1. K [ H 6j= ?;
A2. K [ H j= ; and
A3. sig(H)
As a simpli ed application example from the geology domain, assume we have observed that in an area near a canal, holes appeared in the street as a result of subsidence due to an unstable ground. A possible explanation could ? This work was supported by the DFG in grant 389792660 as part of TRR 248.
Copyright ' 2021 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
involve the presence of a formation of so-called evaporite below the street, which
dissolves when in contact with water [
H = f
EvaFor(e); abov(e; str); bord(e; can); 8lin:?(can) g stating that there is an evaporite formation e below the street that borders with the canal, and that the canal has no lining. Note that this hypothesis uses a fresh individual name e, as well as a complex concept 8lin:?. The aim of is to restrict to hypotheses that have explanatory character. In the present example, we would for instance also exclude a and Dis from , as the dissolution alone would be a too shallow explanation.
Works on signature-based ABox abduction often restrict hypotheses to at
ABoxes with a given set of individuals [
at ABox abduction problem is ExpTime-complete for E L?, coNExpTimecomplete for ALC and ALCI, and undecidable for ALCF . 3. For E L?, admitting complex concepts is only interesting if we additionally forbid fresh individuals in the hypothesis. Then, they can become double exponential in size, while their existence can still be decided in ExpTime. 4. The most challenging problem turned out to be the case of general ABox abduction in more expressive DLs. For ALC, we found a tight bound on the size of hypotheses which is triple exponential in the input. For deciding their existence, we showed an N2ExpTimeNP upper bound. 5. Finally, the size-bounded abduction problem is NP-complete for E L, it is
NExpTimeNP-complete for the at variant in ALC, and in 2ExpTime for
This is an extended abstract of a paper accepted at IJCAI 2021 [