Lexicographic Closure for Defeasible Description Logics

Abstract

In the field of non-monotonic logics, the lexicographic closure is acknowledged as a a powerful and logically well-characterized approach; we are going to see that such a construction can be applied in the field of Description Logics, an important knowledge representation formalism, and we shall provide a simple decision procedure.

Introduction

The application of non-monotonic reasoning (see, e.g. [ 12 ]) to Description Logics (DLs) [ 1 ] has received a lot of attention in the last years, resulting in the development of various proposals, such as [ 2, 4, 6, 5, 7–11, 13–15, 21, 22 ]. However, between them just a few ([ 8–10, 14, 22 ]) take under consideration the preferential approach (see [ 19 ]), a wellknown approach to non-monotonic reasoning. Here we take under consideration one of the main proposals in the preferential area, the lexicographic closure [ 18 ], developed by Lehmann for propositional languages, and never taken under consideration in the DL field. We are going to readapt such a procedure to ALC, a significant and expressive representative of the various DLs. The procedure we are going to implement is obtained by modifying the rational closure construction defined for ALC in [ 9 ].

We proceed as follows: we present a construction of the lexicographic closure at the propositional level that slightly generalizes the construction presented by Lehmann, and still based on classical entailment tests only; then we implement such a construction in ALC. Due to the space limits, we shall omit the proofs of the presented propositions. In what follows we are going to present a slight generalization of Lehmann’s procedure [ 18 ], that is, a non-monotonic reasoning procedure that relies on a decision procedure for j= only. We then suggest how to transpose such an approach into the framework of DLs.

In the present section we shall proceed in the following way: first, we define the notion of rational consequence relation (see e.g. [ 17 ]) and we present the notions of rational and lexicographic closure; then, we describe a procedure to build a lexicographic closure of a conditional knowledge base.

Rational Consequence Relations. The preferential approach is mainly based the identification of the structural properties that a well-behaved (both from the intuitive and the logical point of view) non-monototonic consequence relation should satisfy. Between the possible interesting options, a particular relevance has been given to the group of properties characterizing the class of rational consequence relations (see [ 17 ]). A consequence relation j is rational iff it satisfies the following properties: (REF) Cj C

Reflexivity (CT) (CM)

Cj D C ^ Dj F Cut (Cumulative Trans.)

Cj F Cj D Cj F C ^ Dj F

Cautious Monotony (LLE) Cj F j= C $ D Left Logical Equival.

Dj F (RW) Cj D D j= F

Cj F (OR) Cj F Dj F

C _ Dj F

Right Weakening

Left Disjunction (RM) Cj F C 6 j :D Rational Monotony

C ^ Dj F

We refer the reader to [ 19 ] for an insight of the meaning of such rules. (RM) is generally considered as the strongest form of monotonicity we can use in the characterization of a reasoning system in order to formalise a well-behaved form of defeasible reasoning. The kind of reasoning we want to implement applies at the level of sequents: let B = fC1j E1; : : : ; Cnj Eng be a conditional knowledge base; we want the agent to be able to reason about the defeasible information at its disposal, that is, to be able to derive new sequents from his conditional base.

Semantically, rational consequence relations can be characterized by means of a particular kind of possible-worlds model, that is, ranked preferential models, but we shall not deepen the connection with such a semantical characterization here (see [ 17 ]). Except for (RM), all the above properties are closure properties, that is, they are preserved under intersection of the consequence relations, allowing for the definition of a notion of entailment (see [ 16 ]), called preferential closure; on the other hand, (RM) is not preserved under intersection, and not every rational consequence relation describes a desirable and intuitive form of reasoning. Two main constructions have been proposed to define interesting and well-behaved rational consequence relations: the rational closure in [ 17 ], and the lexicographic closure in [ 18 ].

