<?xml version="1.0" encoding="UTF-8"?>
<TEI xml:space="preserve" xmlns="http://www.tei-c.org/ns/1.0" 
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
xsi:schemaLocation="http://www.tei-c.org/ns/1.0 https://raw.githubusercontent.com/kermitt2/grobid/master/grobid-home/schemas/xsd/Grobid.xsd"
 xmlns:xlink="http://www.w3.org/1999/xlink">
	<teiHeader xml:lang="en">
		<fileDesc>
			<titleStmt>
				<title level="a" type="main">Context-based defeasible subsumption for dSROIQ</title>
			</titleStmt>
			<publicationStmt>
				<publisher/>
				<availability status="unknown"><licence/></availability>
			</publicationStmt>
			<sourceDesc>
				<biblStruct>
					<analytic>
						<author>
							<persName><forename type="first">Katarina</forename><surname>Britz</surname></persName>
							<email>abritz@sun.ac.za</email>
							<affiliation key="aff0">
								<orgName type="department">CSIR-SU CAIR</orgName>
								<orgName type="institution">Stellenbosch University South Africa</orgName>
							</affiliation>
						</author>
						<author>
							<persName><forename type="first">Ivan</forename><surname>Varzinczak</surname></persName>
							<email>varzinczak@cril.fr</email>
							<affiliation key="aff1">
								<orgName type="department">CRIL</orgName>
								<orgName type="institution" key="instit1">Univ. Artois</orgName>
								<orgName type="institution" key="instit2">CNRS France</orgName>
							</affiliation>
						</author>
						<title level="a" type="main">Context-based defeasible subsumption for dSROIQ</title>
					</analytic>
					<monogr>
						<imprint>
							<date/>
						</imprint>
					</monogr>
					<idno type="MD5">7FED105F40697BDBDD3048BCBA51D86A</idno>
				</biblStruct>
			</sourceDesc>
		</fileDesc>
		<encodingDesc>
			<appInfo>
				<application version="0.7.2" ident="GROBID" when="2023-03-23T21:00+0000">
					<desc>GROBID - A machine learning software for extracting information from scholarly documents</desc>
					<ref target="https://github.com/kermitt2/grobid"/>
				</application>
			</appInfo>
		</encodingDesc>
		<profileDesc>
			<abstract>
