We define a modular multi-concept extension of the lexicographic closure semantics for defeasible description logics with typicality. The idea is that of distributing the defeasible properties of concepts into different modules, according to their subject, and of defining a notion of preference for each module based on the lexicographic closure semantics. The preferential semantics of the knowledge base can then be defined as a combination of the preferences of the single modules. The range of possibilities, from fine grained to coarse grained modules, provides a spectrum of alternative semantics.
Kraus, Lehmann and Magidor’s preferential logics for non-monotonic reasoning [43,
44], have been extended to description logics, to deal with inheritance with exceptions
in ontologies, allowing for non-strict forms of inclusions, called typicality or defeasible
inclusions, with different preferential and ranked semantics [
In this paper we define a modular multi-concept extension of the lexicographic closure for reasoning about exceptions in ontologies. The idea is very simple: different modules can be defined starting from a defeasible knowledge base, containing a set D of typicality inclusions (or defeasible inclusions) describing the prototypical properties of classes in the knowledge base. We will represent such defeasible inclusions as T(C) ⊑ D [30], meaning that “typical C’s are D’s” or “normally C’s are D’s”, corresponding to conditionals C |∼ D in KLM framework.
A set of modules m1, . . . , mn is introduced, each one concerning a subject, and defeasible inclusions belong to a module if they are related with its subject. By subject, here, we mean any concept of the knowledge base. Module mi with subject Ci does not need to contain just typicality inclusions of the form T(Ci) ⊑ D, but all defeasible inclusions in D which are concerned with subject Ci are admitted in mi. We call a collection of such modules a modular multi-concept knowledge base.
This modularization of the defeasible part of the knowledge base does not define a partition of the set D of defeasible inclusions, as an inclusion may belong to more ⋆ Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). than one module. For instance, the typical properties of employed students are relevant both for the module with subject Student and for the module with subject Employee . The granularity of modularization has to be chosen by the knowledge engineer who can fix how large or narrow is the scope of a module, and how many modules are to be included in the knowledge base (for instance, whether the properties of employees and students are to be defined in the same module with subject Person or in two different modules). At one extreme, all the defeasible inclusions in D can be put together in a module associated with subject ⊤ (Thing). At the other extreme, which has been studied in [35], a module mi is a defeasible TBox containing only the defeasible inclusions of the form T(Cj ) ⊑ D for some concept Ci. In this paper we remove this restriction considering general modules, containing arbitrary sets of defeasible inclusions, intuitively pertaining some subject.
In [35], following Gerard Brewka’s framework of Basic Preference Descriptions
for ranked knowledge bases [
Based on the ranked semantics of the single modules, a compositional (preferential) semantics of the knowledge base is defined by combining the multiple preference relations into a single global preference relation <. This gives rise to a modular multiconcept extension of Lehmann’s preference semantics for the lexicographic closure. When there is a single module, containing all the typicality inclusions in the knowledge base, the semantics collapses to a natural extension to DLs of Lehmann’s semantics, which corresponds to Lehmann’s semantics for the fragment of ALC without universal and existential restrictions.
We introduce a notion of entailment for modular multi-concept knowledge bases,
based on the proposed semantics, which satisfies the KLM properties of a preferential
consequence relation. This notion of entailment has good properties inherited from
lexicographic closure: it deals properly with irrelevance and specificity, and it is not subject
to the “blockage of property inheritance” problem, i.e., the problem that property
inheritance from classes to subclasses is not guaranteed, which affects the rational closure
[47]. In addition, separating defeasible inclusions in different modules provides a
simple solution to another problem of the rational closure and its refinements (including
the lexicographic closure), that was recognized by Geffner and Pearl [
The description logics ALC and its extension with typicality
In this section we recall the syntax and semantics of the description logic ALC [
Let NC be a set of concept names, NR a set of role names and NI a set of individual names. The set of ALC concepts (or, simply, concepts) can be defined inductively: - A ∈ NC , ⊤ and ⊥ are concepts; - if C and D are concepts, and r ∈ NR, then C ⊓ D, C ⊔ D, ¬C, ∀r.C, ∃r.C are concepts.
A knowledge base (KB) K is a pair (T , A), where T is a TBox and A is an ABox. The TBox T is a set of concept inclusions (or subsumptions) C ⊑ D, where C, D are concepts. The ABox A is a set of assertions of the form C(a) and r(a, b) where C is a concept, a and b are individual names in NI and r a role name in NR.
An ALC interpretation is defined as a pair I = hΔ, ·I i where: Δ is a domain—a set whose elements are denoted by x, y, z, . . . —and ·I is an extension function that maps each concept name C ∈ NC to a set CI ⊆ Δ, each role name r ∈ NR to a binary relation rI ⊆ Δ × Δ, and each individual name a ∈ NI to an element aI ∈ Δ. It is extended to complex concepts as follows: ⊤I = Δ, ⊥I = ∅, (¬C)I = Δ\CI , (∃r.C)I = {x ∈ Δ | ∃y.(x, y) ∈ rI and y ∈ CI }, (C ⊓ D)I = CI ∩ DI , (∀r.C)I = {x ∈ Δ | ∀y.(x, y) ∈ rI ⇒ y ∈ CI }, (C ⊔ D)I = CI ∪ DI . The notion of satisfiability of a KB in an interpretation and the notion of entailment are defined as follows: Definition 1 (Satisfiability and entailment). Given an ALC interpretation I = hΔ, ·I i: - I satisfies an inclusion C ⊑ D if CI ⊆ DI ; - I satisfies an assertion C(a) (resp., r(a, b)) if aI ∈ CI (resp., (aI , bI ) ∈ rI ). Given a KB K = (T , A), an interpretation I satisfies T (resp. A) if I satisfies all inclusions in T (resp. all assertions in A); I is a model of K if I satisfies T and A.
A subsumption F = C ⊑ D (resp., an assertion C(a), r(a, b)), is entailed by K, written K |= F , if for all models I =hΔ, ·I i of K, I satisfies F .
Given a knowledge base K, the subsumption problem is the problem of deciding whether an inclusion C ⊑ D is entailed by K.
In the following we will refer to an extension of ALC with typicality inclusions, that we will call ALC + T as in [30], and to the rational closure of ALC + T knowledge bases (T , A) [33]. In addition to standard ALC inclusions C ⊑ D (called strict inclusions in the following), in ALC + T the TBox T also contains typicality inclusions of the form T(C) ⊑ D, where C and D are ALC concepts. Let us recall the notions of preferential, ranked and canonical model of a defeasible knowledge base (T , A).
structure hΔ, <, ·I i where: Δ is a domain; < is an irreflexive, transitive and wellfounded relation over Δ; ·I is a function that maps all concept names, role names and individual names as defined above for ALC interpretations, and provides an interpretation to all ALC concepts as above, and to typicality concepts as follows: (T(C))I = min<(CI ), where min<(S) = {u : u ∈ S and ∄z ∈ S s.t. z < u}.
When relation < is required to be also modular (i.e., for all x, y, z ∈ Δ, if x < y then x < z or z < y), N is called a ranked interpretation.
Preferential interpretations for description logics were first studied in [30], while ranked
interpretations (i.e., modular preferential interpretations) were first introduced for ALC
in [
A canonical model for K is a preferential (ranked) model containing, roughly speaking, as many domain elements as consistent with the knowledge base specification K . Given an ALC + T knowledge base K = (T , A) and a query F , let us define SK as the set of all ALC concepts (and subconcepts) occurring in K or in F , together with their complements. We consider all the sets of concepts {C1, C2, . . . , Cn} ⊆ SK consistent with K , i.e., s.t. K 6|=ALC+T C1 ⊓ C2 ⊓ · · · ⊓ Cn ⊑ ⊥.
Definition 3 (Canonical model). . A preferential model M =hΔ, <, I i of K is canonical with respect to SK if it contains at least a domain element x ∈ Δ s.t. x ∈ (C1 ⊓ C2 ⊓ · · · ⊓ Cn)I , for each set {C1, C2, . . . , Cn} ⊆ SK consistent with K . For finite, consistent ALC + T knowledge bases, existence of finite (ranked) canonical models has been proved in [33] (Theorem 1). In the following, we consider finite ALC + T knowledge bases, and we can restrict our consideration to finite preferential models. 3
In this section we introduce a notion of a multi-concept knowledge base, starting from a set of strict inclusions T , a set of assertions A, and a set of typicality inclusions D, each one of the form T(C) ⊑ D, where C and D are ALC concepts.
Definition 4. A modular multi-concept knowledge base K is a tuple hT , D, m1 , . . . , mk , A, s i, where T is an ALC TBox, D is a set of typicality inclusions, such that m1 ∪ . . . ∪ mk = D, A is an ABox, and s is a function associating each module mi with a concept, s(mi) = Ci, the subject of mi.
The idea is that each mi is a module defining the typical properties of the instances of some concept Ci. The defeasible inclusions belonging to a module mi with subject Ci are the inclusions that intuitively pertain to Ci. We expect that all the typicality inclusions T(C) ⊑ D, such that C is a subclass of Ci, belong to mi, but not only. For instance, for a module mi with subject Ci = Bird , the typicality inclusion T(Bird ⊓ Live at SouthPole) ⊑ Penguin , meaning that the birds living at the south pole are normally penguins, is clearly to be included in mi. As penguins are birds, also inclusion T(Penguin) ⊑ Black is to be included in mi, and, if T(Bird ) ⊑ Flying Animal and T(FlyingAnimal ) ⊑ BigWings are defeasible inclusions in the knowledge base, they both may be relevant properties of birds to be included in mi. For this reason we will not put restrictions on the typicality inclusions that can belong to a module. We will see that the semantic construction for a module mi will be able to ignore the typicality inclusions which are not relevant for subject Ci.
The modularization m1, . . . , mk of the defeasible part D of the knowledge base does not define a partition of D, as the same inclusion may belong to more than one module mi. For instance, the typical properties of employed students are relevant for both concept Student and concept Employee and should belong to their related modules (if any). Also, a granularity of modularization has to be chosen and, as we will see, this choice may have an impact on the global semantics of the knowledge base. At one extreme, all the defeasible inclusions in D are put together in the same module, e.g., the module associated with concept ⊤. At the other extreme, which has been studied in [35], a module mi contains only the defeasible inclusions of the form T(Ci) ⊑ D, where Ci is the subject of mi (and in this case, the inclusions T(C) ⊑ D with C subsumed by Ci are not admitted in mi). In this regard, the framework proposed in this paper could be seen as an extension of the proposal in [35] to allow coarser grained modules, while here we do not allow for user-defined preferences among defaults.
Let us consider an example of multi-concept knowledge base.
Example 1. Let K be the knowledge base hT , D, m1 , m2 , m3 , A, s i, where A = ∅, T contains the strict inclusions:
and the defeasible inclusions in D are distributed in the modules m1, m2, m3 as follows.
Module m1 has subject Employee, and contains the defeasible inclusions: (d1) T(Employee) ⊑ ¬Young (d2) T(Employee) ⊑ ∃has boss .Employee (d3) T(ForeignerEmployee) ⊑ ∃has Visa.⊤ (d4) T(Employee ⊓ Student ) ⊑ Busy (d5) T(Employee ⊓ Student ) ⊑ ¬Young
Module m2 has subject Student, and contains the defeasible inclusions: (d6) T(Student ) ⊑ ∃has classes .⊤ (d7) T(Student ) ⊑ Young (d8) T(Student ) ⊑ Has no Scolarship (d9) T(HighSchoolStudent ) ⊑ Teenager (d10) T(PhDStudent ) ⊑ ∃hasScolarship.Amount (d11) T(PhDStudent ) ⊑ Bright together with (d4) and (d5). Module m3 has subject V ehicle, and we omit its content. Observe that, in previous example, (d4) and (d5) belong to both modules m1 and m2. 4
In this section, we define a semantics of modular multi-concept knowledge bases, based on Lehmann’s lexicographic closure semantics [45]. The idea is that, for each module mi, a semantics can be defined using lexicographic closure semantics, with some minor modification.
Given a modular multi-concept knowledge base K = hT , D, m1 , . . . , mk , A, s i, we let rank (C ) be the rank of concept C in the rational closure ranking of the knowledge base (T ∪ D, A), according to the rational closure construction in [33]. In the rational closure ranking, concepts with higher ranks are more specific than concepts with lower ranks. While we will not recall the rational closure construction, let us consider again Example 1. In Example 1, the rational closure ranking assigns to concepts Adult , Employee , ForeignEmployee , Driver , Student, HighSchoolStudent , Primary SchoolStudent the rank 0, while to concepts PhDStudent and Employee ⊓ Student the rank 1. In fact, PhDStudent are exceptional students, as they have a scholarship, while employed students are exceptional students, as they are not young: they are exceptional subclasses of class Student.
Based on the concept ranking, the rational closure assigns a rank to typicality inclusions: the rank of T(C) ⊑ D is equal to the rank of concept C. For each module mi of a knowledge base K = hT , D, m1 , . . . , mk , A, s i, we aim to define a canonical model, using the lexicographic order based on the rank of typicality inclusions in mi. In the following we will assume that the knowledge base hT ∪ D, Ai is consistent in the logic ALC + T, that is, it has a preferential model. This also guarantees the existence of (finite) canonical models [33].
Let us define the projection of the knowledge base K on module mi as the knowledge base Ki = hT ∪ mi, Ai. Ki is an ALC + T knowledge base. Hence a preferential model Ni = hΔ, <i, ·I i of Ki is defined as in Section 2 (but now we use <i, instead of <, for the preference relation in Ni, for i = 1, . . . , k).
In his seminal work on the lexicographic closure, Lehmann [45] defines a model theoretic semantics of the lexicographic closure construction by introducing an order relation among propositional models, considering which defaults are violated in each model, and introducing a seriousness ordering ≺ among sets of violated defaults. For two propositional models w and w′, w ≺ w′ (w is preferred to w′) is defined in [45] as: w ≺ w′ iff V (w) ≺ V (w′) (1) w is preferred to w′ when the defaults V (w) violated by w are less serious than the defaults V (w′) violated by w′. As we will recall below, the seriousness ordering also depends on the number of defaults violated by w and by w′ for each rank.
In a similar way, in the following, we introduce a ranked relation <i on the domain Δ of a model of Ki. Let us first define, for a preferential model Ni = hΔ, <i, ·I i of Ki, what it means that an element x ∈ Δ violates a typicality inclusion T(C) ⊑ D in mi. Definition 5. Given a module mi of K, with s(mi) = Ci, and a preferential model Ni = hΔ, <i, ·I i of Ki, an element x ∈ Δ violates a typicality inclusion T(C) ⊑ D in mi if x ∈ CiI , x ∈ CI and x 6∈ DI .
Notice that, the set of typicality inclusions violated by a domain element x in a model only depends on the interpretation ·I of ALC concepts, and on the defeasible inclusions in mi. Furthermore, differently from the usual notion of violation in Lehmann’s semantics, for a module mi with subject Ci, we do not consider the violations of domain elements x 6∈ CiI (i.e., the domain elements x which are not Ci-instances are assumed not to violate any default in mi). Let Vi(x) be the set of the defeasible inclusions of mi violated by domain element x, and let Vih(x) be the set of all defeasible inclusions in mi with rank h which are violated by domain element x.
In order to compare alternative sets of defaults, in [45] the seriousness ordering ≺ among sets of defaults is defined by associating with each set of defaults D ⊆ K a tuple of numbers hn0, n1, . . . , nri, where r is the order of K , i.e. the least finite i such that there is no default with the finite rank r or rank higher than r (but there is at least one default with rank r − 1). The tuple is constructed considering the ranks of defaults in the rational closure. n0 is the number of defaults in D with rank ∞ and, for 1 ≤ i ≤ k, ni is the number of defaults in D with rank r − i (in particular, nr is the number of defaults in D with rank 0). Lehmann defines the strict modular order ≺ among sets of defaults from the natural lexicographic order over the tuples hn0, n1, . . . , nri. This order gives preference to those sets of defaults containing a larger number of more specific defaults. As we have seen from equation (1), ≺ is used by Lehmann to compare sets of violated defaults and to prefer the propositional models whose violations are less serious.
We use the same criterion for comparing domain elements, introducing a seriousness ordering ≺i for each module mi. Considering that the defaults with infinite rank must be satisfied by all domain elements, we will not need to consider their violation in our definition (that is, we will not consider n0 in the following).
The set Vi(x) of defaults from module mi which are violated by x, can be associated with a tuple of numbers ti,x = h|Vir−1(x)|, . . . , |Vi0(x)|i, where Vil(x) is the number of defaults in D with rank l which are violated by x. Following Lehmann, we let Vi(x) ≺i Vi(y) iff ti,x comes before ti,y in the natural lexicographic order on tuples (restricted to the violations of defaults in mi), that is:
Vi(x) ≺i Vi(y) iff ∃l such that |Vil(x)| < |Vil(y)| and, ∀h > l, |Vih(x)| = |Vih(y)| Definition 6. A preferential model Ni = hΔ, <i, ·I i of Ki = hT ∪ mi, Ai, is a lexicographic model of Ki if hΔ, ·I i is an ALC model of hT , Ai and <i satisfies the following condition: x <i y iff Vi(x) ≺i Vi(y).
Informally, <Cj gives higher preference to domain elements violating less typicality inclusions of mi with higher rank. In particular, all x, y 6∈ CI , x ∼Ci y, i.e., all ¬Cii elements are assigned the same preference wrt <i, the least one, as they trivially satisfy all the typicality properties in mi. As in Lehmann’s semantics, in a lexicographic model Ni = hΔ, <i, ·I i of Ki, the preference relation <i is a strict modular partial order, i.e. an irreflexive, transitive and modular relation. As well-foundedness trivially holds for finite interpretations, a lexicographic model Ni of Ki is a ranked model of Ki.
A multi-concept model for K can be defined as a multi-preference interpretation with a preference relation <i for each module mi.
Definition 7 (Multi-concept interpretation). Let K = hT , D, m1 , . . . , mk , A, s i be a multi-concept knowledge base. A multi-concept interpretation M for K is a tuple hΔ, <1, . . . , <k, ·I i such that, for all i = 1, . . . , k, hΔ, <i, ·I i is a ranked ALC + T interpretation, as defined in Section 2.
Definition 8 (Multi-concept lexicographic model). Let K = hT , D, m1 , . . . , mk , A, si be a multi-concept knowledge base. A multi-concept lexicographic model M = hΔ, <1 , . . . , <k, ·I i of K is a multi-concept interpretation for K, such that, for all i = 1, . . . , k, Ni = hΔ, <i, ·I i is a lexicographic model of Ki = hT ∪ mi, Ai.
A canonical multi-concept lexicographic model of K is multi-concept lexicographic model of K such that Δ and ·I are the domain and interpretation function of some canonical preferential model of hT ∪ D, Ai, according to Definition 3 (see [36]).
Observe that, restricting to the propositional fragment of the language (which does not allow universal and existential restrictions nor assertions), for a knowledge base K without strict inclusions and with a single module m1, with subject ⊤, containing all the typicality inclusions in K, the preference relation <1 corresponds to Lehmann’s lexicographic closure semantics, as its definition is based on the set of all defeasible inclusions in the knowledge base. 5
For multiple modules, each <i determines a ranked preference relation which can be
used to answer queries over module mi (i.e. queries whose subject is Ci). If we want
to evaluate the query T(C) ⊑ D (are all typical C elements also D elements?) in
module mi (assuming that C concerns subject Ci), we can answer the query using the
<i relation, by checking whether min<i (CI ) ⊆ DI . For instance, in Example 1, the
query “are all typical Phd students young?” can be evaluated in module m2. The answer
would be positive, as the property of students of being normally young is inherited by
PhD Student. The evaluation of a query in a specific module is something considered
in context-based formalisms, such as in the CKR framework [
The lexicographic orders <i and <j (for i 6= j) do not need to agree. For instance, in Example 1, for two domain elements x and y, we might have that x <1 y and y <2 x, as x is more typical than y as an employee, but less typical than x as a student. To answer a query T(C) ⊑ D, where C is a concept which is concerned with more than one subject in the knowledge base (e.g., are typical employed students young?), we need to combine the relations <i.
A simple way of combining the modular partial order relations <i is to use Pareto combination. Let ≤i be defined as follows: x ≤i y iff y 6<i x. As <i is a modular partial order, ≤i is a total preorder. Given a canonical multi-concept lexicographic model M = hΔ, <1, . . . , <k, ·I i of K, we define a global preference relation < on Δ as follows: x < y iff (i) for some i = 1, . . . , k, x <i y and (∗) (ii) for all j = 1, . . . , k, x ≤j y, The resulting relation < is a partial order, while modularity may not hold for <. Definition 9. Given a canonical multi-concept lexicographic model M = hΔ, <1, . . . , <k , ·I i of K, the combined lexicographic interpretation of M, is a triple MP = hΔ, <, ·I i, where < is the global preference relation defined by (*).
We call MP a combined lexicographic model of K (shortly, an mlc-model of K ). Proposition 1. A combined lexicographic model MP of K is a preferential interpretation satisfying all the strict inclusions and assertions in K .
A combined lexicographic model MP of K is a preferential interpretation as those defined for ALC + T in Definition 2 (and, in general, it is not a ranked interpretation). However, preference relation < in MP is not an arbitrary irreflexive, transitive and well-founded relation. It is obtained by first computing the lexicographic preference relations <i for modules, and then by combining them into <. As MP satisfies all strict inclusions and assertions in K but is not required to satisfy all typicality inclusions T(C) ⊑ D in K , MP is not a preferential ALC + T model of K defined in Section 2.
Consider a situation in which there are two concepts, Student and YoungPerson , that are very related in that students are normally young persons and young persons are normally students (i.e., T(Student ) ⊑ YoungPerson and T(YoungPerson ) ⊑ Student ) and suppose there are two modules m1 and m2 such that s(m1) = Student and s(m2) = YoungPerson . The two concepts may have different (and even contradictory) prototypical properties, for instance, normally students are quiet (T(Student ) ⊑ Quiet ), but normally young persons are not quiet (T(YoungPerson ) ⊑ ¬Quiet ). Considering the preference relations <1 and <2, associated with m1 and m2 in a canonical multiconcept lexicographic model, there may be two young persons and student Bob and John, such that bob <1 john and john <2 bob, as Bob is quiet and John is not. Then, John and Bob are incomparable in the global relation <. Both of them, depending on the other prototypical properties of students and young persons, might be minimal, among students, wrt the global preference relation <.
In general, for a knowledge base K and a module mi, with s(mi) = Ci, the inclusion min<(CiI ) ⊆ min<i (CiI ) may not hold and, for this reason, a combined lexicographic interpretation may fail to satisfy all typicality inclusions. In this respect, canonical multi-concept lexicographic models are more liberal than KLM-style preferential models for typicality logics [31], where min<(Student I ) ⊑ Quiet I must hold for the typicality inclusion to be satisfied. As a consequence, the knowledge base above has no preferential model according to the semantics in Section 2.
In [36] the notion of mlc-model of K has also been strengthened, by considering T-compliant mlc-models (or mcT-models) of K , which further satisfy the condition that, for all the typicality inclusilons T(C) ⊑ D in K , (T(C ))I = min<(C I ) ⊆ D I .
A notion of multi-concept lexicographic entailment (mlc-entailment) can be defined as usual: a query F is mlc-entailed by K (K |=mlc F ) if, for all mlc-models MP = hΔ, <, ·I i of K , F is satisfied in MP. Notice that a query T(C) ⊑ D is satisfied in MP when min<(CI ) ⊆ DI . Similarly, a notion of mcT-entailment can be defined: l K |=mlcT F if, for all mlcT-models MP = hΔ, <, ·I i of K , F is satisfied in MP.
As, for any multi-concept knowledge base K , the set of mcT-models of K is a
l
subset of the set of mlc-models of K , and there is some K for which the inclusion
is proper, mcT-entailment is stronger than mlc-entailment. It can be proven that both
l
notions of entailment satisfy the KLM postulates of preferential consequence relations,
which can be reformulated for a typicality logic, considering that typicality inclusions
T(C) ⊑ D [30] stand for conditionals C|∼D in KLM preferential logics [43, 44]. See
also [
The notions ofmlc-entailment and mcT-entailment are not stronger than Lehmann’s l lexicographic closure in the propositional case. Let us consider again Example 1. Example 2. Let us add another module m4 with subject Citizen to the knowledge base K, plus the following additional axioms in T :
Italian ⊑ Citizen French ⊑ Citizen Canadian ⊑ Citizen Module m4 has subject Citizen , and contains the defeasible inclusions:
(d17) T(Italian) ⊑ DriveFast (d18) T(Italian) ⊑ HomeOwner Suppose the following typicality inclusion is also added to module m2:
(d19) T(PhDStudent ) ⊑ ¬HomeOwner What can we conclude about typical Italian PhD students? We can see that neither the inclusion T(PhDStudent ⊓ Italian) ⊑ HomeOwner nor the inclusion T(PhDStudent ⊓Italian) ⊑ ¬HomeOwner is mlc-entailed by K. In fact, as <2-minimal and <4-minimal PhDStudent ⊓Italian -elements are incomparable with respect to <, the <-minimal Italian PhD students will include them all. Thus, min<((PhDStudent ⊓ Italian)I ) 6⊆ HomeOwner I and min<((PhDStudent ⊓ Italian)I ) 6⊆ (¬HomeOwner )I .
The home owner example is a reformulation of the example used by Geffner and Pearl
to show that the rational closure of conditional knowledge bases sometimes gives too
strong conclusions, as “conflicts among defaults that should remain unresolved, are
resolved anomalously” [
Geffner and Pearl’s Conditional Entailment [
The approach considered in Section 4 does not allow to reason with a hierarchy of modules, but it considers a flat collection of modules m1, . . . , mk, each module concerning some subject Ci. As we have seen, a module mi may contain defeasible inclusions referring to subclasses of Ci, such as PhDStudent in the case of module m2 with subject Student. When defining the preference relation <i the lexicographic closure semantics already takes into account the specificity relation among concepts within the module (e.g., the fact that PhDStudent is more specific than Student).
However, nothing prevents us from defining two modules mi (with subject Ci) and mj (with subject Cj ), such that concept Cj is more specific than concept Ci. For instance, as a variant of Example 1, we might have introduced two different modules m2 with subject Student and m5 with subject PhDStudent . As concept PhDStudent is more specific than concept Student (in particular, PhDStudent ⊑ Student is entailed from the strict part of knowledge base T in ALC), the specificity information should be taken into account when combining the preference relations. More precisely, preference <5 should override preference <2 when comparing PhDStudent -instances.
This is the principle followed by Giordano and Theseider Dupre´ [35] to define a global preference relation, in the case when each module with subject Ci only contains typicality inclusions of the form T(Ci) ⊑ D. A more sophisticated way to combine the preference relations <i into a global relation < is used to deal with this case with respect to Pareto combination, by exploiting the specificity relation among concepts. While we refer therein for a detailed description of this more sophisticated notion of preference combination, let us observe that this solution could be as well applied to the modular multi-concept knowledge bases considered in this paper, provided an irreflexive and transitive notion of specificity among modules is defined.
Another aspect that has been considered in the previously mentioned paper is the
possibility of assigning ranks to the defeasible inclusions associated with a given
concept. While assigning a rank to all typicality inclusions in the knowledge base may be
awkward, often people have a clear idea about the relative importance of the properties
for some specific concept. For instance, we may know that the defeasible property that
students are normally young is more important than the property that student normally
do not have a scholarship. For small modules, which only contain typicality inclusions
T(Ci) ⊑ D for a concept Ci, the specification of user-defined ranks of the Ci’s typical
properties is a feasible option and a ranked modular preference relation can be defined
from it, by using Brewka’s # strategy from his framework of Basic Preference
Descriptions for ranked knowledge bases [
According to the choice of fine grained or coarse grained modules, to the choice of the preferential semantics for each module (e.g., based on user-specified ranking or on Lehmann’s lexicographic closure, or on the rational closure, etc.), and to the presence of a specificity relation among modules, alternative preferential semantics for modularized multi-concept knowledge bases can emerge. 7
In this paper, we have proposed a modular multi-concept extension of the lexicographic closure semantics, based on the idea that defeasible properties in the knowledge base can be distributed in different modules, for which alternative preference relations can be computed. Combining multiple preferences into a single global preference allows a new preferential semantics and a notion of multi-concept lexicographic entailment (mlc-entailment) which, in the propositional case, is not stronger than the lexicographic closure. This work has been first presented in [36].
mlc-entailment satisfies the KLM postulates of a preferential consequence relation.
It retains some good properties of the lexicographic closure, being able to deal with
irrelevance, with specificity within the single modules, and not being subject to the
“blockage of property inheritance” problem. The combination of different preference
relations provides a simple solution to a problem, recognized by Geffner and Pearl, that
the rational closure of conditional knowledge bases sometimes gives too strong
conclusions, as “conflicts among defaults that should remain unresolved, are resolved
anomalously” [
Reasoning about exceptions in ontologies has led to the development of many
nonmonotonic extensions of Description Logics (DLs), incorporating non-monotonic
features from most of NMR formalisms in the literature. In addition to those already
mentioned in the introduction, let us recall the work by Straccia on inheritance reasoning in
hybrid KL-One style logics [48] the work on defaults in DLs [
The lexicographic closure for DLs has been first investigated by Casini and Straccia
[
Starting from Brewka’s framework of basic preference descriptions [
Bozzato et al. present extensions of the CKR (Contextualized Knowledge
Repositories) framework by Bozzato et al. [
For the lightweight description logic E L+⊥, an Answer Set Programming (ASP)
approach has been proposed [35] for defeasible inference in a miltipreference extension
of E L+⊥, in the specific case in which each module only contains the defeasible
inclusions T(Ci) ⊑ D for a single concept Ci, where the ranking of defeasible inclusions
is specified in the knowledge base, following the approach by Gerhard Brewka in his
framework of Basic Preference Descriptions for ranked knowledge bases [
For E L+⊥ knowledge bases, we aim at extending this ASP encoding to deal with
the modular multi-concept lexicographic closure semantics proposed in this paper, as
well as with a more general framework, allowing for different choices of preferential
semantics for the single modules and for different specificity relations for combining
them. For lightweight description logics of the E L family [
Acknowledgement: This research is partially supported by INDAM-GNCS Projects 2019 and 2020. 30. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Preferential Description Logics. In
LPAR 2007, volume 4790 of LNAI, pages 257–272, Yerevan, Armenia, October 2007. 31. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. ALC+T: a preferential extension of
Description Logics. Fundamenta Informaticae, 96:1–32, 2009. 32. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. A NonMonotonic Description Logic for Reasoning About Typicality. Artif. Intell., 195:165–202, 2013. 33. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Semantic characterization of rational closure: From propositional logic to description logics. Artif. Intell., 226:1–33, 2015. 34. L. Giordano and D. Theseider Dupre´. Defeasible Reasoning in SROEL from Rational Entailment to Rational Closure. Fundam. Inform., 161(1-2):135–161, 2018. 35. L. Giordano and D. Theseider Dupre´. An ASP approach for reasoning in a conceptaware multipreferential lightweight DL. Theory and Practice of Logic programming, TPLP, 10(5):751–766, 2020. 36. L. Giordano and D. Theseider Dupre´. A framework for a modular multi-concept lexicographic closure semantics. In 18th Int. Workshop on Non-Monotonic Reasoning, NMR2020, September 12th - 14th, 2020. https://nmr2020.dc.uba.ar/WorkshopNotes.pdf. 37. L. Giordano and D. Theseider Dupre´. Weighted conditional E L⊥ knowledge bases with integer weights: an ASP approach. In ICLP 2021, 2021. To appear. 38. L. Giordano and D. Theseider Dupre´. Weighted defeasible knowledge bases and a multipreference semantics for a deep neural network model. In JELIA 2021, May 17-20, volume 12678 of LNCS, pages 225–242. Springer, 2021. 39. V. Gliozzi. Reasoning about multiple aspects in rational closure for DLs. In Proc. AI*IA 2016, Genova, Italy, Nov 29 - Dec 1, 2016, pages 392–405, 2016. 40. G. Gottlob, A. Hernich, C. Kupke, and T. Lukasiewicz. Stable model semantics for guarded existential rules and description logics. In Proc. KR 2014, 2014. 41. G. Kern-Isberner and M. Ritterskamp. Preference fusion for default reasoning beyond system
Z. J. Autom. Reasoning, 45(1):3–19, 2010. 42. M. Knorr, P. Hitzler, and F. Maier. Reconciling owl and non-monotonic rules for the semantic web. In ECAI 2012, page 474479, 2012. 43. S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence, 44(1-2):167–207, 1990. 44. D. Lehmann and M. Magidor. What does a conditional knowledge base entail? Artificial
Intelligence, 55(1):1–60, 1992. 45. D. J. Lehmann. Another perspective on default reasoning. Ann. Math. Artif. Intell., 15(1):61– 82, 1995. 46. B. Motik and R. Rosati. Reconciling Description Logics and rules. Journal of the ACM, 57(5), 2010. 47. J. Pearl. System Z: A Natural Ordering of Defaults with Tractable Applications to Nonmonotonic Reasoning. In TARK (3rd Conference on Theoretical Aspects of Reasoning about Knowledge), pages 121–135, Pacific Grove, CA, USA, 1990. Morgan Kaufmann. 48. U. Straccia. Default inheritance reasoning in hybrid kl-one-style logics. In R. Bajcsy, editor, Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI 1993), pages 676–681, Chambe´ry, France, August 1993. Morgan Kaufmann.