Lehmann and Magidor’s rational closure operation behaves in an intuitive way and it is logically strongly characterized (we refer the reader to [ 17, 9 ] for a description of

3 Read B as ‘Bird’, P as ‘Penguin’ and F as ‘Flying’.

rational closure). Notwithstanding, rational closure is considered a too weak form of reasoning, since often we cannot derive intuitive conclusions from our premises. The main problem of the rational closure is that if an individual falls under an atypical subclass (for example, penguins are an atypical subclass of birds, since they do not fly), we cannot associate to it any of the typical properties characterizing the superclass. Example 2. Consider the KB in example 1, and add to the set B the sequent Bj T (read T as ‘Has feathers’). Even if it would be desirable to conclude that penguins have feathers (P j T ), in the rational closure it is not possible, since penguins, being atypical birds, are not allowed to inherit any of the typical properties of birds.

Rational closure fails to respect the presumption of independence ([ 18 ], pp.63-64): even if a class does not satisfy a typical property of a superclass, we should presume that it behaves in a typical way w.r.t. the other properties, if not forced to conclude the contrary. In an attempt to overcome such a shortcoming, Lehmann has proposed in [ 18 ] a possible extension of rational closure, in order to preserve the desirable logical properties of rational closure, but augmenting in an intuitive way its inferential power. Lexicographic Closure. In this paragraph we are going to present the procedure to define the lexicographic closure of a conditional knowledge base. Our procedure just slightly generalizes the one in [ 18 ], considering also knowledge bases K = hT ; Bi with a strict part T .

The essence of the procedure to build the lexicographic closure of K consists in transforming hT ; Bi into a KB h ; i, where and are sets containing formulae instead of sequents; that is, contains what we are informed to be necessarily true, while contains the formulae we consider to be typically, but not necessarily true. Once we have defined the pair h ; i, we can easily define from it the lexicographic closure of K.

