Description Logics (DLs) are well-known formalisms for reasoning about information in a given domain. DLs have many advantages such as being decidable fragments of First-Order Logic, and having a clear semantics and well-de ned reasoning procedures which can be automated [7, 2]. Take the classic penguin example, and consider a knowledge base containing the statements: \penguins are birds", \robins are birds", \penguins do not y", \birds y" and \birds have wings".We can use the well-de ned syntax and semantics of DLs to de ne entailment which allows us to derive implicit knowledge that can be made explicit through inferences [2]. For example using the information above we can query the knowledge base, ask \do robins have wings", and the answer would be YES. DLs employ various reasoning services such as concept satis ability, subsumption, consistency checking and instance checking which can be used to derive useful implicit information from knowledge bases. Reductions between reasoning services also enable only one reasoning procedure to be implemented which alleviates the need of creating tools to perform each and every reasoning service [9, 10]. Various reasoning techniques/algorithms have been developed to solve some of the reasoning problems highlighted above. The most widely used technique, the tableau-based approach, have been shown to be e cient in practice for real knowledge bases [2]. The DLs services mentioned above can be more useful by adding explanations to the conclusions that DLs systems can draw. Using the example above, the answer to our query \do robins have wings" was YES. However, it is more bene cial to users if the DL system can also provide an explanation of how it came to the conclusion. In this example an explanation to the query is that \we know that robins are birds, and birds have wings, therefore we can conclude that robins have wings". Explanation facilities are useful in understanding entailments, debugging and repairing information declared in knowledge bases and also knowledge base comprehension. In our example above our knowledge base is very small with only ve statements. In reality knowledge bases can contain ten of thousand of statements and without automated support for explanation, it can be di cult to identify the statements that give rise to entailments [3, 6]. There are various algorithms to compute justi cations, and implementations of these algorithms for the DL case are available through the ontology editor Protege [6]. Classical DLs cannot deal with exceptional cases. For this reason, there have been numerous proposals to de ne non-monotonic reasoning systems. One such approach is the KLM approach to defeasible reasoning, which was originally
V Chama, T Meyer
de ned for propositional logic, but has been lifted to the case for DLs [
The rational closure algorithm performs reasoning by rst constructing a
ranking where every defeasible condition has a rank [
Let us extend the example above to the defeasible case. Suppose the knowledge base contains the following the statements: \penguins are birds", \robins are birds", \penguins do not y", \birds typically y" and \birds typically have wings".
When we query this knowledge base and ask \do penguins typically have wings", the answer to the query using rational closure is NO. The reason the system returns NO is not as straightforward as one might think. Initially, a user might use the same arguments that were used in our initial version of our example but that justi cation leads to errors. Thus, it is useful if defeasible reasoning is extended to include explanations.
In this work, we combine explanations with defeasible reasoning. Generally, when you look at classical DLs, the explanations can be derived from using DL reasoning services. But here we need to take defeasibility into account, and the way in which the explanations are obtained are more complex because we have to consider the ranking of statements.
For instance, in order to obtain the explanation to the query \do penguins typically have wings", we rst look at all justi cations that support the answer YES. The statements \penguins are birds" and \birds typically have wings" can be used to justify the answer. However, according to the information in our knowledge base we know that penguins can not y thus the logical consequence of this is that there are no penguins since the existence of penguins will cause a con ict. As a result using rational closure, the statements \birds typically y" and \birds typically have wings" are discarded meaning we can no longer use them in our justi cation, thus giving the explanation of why the answer to the query is NO.
Generally from an algorithmic perspective what is happening is if the answer
to a query is YES, look at all the minimal sets which include only the statements
required for the entailment to hold. Then check for the ones that occur as part of
the ranked statements. That will be the real explanation. However, note that an
entailment can have more than one justi cation and other justi cations can be
used to build up the explanation. If the answer is NO, then check to see if there
are any minimal subsets that entail the negation [