=Paper=
{{Paper
|id=None
|storemode=property
|title=Lexichographic Closure for Defeasible Description Logics
|pdfUrl=https://ceur-ws.org/Vol-969/paper3.pdf
|volume=Vol-969
}}
==Lexichographic Closure for Defeasible Description Logics==
https://ceur-ws.org/Vol-969/paper3.pdf
Lexicographic Closure for Defeasible Description Logics
Giovanni Casini1 and Umberto Straccia2
1
Centre for Artificial Intelligence Research, CSIR Meraka Institute and UKZN, South Africa
Email: GCasini@csir.co.za
2
Istituto di Scienza e Tecnologie dell’Informazione (ISTI - CNR), Pisa, Italy
Email: straccia@isti.cnr.it
Abstract. In the field of non-monotonic logics, the lexicographic closure is ac-
knowledged 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.
1 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 well-
known 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.
2 Propositional Lexicographic Closure
Let ` be a finitely generated classical propositional language, defined in the usual way
using ¬, ∧, ∨, → as connectives, C, D, . . . as sentences, Γ, ∆, . . . as finite sets of sen-
tences, > and ⊥ as abbreviations for, respectively, A ∨ ¬A and A ∧ ¬A for some A.
The symbols |= and |∼ will indicate, respectively, the classical consequence relation and
a defeasible consequence relation. An element of a consequence relation, Γ |= C or
Γ |∼C, will be called a sequent, and in the case of |∼ it has to be read as ‘If Γ , then
typically C’.
We call conditional knowledge base a pair hT , Bi, where T is a set of strict sequents
C |= D, representing certain knowledge, and B is a set of defeasible sequents C|∼D,
representing default information.
Example 1. The typical ‘penguin’ example can be encoded as 3 : K = hT , Bi with T =
{P |= B} and B = {P |∼¬F, B|∼F }. 2
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 |= 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 ra-
tional 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 iden-
tification 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 con-
sequence relation |∼ is rational iff it satisfies the following properties:
(REF) C|∼C Reflexivity
C|∼D D |= F
C|∼D C ∧ D|∼F (RW) Right Weakening
(CT) Cut (Cumulative Trans.) C|∼F
C|∼F
C|∼F D|∼F
C|∼D C|∼F (OR) Left Disjunction
(CM) Cautious Monotony C ∨ D|∼F
C ∧ D|∼F
C|∼F C 6 |∼¬D
C|∼F |= C ↔ D (RM) Rational Monotony
(LLE) Left Logical Equival. C ∧ D|∼F
D|∼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 character-
ization 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 = {C1 |∼E1 , . . . , Cn |∼En } 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 par-
ticular 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]). Ex-
cept 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 pre-
served under intersection, and not every rational consequence relation describes a de-
sirable 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 sub-
class (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 B|∼T
(read T as ‘Has feathers’). Even if it would be desirable to conclude that penguins have
feathers (P |∼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 = {C1 |∼E1 , . . . , Cn |∼En }. The steps for the construc-
tion 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 |∼-sequents and add it to
B, that is, we move from a characterization hT , Bi to h∅, B 0 i, where B 0 = B ∪
{(C ∧ ¬D)|∼⊥ | C |= D ∈ T }. Intuitively, C |= D is equivalent to saying that its
negation is an absurdity, i.e. (C ∧ ¬D)|∼⊥ (see [3], Section 6.5).
Step 2. We define ∆B0 as the set of the materializations of the sequents in B 0 , i.e. the
material implications corresponding to such sequents: ∆B0 = {C → D | C|∼D ∈
B 0 }. Also, we indicate by AB0 the set of the antecedents of the sequents in B 0 :
AB0 = {C | C|∼D ∈ B 0 }.
Step 3. Now we define an exceptionality ranking of sequents w.r.t. B 0 .
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 >|∼¬C from
the preferential closure of D. C|∼D is said to be exceptional for D iff its antecedent
C is exceptional for D. Exceptionality of sequents can be decided based on |= only
(see [17], Corollary 5.22), as C is exceptional for a set of sequents D iff ∆D |= ¬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 ) = {C ∈ AD | ∆D |= ¬C}, and with E(D) the
exceptional sequents in D, i.e. E(D) = {C|∼D ∈ D | C ∈ E(AD )}. Obviously,
for every D, E(D) ⊆ D.
Step 3.1. We can construct iteratively a sequence E0 , E1 . . . of subsets of the con-
ditional base B 0 in the following way: E0 = B 0 , Ei+1 = E(Ei ). Since B 0 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 B 0 a number, representing its level of exceptionality:
i if C|∼D ∈ Ei and C|∼D ∈ / Ei+1
r(C|∼D) =
∞ if C|∼D ∈ Ei for every i .
Step 4. In Step 3, we defined the materialization of B 0 and the rank of every sequent in
it. Now,
Step 4.1. we can determine if B 0 is inconsistent. A conditional base is inconsistent
if in its preferential closure we obtain the sequent >|∼⊥ (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 B 0 using ∆B0 : >|∼⊥ is in the preferential
closure of B 0 iff ∆B0 |= ⊥.
Step 4.2. Assuming B 0 is consistent, and given the ranking, we define the back-
ground theory Te of the agent as Te = {> |= ¬C | C|∼D ∈ B 0 and r(C|∼D) =
∞}4 , and a correspondent set of formulae Φ = {¬C | > |= ¬C ∈ Te } (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 B,
e i.e., the defea-
sible part of the information contained in B : B = {C|∼D ∈ B 0 | r(C|∼D) <
0 e
∞} (one may verify that Be ⊆ B). We indicate the ranking of Be as the highest
ranking value of the conditionals in B, e i.e. r(B)
e = max{r(C|∼D) | C|∼D ∈
B}.
e
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 , Bi. e Consider the set of the
materializations of the sequents in B, e ∆ = {C → D | C|∼D ∈ B}, e and assume
that r(B) e = k. ∆k represents the subset of ∆ composed by conditionals of rank k,
i.e. ∆i = {C → D ∈ ∆ | r(C|∼D) = i}. We can associate to every subset D of ∆
a string of natural numbers hn0 , . . . , nk iD , where n0 =| D ∩ ∆k |, and, in general,
ni =| D ∩ ∆k−i |. 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 , . . . , nk iD using the classic lexicographic order:
hn0 , . . . , nk i ≥ hm0 , . . . , mk i 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 ∞ 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 , . . . , nk iD > hn0 , . . . , nk iE .
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Γ = min{D ⊆ ∆ | Γ ∪ Φ ∪ D 6|= ⊥}
≺
l
The consequence relation |∼hT ,Bi , corresponding to the lexicographic closure of
hT , Bi, will be defined as:
l
Γ |∼hT ,Bi E iff Γ ∪ Φ ∪ D |= E for every D ∈ DΓ .
The procedure proposed by Lehmann relies heavily on a proposal by Poole, [20],
but it makes also use of the cardinality and the exceptionality ranking of the sets of
defaults. At the propositional level, the problem of deciding if a sequent C|∼D is in the
lexicographic closure of a conditional base K = hT , Bi is exponential (see [18], p.81).
Example 3. Consider the knowledge base in the example 2: K = hT , Bi with T =
{P |= B} and B = {P |∼¬F, B|∼F, B|∼T }. We define (Step 1) the set B 0 = {P ∧
¬B|∼⊥, P |∼¬F, B|∼F, B|∼T }, and the ranking values obtained from the materializa-
tion of B 0 are r(B|∼F ) = r(B|∼T ) = 0, r(P |∼¬F ) = 1, r(P ∧ ¬B|∼⊥) = ∞ (Steps
2-3) . Hence, we end up with a pair hΦ, ∆i, with Φ = {¬(P ∧ ¬B)}, ∆ = ∆0 ∪ ∆1 ,
∆0 = {B → F, B → T }, and ∆1 = {P → ¬F } (Steps 4-5). We want to check if we
can derive P |∼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 = {B → T, P → ¬F }, and we have {P } ∪ Φ ∪ D |= T , that
l
is, P |∼hT ,Bi T .
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 proce-
dure 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 |= and |∼ to in-
dicate, 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) >, ⊥ ∈ L; (iii) C, D ∈ L ⇒ C u D, C t D, ¬C ∈ L; and (iii)
C ∈ L, R ∈ R ⇒ ∃R.C, ∀R.C ∈ 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 ∈ L) or of the form (a, b):R (R ∈ 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 ∈ 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)
τ (x, C u D) = τ (x, C) ∧ τ (x, D)
τ ((a, b):R) = R(a, b)
τ (x, C t D) = τ (x, C) ∨ τ (x, D)
τ (C v D) = ∀x.τ (x, C) → τ (x, D)
τ (x, ∃R.C) = ∃y.R(x, y) ∧ τ (y, C)
τ (x, A) = A(x)
τ (x, ∀R.C) = ∀y.R(x, y) → τ (y, C) .
τ (x, ¬C) = ¬τ (x, 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 ∈ 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 = {a:P , b:B,
(a, c):P rey, (b, c):P rey}; T = {P v B, I v ¬F i} and B = {P @ ∼ ¬F , B @
∼ F,
B@ ∼ T, P @ ∼ ∀P rey.F i, B @ ∼ ∀P rey.I}. 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 analo-
gous 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 B 0 = B ∪{C u¬D @ ∼ ⊥ | C v D ∈ T }. Now our agent is characterized
by the pair h∅, B 0 i.
Step 2. Define ∆B0 = {> v C → D | C @ ∼ D ∈ B 0 }, and define a set AB0 as the set
of the antecedents of the conditionals in B 0 , i.e. AB0 = {C | C @
∼ D ∈ B 0 }.
Step 3. We determine the exceptionality ranking of the sequents in B 0 using the set of
the antecedents AB0 and the materializations in ∆B0 , where a concept C is excep-
tional w.r.t. a set of sequents D iff ∆D |= > v ¬C. The steps are the same of the
propositional case (Steps 3.1 – 3.2), we just replace the expression ∆D |= ¬C with
the expression ∆D |= > 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:
∼ D ∈ B 0 and r(C @
Te = {> v ¬C | C @ ∼ D) = ∞}
Be = {C @
∼D|C@ ∼ D ∈ B 0 and r(C|∼D) < ∞} .
From Te and Be we define the correspondent sets of concepts Φ = {¬C | > v ¬C ∈
Te } and ∆ = {C → D | C @ ∼ D ∈ B}.e
Step 5. Now, obtained hΦ, ∆i and the ranking value of the elements of Be and, conse-
quently, of ∆ (assume r(B)
e = 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 , . . . , nk i with ni =| D ∩ ∆k−i |,
and we obtain a lexicographic order ‘>’ between the strings. Then we define the
seriousness ordering ≺ between the subsets of ∆ as
D ≺ E iff hn0 , . . . , nk iD > hn0 , . . . , nk iE
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 no-
l
tion of lexicographic closure over the concepts, that is, a relation |∼hT ,Bi that tells us
what presumably follows from a finite set of concepts Γ . Again, we define for a set of
premises Γ the set of the most serious subsets of ∆ that are consistent with Γ and Φ.
l l l
DΓ = min{D ⊆ ∆ | 6|= Γu Φu D v ⊥}
≺
Having obtained DΓ , the lexicographic closure is defined as follows:
Γ |∼lhT ,Bi E iff |=
d d d
Γu Φu D v E for every D ∈ DΓ .
We can prove two main properties characterizing the proposition lexicographic closure
l l l
and respected by |∼hT ,Bi : (i) |∼hT ,Bi is a rational consequence relation, and (ii) |∼hT ,Bi
extends the rational closure.
Proposition 1. |∼hTe ,Bi
e is a rational consequence relation validating K = hT , Bi.
This can be shown by noting that the analogous properties of the propositional rational
consequence relation are satisfied, namely:
(REF) C|∼hT ,∆i C
C |∼hT ,∆i E |= C = D C |∼hT ,∆i D |= D v E
(LLE) (RW)
D |∼hT ,∆i E C |∼hT ,∆i E
C u D |∼hT ,∆i E C |∼hT ,∆i D C |∼hT ,∆i E C |∼hT ,∆i D
(CT) (CM)
C |∼hT ,∆i E C u D |∼hT ,∆i E
C |∼hT ,∆i E D |∼hT ,∆i E C |∼hT ,∆i D C 6 |∼hT ,∆i ¬E
(OR) (RM)
C t D |∼hT ,∆i E C u E |∼hT ,∆i D
For the rational closure in ALC, we refer to the construction presented in [9], Section 3.
r
We indicate by |∼hT ,Bi the consequence relation defined there.
r
Proposition 2. The lexicographic closure extends the rational closure, i.e. |∼hT ,Bi ⊆
l
|∼hT ,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 associ-
ated 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 B 0 = {P u¬B @∼ ⊥, IuF i @
∼ ⊥, P @∼ ¬F , B @∼ F,
B @ ∼ T, P @ ∼ ∀P rey.I}. The set of the materializations of B 0 is
∼ ∀P rey.F i, B @
∆B0 = {> v P ∧ ¬B → ⊥, > v I u F i → ⊥, > v P → ¬F, > v B → F, > v B →
T, > v P → ∀P rey.F i, > v B → ∀P rey.I}, with AB0 = {P ∧ ¬B, I u F i, P, B}.
Following the procedure at Step 3, we obtain the ranking values of every inclusion
axiom in B 0 : namely, r(B @
∼ F ) = r(B @∼ T ) = r(B @
∼ ∀P rey.I) = 0; r(P @∼ ¬F ) =
r(P @∼ ∀P rey.F i) = 1 and r(P u ¬B @ ∼ ⊥) = r(I u F i @
∼ ⊥) = ∞. From such a
ranking, we obtain a background theory Φ = {¬(P ∧ ¬B), ¬(I u F i)}, and a default
set ∆ = ∆0 ∪ ∆1 , with
∆0 = {B → F, B → T, B → ∀P rey.I}
∆1 = {P → ¬F, P → ∀P rey.F i} .
l
To check if P |∼hT ,Bi T , we have to find the most serious subsets of ∆ that are consistent
d d
d P and the concepts in Φ (i.e. the most serious subsets D of ∆ s.t. 6|= Γ u Φ u
with
D v ⊥). Turns
d d that there is only one, D = {P → ¬F, P → ∀P rey.F i, B → T },
out
and |= P u Φ u 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
l l
roles, such as B|∼hT ,Bi ∀P rey.¬F i and P |∼hT ,Bi ∀P 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 , Bi, e 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 = {(a, b):R} and ∆ = {A u ∀R.¬A}.
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 6|= 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
– K
e is classically consistent and A ⊆ A∆ .
d
– For any a ∈ OA , a:C ∈ A∆ \ A iff C = D for some D ⊂ ∆ s.t. hA∆ ∪
0 0 0
{a:D }, T i |= ⊥ for every D ⊆ ∆, with D ≺ D.
Essentially, we assign to each individual a ∈ OA one of the most serious default sets
that are consistent with the ABox.
Example 7. Referring to Example 6, consider K = hA, ∅, ∆i, with A = {(a, b) : R}
and ∆ = {A u ∀R.¬A, >}. Then we have two default-assumption extensions, namely
K
e 1 = hA ∪ {a:A, a:∀R.¬A}, ∅i and Ke 2 = hA ∪ {b:A, b:∀R.¬A}, ∅i. 2
A procedure to obtain a set As of default extensions is as follows:
(i) fix a linear order s = ha1 , . . . , am i of the individuals in OA , and let A0s = {A}.
Now, for every ai , 1 ≤ i ≤ m, do:
(ii) for every element X of Adi−1
s , find the set all the ≺-minimal default sets {D1 , . . . ,
Dn }, s.t. Dj ⊆ ∆ and X ∪ {ai : Dj } is consistent (1 ≤ j ≤ n);
d
(iii) Define a new set Ais containing all the sets X ∪ {ai : Dj } 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 , . . . , am i, set As = Am m
s , where As 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 = {A, ∆} 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, K
e 1 is obtained from the order ha, bi, while K
e 2 is
obtained from the order hb, ai.
Example 8. Refer to Example 5, and let K = {A, T , ∆}, where A = {a:P , b:B,
(a, c):P rey, (b, c):P rey}, T = {P v B, I v ¬F i}, ∆ = {B → F, B → T, B →
∀P rey.I, P → ¬F, P → ∀P rey.F i}. If we consider an order where a is before b then
we associate D = {B → T, P → ¬F, P → ∀P rey.F i} to a, and consequently c is
presumed to be a fish and we are prevented in the association of B → ∀P rey.I to b. If
we consider b before a, c is not a fish and we cannot apply P → ∀P 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 A0 |= a:C for every A ∈ As .
For instance, related to Example 7 and order s1 = ha, bi, we may infer that K ls1 a:A,
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.
REFDL hA, ∆i s a:C for every a:C ∈ A
hA, ∆i s a:C hA, ∆i s b:D
hA ∪ {b:D}, ∆i s a:C D = E CMDL
hA ∪ {b:D}, ∆i s a:C
LLEDL
hA ∪ {b:E}, ∆i s a:C
hA ∪ {b:D}, ∆i s a:C hA ∪ {b:E}, ∆i s a:C
hA, ∆i s a:C C v D ORDL
hA ∪ {b:D t E}, ∆i s a:C
RWDL
hA, ∆i s a:D
hA, ∆i s a:C hA, ∆i 6 s b:¬D
hA ∪ {b:D}, ∆i s a:C hA, ∆i RMDL
s b:D hA ∪ {b:D}, ∆i s a:C
CTDL
hA, ∆i s a:C
We can show that
Proposition 4. Given K and a linear order s of the individuals in K, the consequence
relation ls satisfies the properties REFDL − RMDL .
4 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 pre-
sented. 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 Patel-
Schneider. 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 IJCAI-
87, 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 Niemelä, editors, JELIA, volume 6341 of Lecture Notes in Com-
puter 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 in-
telligence 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 pref-
erential 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, preferen-
tial 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 arti-
ficial 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.