<div xmlns="http://www.tei-c.org/ns/1.0"><p>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.</p></div>
			</abstract>
		</profileDesc>
	</teiHeader>
	<text xml:lang="en">
		<body>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">Introduction</head><p>SROIQ <ref type="bibr" target="#b3">[Horrocks et al., 2006</ref>] 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 <ref type="bibr" target="#b0">[Bonatti et al., 2009;</ref><ref type="bibr" target="#b0">2011;</ref><ref type="bibr">2015;</ref><ref type="bibr" target="#b2">Britz et al., 2011;</ref><ref type="bibr">2013a;</ref><ref type="bibr">2013b;</ref><ref type="bibr">Britz and Varzinczak, 2016a;</ref><ref type="bibr" target="#b2">Casini et al., 2015;</ref><ref type="bibr" target="#b2">Casini and Straccia, 2010;</ref><ref type="bibr" target="#b2">2013;</ref><ref type="bibr" target="#b2">Giordano et al., 2013;</ref><ref type="bibr">2015;</ref><ref type="bibr" target="#b5">Sengupta et al., 2011</ref>]. Yet, SROIQ does not allow for the direct expression of and reasoning with different aspects of defeasibility.</p><p>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.</p><p>Recently, we proposed a decidable extension of SROIQ that supports defeasible knowledge representation and rea-soning over defeasible ontologies <ref type="bibr">[Britz and Varzinczak, 2016a;</ref><ref type="bibr" target="#b2">2017]</ref>. 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 <ref type="bibr" target="#b2">[Britz and Varzinczak, 2013;</ref><ref type="bibr">2016b]</ref>.</p><p>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'.</p><p>However, even this generalisation leaves open the question of different, possibly incompatible, notions of defeasibility in subsumption, similar to those studied in contextual argumentation <ref type="bibr" target="#b0">[Amgoud et al., 2000;</ref><ref type="bibr" target="#b0">Bikakis and Antoniou, 2010]</ref>. 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.</p><p>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.</p><p>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.</p><p>We shall assume the reader's familiarity with the preferential approach to non-monotonic reasoning <ref type="bibr" target="#b4">[Kraus et al., 1990;</ref><ref type="bibr" target="#b4">Lehmann and Magidor, 1992;</ref><ref type="bibr" target="#b5">Shoham, 1988]</ref>. Whenever necessary, we refer the reader to the definitions and results in the relevant literature.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">The description logic SROIQ</head><p>In this section, we provide the basics of SROIQ <ref type="bibr" target="#b3">[Horrocks et al., 2006]</ref>. For space considerations, but also to avoid repetition, we defer many of its technicalities to the upcoming sections.</p><p>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 ∪ {r − | r ∈ R} ∪ {u}, 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.</p><p>The set of SROIQ complex concepts is the smallest set such that: , ⊥ and every A ∈ C are concepts; if C and D are concepts, r, s ∈ R, and n ∈ N, then ¬C (concept complement), C D (concept conjunction), C D (concept disjunction), ∀r.C (value restriction), ∃r.C (existential restriction), ∃r.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.</p><p>If A role inclusion axiom (RIA) is a statement of the form</p><formula xml:id="formula_0">r 1 •• • ••r n r, where r 1 , . . . , r n , r ∈ R\{u} and r 1 •• • ••r n</formula><p>denotes the composition of r 1 , . . . , r n . 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 = u. A more detailed description of the roles allowed in RIAs will be given in Definition 2.</p><p>The semantics of SROIQ is in terms of the standard set theoretic Tarskian semantics. An interpretation is a structure I := ∆ I , • I , where ∆ I is a non-empty set called the domain, and • I is an interpretation function mapping concept names A ∈ C to subsets A I of ∆ I (with o I a singleton if o ∈ N), role names r ∈ R to binary relations r I over ∆ I , and individual names a ∈ I to elements of the domain ∆ I , i.e., A I ⊆ ∆ I , r I ⊆ ∆ I × ∆ I , a I ∈ ∆ I . We extend • I from role names to roles by letting u I := ∆ I × ∆ I and (r − ) I := {(y, x) | (x, y) ∈ r I }, and to role chains by setting</p><formula xml:id="formula_1">(r 1 • • • • • r n ) I := r I 1 • • • • • r I n . As an example, let C := {A 1 , A 2 , A 3 }, R := {r 1 , r 2 } and I := {a 1 , a 2 , a 3 }. Figure 1 depicts the interpreta- tion I 1 = ∆ I1 , • I1 , where ∆ I1 = {x i | 1 ≤ i ≤ 9}, A I1 1 = {x 1 , x 4 , x 6 }, A I1 2 = {x 3 , x 5 , x 9 }, A I1 3 = {x 6 , x 7 , x 8 }, r I1 1 = {(x 1 , x 6 ), (x 4 , x 8 ), (x 2 , x 5 )}, r I1 2 = {(x 4 , x 4 ), (x 6 , x 4 ), (x 5 , x 8 ), (x 9 , x 3 )}, a I1 1 = x 5 , a I1 2 = x 1 , and a I1 3 = x 2 . I1 : ∆ I1 A I1 1 A I1 2 A I1 3 x a2 1 x a3 2 x3 x4 x a1 5 x6 x7 x8 x9 r1 r2 r1 r2 r1 r2 r2 Figure 1: A SROIQ interpretation.</formula><p>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.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3">Context-based defeasible SROIQ</head><p>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 <ref type="bibr" target="#b2">[Britz and Varzinczak, 2017]</ref> 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.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.1">Defeasibility in RBoxes</head><formula xml:id="formula_2">Let inv : R −→ R be such that inv : r → r − , if r ∈ R, inv : r → s, if r = s − , and inv : u → u. Let r 1 , . . . , r n , r ∈ R \ {u}. A classical role inclusion ax- iom is a statement of the form r 1 • • • • • r n r. A defeasible role inclusion axiom has the form r 1 • • • • • r n ∼ r, read "usu- ally, r 1 • • • • • r n is included in r".</formula><p>A finite set of (classical or defeasible) role inclusion axioms (RIAs) is called a role hierarchy and is denoted by R h .</p><p>Definition 1 ((Non-)Simple Role) Let r ∈ R and let R h be a role hierarchy. Then r is non-simple in R h iff:</p><formula xml:id="formula_3">1. There is r 1 • • • • • r n r or r 1 • • • • • r n ∼ r in R h such that n &gt; 1, or 2. There is s r or s ∼ r in R h such that s is non-simple, or 3. inv(r) is non-simple. With R n we denote the set of non-simple roles in R h . R s := R \ R n is the set of simple roles in R h .</formula><p>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 <ref type="bibr" target="#b3">[Horrocks et al., 2006]</ref>.</p><p>Definition 2 (Regular Hierarchy) A role hierarchy R h is regular if there is a strict partial order &lt; on R n such that:</p><p>1. s &lt; r iff inv(s) &lt; r, for every r, s in R n , and 2. every role inclusion in R h is of one of the forms:</p><formula xml:id="formula_4">(1a) r • r r, (1b) r • r ∼ r, (2a) inv(r) r, (2b) inv(r) ∼ r, (3a) s 1 • • • • • s n r, (3b) s 1 • • • • • s n ∼ r, (4a) r • s 1 • • • • • s n r, (4b) r • s 1 • • • • • s n ∼ r, (5a) s 1 • • • • • s n • r r, (5b) s 1 • • • • • s n • r ∼ r</formula><p>, where r ∈ R (i.e., a role name), and s i &lt; r, for i = 1, . . . , n.</p><p>(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 = 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 = u. With R a we denote a finite set of role assertions.</p><p>Given a role hierarchy R h , we say that R a is simple w.r.t. R h 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 R h (see Definition 1).</p><p>A dSROIQ RBox is a set R := R h ∪ R a , where R h is a regular hierarchy and R a is a set of role assertions which is simple w.r.t. R h .</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2">Defeasibility in concepts</head><p>We now extend the set of SROIQ complex concepts via the definition of concept constructors allowing for the expression of defeasibility at the object level. Note that every SROIQ concept is a dSROIQ concept, too. We shall use C, D . . ., possibly with subscripts, to denote complex dSROIQ concepts. Let A be an ABox, T be a TBox and R an RBox. A knowledge base (alias ontology) is a tuple KB := A, R, T .</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.3">Context-based defeasible subsumption</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4">Preferential semantics</head><p>We shall anchor our semantic constructions in the wellknown preferential approach to non-monotonic reasoning <ref type="bibr" target="#b4">[Kraus et al., 1990;</ref><ref type="bibr" target="#b4">Lehmann and Magidor, 1992;</ref><ref type="bibr" target="#b5">Shoham, 1988]</ref> and its extensions <ref type="bibr" target="#b1">[Boutilier, 1994;</ref><ref type="bibr" target="#b2">Britz and Varzinczak, 2013;</ref><ref type="bibr">a;</ref><ref type="bibr">2016b;</ref><ref type="bibr" target="#b2">b]</ref>, especially those to the DL case <ref type="bibr" target="#b2">[Britz et al., 2011;</ref><ref type="bibr">Britz and Varzinczak, 2016a;</ref><ref type="bibr" target="#b2">Giordano et al., 2009;</ref><ref type="bibr" target="#b4">Quantz and Royer, 1992]</ref>.</p><p>Let X be a set and let &lt; be a strict partial order on X. With min &lt; X := {x ∈ X | there is no y ∈ X s.t. y &lt; x} we denote the minimal elements of X w.r.t. &lt;. With #X we shall denote the cardinality of X.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Definition 4 (Ordered Interpretation) An ordered interpretation is a tuple</head><formula xml:id="formula_5">O := ∆ O , • O , O in which ∆ O , • O is a SROIQ interpretation with A O ⊆ ∆ O , for every A ∈ C, A O a singleton for every A ∈ N, r O ⊆ ∆ O × ∆ O ,</formula><p>for all r ∈ R, and a O ∈ ∆ O , for every a ∈ I, and</p><formula xml:id="formula_6">O := O 1 , . . . , O #R , where O i ⊆ r O i × r O i , for i = 1, . . . , #R,</formula><p>and such that each O i satisfies the smoothness condition <ref type="bibr" target="#b4">[Kraus et al., 1990]</ref>.</p><p>As an example, let C := {A 1 , A 2 , A 3 }, R := {r 1 , r 2 }, I := {a 1 , a 2 , a 3 }, and let the r-ordered interpretation O 1 = ∆ O1 , • O1 , O1 , where ∆ O1 = ∆ I1 , • O1 = • I1 , and</p><formula xml:id="formula_7">O1 = O1 1 , O1<label>2</label></formula><p>, where O1 1 = {(x 4 x 8 , x 2 x 5 ), (x 2 x 5 , x 1 x 6 ), (x 4 x 8 , x 1 x 6 )} and O1 2 = {(x 6 x 4 , x 4 x 4 ), (x 5 x 8 , x 9 x 3 )}. (For the sake of readability, we shall henceforth sometimes write tuples of the form (x, y) as xy.) Figure <ref type="figure" target="#fig_3">2</ref> below depicts the r-ordered interpretation O 1 . In the picture, O1</p><p>1 and O1 2 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. Given O = ∆ O , • O , O , 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 <ref type="bibr" target="#b5">[Shoham, 1988]</ref> with a preference on worlds in a propositional setting and as extensively investigated by Kraus et al. <ref type="bibr" target="#b4">[Kraus et al., 1990;</ref><ref type="bibr" target="#b4">Lehmann and Magidor, 1992]</ref> and others <ref type="bibr" target="#b1">[Boutilier, 1994;</ref><ref type="bibr" target="#b2">Britz et al., 2008;</ref><ref type="bibr" target="#b2">Giordano et al., 2007]</ref>: the pairs (x, y) that are lower down in the ordering O i are deemed as the most normal (or typical, or expected) in the context of (the interpretation of) r i . Technically, the difference between our definitions and those in the aforementioned work lies on the fact that our O i are orderings on binary relations on the domain ∆ O , instead of orderings on propositional valuations or on plain objects of ∆ O .</p><formula xml:id="formula_8">O : ∆ O A O 1 A O 2 A O 3 x a2</formula><p>In the following definition we show how ordered interpretations can be extended to interpret the complex concepts of the language.</p><formula xml:id="formula_9">Definition 5 (O extended) Let O = ∆ O , • O , O .</formula><p>For any r, r 1 , r 2 ∈ R \ {u}, O interprets orderings on role inverses and on role compositions as follows: </p><formula xml:id="formula_10">O r − := {((y 1 , x 1 ), (y 2 , x 2 )) | ((x 1 , y 1 ), (x 2 , y 2 )) ∈ O r }, and O r1•r2 := {((x 1 , y 1 ), (x 2 , y 2 )) | for some z 1 , z 2 [((x 1 , z 1 ), (x 2 , z 2 )) ∈ O r1 and ((z 1 , y 1 ), (z 2 , y 2 )) ∈ O r2 ], and for no z 1 , z 2 [((x 2 , z 2 ), (x 1 , z 1 )) ∈ O r1 and ((z 2 , y 2 ), (z 1 , y 1 )) ∈ O r2 ]}. Moreover, let r O|x i := r O i ∩ ({x} × ∆ O ) (i.e.,</formula><formula xml:id="formula_11">:= ∆ O ; ⊥ O := ∅; (¬C) O := ∆ O \ C O ; (C D) O := C O ∩ D O ; (C D) O := C O ∪ D O ; (∀r.C) O := {x | r O (x) ⊆ C O }; ( ∼ r.C) O := {x | min O (r O|x )(x) ⊆ C O }; (∃r.C) O := {x | r O (x) ∩ C O = ∅}; ( − ∼ − | r.C) O := {x | min O (r O|x )(x) ∩ C O = ∅}; (∃r.Self) O := {x | (x, x) ∈ r O }; ( − ∼ − | r.Self) O := {x | (x, x) ∈ min O (r O|x )}; (≥ nr.C) O := {x | #r O (x) ∩ C O ≥ n}; (≤ nr.C) O := {x | #r O (x) ∩ C O ≤ n}; ( nr.C) O := {x | # min O (r O|x )(x) ∩ C O } ≥ n; ( nr.C) O := {x | # min O (r O|x )(x) ∩ C O ≤ n}.</formula><p>It is not hard to see that, analogously to the classical case, ∼ and − ∼ − | , as well as and , are dual to each other. Definition 6 (Satisfaction)</p><formula xml:id="formula_12">Let O = ∆ O , • O , O and let r 1 , . . . , r n , r, s ∈ R, C, D ∈ C, and a, b ∈ I. Let ≺ O r := {(x, y) | there is some (x, z) ∈ r O such that for all (y, v) ∈ r O [((x, z), (y, v)) ∈ O r ]}.</formula><p>The satisfaction relation is defined as follows:</p><formula xml:id="formula_13">O r s if r O ⊆ s O ; O r ∼ s if min O r O ⊆ s O ; O r 1 • • • • • r n r if (r 1 • • • • • r n ) O ⊆ r O ; O r 1 • • • • • r n ∼ r if min O (r 1 • • • • • r n ) O ⊆ r O ; O Fun(r) if r O is a function; O dFun(r) if for all x, # min O (r O|x )(x) ≤ 1; O Ref(r) if {(x, x) | x ∈ ∆ O } ⊆ r O ; O dRef(r) if for every x ∈ min ≺ O u ∆ O , (x, x) ∈ r O ; O Irr(r) if r O ∩ {(x, x) | x ∈ ∆ O } = ∅; O dIrr(r) if for every x ∈ min ≺ O u ∆ O , (x, x) / ∈ r O ; O Sym(r) if inv(r) O ⊆ r O ; O dSym(r) if min O (r − ) O ⊆ r O ; O Asy(r) if r O ∩ inv(r) O = ∅; O dAsy(r) if min O r O ∩ min O (r − ) O = ∅; O Tra(r) if (r • r) O ⊆ r O ; O dTra(r) if min O (r • r) O ⊆ r O ; O Dis(r, s) if r O ∩ s O = ∅; O dDis(r, s) if min O r O ∩ min O s O = ∅; O C D if C O ⊆ D O ; O C ∼r D if min ≺ O r C O ⊆ D O ; O a : C if a O ∈ C O ; O (a, b) : r if (a O , b O ) ∈ r O ; O (a, b) : ¬r if O (a, b) : r; O a = b if a O = b O ; O a = b if O a = b. If O α, then we say O satisfies α. O satisfies a set of statements or assertions X (denoted O X) if O α for every α ∈ X, in which case we say O is a model of X. We say C ∈ C is satisfiable w.r.t. KB = A, R, T if there is a model O of KB s.t. C O = ∅,</formula><p>and unsatisfiable otherwise.</p><p>A statement α is (classically) entailed by a knowledge base KB, denoted KB |= α, if every model of KB satisfies α.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5">Modelling with dSROIQ ontologies</head><p>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:</p><formula xml:id="formula_14">Cheninblanc − ∼ − | hasAroma.Wood ∃hasStyle.Wooded</formula><p>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 Cheninblanc ∼u ∃hasAroma.Floral 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, Cheninblanc ∼u ∀hasOrigin.Loire 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 <ref type="bibr" target="#b2">[Britz et al., 2008;</ref><ref type="bibr" target="#b0">2011;</ref><ref type="bibr" target="#b2">Giordano et al., 2007;</ref><ref type="bibr" target="#b0">2009;</ref><ref type="bibr" target="#b2">2013]</ref>, 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: Cheninblanc ∼hasAroma ∃hasAroma.Floral Cheninblanc ∼hasOrigin ∀hasOrigin.Loire Note that this knowledge base cannot be changed to:</p><formula xml:id="formula_15">Cheninblanc − ∼ − | hasAroma.Floral Cheninblanc ∼ hasOrigin.Loire</formula><p>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).</p><p>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 ≺ O u ,</p><p>since it shows the more traditional preference ordering on all objects in the domain to be a special case of our proposal. 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.</p><p>Context-based defeasible subsumption ∼r can therefore also be viewed as defeasible subsumption based on a preference order on objects in the domain of r O , bearing in mind that in any given interpretation, it is dependent on O r . This raises the question whether a preference order on objects in the range of r O could be considered as an alternative, but since role inverses are allowed in context-based defeasible subsumption, ∼inv(r) achieves this.</p><p>The following result shows that context-based defeasible subsumption is indeed an appropriate notion of defeasible subsumption: Lemma 3 For every r ∈ R, ∼r is a preferential subsumption relation on concepts in that, for every O, the following properties hold:</p><formula xml:id="formula_16">(Ref) O C ∼r C (LLE) O C ≡ D, O C ∼r E O D ∼r E (And) O C ∼r D, O C ∼r E O C ∼r D E (Or) O C ∼r E, O D ∼r E O C D ∼r E (RW) O C ∼r D, O D E O C ∼r E (CM) O C ∼r D, O C ∼r E O C D ∼r E</formula><p>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:</p><formula xml:id="formula_17">(RM) O C ∼r D, O C ∼r ¬C O C C ∼r D</formula><p>A further feature of context-based subsumption is therefore the ability to allow for both rational and preferential-only subsumption relations. 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</p><p>1r.</p><p>-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 ∼ ∃r.Self and ∼ ¬∃r.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 R a contains only statements of the form Dis(r, s) and dDis(r, s).</p><p>Finally, we can apply the same procedure for eliminating both all classical TBox statements and the universal role u defined for classical <ref type="bibr">SROIQ [Horrocks et al., 2006</ref><ref type="bibr">, Lemma 8][Schild, 1991]</ref>, extended to the case of dSROIQ concepts. Hence, from now on we can assume that all classical concept subsumptions (as well as occurrences of u therein) have been eliminated.</p><p>The next theorem summarises the reduction outlined in this section: Theorem 1 Let KB = A, R, T and let D := {C ∼r D | C ∼r D ∈ T }. Satisfiability of dSROIQ-concepts w.r.t. KB can be polynomially reduced to satisfiability of dSROIQconcepts w.r.t. ∅, R, D where all role assertions in R are of the form Dis(r, s) and dDis(r, s).</p><p>We leave an investigation of a reduction of the axioms in D for future work.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="7">Concluding remarks</head><p>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.</p><p>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.</p><p>The definitions and preliminary results reported in this paper raise a number of immediate questions:</p><p>• How to obtain the other direction of the KLM-style representation result (cf. Lemma 3)?</p><p>• How to reduce satisfiability w.r.t. defeasible TBoxes and RBoxes to satisfiability w.r.t. only defeasible RBoxes?</p><p>• How to extend the tableau system for dSROIQ to account for multi-defeasible subsumptions of the kind we introduced here?</p><p>• How to define and compute rational closure of a family of defeasible concept inclusions?</p><p>• 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?</p><p>These are some of the questions that will drive future investigation of the topic.</p></div><figure xmlns="http://www.tei-c.org/ns/1.0" xml:id="fig_0"><head></head><label></label><figDesc>C and D are concepts, then C D is a general concept inclusion axiom (GCI, for short), read "C is subsumed by D". C ≡ D is an abbreviation for both C D and D C. Given C a concept, r ∈ R and a, b ∈ I, an individual assertion is an expression of the form a : C, (a, b) : r, (a, b) : ¬r, a = b or a = b.</figDesc></figure>
