We extend ALC with preferential role restrictions as concept constructors, and argue that preferential universal restriction represents a defeasible version of standard universal restriction. The resulting DL is more expressive without adding to the complexity of TBox reasoning. We present a tableau system to compute TBox entailment, show that this notion of entailment is not su cient when adding ABoxes, and re ne entailment to deal adequately with ABox reasoning.
Description logics (DLs) have been extended with features to express defeasibility
in a number of ways, one of which is to incorporate preferential reasoning into
the semantics [
Di erent preferential extensions to DLs do not all share the same aim, and
hence also do not share a semantics. One such aim is the representation of
defeasible subsumption statements, which semantically translate to set inclusions
admitting classical counter-examples. The focus there is therefore on defeasible
statements of the form C @ D, read \Cs are usually Ds" or \normally Cs are
Ds", leaving open the option for Cs that are, in a sense, exceptional not to be
instances of D. There are, however, a number of other aspects of defeasibility at
the object level besides that of defeasible subsumption [
Here we make a case for defeasible universal restrictions, in which a concept description of the form 8r:C may be too strong, calling for a weaker version thereof which is defeasible in the sense that it admits classical counter-examples. As an example, consider the concept description Lawyeru8hasClient:PayingClient, intended to capture the class of all private practice lawyers who only handle the cases of paying clients. This concept description may be too strong, calling for a weaker concept description of lawyers who normally defend only paying clients, but who may exceptionally take on pro bono work. This leads to the introduction of defeasible universal restrictions. For example, Lawyer u 8hasClient:PayingClient can be used to describe the class of all lawyers having only paying clients, yet allowing for relatively exceptional role llers to the hasClient role.
Dually, a concept description of the form 9r:C may be too lenient, calling for a strengthening of the existential restriction construct that discounts exceptional role llers. For example, 9hasClient:PayingClient describes the class of individuals having at least one paying client, whereas a description of the class of individuals whose normal clientele includes at least one paying client requires a stricter version of existential restriction, written 9hasClient:PayingClient. This notion can incidentally also be generalized to number restrictions.
In Section 2 we present some background on preferential DL semantics. We then introduce preferential versions of universal and existential role restrictions, and de ne their semantics (Section 3). In Section 4 we present a tableau system for ALC TBox entailment with the added role restrictions. Before concluding we extend our framework for reasoning in the presence of ABoxes (Section 5). 2
Preferential semantics for description logics We assume the reader to be familiar with the description logic ALC, and shall follow standard DL notation. We denote the set of all ALC concepts by L.
In this section we outline the preferential semantics for DLs obtained by
enriching standard DL interpretations with an ordering on the elements in the
domain. The intuition on which this approach is based is simple and natural,
and extends similar work done for the propositional case [
Informally, the semantics is based on the idea that objects of the domain can
be ordered according to their degree of normality [
De nition 1 (Preferential Interpretation). A preferential interpretation is
a structure P = h P ; P ; P i, where h P ; P i is a DL interpretation (which we
denote by IP and refer to as the standard interpretation associated with P),
and P is a strict partial order on P (i.e., P is irre exive and transitive)
that is well-founded.1
1 Observe that well-foundedness is a stricter condition to impose than the smoothness
condition used for modelling defeasible subsumption [
A preferential interpretation P satis es a subsumption statement C v D (denoted P C v D) if and only if CP DP .
Example 1. Let NC = fA; Bg and let NR = f g r . Figure 1 below depicts the preferential interpretation P = h P ; P ; P i, where P = fxi j 1 i 5g, AP = fx1; x2; x3g, BP = fx2; x3; x4g, rP = f(x1; x2), (x2; x3), (x3; x2), (x1; x4), (x4; x5), (x5; x4)g, which is represented by the solid arrows in the picture, and P is the transitive closure of f(x1; x2), (x1; x3), (x2; x4), (x3; x4), (x4; x5)g, i.e., of the relation represented by the dashed arrows in the picture. (Note the direction of the dashed arrows, pointing from more to less preferred objects, with more preferred objects lower in the order.) x5 fg x4 fBg x1 fAg P : fA; Bg x2
x3 fA; Bg
The preferential DL interpretations presented above have been used elsewhere
to de ne a defeasible subsumption relation, and also to de ne preferential and
ranked entailment relations on defeasible DL knowledge bases [
De nition 2. Let P = h P ; P ; P i be a preferential interpretation. Given a role name r and a concept description C, the truth conditions for defeasible universal restriction 8r:C and strict existential restriction 9r:C are given by: (8r:C)P := fx 2 (9r:C)P := fx 2
P j min P rP (x) CP g;
P j min P rP (x) \ CP 6= ;g.
With Le we denote the extension of L obtained by adding 8 and 9 to the concept constructors of ALC. It is easy to see that 8 and 9 are dual in the usual sense.
We say that C 2 Le is preferentially satis able if and only if there is a preferential interpretation P such that CP 6= ;. Preferential satis ability of C with respect to a TBox T is de ned in the usual way. If C; D 2 Le, then satisfaction of subsumption statements of the form C v D is just as before.
we say that T preferentially entails , denoted T j= , if and only if for every preferential interpretation P, P T implies P .
Lemma 1. Let T be a TBox and let C; D 2 Le. T j= C v D if and only if
De nition 3 yields a monotonic entailment relation (in the sense that, if
T j= then we also have that T [ f g j= for any subsumption statement )
with associated Tarskian consequence relation [
Non-monotonicity is often con ated in this way with defeasibility in the AI literature, probably because there is a connection between non-monotonic entailment relations and the intended application of such logics in defeasible reasoning. While not much harm may be done in that context, a more careful analysis is required when studying defeasibility of functions, operators or connectives in a language. We therefore brie y digress to recall some basic de nitions surrounding these notions.
an n-ary function f : in=01Si ! Sn is monotone increasing in all its arguments on Sn if the following holds:
If xi yi for 0 i < n; then f (x0; : : : ; xn 1) f (y0; : : : ; yn 1):
It is then easy to see that (the semantic interpretations of) the concept constructors u, t and 9 induce monotone increasing binary functions on hP( ); i, the concept constructor : induces a monotone decreasing unary function, and the concept constructors 8, 8 and 9 induce binary functions that are neither monotone increasing nor monotone decreasing, i.e., they are non-monotonic. We may alternatively take a more proof-theoretic approach and observe that u, t and 9 induce monotone increasing functions on the concept subsumption hierarchy hL; vi, : induces a monotone decreasing function and 8, 8 and 9 induce non-monotonic functions on hLe; vi. Although we cannot express r v s in ALC, semantically 8 remains a non-monotonic concept constructor, and in more expressive DLs with role hierarchies this can also be expressed syntactically, in that it does not in general follow from r v s and C v D that 8r:C v 8s:D.
Defeasible reasoning dates back to Aristotle's analysis of dialectics, and relates to argument forms that seem compelling but are not classically valid. As mentioned above, a more restrictive view of defeasible reasoning is often taken, con ating it with non-monotonic reasoning. However, demonstrating nonmonotonicity to prove defeasibility is not always accurate. For example, as we showed above standard universal restriction is non-monotonic, but there is no reason why it should be regarded as a defeasible concept constructor.
Informally, a defeasible relation on a set is one which admits classical counterexamples. The defeasibility of the relation does not refer to its non-monotonicity, but rather to the possibility of defeat by counter-example. A requirement of a defeasible function is therefore that it is more tolerant than some base function in the following sense: De nition 5. Given n + 1 partially ordered sets of objects hSi; ii, 0 i n, an n-ary function f : in=01Si ! Sn is tolerant with respect to an n-ary function f 0 : in=01Si ! Sn if the following holds: f 0(x1; : : : ; xn) f (x1; : : : ; xn); for all xi 2 Si; 0 i < n f 0(x1; : : : ; xn) 6= f (x1; : : : ; xn); for some xi 2 Si; 0 i < n
The obvious examples relevant to the content of this paper are 8, which is tolerant with respect to 8, and 9, which is tolerant with respect to 9. Our claim is not that tolerance as de ned above corresponds precisely to defeasibility (and could therefore be used as a de nition of defeasibility). A simple illustration of this point is that classical disjunction is tolerant with respect to conjunction, but it does not seem to make sense to consider disjunction as being defeasible with respect to conjunction.
We contend that 8 may be interpreted as defeasible universal restriction: Informally, PrivateLawyer Lawyer u 8hasClient:PayingClient de nes the class of private lawyers as the set of objects that are lawyers, and whose most normal clients are the ones who pay. The defeasibility resides in the concept constructor of universal quanti cation 8, rather than in any of the concept or role descriptions involved, or in the subsumption relation. Thus we are not stating that, normally, private lawyers only have paying clients, but rather that the normal clientele of private lawyers are restricted to paying clients. This is made more precise in Example 2 below. First we need a de nition.
(Preferential coherence is a generalisation of classical concept coherence as
de ned by Schlobach and Cornet [
T = (
PrivateLawyer
Lawyer u 8hasClient:PayingClient;
CommunityLawyer v PrivateLawyer u 9hasClient::PayingClient
)
It is easy to show that T is preferentially coherent. Informally, this means it
is possible for community lawyers, by virtue of being private lawyers, to
normally have paying clients, but to have some non-paying clients at the same
time. Furthermore, it can be veri ed that T preferentially entails the statement
CommunityLawyer v 9hasClient:PayingClient. Informally, because we know that
all community lawyers have some clients (albeit non-paying clients), it must be
the case that they all have paying clients as well. This follows from the fact that
community lawyers are also private lawyers.
In this section we present a simple tableau-based proof procedure for reasoning
with preferential role restrictions. Our tableau calculus is based on standard
modal tableaux with labeled formulae and explicit accessibility relations [
As usually done in the DL community, it is enough to de ne a tableau system that checks only for concept satis ability (cf. Lemma 1).
In a labeled concept n :: C, n is the label. (As we shall see, informally, the idea is that the label stands for some object in a DL interpretation.) De nition 8. A skeleton is a function : NR ! P(N
N).
That is, a skeleton maps role names in the language to binary relations on labels.
Our tableau system also makes use of an auxiliary structure of which the intention is to build a preference relation on objects of the domain: De nition 9. A preference relation is a binary relation on N.
As we shall see below, like , is built cumulatively through successive applications of the tableau rules we shall introduce.
cepts, is a skeleton and is a preference relation.
De nition 11. A tableau rule is a rule of the form:
N ; D1 ; 10 j : : : j Dk ; 0 k where N ; is the numerator and D1 ; 10 j : : : j Dk ; k0 is the denominator.
Given a rule , N represents one or more labeled concepts, called the main concept of the rule, separated by `,'. stands for any additional condition (on or ) that must be satis ed for the rule to be applicable (see below). In the denominator, each Di, 1 i k, has one or more labeled concepts, whereas each i0 is a condition to be satis ed after the application of the rule (e.g. structural changes in the skeleton or in the relation ). The symbol `j' indicates the occurrence of a split in the branch, characteristic of the so-called don't-know non-deterministic rules.
Figure 2 below presents the set of tableau rules for Le. In the rules we abbreviate (n; n0) 2 (i) as n !i n0, and n0 2 (i)(n) as n0 2 i(n). Finally, with n0?; n00?; : : : we denote labels that have not been used before. We say that a rule is applicable to a branch hS; ; i if and only if S contains an instance of the main concept of and the conditions of are satis ed by and . n :: ::C n :: C
n :: C u D (u) n :: C; n :: D (t)
n :: :(C u D) n :: :C j n :: :D (8) n :: 8ri:C ; n !i n0; n0 2 min n0 :: C i(n) (9)
n :: :8ri:C n0? :: :C ; n !i n0?; n0? 2 min i(n) (8) n :: 8ri:C ; n !i n0 n0 :: C ( ) n :: :8ri:C 9 n0? :: :C ; 10 j n0? :: :C ; 20 ; where 10 = fn !i n0?; n0? 2 min i(n)g and 20 = fn !i n0?; n !i n00?; n00?
n0?; n00? 2 min i(n)g
The Boolean rules together with (8) are as usual and need no explanation. Rule (8) propagates concepts in the scope of a defeasible universal restriction to the most preferred (with respect to ) of all successor nodes. Rule (9) creates a preferred (minimal) successor node with the corresponding labeled concept as content. Rule (9) replaces the standard rule for 9-concepts with a don't-know non-deterministic version thereof and requires a more thorough explanation. When creating a new successor node, there are two possibilities: Either (i) it is minimal (with respect to ) amongst all successor nodes, in which case the result is the same as that of applying Rule (9), or (ii) it is not minimal, in which case there must be a most preferred successor node that is more preferred (with respect to ) than the newly created one. (This splitting is of the same nature as that in the (t)-rule, i.e., it ts the purpose of a proof by cases.)
We make the so-called fairness assumption: Any rule that can be applied will eventually be applied, i.e., the order of rule applications is not relevant. We say a tableau is saturated if no rule is applicable to any of its branches.
For an example, consider the concept C = 9r:(A u :B) t 9r::A t 8r:B. Figure 3 depicts the (open) tableau for :C = 8r::(A u :B) u 8r:A u :8r:B. 1 :: A 1 :: :(A u :B) (t) 1 :: :A (?) 1 :: ? (t) 1 :: ::B (:) (?) 1 :: B 1 :: ? (9) 2 :: :B ; 20 2 :: A 3 :: A (8) (8) (8) 3 :: :(A u :B) (t) 3 :: :A (?) 3 :: ? (t) 3 :: ::B
(:) 3 :: B 10 = add (0; 1) to and 1 to min (0); 20 = add (0; 2) and (0; 3) to , (3; 2) to and 3 to min (0)
From the open tableau in Figure 3 one can extract the preferential interpretation P as depicted in Figure 4. (In Figure 4 the understanding is that 3 2 and that 0 is incomparable with respect to to the other objects in the domain.)
We are now ready to state the main result of this section. (The proof of
Theorem 1 is analogous to that by Britz and Varzinczak in the modal case [
(saturated) tableau for C.
It can easily be checked that in the construction of the tableau there is only a nite number of distinct states since every concept generated by the application of a rule is a subconcept of the original one. Therefore we have a decision procedure for our enriched description logic.
It is well-known that satis ability checking for the description logic ALC is pspace-complete. It is not that hard to see that the addition of 8 and 9 to the concept language does not a ect the space complexity of the resulting tableaux.
2 fAg 3 fA; Bg 0 fg To see why, if the concept at the root of the tableau is C, and jCj = m, i.e., m is the number of symbols occurring in C, then the space requirement for each label is at most O(m). Since there exists a saturated tableau with depth at most O(m2), the total space requirement is O(m3). In summary, in spite of the additional expressivity brought in by the introduction of preferential role restrictions, we remain in the same complexity class as that of the logic we started o with.
Finally, the tableau system we have just introduced checks only for concept
satis ability and therefore no TBox information is assumed. From the
perspective of knowledge representation and reasoning it becomes important to check for
concept satis ability with respect to background knowledge provided in the form
of a TBox and (possibly) an ABox. Fortunately our tableau calculus can easily
be adapted to take care of this need. For instance, satis ability with respect to
a TBox can be achieved with the addition of the following rule [
n :: E n :: E u dCvD2T (:C t D)
The rule (TB) is the only one that does not have the subconcept property,
but it is not hard to see that it does not a ect decidability of the method.
Complexitywise, since TBox entailment in ALC is exptime [
In the previous section we showed how to perform preferential TBox reasoning, and provided a tableau system for computing preferential TBox entailment. In this section we investigate the immediate consequences of including ABoxes.
Let NI be a nite set of individual names. An ALC ABox A is a nite set of assertions of the form C(a) or r(a; b), where a; b 2 NI , C 2 Le and r 2 NR. We extend the preferential interpretation function P of De nition 1 to include mappings from individual names to elements of the domain P in the standard way: for every a 2 NI , aP 2 P . The satisfaction of (extended) ABox assertions is then de ned as usual: For a preferential interpretation P, and for a; b 2 NI , C 2 Le and r 2 NR, P C(a) if and only if aP 2 CP , and P r(a; b) if and only if (aP ; bP ) 2 rP .
Henceforth, an Le-knowledge base K is a tuple hT ; Ai where T is a TBox and A is a ABox. We sometimes abuse notation by referring to the knowledge base K = hT ; Ai as the set T [ A.
Given a knowledge base K, the preferential models of K is the set of preferential interpretations PM (K) := fP j P for every 2 Kg: K is preferentially satis able if it has a preferential model. De nition 3 then applies without change also to preferential entailment from knowledge bases.
Example 3. Let T be the TBox given in Example 2 and consider the ABox A = fPrivateLawyer(sam); 9hasClient:>(sam)g. The knowledge base K = hT ; Ai preferentially entails the ABox statement 9hasClient:PayingClient(sam). That is, if we know that Sam, the private lawyer, has a client, we can conclude that he has a paying client. In fact, in line with the reasoning exhibited in Example 2, if we replace the statement 9hasClient:>(sam) in A with the stronger statement 9hasClient::PayingClient(sam), the resulting knowledge base is preferentially satis able, and preferentially entails 9hasClient:PayingClient(sam). In other words, given that Sam the private lawyer has a non-paying client, we can also conclude that he has a paying client.
At rst glance, preferential entailment for knowledge bases may seem to provide appropriate results. However, closer inspection reveals that preferential entailment for knowledge bases sometimes gives counterintuitive results. Consider the knowledge base K = hT ; Ai where T = fLawyer v 8hasClient:PayingClientg and A = fLawyer(sam), hasClient(sam; peter)g. From this we would like to (defeasibly) conclude the statement PayingClient(peter). But is easy to see that preferential entailment does not sanction this conclusion. The issue is that we need individuals to be as normal as is allowed by the knowledge. For example, the reason why PayingClient(peter) is not entailed by K is because there are some preferential models of K in which Peter is not a paying client, and is therefore not one of Sam's normal clients.
To rectify this, we introduce an ordering on the preferential models of a knowledge base. Intuitively, a preferential model P1 of K is at least as preferred (at least as low down in the ordering) as P2 if (i) it agrees with P2 everywhere except on the denotation of individual names, and (ii) all names in P1 denote objects that are at least as low down in the ordering as in P2.
PM (K) as follows: P1 K P2 if and only if P1 = P2 , CP1 = CP2 for every C 2 Le, rP1 = rP2 for every r 2 NR, and aP1 P1 aP2 for every a 2 NI .2
It is easily veri ed that K is a weak partial order (i.e., it is re exive, antisymmetric and transitive). Moreover, since all preferential interpretations are well-founded, it follows that K is also well-founded. Let min K PM (K) := fP 2 PM (K) j P0 6 K P for every P0 2 PM (K) s.t. P0 6= Pg. 2 Note that
P1 is the weak partial order obtained from
It can now be veri ed that the statement PayingClient(peter) is minimally preferentially entailed by the knowledge base in Example 3. To see that this is a defeasible conclusion, note that if we add the statement :PayingClient(peter) to the knowledge base in Example 3, the statement PayingClient(peter) is not minimally preferentially entailed by the new knowledge base (and the new knowledge base is preferentially satis able). 6
We conclude with a comment on the expression of defeasible subsumption
statements [
For every concept C 2 L and preferential interpretation P, we can de ne in P its left cylindri cation rC in the following way: rC := fhx; yi j x 2
P and y 2 CP g: Practically, rC is the largest role r de nable in a preferential model P such that P > v 8r:C. It follows that, for every C; D 2 L, P C @ D if and only if P > v 8rC :D.
The implications of this connection between defeasible subsumption and defeasible universal restriction requires further investigation. Other future work include extension of the tableau procedure to minimal preferential entailment.
Finally, from a knowledge representation and reasoning perspective, when
dealing with knowledge bases, issues related to modularization [
This work is based upon research supported in part by the National Research Foundation of South Africa (UID 85482, IFR2011032700018). Any opinion, ndings and conclusions or recommendations expressed in this material are those of the authors and therefore the NRF do not accept any liability in regard thereto. This work was also partially funded by Project number 247601, Net2: Network for Enabling Networked Knowledge, from the FP7-PEOPLE- 2009-IRSES call.