So, consider hT ; Bi, with B = fC1j E1; : : : ; Cnj Eng. The steps for the construction of h ; i (obtained by combining the construction in [ 18 ] with some results from [ 3 ]) are the following: Step 1. We transfer the information in T into correspondent j -sequents and add it to B, that is, we move from a characterization hT ; Bi to h;; B0i, where B0 = B [ f(C ^ :D)j ? j C j= D 2 T g. Intuitively, C j= D is equivalent to saying that its negation is an absurdity, i.e. (C ^ :D)j ? (see [ 3 ], Section 6.5).

Step 2. We define B0 as the set of the materializations of the sequents in B0, i.e. the material implications corresponding to such sequents: B0 = fC ! D j Cj D 2 B0g. Also, we indicate by AB0 the set of the antecedents of the sequents in B0: 0 .

AB0 = fC j Cj D 2 B g Step 3. Now we define an exceptionality ranking of sequents w.r.t. B0.

Exceptionality: Lehmann and Magidor call a formula C exceptional for a set of sequents D iff it is false in all the most typical situations satisfying D (see [ 17 ], Section 2.6); in particular, C is exceptional w.r.t. D if we can derive >j :C from the preferential closure of D. Cj D is said to be exceptional for D iff its antecedent C is exceptional for D. Exceptionality of sequents can be decided based on j= only (see [ 17 ], Corollary 5.22), as C is exceptional for a set of sequents D iff D j= :C. Given a set of sequents D, indicate by E(AD) the set of the antecedents that result exceptional w.r.t. D, that is E(AD) = fC 2 AD j D j= :Cg, and with E(D) the exceptional sequents in D, i.e. E(D) = fCj D 2 D j C 2 E(AD)g. Obviously, for every D, E(D) D.

Step 3.1. We can construct iteratively a sequence E0; E1 : : : of subsets of the conditional base B0 in the following way: E0 = B0, Ei+1 = E(Ei). Since B0 is a finite set, the construction will terminate with an empty (En = ;) or a finite (En + 1 = En 6= ;) fixed point of E.

Step 3.2. Using such a sequence, we can define a ranking function r that associates to every sequent in B0 a number, representing its level of exceptionality: r(Cj D) = i if Cj D 2 Ei and Cj D 2= Ei+1 1 if Cj D 2 Ei for every i : Step 4. In Step 3, we defined the materialization of B0 and the rank of every sequent in it. Now, Step 4.1. we can determine if B0 is inconsistent. A conditional base is inconsistent if in its preferential closure we obtain the sequent >j ? (from this sequent we can derive any other sequent using (RW) and (CM)). Given the result in Step 3.1, we can check the consistency of B0 using B0 : >j ? is in the preferential closure of B0 iff B0 j= ?.

Step 4.2. Assuming B0 is consistent, and given the ranking, we define the background theory Te of the agent as Te = f> j= :C j Cj D 2 B0 and r(Cj D) = 1g4 , and a correspondent set of formulae = f:C j > j= :C 2 Te g (one may verify that, modulo classical logical equivalence, T Te ).

Step 4.3. once we have Te , we can also identify the set of sequents Be, i.e., the defeasible part of the information contained in B0: Be = fCj D 2 B0 j r(Cj D) < 1g (one may verify that Be B). We indicate the ranking of Be as the highest ranking value of the conditionals in Be, i.e. r(Be) = maxfr(Cj D) j Cj D 2 Beg.

Essentially, so far we have moved the non-defeasible knowledge ‘hidden’ in B to T . Step 5. Now we can define the lexicographic closure of hTe ; Bei. Consider the set of the materializations of the sequents in Be, = fC ! D j Cj D 2 Beg, and assume that r(Be) = k. k represents the subset of composed by conditionals of rank k, i.e. i = fC ! D 2 j r(Cj D) = ig. We can associate to every subset D of a string of natural numbers hn0; : : : ; nkiD, where n0 =j D \ k j, and, in general, ni =j D \ k i j. In this way we obtain a string of numbers expressing how many materializations of defaults are contained in D for every ranking value. We can order linearly the tuples hn0; : : : ; nkiD using the classic lexicographic order: hn0; : : : ; nki hm0; : : : ; mki iff (i) for every i (0 i k), ni mi, or (ii) if ni < mi, there is a j s.t. j < i and nj > mj . 4 One may easily verify the correctness of this definition referring to the following results in [ 3 ], Section 7.5.3: Definition 7.5.1, the definition of clash (p.178), Corollary 7.5.7, Definition 7.5.2, and Lemma 7.5.5. It suffices to show that the set of the sequents with 1 as ranking value represents the greatest clash of B, which can be proved quite immediately by the definition of the exceptionality ranking.

This lexicographic order is based on the intuitions that the more conditionals are satisfied, the better it is, and that more exceptional conditionals have the priority over less exceptional ones. The linear ordering > between the tuples corresponds to a modular ordering between the subsets of : Seriousness ordering ([ 18 ], Definition 2). Let D and E be subsets of . D is preferred to (more serious than) E (D E ) iff hn0; : : : ; nkiD > hn0; : : : ; nkiE .

Given a conditional knowledge base hT ; Bi (transformed into h ; i) and a set of premises , we indicate by D the set of the preferred subsets of that are consistent with the certain information we have at our disposal, that is and :

D Example 3. Consider the knowledge base in the example 2: K = hT ; Bi with T = fP j= Bg and B = fP j :F; Bj F; Bj T g. We define (Step 1) the set B0 = fP ^ :Bj ?; P j :F; Bj F; Bj T g, and the ranking values obtained from the materialization of B0 are r(Bj F ) = r(Bj T ) = 0, r(P j :F ) = 1, r(P ^ :Bj ?) = 1 (Steps 2-3) . Hence, we end up with a pair h ; i, with = f:(P ^ :B)g, = 0 [ 1, 0 = fB ! F; B ! T g, and 1 = fP ! :F g (Steps 4-5). We want to check if we can derive P j T , impossible to derive from the rational closure of K. We have to find which are the most serious subsets of that are consistent with P and : it turns out that there is only one, D = fB ! T; P ! :F g, and we have fP g [ [ D j= T , that is, P j lhT ;BiT . 3

Lexicographic Closure in ALC Now we redefine Lehmann’s procedure for the DL case. We consider a significant DL representative, namely ALC (see e.g. [ 1 ], Chap. 2). ALC corresponds to a fragment of first order logic, using monadic predicates, called concepts, and diadic ones, called roles. To ease the reader in taking account of the correspondence between the procedure presented in Section 2 and the proposal in ALC, we are going to use the same notation for the components playing an analogous role in the two constructions: capital letters C; D; E; : : : now indicate concepts, instead of propositions, and j= and j to indicate, respectively, the ‘classical’ consequence relation of ALC and a non-monotonic consequence relation in ALC. We have a finite set of concept names C, a finite set of role names R and the set L of ALC -concepts is defined inductively as follows: (i) C L; (ii) >; ? 2 L; (iii) C; D 2 L ) C u D; C t D; :C 2 L; and (iii) C 2 L; R 2 R ) 9R:C; 8R:C 2 L. Concept C ! D is used as a shortcut of :C t D. The symbols u and t correspond, respectively, to the conjunction ^ and the disjunction _ of classical logic. Given a set of individuals O, an assertion is of the form a:C (C 2 L) or of the form (a; b):R (R 2 R), respectively indicating that the individual a is an instance of concept C, and that the individuals a and b are connected by the role R. A general inclusion axiom (GCI) is of the form C v D (C; D 2 L) and indicates that any instance of C is also an instance of D. We use C = D as a shortcut of the pair of C v D and D v C.

From a FOL point of view, concepts, roles, assertions and GCIs, may be seen as formulae obtained by the following transformation (a:C) = (a; C) ((a; b):R) = R(a; b) (C v D) = 8x: (x; C) ! (x; D) (x; A) = A(x) (x; :C) = : (x; C) (x; C u D) = (x; C) ^ (x; D) (x; C t D) = (x; C) _ (x; D) (x; 9R:C) = 9y:R(x; y) ^ (y; C) (x; 8R:C) = 8y:R(x; y) ! (y; C) : Now, a classical knowledge base is defined by a pair K = hA; T i, where T is a finite set of GCIs (a TBox) and A is a finite set of assertions (the ABox), whereas a defeasible knowledge base is represented by a triple K = hA; T ; Bi, where additionally B is a finite set of defeasible inclusion axioms of the form C @ D (‘an instance of a concept C is typically an instance of a concept D’ ), with C; D 2 L.

Example 4. Consider Example 3. Just add a role P rey in the vocabulary, where a role instantiation (a; b):P rey is read as ‘a preys on b’, and add also two more concepts, I (Insect) and F i (Fish). A defeasible KB is K = hA; T ; Bi with A = fa:P ; b:B, (a; c):P rey; (b; c):P reyg; T = fP v B; I v :F ig and B = fP @ :F , B @ F , B @ T , P @ 8P rey:F i; B @ 8P rey:Ig. 2 The particular structure of a defeasible KB allows for the ‘isolation’ of the pair hT ; Bi, that we could call the conceptual system of the agent, from the information about the individuals (formalised in A) that will play the role of the facts known to be true. In the next section we are going to work with the information about concepts hT ; Bi first, exploiting the immediate analogy with the homonymous pair of Section 2, then we will address the case involving individuals as well.

Construction of the Lexicographic Closure. We apply to hT ; Bi a procedure analogous to the propositional one, in order to obtain from hT ; Bi a pair h ; i, where and are two sets of concepts, the former representing the background knowledge, that is, concepts necessarily applying to each individual, the latter playing the role of defaults, that is, concepts that, modulo consistency, apply to each individual. Hence, starting with hT ; Bi, we apply the following steps.

Step 1. Define B0 = B [ fC u :D @ ? j C v D 2 T g. Now our agent is characterized by the pair h;; B0i.

Step 2. Define B0 = f> v C ! D j C @ D 2 B0g, and define a set AB0 as the set of the antecedents of the conditionals in B0, i.e. AB0 = fC j C @ D 2 B g 0 .

Step 3. We determine the exceptionality ranking of the sequents in B0 using the set of the antecedents AB0 and the materializations in B0 , where a concept C is exceptional w.r.t. a set of sequents D iff D j= > v :C. The steps are the same of the propositional case (Steps 3.1 – 3.2), we just replace the expression D j= :C with the expression D j= > v :C. In this way we define a ranking function r. Step 4. From B0 and the ranking function r we obtain (i) that (Step 4.1.) we can verify if the conceptual system of the agent is consistent by checking the consistency of

B0 , and (ii) (Steps 4.2.-4.3.) we can define the real background theory and the defeasible information of the agent, respectively the sets Te and Be as: From Te and Be we define the correspondent sets of concepts = f:C j > v :C 2

Te g and = fC ! D j C @ D 2 Beg.

Step 5. Now, obtained h ; i and the ranking value of the elements of Be and, consequently, of (assume r(Be) = k), we can determine the seriousness ordering on the subsets of . The procedure is the same as for the propositional case, that is, (i) we associate to every subset D of a string hn0; : : : ; nki with ni =j D \ k i j, and we obtain a lexicographic order ‘>’ between the strings. Then we define the seriousness ordering between the subsets of as

D

E iff hn0; : : : ; nkiD > hn0; : : : ; nkiE for every pair of subsets D and E of .

Hence, we obtain an analogous of the procedure defined for the propositional case by substituting the conceptual system hT ; Bi with the pair h ; i.

Closure Operation over Concepts. Consider the pair h ; i. Now we specify the nol that tells us tion of lexicographic closure over the concepts, that is, a. Areglaaitnio,nwje dhTefi;Bnie for a set of what presumably follows from a finite set of concepts premises the set of the most serious subsets of that are consistent with and .

D

We can prove two main properties characterizing the proposition lexicographic closure and respected by j lhT ;Bi: (i) j lhT ;Bi is a rational consequence relation, and (ii) j lhT ;Bi extends the rational closure.

Proposition 1. j hTe;Bei is a rational consequence relation validating K = hT ; Bi.

(LLE) (CT) (OR) (REF) Cj hT ; iC C j hT ; i E

j= C = D D j hT ; i E

C j hT ; i E C j hT ; i E

D j hT ; i E

C t D j hT ; i E This can be shown by noting that the analogous properties of the propositional rational consequence relation are satisfied, namely: (RW) (CM) (RM)

C j hT ; i D

j= D v E

C j hT ; i E

C u D j hT ; i E C j hT ; i D

C 6 j hT ; i:E C u E j hT ; i D C u D j hT ; i E

C j hT ; i D

C j hT ; i E

C j hT ; i D For the rational closure in ALC, we refer to the construction presented in [ 9 ], Section 3. We indicate by j hrT ;Bi the consequence relation defined there. r Proposition 2. The lexicographic closure extends the rational closure, i.e. j hT ;Bi j lhT ;Bi for every pair hT ; Bi.

To prove this it is sufficient to check that, given a set of premises and a pair h ; i, each of the sets in D classically implies the default information that would be associated to in its rational closure, as defined in [ 9 ].

Let us work out the analogue of Example 3 in the DL context.

Example 5. Consider the KB of Example 4 without the ABox. Hence, we start with K = hT ; Bi. Then K is changed into B0 = fP u:B @ ?; IuF i @ ?, P @ :F , B @ F , B @ T , P @ 8P rey:F i; B @ 8P rey:Ig. The set of the materializations of B0 is

B0 = f> v P ^ :B ! ?; > v I u F i ! ?; > v P ! :F; > v B ! F; > v B ! T; > v P ! 8P rey:F i; > v B ! 8P rey:Ig, with AB0 = fP ^ :B; I u F i; P; Bg. Following the procedure at Step 3, we obtain the ranking values of every inclusion axiom in B0: namely, r(B @ F ) = r(B @ T ) = r(B @ 8P rey:I) = 0; r(P @ :F ) = r(P @ 8P rey:F i) = 1 and r(P u :B @ ?) = r(I u F i @ ?) = 1. From such a ranking, we obtain a background theory = f:(P ^ :B); :(I u F i)g, and a default set = 0 [ 1, with 0 = fB ! F; B ! T; B ! 8P rey:Ig 1 = fP ! :F; P ! 8P rey:F ig : To check if P j lhT ;BiT , we have to find the most serious subsets of that are consistent with P and the concepts in (i.e. the most serious subsets D of s.t. 6j= d u d u d D v ?). Turns out that there is only one, D = fP ! :F; P ! 8P rey:F i; B ! T g, and j= P u d u d D v T .

It is easy to check that we obtain the analogue sequents as in the propositional case and avoid the same undesirable ones. Moreover we can derive also sequents connected to the roles, such as Bj lhT ;Bi8P rey::F i and P j lhT ;Bi8P rey::I. 2 We do not have yet a proper proof, but we conjecture that the decision procedure should be EXPTIME-complete also in ALC.

Closure Operation over Individuals. Now we will pay attention on how to apply the lexicographic closure to the ABox. Unfortunately, the application of the lexicographic closure to the ABox results into a really more complicated procedure than in the case of rational closure, as presented in the last paragraph of [ 9 ], Section 3. Assume that we have already transformed our conceptual system hT ; Bi into a pair hTe ; Bei, and eventually into a pair h ; i. In particular, dealing with the ABox, we assume that we start with a knowledge base K = hA; Te ; i. We would like to infer whether a certain individual a is presumably an instance of a concept C or not. The basic idea remains to associate to every individual in A every default information from that is consistent with our knowledge base, respecting the seriousness ordering of the subsets of . As we will see, the major problem to be addressed here is that we cannot obtain anymore a unique lexicographic extension of the KB.

Example 6. Consider K = hA; ;; i, with A = f(a; b):Rg and = fA u 8R::Ag. Informally, if we apply the default to a first, we get b::A and we cannot apply the default to b, while if we apply the default to b first, we get b:A and we cannot apply the default to a. Hence, we may have two extensions. 2 The possibility of multiple extensions is due to the presence of the roles, that allow the transmission of information from an individual to another; if every individual was ‘isolated’, without role-connections, then the addition of the default information to each individual would have been a ‘local’ problem, treatable without considering the concepts associated to the other individuals in the domain, and the extension of the knowledge base would have been unique. On the other hand, while considering a specific individual, the presence of the roles forces to consider also the information associated to other individuals in order to maintain the consistency of the knowledge base, and, as shown in example 6, the addition of default information to one individual could prevent the association of default information to another.

We assume that hA; T i is consistent, i.e. hA; T i 6j= a:?, for any a. With OA we indicate the individuals occurring in A. Given K = hA; T ; i, we say that a knowledge base Ke = hA ; T i is a default extension of K iff – Ke is classically consistent and A – For any a 2 OA, a:C 2 A fa:D0g; T i j= ? for every D0

A . n A iff C = d D for some D , with D0 D.

s.t. hA [ Essentially, we assign to each individual a 2 OA one of the most serious default sets that are consistent with the ABox.

Ke1 = hA [ fa:A; a:8R::Ag; ;i and Ke2 = hA [ fb:A; b:8R::Ag; ;i.

Example 7. Referring to Example 6, consider K = hA; ;; i, with A = f(a; b) : Rg and = fA u 8R::A; >g. Then we have two default-assumption extensions, namely 2 A procedure to obtain a set As of default extensions is as follows: (i) fix a linear order s = ha1; : : : ; ami of the individuals in OA, and let As0 = fAg.

Now, for every ai, 1

i

m, do: (ii) for every element X of Ais 1, find the set all the -minimal default sets fD1; : : : ; Dng, s.t. Dj and X [ fai:d Dj g is consistent (1 j n);

(iii) Define a new set Ais containing all the sets X [ fai:d Dj g obtained at the point (ii).

(iv) Move to the next individual ai+1.

(v) Once the points (ii)-(iv) have been applied to all the individuals in the sequence s = ha1; : : : ; ami, set As = Asm, where Asm is the final set obtained at the end of the procedure.

It can be shown that

Proposition 3. An Abox A0 is a default extension of K = fA; g iff it is in the set As obtained by some linear ordering s on OA and the above procedure.

For instance, related to Example 7, Ke1 is obtained from the order ha; bi, while Ke2 is obtained from the order hb; ai.

Example 8. Refer to Example 5, and let K = fA; T ; g, where A = fa:P , b:B, (a; c):P rey, (b; c):P reyg, T = fP v B; I v :F ig, = fB ! F; B ! T; B ! 8P rey:I; P ! :F; P ! 8P rey:F ig. If we consider an order where a is before b then we associate D = fB ! T; P ! :F; P ! 8P rey:F ig to a, and consequently c is presumed to be a fish and we are prevented in the association of B ! 8P rey:I to b. If we consider b before a, c is not a fish and we cannot apply P ! 8P rey:F i to a. 2 If we fix a priori a linear order s on the individuals, we may define a consequence relation depending on the default extensions generated from it, i.e. the sets of defaults in As: we say that a:C is a defeasible consequence of K = hA; T ; i w.r.t. s, written K ls a:C, iff A j 0 = a:C for every A 2 As.

For instance, related to Example 7 and order s1 = ha; bi, we may infer that K while with order s2 = hb; ai, we may infer that K ls2 b:A.

The interesting point of such a consequence relation is that it satisfies the properties of a rational consequence relation in the following way. ls1 a:A, REFDL hA; i s a:C for every a:C 2 A LLEDL hA [ fb:Dg; i s a:C D = E

hA [ fb:Eg; i s a:C RWDL CTDL hA; i s a:C C v D

hA; i s a:D hA [ fb:Dg; i s a:C hA; i s b:D

hA; i s a:C

We can show that

CMDL hA; i s a:C hA; i s b:D hA [ fb:Dg; i s a:C

ORDL hA [ fb:Dg; i s a:C hA [ fb:Eg; i s a:C

hA [ fb:D t Eg; i s a:C

RMDL hA; i s a:C hA; i 6 s b::D

hA [ fb:Dg; i s a:C Proposition 4. Given K and a linear order s of the individuals in K, the consequence relation ls satisfies the properties REFDL RMDL.

Conclusions

In this paper we have proposed an extension of a main non-monotonic construction, the lexicographic closure (see [ 18 ]), for the DL ALC. This work carries forward the approach presented in [ 9 ], where the adaptation of the rational closure in ALC is presented. Here we have first presented the procedure at the propositional level, and then we have adapted it for ALC, first considering only the conceptual level, the information contained in the TBox, and then considering also the particular information about the individuals, the ABox, assuming we are working with unfoldable KB.

It is straightforward to see that, while the procedure defined for the TBox is simple and well-behaved, the procedure for the ABox is really more complex than the one for the rational closure presented in [ 9 ].

Besides checking the exact costs of these procedures from the computational point of view and checking for which other DL formalisms we can apply them, we conjecture that a semantical characterization of the above procedures can be obtained using the kind of semantical constructions presented in [ 8 ].

References

1. Franz Baader , Diego Calvanese, Deborah McGuinness , Daniele Nardi , and Peter PatelSchneider . The Description Logic Handbook: Theory, Implementation and Applications . Cambridge University Press, 2003 .

2. Franz Baader and Bernhard Hollunder . How to prefer more specific defaults in terminological default logic . In In Proceedings of the IJCAI , pages 669 - 674 . Morgan Kaufmann Publishers, 1993 .

3. Alexander Bochman . A logical theory of nonmonotonic inference and belief change . Springer-Verlag New York, Inc., New York, NY, USA, 2001 .

4. P. Bonatti , C. Lutz , and F. Wolter . The complexity of circumscription in description logic . Journal of Artificial Intelligence Research , 35 : 717 - 773 , 2009 .

5. Piero A. Bonatti , Marco Faella, and Luigi Sauro . Defeasible inclusions in low-complexity dls . J. Artif. Intell. Res. (JAIR) , 42 : 719 - 764 , 2011 .

6. Piero A. Bonatti , Marco Faella, and Luigi Sauro . On the complexity of el with defeasible inclusions . In IJCAI-11 , pages 762 - 767 . IJCAI/AAAI, 2011 .

7. Gerhard Brewka and D Sankt Augustin . The logic of inheritance in frame systems . In IJCAI87 , pages 483 - 488 . Morgan Kaufmann Publishers, 1987 .

8. K. Britz , T. Meyer, and I. Varzinczak. Semantic foundation for preferential description logics . In D. Wang and M. Reynolds, editors, Proceedings of the 24th Australasian Joint Conference on Artificial Intelligence, number 7106 in LNAI , pages 491 - 500 . Springer, 2011 .

9. Giovanni Casini and Umberto Straccia . Rational closure for defeasible description logics . In Tomi Janhunen and Ilkka Niemela¨, editors, JELIA , volume 6341 of Lecture Notes in Computer Science, pages 77 - 90 . Springer, 2010 .

10. Giovanni Casini and Umberto Straccia . Defeasible inheritance-based description logics . In IJCAI-11 , pages 813 - 818 , 2011 .

11. Francesco M. Donini , Daniele Nardi, and Riccardo Rosati . Description logics of minimal knowledge and negation as failure . ACM Trans. Comput. Log. , 3 ( 2 ): 177 - 225 , 2002 .

12. Dov M. Gabbay , C. J. Hogger , and J. A . Robinson, editors. Handbook of logic in artificial intelligence and logic programming (vol. 3): nonmonotonic reasoning and uncertain reasoning . Oxford University Press, Inc., New York, NY, USA, 1994 .

13. Laura Giordano , Valentina Gliozzi, Nicola Olivetti, and Gian Luca Pozzato. Reasoning about typicality in low complexity dls: The logics el;tmin and dl-litec tmin . In IJCAI , pages 894 - 899 . IJCAI/AAAI, 2011 .

14. Laura Giordano , Nicola Olivetti, Valentina Gliozzi, and Gian Luca Pozzato. Alc + t: a preferential extension of description logics . Fundam . Inform., 96 ( 3 ): 341 - 372 , 2009 .

15. S. Grimm and P. Hitzler . A preferential tableaux calculus for circumscriptive ALCO . In RR-09, number 5837 in LNCS , pages 40 - 54 , Berlin, Heidelberg, 2009 . Springer-Verlag.

16. Sarit Kraus , Daniel Lehmann, and Menachem Magidor . Nonmonotonic reasoning, preferential models and cumulative logics . Artif . Intell., 44 ( 1-2 ): 167 - 207 , 1990 .

17. Daniel Lehmann and Menachem Magidor . What does a conditional knowledge base entail? Artif . Intell., 55 ( 1 ): 1 - 60 , 1992 .

18. Daniel J. Lehmann . Another perspective on default reasoning . Ann. Math. Artif. Intell., 15 ( 1 ): 61 - 82 , 1995 .

19. David Makinson . General patterns in nonmonotonic reasoning. In Handbook of logic in artificial intelligence and logic programming: nonmonotonic reasoning and uncertain reasoning , volume 3 , pages 35 - 110 . Oxford University Press, Inc., New York, NY, USA, 1994 .

20. David Poole . A logical framework for default reasoning . Artif. Intell., 36 ( 1 ): 27 - 47 , 1988 .

21. Joachim Quantz and Veronique Royer . A preference semantics for defaults in terminological logics . In KR-92 , pages 294 - 305 . Morgan Kaufmann, Los Altos, 1992 .

22. U. Straccia . Default inheritance reasoning in hybrid kl-one-style logics . IJCAI-93 , pages 676 - 681 , 1993 .