The description logic dSROIQ is a decidable extension of SROIQ that supports defeasible reasoning in the KLM tradition. It features a parameterised preference order on binary relations in a domain of interpretation, which allows for the use of defeasible roles in complex concepts, as well as in defeasible concept and role subsumption, and in defeasible role assertions. In this paper, we address an important limitation both in dSROIQ and in other defeasible extensions of description logics, namely the restriction in the semantics of defeasible concept subsumption to a single preference order on objects. We do this by inducing preference orders on objects from preference orders on roles, and use these to relativise defeasible subsumption. This yields a notion of contextualised defeasible subsumption, with contexts described by roles.
SROIQ [Horrocks et al., 2006] is an expressive, yet decidable Description Logic (DL) that serves as semantic foundation for the OWL 2 profile, on which several ontology languages of various expressivity are based. However, SROIQ still allows for meaningful, decidable extension, as new knowledge representation requirements are identified. A case in point is the need to allow for exceptions and defeasibility in reasoning over logic-based ontologies [Bonatti et al., 2009; 2011; 2015; Britz et al., 2011; 2013a; 2013b; Britz and Varzinczak, 2016a; Casini et al., 2015; Casini and Straccia, 2010; 2013; Giordano et al., 2013; 2015; Sengupta et al., 2011]. Yet, SROIQ does not allow for the direct expression of and reasoning with different aspects of defeasibility.
Given the special status of subsumption in DLs in particular, and the historical importance of entailment in logic in general, past research efforts in this direction have focused primarily on accounts of defeasible subsumption and the characterisation of defeasible entailment. Semantically, the latter usually takes as point of departure orderings on a class of first-order interpretations, whereas the former usually assume a preference order on objects of the domain.
Recently, we proposed a decidable extension of SROIQ that supports defeasible knowledge representation and reasoning over defeasible ontologies [Britz and Varzinczak, 2016a; 2017]. Our proposal built on previous work to resolve two important ontological limitations of the preferential approach to defeasible reasoning in DLs — the assumption of a single preference order on all objects in the domain of interpretation, and the assumption that defeasibility is intrinsically linked to argument form [Britz and Varzinczak, 2013; 2016b].
We achieved this by extending SROIQ with nonmonotonic reasoning features in the concept language, in subsumption statements and in role assertions, via an intuitive notion of normality for roles. This parameterised the idea of preference while at the same time introducing the notion of defeasible class membership. Defeasible subsumption allows for the expression of statements of the form “C is usually subsumed by D”, for example, “Chenin blanc wines are usually unwooded”. In the extended language dSROIQ, one can also refer directly to, for example, “Chenin blanc wines that usually have a wood aroma”. We can also combine these seamlessly, as in: “Chenin blanc wines that usually have a wood aroma are usually wooded”. This cannot be expressed in terms of defeasible subsumption alone, nor can it be expressed w.l.o.g. using a typicality operator on concepts. This is because the semantics of the expression is inextricably tied to the two distinct uses of the term ‘usually’.
However, even this generalisation leaves open the question of different, possibly incompatible, notions of defeasibility in subsumption, similar to those studied in contextual argumentation [Amgoud et al., 2000; Bikakis and Antoniou, 2010]. In the statement “Chenin blanc wines are usually unwooded”, the context relative to which the subsumption is normal is left implicit – in this case, the style of the wine. In a different context such as consumer preference or origin, the most preferred (or normal, or typical) Chenin blanc wines may not correlate with the usual wine style. Wine x may be more exceptional than y in one context, but less exceptional in another context. This represents a form of inconsistency in defeasible knowledge bases arising from the presence of named individuals in the ontology. The example illustrates why a single ordering on individuals does not suffice. It also points to a natural index for relativised context, namely the use of preferential role names previously proposed for dSROIQ.
In this paper, we therefore propose to induce preference orders on objects from preference orders on roles, and use these to relativise defeasible subsumption. This yields a notion of contextualised defeasible subsumption, with contexts described by roles.
The remainder of the paper is structured as follows: In Section 2 we present some DL background on SROIQ. In Section 3 we introduce the syntax of the extended language dSROIQ, and in Section 4 its semantics. The newly introduced defeasible language constructs are discussed in Section 5, where we also give examples to illustrate their semantics and use. Section 6 covers a number of rewriting and elimination results required for effective reasoning with dSROIQ knowledge bases.
We shall assume the reader’s familiarity with the preferential approach to non-monotonic reasoning [Kraus et al., 1990; Lehmann and Magidor, 1992; Shoham, 1988]. Whenever necessary, we refer the reader to the definitions and results in the relevant literature. 2
In this section, we provide the basics of SROIQ [Horrocks et al., 2006]. For space considerations, but also to avoid repetition, we defer many of its technicalities to the upcoming sections.
The language of SROIQ is built upon a finite set of atomic concept names C, of which N, the set of nominals, is a subset, a finite set of role names R and a finite set of individual names I such that C, R and I are pairwise disjoint. The universal role is denoted by u and the set of all roles is given by R := R [ fr j r 2 Rg [ fug, where r denotes the inverse of r. With A; B; : : : we denote atomic concepts, with r; s; : : : roles, and with a; b; : : : individual names. A nominal will also be denoted by o, possibly with subscripts.
The set of SROIQ complex concepts is the smallest set such that: >, ? and every A 2 C are concepts; if C and D are concepts, r; s 2 R, and n 2 N, then :C (concept complement), C u D (concept conjunction), C t D (concept disjunction), 8r:C (value restriction), 9r:C (existential restriction), 9r:Self (self restriction), ns:C (at-least restriction), ns:C (at-most restriction) are also concepts. With C; D : : : we denote complex SROIQ concepts. A more detailed description of the roles allowed in complex concept descriptions will be provided in Definitions 1 and 3.
If C and D are concepts, then C v D is a general concept inclusion axiom (GCI, for short), read “C is subsumed by D”. C D is an abbreviation for both C v D and D v C.
Given C a concept, r 2 R and a; b 2 I, an individual assertion is an expression of the form a : C, (a; b) : r, (a; b) : :r, a = b or a 6= b.
A role inclusion axiom (RIA) is a statement of the form r1 rn v r, where r1; : : : ; rn; r 2 Rnfug and r1 rn denotes the composition of r1; : : : ; rn. A role assertion is a statement of the form Fun(r) (functionality), Ref(r) (reflexivity), Irr(r) (irreflexivity), Sym(r) (symmetry), Asy(r) (asymmetry), Tra(r) (transitivity), and Dis(r; s) (role disjointness), where r; s 6= u. A more detailed description of the roles allowed in RIAs will be given in Definition 2.
The semantics of SROIQ is in terms of the standard set theoretic Tarskian semantics. An interpretation is a structure xa2 1 r1 x6
AI1 1 r2 x4 x7 r2 r1
I := h I ; I i, where I is a non-empty set called the domain, and I is an interpretation function mapping concept names A 2 C to subsets AI of I (with oI a singleton if o 2 N), role names r 2 R to binary relations rI over I , and individual names a 2 I to elements of the domain I , i.e., AI I , rI I I , aI 2 I . We extend I from role names to roles by letting uI := I I and (r )I := f(y; x) j (x; y) 2 rI g, and to role chains by setting (r1 rn)I := r1I rnI .
As an example, let C := fA1; A2; A3g, R := fr1; r2g and I := fa1; a2; a3g. Figure 1 depicts the interpretation I1 = h I1 ; I1 i, where I1 = i fxi j 1 9g, A1I1 = fx1; x4; x6g, A2I1 = fx3; x5; x9g, A3I1 = fx6; x7; x8g, r1I1 = f(x1; x6); (x4; x8); (x2; x5)g, rI1 = 2 f(x4; x4); (x6; x4); (x5; x8); (x9; x3)g, a1I1 = x5, a2I1 = x1, I1 : I1
The notion of interpretation can be extended to interpret (complex) SROIQ concepts and to provide a notion of satisfaction of GCIs, RIAs, individual and role assertions in a way that will be made clear in Section 3. 3
In this section, we present the syntax and semantics of an extension to SROIQ to represent defeasible complex concepts and subsumption. The logic presented here is an incremental extension of dSROIQ, which was introduced recently [Britz and Varzinczak, 2017] to add defeasible reasoning features to SROIQ. Previous work included various defeasible constructs on concepts based on preferential roles, but only a single preference order on objects. This was somewhat of an anomaly, as pointed out by some reviewers and colleagues. We address this anomaly by adding context-based orderings on objects that are derived from preferential roles. This turns out to be a remarkably seamless yet very useful refinement. Briefly, each preferential role r, interpreted as a strict partial order on the binary product space of the domain, gives rise to a context-based order on objects as detailed in Definition 6 below. 3.1
Let inv : R ! R be such that inv : r 7! r , if r 2 R, inv : r 7! s, if r = s , and inv : u 7! u.
Let r1; : : : ; rn; r 2 R n fug. A classical role inclusion axiom is a statement of the form r1 rn v r. A defeasible role inclusion axiom has the form r1 rn @r, read “usually, r1 rn is included in r”. A finite set of (classical or defeasible) role inclusion axioms (RIAs) is called a role hierarchy and is denoted by Rh.
a role hierarchy. Then r is non-simple in Rh iff: 1. There is r1 rn v r or r1 rn @r in Rh such that n > 1, or 2. There is s v r or s @r in Rh such that s is non-simple, or 3. inv(r) is non-simple.
With Rn we denote the set of non-simple roles in Rh. Rs := R n Rn is the set of simple roles in Rh.
Intuitively, simple roles are those that are not implied by the composition of roles. They are needed to restrict the type of roles in certain concept constructors (see below), thereby preserving decidability [Horrocks et al., 2006].
Definition 2 (Regular Hierarchy) A role hierarchy Rh is regular if there is a strict partial order < on Rn such that: 1. s < r iff inv(s) < r, for every r; s in Rn, and 2. every role inclusion in Rh is of one of the forms: (1a) r r v r, (1b) r r @r, (2a) inv(r) v r, (2b) inv(r) @r, (3a) s1 sn v r, (3b) s1 sn @r, (4a) r s1 sn v r, (4b) r s1 sn @r, (5a) s1 sn r v r, (5b) s1 sn r @r, where r 2 R (i.e., a role name), and si < r, for i = 1; : : : ; n. (Regularity prevents a role hierarchy from inducing cyclic dependencies, which are known to lead to undecidability.)
A classical role assertion is a statement of the form Fun(r) (functionality), Ref(r) (reflexivity), Irr(r) (irreflexivity), Sym(r) (symmetry), Asy(r) (asymmetry), Tra(r) (transitivity), and Dis(r; s) (role disjointness), where r; s 6= u. A defeasible role assertion is a statement of the form dFun(r) (r is usually functional), dRef(r) (r is usually reflexive), dIrr(r) (r is usually irreflexive), dSym(r) (r is usually symmetric), dAsy(r) (r is usually asymmetric), dTra(r) (r is usually transitive), and dDis(r; s) (r and s are usually disjoint), also with r; s 6= u. With Ra we denote a finite set of role assertions.
Given a role hierarchy Rh, we say that Ra is simple w.r.t. Rh if all roles r; s appearing in statements of the form Irr(r), dIrr(r), Asy(r), dAsy(r), Dis(r; s) or dDis(r; s) are simple in Rh (see Definition 1).
A dS ROIQ RBox is a set R := Rh [ Ra, where Rh is a regular hierarchy and Ra is a set of role assertions which is simple w.r.t. Rh. 3.2
We now extend the set of S ROIQ complex concepts via the definition of concept constructors allowing for the expression of defeasibility at the object level.
complex concepts is the smallest set such that >, ? and every A 2 C are concepts, and if C and D are concepts, r 2 R, s 2 Rs, and n 2 N, then :C (concept complement), C u D (concept conjunction), C t D (concept disjunction), 8r:C (value restriction), 9r:C (existential restriction), Wr:C (defeasible value restriction), jr:C (defeasible existential restriction), 9r:Self (self restriction), jr:Self (defeasible self restriction), ns:C (at-least restriction), ns:C (at-most restriction), & ns:C (defeasible at-least restriction), . ns:C (defeasible at-most restriction) are also concepts. With C we denote the set of all complex concepts.
Note that every S ROIQ concept is a dS ROIQ concept, too. We shall use C; D : : :, possibly with subscripts, to denote complex dS ROIQ concepts. 3.3
Given C; D 2 C, C v D is a classical general concept inclusion, read “C is subsumed by D”. C D is an abbreviation for both C v D and D v C.
The extension of dS ROIQ we propose here includes context-based defeasible subsumption statements in the TBox. Given C; D 2 C and r 2 R, C @rD is a defeasible general concept inclusion, read “C is usually subsumed by D in the context r”. A dS ROIQ TBox T is a finite set of general concept inclusions (GCIs), whether classical or defeasible.
Before we present the semantics, we introduce the remaining components of dS ROIQ ontologies. Recall I is a set of individual names disjoint from both C and R. Given C 2 C, r 2 R and a; b 2 I, an individual assertion is an expression of the form a : C, (a; b) : r, (a; b) : :r, a = b or a 6= b. A dS ROIQ ABox A is a finite set of individual assertions.
Let A be an ABox, T be a TBox and R an RBox. A knowledge base (alias ontology) is a tuple KB := hA; R; T i. 4
Preferential semantics We shall anchor our semantic constructions in the wellknown preferential approach to non-monotonic reasoning [Kraus et al., 1990; Lehmann and Magidor, 1992; Shoham, 1988] and its extensions [Boutilier, 1994; Britz and Varzinczak, 2013; a; 2016b; b], especially those to the DL case [Britz et al., 2011; Britz and Varzinczak, 2016a; Giordano et al., 2009; Quantz and Royer, 1992].
Let X be a set and let < be a strict partial order on X . With min< X := fx 2 X j there is no y 2 X s.t. y < xg we denote the minimal elements of X w.r.t. <. With #X we shall denote the cardinality of X . 1; : : : ; #R, and such that each condition [Kraus et al., 1990].
pretation is a tuple O := h O; O; Oi in which h O; Oi is a S ROIQ interpretation with AO O, for every A 2 C, AO a singleton for every A 2 N, rO O O, for all r 2 R, and aO 2 O, for every a 2 I, and O:= h 1O; : : : ; O#Ri, where iO riO riO, for i = iO satisfies the smoothness
As an example, let C := fA1; A2; A3g, R := fr1; r2g, I := fa1; a2; a3g, and let the r-ordered interpretation O1 = h O1 ; O1 ; O1 i, where O1 = xa2 1 r1 x6
A1O r2 x4 x7 r2 r1
I1 , and h 1O1 = f(x4x8; x2x5); (x2x5; x1x6); (x4x8; x1x6)g and O1 = f(x6x4; x4x4); (x5x8; x9x3)g. (For the sake of read2 ability, we shall henceforth sometimes write tuples of the form (x; y) as xy.) Figure 2 below depicts the r-ordered interpretation O1. In the picture, 1O1 and 2O1 are represented, respectively, by the dashed and the dotted arrows. (Note the direction of the O-arrows, which point from more preferred to less preferred pairs of objects.) Also for the sake of readability, we shall omit the transitive O-arrows.
2O1 i, where 1O1 ;
Given O = h O; O; Oi, the intuition of O and O is the same as in a standard DL interpretation. The intuition underlying each of the orderings in O is that they play the role of preference relations (or normality orderings), in a sense similar to that introduced by Shoham [Shoham, 1988] with a preference on worlds in a propositional setting and as extensively investigated by Kraus et al. [Kraus et al., 1990; Lehmann and Magidor, 1992] and others [Boutilier, 1994; Britz et al., 2008; Giordano et al., 2007]: the pairs (x; y) that are lower down in the ordering iO are deemed as the most normal (or typical, or expected) in the context of (the interpretation of) ri. Technically, the difference between our definitions and those in the aforementioned work lies on the fact that our iO are orderings on binary relations on the domain O, instead of orderings on propositional valuations or on plain objects of O.
In the following definition we show how ordered interpretations can be extended to interpret the complex concepts of the language.
rO1 r2 := [((x1; z1); (x2; z2)) 2 and for no z1, z2 [((x2; z2), (x1; z1)) 2 Definition 5 (O extended) Let O = h O; O; Oi. For any r; r1; r2 2 R n fug, O interprets orderings on role inverses and on role compositions as follows: rO := f((y1; x1); (y2; x2)) j ((x1; y1); (x2; y2)) 2 rOg, and f((x1; y1), (x2; y2)) j for some z1, z2 rO1 and ((z1; y1); (z2; y2)) 2 rO1 and ((z2; y2), rO2 ], (z1; y1)) 2 rO2 ]g. Moreover, let riOjx := riO \ (fxg O) (i.e., the restriction of the domain of riO to fxg). The interpretation function O interprets dSROIQ concepts in the following way (whenever it is clear which component of O is used, we shall drop the subscript in iO): >O :=
O; ?O := ;; (:C)O :=
O n CO; (C u D)O := CO \ DO;
(C t D)O := CO [ DO; (8r:C)O := fx j rO(x) COg; (Wr:C)O := fx j min O (rOjx)(x) (9r:C)O := fx j rO(x) \ CO 6= ;g; COg; ( jr:C)O := fx j min O (rOjx)(x) \ CO 6= ;g; (9r:Self)O := fx j (x; x) 2 rOg; ( jr:Self)O := fx j (x; x) 2 min O (rOjx)g; ( ( nr:C)O := fx j #rO(x) \ CO nr:C)O := fx j #rO(x) \ CO ng; ng; (& nr:C)O := fx j # min O (rOjx)(x) \ COg (. nr:C)O := fx j # min O (rOjx)(x) \ CO n; ng:
It is not hard to see that, analogously to the classical case, W and j, as well as & and ., are dual to each other. Definition 6 (Satisfaction) Let O = h O; O; Oi and let r1; : : : ; rn; r; s 2 R, C; D 2 C, and a; b 2 I. Let rO:= f(x; y) j there is some (x; z) 2 rO such that for all (y; v) 2 rO [((x; z); (y; v)) 2 rO]g: The satisfaction relation is defined as follows:
O O O O O O O O O O O O O O O O O O O O r1 r1 sO;
O (r1 rn)O
rO; rn)O Fun(r) if rO is a function; dFun(r) if for all x, # min O (rOjx)(x) Ref(r) if f(x; x) j x 2 Og rO; dRef(r) if for every x 2 min uO Irr(r) if rO \ f(x; x) j x 2 dIrr(r) if for every x 2 min uO
Og = ;;
O, (x; x) 2= rO; Sym(r) if inv(r)O rO; dSym(r) if min O (r )O rO;
O, (x; x) 2 rO; Asy(r) if rO \ inv(r)O = ;; dAsy(r) if min O rO \ min O (r )O = ;; Tra(r) if (r r)O rO; dTra(r) if min O (r r)O rO; Dis(r; s) if rO \ sO = ;; dDis(r; s) if min O rO \ min O sO = ;; C v D if CO DO; rO; 1; C @rD if min rO CO DO; a : C if aO 2 CO; O (a; b) : :r if O 6 (a; b) : r; a = b if aO = bO; O a 6= b if O 6 a = b.
O O O
If O , then we say O satisfies . O satisfies a set of statements or assertions X (denoted O X) if O for every 2 X, in which case we say O is a model of X. We say C 2 C is satisfiable w.r.t. KB = hA; R; T i if there is a model O of KB s.t. CO 6= ;, and unsatisfiable otherwise. (a; b) : r if (aO; bO) 2 rO;
A statement is (classically) entailed by a knowledge base KB, denoted KB j= , if every model of KB satisfies . 5
The motivation for dSROIQ is to represent defeasible knowledge, and to reason over defeasible ontologies. We now consider the different aspects of defeasibility that can be expressed in dSROIQ. We first consider defeasible existential restriction:
Cheninblanc u j hasAroma:Wood v 9hasStyle:Wooded This statement is read: “Chenin blanc wines that normally have a wood aroma are wooded”. That is, any Chenin blanc wine that has a characteristic wood aroma, has a wooded wine style. For an example of defeasible subsumption, consider the statement which states that Chenin blanc wines usually have some floral aroma. That is, the most typical Chenin blanc wines all have some floral aroma. Similarly, states that Chenin blanc wines usually come only from the Loire Valley. Now suppose we have a Chenin blanc wine x, which comes from the Loire Valley but does not have a floral aroma, and another Chenin blanc wine y which has a floral aroma but comes from Languedoc. No model of this ontology can simultaneously have x u y w.r.t. origin and y u x w.r.t. aroma. There can therefore be no model that accurately models reality.
This is precisely the limitation imposed by having only a single ordering on objects, as usually assumed by preferential approaches to defeasible DLs [Britz et al., 2008; 2011; Giordano et al., 2007; 2009; 2013], and the motivation for introducing context-based defeasible subsumption. Although the two defeasible statements are not inconsistent, the presence of both rules out certain intended models. In contrast, with context-based defeasible subsumption, both subsumption statements can be expressed and x and y can have incompatible preferential relationships in the same model: Note that this knowledge base cannot be changed to: Cheninblanc v jhasAroma:Floral
Cheninblanc v WhasOrigin:Loire as the latter states that every Chenin blanc wine has a characteristic floral aroma and is usually exclusive to the Loire Valley (ruling out the possibility of a Chenin blanc without a floral aroma, or one that comes only from Languedoc).
Lemma 1 below shows that every strict partial order on objects in the domain O can be obtained from some strict partial order on O O as in Definition 6. This justifies the use of @u in defeasible subsumption statements where the context is universal. It also supports the definition of uO, since it shows the more traditional preference ordering on all objects in the domain to be a special case of our proposal. Lemma 2 shows that the converse of Lemma 1 holds in the more general case of any context-based preference order rO. Lemma 1 Given domain O and strict partial order on
O, let uO:= f((x; z); (y; z)) j x yg, and let uO be as in Definition 6. Then = uO.
Lemma 2 Let O = h O; O; Oi, and let rO be as in Definition 6. Then rO is a strict partial order on O.
Corollary 1 makes the intuition of universal defeasible subsumption clear. For the more general parameterised case, the intuition is essentially the same. Consider the role hasOrigin, which links individual wines to origins. Wine x is considered more typical (or less exceptional) than y w.r.t. its origin if it has some origin link which is preferred to any such link from y.
Context-based defeasible subsumption @r can therefore also be viewed as defeasible subsumption based on a preference order on objects in the domain of rO, bearing in mind that in any given interpretation, it is dependent on rO. This raises the question whether a preference order on objects in the range of rO could be considered as an alternative, but since role inverses are allowed in context-based defeasible subsumption, @inv(r) achieves this.
The following result shows that context-based defeasible subsumption is indeed an appropriate notion of defeasible subsumption: Lemma 3 For every r 2 R, @r is a preferential subsumption relation on concepts in that, for every O, the following properties hold: (Ref) O (And) O
O (RW) O C @rD; O D v E (CM) O C @rD; O C @rE
O C @rE O C u D @rE
It is not hard to show that, moreover, if the ordering associated to a role r is modular, the defeasible subsumption @r it induces is also rational, i.e., it satisfies the following rational monotonicity property: (RM) O
O C u C0 @rD
A further feature of context-based subsumption is therefore the ability to allow for both rational and preferential-only subsumption relations. 6
Eliminating ABoxes, classical GCIs and the universal role As for classical SROIQ [Horrocks et al., 2006, Lemma 7], it is possible to eliminate an ABox A by compiling all individual assertions in A as follows: 1. Let N0 := N [ foa j a appears in Ag (i.e., extend the signature with new nominals); 2. Let A0 := fa : C 2 Ag[fa : 9r:ob j (a; b) : r 2 Ag[fa : 8r::ob j (a; b) : :r 2 Ag [ fa : :ob j a 6= b 2 Ag; 3. For every C 2 C, let C0 := C u da:D2A0 9u:(oa u D).
It is then easy to see that C is satisfiable w.r.t. hA; R; T i if and only if C0 is satisfiable w.r.t. h;; R; T i, which allows us to assume from now on and w.l.o.g. that ABoxes have been eliminated.
Next, in the same way that most of the classical role assertions can equivalently be replaced by GCIs or RIAs, under our preferential semantics, all of our defeasible role assertions, with the exception of dAsy( ) and dDis( ), can be reduced to defeasible RIAs in the following way. dFun(r) can be replaced by > v. 1r:> — to be ‘usually functional’ means only non-normal arrows can break functionality. (Note that, since the number restriction is unqualified, r need not be simple.) dRef(r) and dIrr(r) can, respectively, be replaced with > @9r:Self and > @:9r:Self. dSym(r) can be reduced to r @r and dTra(r) to r r @r. Furthermore, note that dAsy(r) can be reduced to dDis(r; r ) (cf. Definition 6). Hence, from now on we can assume, w.l.o.g., that the set of role assertions Ra contains only statements of the form Dis(r; s) and dDis(r; s).
Finally, we can apply the same procedure for eliminating both all classical TBox statements and the universal role u defined for classical S ROIQ [Horrocks et al., 2006, Lemma 8][Schild, 1991], extended to the case of dS ROIQ concepts. Hence, from now on we can assume that all classical concept subsumptions (as well as occurrences of u therein) have been eliminated.
The next theorem summarises the reduction outlined in this section: Theorem 1 Let KB = hA; R; T i and let D := fC @ D j r C @rD 2 T g. Satisfiability of dS ROIQ-concepts w.r.t. KB can be polynomially reduced to satisfiability of dS ROIQconcepts w.r.t. h;; R; Di where all role assertions in R are of the form Dis(r; s) and dDis(r; s).
We leave an investigation of a reduction of the axioms in D for future work. 7
Concluding remarks In this paper, we have made a case for a context-based notion of defeasible concept inclusion in description logics. We have seen that roles can be used to provide a simple yet powerful context for such a notion. We have shown how the semantics of the resulting family of defeasible subsumption relations can be anchored to that of preferential roles, which we studied in previous work.
From the knowledge-representation standpoint, contextbased subsumption provides the user with more flexibility in making defeasible statements in ontologies. From a modelling point of view, the semantic characterisation we propose here resolves an important limitation of many defeasible extensions of description logics, namely the restriction in the semantics of defeasible concept subsumption to a single preference order on objects.
The definitions and preliminary results reported in this paper raise a number of immediate questions:
How to obtain the other direction of the KLM-style representation result (cf. Lemma 3)? How to reduce satisfiability w.r.t. defeasible TBoxes and RBoxes to satisfiability w.r.t. only defeasible RBoxes? How to extend the tableau system for dS ROIQ to account for multi-defeasible subsumptions of the kind we introduced here? How to define and compute rational closure of a family of defeasible concept inclusions? Can a notion of context, together with our more expressive language, give rise to new KLM-style postulates characterising defeasible subsumption relations that are more powerful than the rational ones? These are some of the questions that will drive future investigation of the topic.
Acknowledgements This work is based on research supported in part by the National Research Foundation of South Africa (Grant Numbers 103345 and 85482).