<figure xmlns="http://www.tei-c.org/ns/1.0" xml:id="fig_1"><head>Definition 3 (</head><label>3</label><figDesc>dSROIQ Concepts) The set of dSROIQ complex concepts is the smallest set such that , ⊥ and every A ∈ C are concepts, and if C and D are concepts, r ∈ R, s ∈ R s , and n ∈ N, then ¬C (concept complement), C D (concept conjunction), C D (concept disjunction), ∀r.C (value restriction), ∃r.C (existential restriction), ∼ r.C (defeasible value restriction), − ∼ − | r.C (defeasible existential restriction), ∃r.Self (self restriction), − ∼ − | r.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.</figDesc></figure>
<figure xmlns="http://www.tei-c.org/ns/1.0" xml:id="fig_2"><head></head><label></label><figDesc>Given C, D ∈ C, C D is a classical general concept inclusion, read "C is subsumed by D". C ≡ D is an abbreviation for both C D and D C. The extension of dSROIQ we propose here includes context-based defeasible subsumption statements in the TBox. Given C, D ∈ C and r ∈ R, C ∼r D is a defeasible general concept inclusion, read "C is usually subsumed by D in the context r". A dSROIQ 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 dSROIQ ontologies. Recall I is a set of individual names disjoint from both C and R. Given C ∈ C, r ∈ R and a, b ∈ I, an individual assertion is an expression of the form a : C, (a, b) : r, (a, b) : ¬r, a = b or a = b. A dSROIQ ABox A is a finite set of individual assertions.</figDesc></figure>
<figure xmlns="http://www.tei-c.org/ns/1.0" xml:id="fig_3"><head>Figure 2 :</head><label>2</label><figDesc>Figure 2: A dSROIQ ordered interpretation.</figDesc></figure>
<figure xmlns="http://www.tei-c.org/ns/1.0" xml:id="fig_4"><head></head><label></label><figDesc>Lemma 2 shows that the converse of Lemma 1 holds in the more general case of any context-based preference order O r . Lemma 1 Given domain ∆ O and strict partial order ≺ on ∆ O , let O u := {((x, z), (y, z)) | x ≺ y}, and let ≺ O u be as in Definition 6. Then ≺ = ≺ O u . Lemma 2 Let O = ∆ O , • O , O , and let ≺ O r be as in Definition 6. Then ≺ O r is a strict partial order on ∆ O . Corollary 1 Let ≺ be a strict partial order on ∆ O , and let O C ∼ D iff min ≺ C O ⊆ D O . Then universal defeasible subsumption ∼u has the same semantics as ∼ .</figDesc></figure>
<figure xmlns="http://www.tei-c.org/ns/1.0" type="table" xml:id="tab_0"><head></head><label></label><figDesc>the restriction of the domain of r O i to {x}). 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 O i ): O</figDesc><table /></figure>
<figure xmlns="http://www.tei-c.org/ns/1.0" type="table" xml:id="tab_1"><head></head><label></label><figDesc>Let N := N ∪ {o a | a appears in A} (i.e., extend the signature with new nominals); 2. Let A := {a : C ∈ A}∪{a : ∃r.o b | (a, b) : r ∈ A}∪{a : ∀r.¬o b | (a, b) : ¬r ∈ A} ∪ {a : ¬o b | a = b ∈ A}; 3. For every C ∈ C, let C := C a:D∈A ∃u.(o a D).It is then easy to see that C is satisfiable w.r.t. A, R, T if and only if C is satisfiable w.r.t. ∅, R, T , which allows us to assume from now on and w.l.o.g. that ABoxes have been eliminated.</figDesc><table><row><cell>1.</cell></row><row><cell>6 Eliminating ABoxes, classical GCIs and the</cell></row><row><cell>universal role</cell></row><row><cell>As for classical SROIQ [Horrocks et al., 2006, Lemma 7],</cell></row><row><cell>it is possible to eliminate an ABox A by compiling all indi-</cell></row><row><cell>vidual assertions in A as follows:</cell></row></table></figure>
		</body>
		<back>

			<div type="acknowledgement">
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Acknowledgements</head><p>This work is based on research supported in part by the National Research Foundation of South Africa (Grant Numbers 103345 and 85482).</p></div>
			</div>

			<div type="references">

				<listBibl>

<biblStruct xml:id="b0">
	<analytic>
		<title level="a" type="main">Defeasible contextual reasoning with arguments in ambient intelligence</title>
		<author>
			<persName><surname>Amgoud</surname></persName>
		</author>
	</analytic>
	<monogr>
		<title level="m">Proceedings of the International Conference on Formal and Applied and Practical Reasoning (FAPR)</title>
				<meeting>the International Conference on Formal and Applied and Practical Reasoning (FAPR)</meeting>
		<imprint>
			<date type="published" when="2000">2000. 2000. 2010. 2010. 2009. 2009. 2011. 2011. 2015</date>
			<biblScope unit="volume">22</biblScope>
			<biblScope unit="page" from="1" to="48" />
		</imprint>
	</monogr>
	<note>Artificial Intelligence</note>
</biblStruct>

<biblStruct xml:id="b1">
	<analytic>
		<title level="a" type="main">Conditional logics of normality: A modal approach</title>
		<author>
			<persName><forename type="first">;</forename><forename type="middle">C</forename><surname>Boutilier</surname></persName>
		</author>
		<author>
			<persName><forename type="first">;</forename><surname>Boutilier</surname></persName>
		</author>
		<author>
			<persName><surname>Britz</surname></persName>
		</author>
	</analytic>
	<monogr>
		<title level="j">Artificial Intelligence</title>
		<editor>K. Britz and I. Varzinczak</editor>
		<imprint>
			<biblScope unit="volume">68</biblScope>
			<biblScope unit="issue">1</biblScope>
			<biblScope unit="page" from="87" to="154" />
			<date type="published" when="1994">1994. 1994</date>
		</imprint>
	</monogr>
	<note>From KLM-style conditionals to defeasible modalities, and back. To appear</note>
</biblStruct>

<biblStruct xml:id="b2">
	<analytic>
		<title level="a" type="main">Preferential accessibility and preferred worlds. Journal of Logic, Language and Information</title>
		<author>
			<persName><surname>Britz</surname></persName>
		</author>
		<author>
			<persName><forename type="first">]</forename><forename type="middle">K</forename><surname>Varzinczak</surname></persName>
		</author>
		<author>
			<persName><forename type="first">I</forename><surname>Britz</surname></persName>
		</author>
		<author>
			<persName><surname>Varzinczak</surname></persName>
		</author>
		<author>
			<persName><forename type="first">;</forename><forename type="middle">K</forename><surname>Britz</surname></persName>
		</author>
		<author>
			<persName><forename type="first">I</forename><surname>Britz</surname></persName>
		</author>
		<author>
			<persName><surname>Varzinczak</surname></persName>
		</author>
		<author>
			<persName><forename type="first">;</forename><forename type="middle">K</forename><surname>Britz</surname></persName>
		</author>
		<author>
			<persName><forename type="first">I</forename><surname>Britz</surname></persName>
		</author>
		<author>
			<persName><surname>Varzinczak</surname></persName>
		</author>
		<author>
			<persName><forename type="first">;</forename><forename type="middle">K</forename><surname>Britz</surname></persName>
		</author>
		<author>
			<persName><forename type="first">I</forename><surname>Britz</surname></persName>
		</author>
		<author>
			<persName><surname>Varzinczak</surname></persName>
		</author>
		<author>
			<persName><forename type="first">;</forename><forename type="middle">K</forename><surname>Britz</surname></persName>
		</author>
		<author>
			<persName><forename type="first">I</forename><surname>Britz</surname></persName>
		</author>
		<author>
			<persName><surname>Varzinczak</surname></persName>
		</author>
		<author>
			<persName><surname>Britz</surname></persName>
		</author>
	</analytic>
	<monogr>
		<title level="m">Proceedings of the 15th European Conference on Logics in Artificial Intelligence (JELIA), number 10021 in LNCS</title>
				<editor>
			<persName><forename type="first">N</forename><surname>Dershowitz</surname></persName>
		</editor>
		<editor>
			<persName><forename type="first">A</forename><surname>Voronkov</surname></persName>
		</editor>
		<meeting>the 15th European Conference on Logics in Artificial Intelligence (JELIA), number 10021 in LNCS</meeting>
		<imprint>
			<publisher>Springer</publisher>
			<date type="published" when="2007">2013. 2016. 2017. 2008. 2008. 2011. 2011. 2013. 2013. 2010. 2010. 2013. 2013. 2015. 2015. 2007. 2007. 2009. 2009. 2013</date>
			<biblScope unit="volume">1879</biblScope>
			<biblScope unit="page" from="165" to="202" />
		</imprint>
		<respStmt>
			<orgName>CAIR, CSIR Meraka and UKZN, South Africa</orgName>
		</respStmt>
	</monogr>
	<note type="report_type">Technical report</note>
	<note>Artificial Intelligence</note>
</biblStruct>

<biblStruct xml:id="b3">
	<analytic>
		<title level="a" type="main">Semantic characterization of rational closure: From propositional logic to description logics</title>
		<author>
			<persName><forename type="first">Giordano</forename></persName>
		</author>
	</analytic>
	<monogr>
		<title level="m">Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR)</title>
				<editor>
			<persName><forename type="first">P</forename><surname>Doherty</surname></persName>
		</editor>
		<editor>
			<persName><forename type="first">J</forename><surname>Mylopoulos</surname></persName>
		</editor>
		<editor>
			<persName><forename type="first">C</forename><surname>Welty</surname></persName>
		</editor>
		<meeting>the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR)</meeting>
		<imprint>
			<publisher>Morgan Kaufmann</publisher>
			<date type="published" when="2006">2015. 2015. 2006. 2006</date>
			<biblScope unit="volume">226</biblScope>
			<biblScope unit="page" from="57" to="67" />
		</imprint>
	</monogr>
	<note>The even more irresistible SROIQ</note>
</biblStruct>

<biblStruct xml:id="b4">
	<analytic>
		<title level="a" type="main">Nonmonotonic reasoning, preferential models and cumulative logics</title>
		<author>
			<persName><surname>Kraus</surname></persName>
		</author>
	</analytic>
	<monogr>
		<title level="m">Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR)</title>
				<meeting>the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR)</meeting>
		<imprint>
			<date type="published" when="1990">1990. 1990. 1992. 1992. 1992. 1992</date>
			<biblScope unit="volume">44</biblScope>
			<biblScope unit="page" from="294" to="305" />
		</imprint>
	</monogr>
	<note>What does a conditional knowledge base entail? Artificial Intelligence</note>
</biblStruct>

<biblStruct xml:id="b5">
	<analytic>
		<title level="a" type="main">A correspondence theory for terminological logics: Preliminary report</title>
		<author>
			<persName><forename type="first">;</forename><forename type="middle">K</forename><surname>Schild</surname></persName>
		</author>
		<author>
			<persName><surname>Schild</surname></persName>
		</author>
		<author>
			<persName><surname>Sengupta</surname></persName>
		</author>
	</analytic>
	<monogr>
		<title level="m">Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI)</title>
				<editor>
			<persName><forename type="first">Y</forename><surname>Shoham</surname></persName>
		</editor>
		<meeting>the 12th International Joint Conference on Artificial Intelligence (IJCAI)</meeting>
		<imprint>
			<publisher>MIT Press</publisher>
			<date type="published" when="1988">1991. 1991. 2011. 2011. 1988. 1988</date>
			<biblScope unit="page" from="617" to="632" />
		</imprint>
	</monogr>
	<note>Reasoning about Change: Time and Causation from the Standpoint of Artificial Intelligence</note>
</biblStruct>

				</listBibl>
			</div>
		</back>
	</text>
</TEI>
