=Paper=
{{Paper
|id=Vol-3002/paper1
|storemode=property
|title=A Framework for a Modular Multi-Concept Lexicographic Closure Semantics (an abridged report)
|pdfUrl=https://ceur-ws.org/Vol-3002/paper1.pdf
|volume=Vol-3002
|authors=Laura Giordano,Daniele Theseider Dupré
|dblpUrl=https://dblp.org/rec/conf/cilc/0001D21
}}
==A Framework for a Modular Multi-Concept Lexicographic Closure Semantics (an abridged report)==
<pdf width="1500px">https://ceur-ws.org/Vol-3002/paper1.pdf</pdf>
<pre>
       A framework for a modular multi-concept
 lexicographic closure semantics (an abridged report) ⋆

                       Laura Giordano and Daniele Theseider Dupré

                      DISIT - Università del Piemonte Orientale, Italy
                   laura.giordano@uniupo.it, dtd@uniupo.it



        Abstract. We define a modular multi-concept extension of the lexicographic clo-
        sure semantics for defeasible description logics with typicality. The idea is that of
        distributing the defeasible properties of concepts into different modules, accord-
        ing to their subject, and of defining a notion of preference for each module based
        on the lexicographic closure semantics. The preferential semantics of the knowl-
        edge 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.




1 Introduction
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 [30, 15] as well as different
closure constructions such as the rational closure [19, 18, 33], the lexicographic closure
[20], the relevant closure [17], and MP-closure [29].
    In this paper we define a modular multi-concept extension of the lexicographic clo-
sure 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 prop-
erties 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 Li-
    cense 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 con-
sidering 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 [12], we have assumed that a specification of the relative
importance of typicality inclusions for a concept Ci is given by assigning ranks to typ-
icality inclusions. However, for a large module, a specification by hand of the ranking
of the defeasible inclusions in the module would be awkward. In particular, a module
may include all properties of a class as well as properties of its exceptional subclasses
(for instance, the typical properties of penguins, ostriches, etc. might all be included
in a module with subject Bird ). A natural choice is then to consider, for each mod-
ule, a lexicographic semantics which builds on the rational closure ranking to define a
preference ordering on domain elements. This preference relation corresponds, in the
propositional case, to the lexicographic order on worlds in Lehmann’s model theoretic
semantics of the lexicographic closure [45]. This semantics already accounts for the
specificity relations among concepts inside the module, as the lexicographic closure
deals with specificity, based on ranking of concepts computed by the rational closure.
     Based on the ranked semantics of the single modules, a compositional (preferen-
tial) 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 multi-
concept 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 lexi-
cographic 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 inher-
itance from classes to subclasses is not guaranteed, which affects the rational closure
[47]. In addition, separating defeasible inclusions in different modules provides a sim-
ple solution to another problem of the rational closure and its refinements (including
the lexicographic closure), that was recognized by Geffner and Pearl [27], namely, that
“conflicts among defaults that should remain unresolved, are resolved anomalously”,
giving rise to too strong conclusions. The preferential (not necessarily ranked) nature
of the global preference relation < provides a simple way out to this problem, when
defeasible inclusions are suitably separated in different modules.

2 The description logics ALC and its extension with typicality
 In this section we recall the syntax and semantics of the description logic ALC [2] and
 an extension of ALC with typicality [33].
     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 C I ⊆ ∆, 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 = ∆\C I ,
     (∃r.C) = {x ∈ ∆ | ∃y.(x, y) ∈ rI and y ∈ C I },
             I
                                                              (C ⊓ D)I = C I ∩ DI ,
             I                           I          I
     (∀r.C) = {x ∈ ∆ | ∀y.(x, y) ∈ r ⇒ y ∈ C },               (C ⊔ D)I = C I ∪ 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 C I ⊆ DI ;
    - I satisfies an assertion C(a) (resp., r(a, b)) if aI ∈ C I (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 knowl-
edge 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).
Definition 2 (Interpretations for ALC + T). A preferential interpretation N is any
structure h∆, <, ·I i where: ∆ is a domain; < is an irreflexive, transitive and well-
founded 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 interpre-
tation to all ALC concepts as above, and to typicality concepts as follows: (T(C))I =
min< (C I ), 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 [15]. A preferential (ranked) model of an ALC + T knowledge base K is a prefer-
ential (ranked) ALC + T interpretation N = h∆, <, ·I i that satisfies all inclusions in
K, where: a strict inclusion or an assertion is satisfied in N if it is satisfied in the ALC
model h∆, ·I i, and a typicality inclusion T(C) ⊑ D is satisfied in N if (T(C))I ⊆ DI .
Preferential entailment in ALC + T is defined in the usual way: for a knowledge base
K and a query F (a strict or defeasible inclusion or an assertion), F is preferentially
entailed by K (K |=ALC+T F ) if F is satisfied in all preferential models of K.
    A canonical model for K is a preferential (ranked) model containing, roughly speak-
ing, 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∆, <, Ii of K is canon-
ical 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 Modular multi-concept knowledge bases
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, si, 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 sub-
ject Ci are the inclusions that intuitively pertain to Ci . We expect that all the typi-
cality 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 knowl-
edge 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 mod-
ule. 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 mod-
ules (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, si, where A = ∅, T
contains the strict inclusions:
    Adult ⊑ ∃has SSN .⊤    Employee ⊑ Adult      PhdStudent ⊑ Student
    PhDStudent ⊑ Adult              Has no Scolarship ≡ ¬∃hasScolarship.⊤
    PrimarySchoolStudent ⊑ Children    Driver ⊑ ∃has DrivingLicence.⊤
    PrimarySchoolStudent ⊑ HasNoClasses           Driver ⊑ Adult
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 A lexicographic semantics of modular multi-concept KBs
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, si,
we let rank (C ) be the rank of concept C in the rational closure ranking of the knowl-
edge base (T ∪ D, A), according to the rational closure construction in [33]. In the ra-
tional 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 ex-
ceptional subclasses of class Student.
    Based on the concept ranking, the rational closure assigns a rank to typicality in-
clusions: 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, si, 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 knowl-
edge 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 ∈ C I 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 seman-
tics, 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 , . . . , nr i, 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 , . . . , nr i. 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 serious-
ness 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 lexico-
graphic 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∈ CiI , x ∼Ci y, i.e., all ¬Ci -
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, si 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 The combined lexicographic model of a KB
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 (C I ) ⊆ 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 [8], where a language
construct eval (X , c) allows for evaluating a concept (or role) X in context c.
    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 mcl -model of K).
Proposition 1. A combined lexicographic model MP of K is a preferential interpreta-
tion 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) ⊑ Stu-
dent) 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 multi-
concept 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 inclu-
sion min< (CiI ) ⊆ min<i (CiI ) may not hold and, for this reason, a combined lexico-
graphic interpretation may fail to satisfy all typicality inclusions. In this respect, canon-
ical 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 mcl -model of K has also been strengthened, by considering
T-compliant mcl -models (or mcl T-models) of K, which further satisfy the condition
that, for all the typicality inclusions T(C) ⊑ D in K, (T(C ))I = min< (C I ) ⊆ D I .
     A notion of multi-concept lexicographic entailment (mcl -entailment) can be defined
as usual: a query F is mcl -entailed by K (K |=mcl F ) if, for all mcl -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< (C I ) ⊆ DI . Similarly, a notion of mcl T-entailment can be defined:
K |=mcl T F if, for all mcl T-models MP = h∆, <, ·I i of K, F is satisfied in MP .
     As, for any multi-concept knowledge base K, the set of mcl T-models of K is a
subset of the set of mcl -models of K, and there is some K for which the inclusion
is proper, mcl T-entailment is stronger than mcl -entailment. It can be proven that both
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 [7] for the formulation of KLM postulates in the Propositional Typicality Logic.
    The notions ofmcl -entailment and mcl T-entailment are not stronger than Lehmann’s
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 in-
clusion T(PhDStudent ⊓ Italian) ⊑ HomeOwner nor the inclusion T(PhDStudent
⊓Italian) ⊑ ¬HomeOwner is mcl -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 re-
solved anomalously” [27]. Informally, if defaults (d18 ) and (d19 ) are conflicting for
Italian Phd students before adding any default which makes PhD students exceptional
wrt Students (in our formalization, default (d10 )), they should remain conflicting af-
ter this addition. On the contrary, in the propositional case, both the rational closure
[44] and Lehmann’s lexicographic closure [45] would entail that normally Italian Phd
students are not home owners. This conclusion is unwanted, and is based on the fact
that (d18 ) has rank 0, while (d19 ) has rank 1 in the rational closure ranking. On the
other hand, T(PhDStudent ⊓ Italian) ⊑ ¬ HomeOwner is neither mcl -entailed from
K, nor mcl T-entailed from K. Both notions of entailment, when restricted to the propo-
sitional case, cannot be stronger than Lehmann’s lexicographic closure.
     Geffner and Pearl’s Conditional Entailment [27] does not suffer from the above men-
tioned problem as it is based on (non-ranked) preferential models. The same problem,
which is related to the representation of preferences as levels of reliability, has also been
recognized by Brewka [11] in his logical framework for default reasoning, leading to a
generalization of the approach to allow a partial ordering between premises. The exam-
ple above shows that our approach using ranked preferences for the single modules, but
a non-ranked global preference relation < for their combination, does not suffer from
this problem, provided a suitable modularization is chosen.


6 Further issues: Reasoning with a hierarchy of modules and
  user-defined preferences
The approach considered in Section 4 does not allow to reason with a hierarchy of mod-
ules, 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 re-
ferring 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 in-
stance, 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 Dupré [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 con-
cept. 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 De-
scriptions for ranked knowledge bases [12]. This alternative may coexist with the use
of the lexicographic closure semantics built from the rational closure ranking for large
modules.
    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 Conclusions and related work

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
(mcl -entailment) which, in the propositional case, is not stronger than the lexicographic
closure. This work has been first presented in [36].
    mcl -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 conclu-
sions, as “conflicts among defaults that should remain unresolved, are resolved anoma-
lously” [27]. This problem also affects the lexicographic closure, which is stronger than
the rational closure. Our approach using ranked preferences for the single modules, but
a non-ranked preference < for their combination, does not suffer from this problem,
provided a suitable modularization is chosen. As Geffner and Pearl’s Conditional En-
tailment [27], also some non-monotonic DLs, such as ALC + Tmin , a typicality DL
with a minimal model preferential semantics [32], and the non-monotonic description
logic DLN [5], which supports normality concepts based on a notion of overriding, do
not not suffer from the problem above.
    Reasoning about exceptions in ontologies has led to the development of many non-
monotonic extensions of Description Logics (DLs), incorporating non-monotonic fea-
tures from most of NMR formalisms in the literature. In addition to those already men-
tioned 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 [3], on description logics
of minimal knowledge and negation as failure [24], on circumscriptive DLs [6], the gen-
eralization of rational closure to all description logics [4], as well as the combination of
description logics and rule-based languages [26, 25, 46, 42, 40, 9].
    The lexicographic closure for DLs has been first investigated by Casini and Straccia
[19, 21]. Our multipreference semantics is related with the multipreference semantics
for ALC developed by Gliozzi [39], which is based on the idea of refining the rational
closure construction considering the preference relations <Ai associated with different
aspects. We follow a different route concerning the definition of the preference relations
associated with modules, and the way of combining them in a single preference relation.
    Starting from Brewka’s framework of basic preference descriptions [12], multiple
preferences have also been used under different approaches: in system ARS, a refine-
ment of System Z developed by Kern-Isberner and Ritterskamp [41], through prefer-
ence fusion; by Gil [28] to define a multipreference formulation of the typicality DL
ALC + Tmin , mentioned above; by Britz and Varzinczak [16, 14], by associating mul-
tiple preferences to roles; in the first-order logic setting, by Delgrande and Rantsaudis
[23]; in ranked EL⊥ knowledge bases, by Giordano and Theseider Dupré [35].
    Bozzato et al. present extensions of the CKR (Contextualized Knowledge Reposito-
ries) framework by Bozzato et al. [8, 9] in which defeasible axioms are allowed in the
global context and exceptions can be handled by overriding and have to be justified in
terms of semantic consequence, considering sets of clashing assumptions for each defea-
sible axiom. An extension of this approach to deal with general contextual hierarchies
has been studied by the same authors [10], by introducing a coverage relation among
contexts, and defining a notion of preference among clashing assumptions, which is
used to define a preference relation among justified CAS models, based on which CKR
models are selected. An ASP based reasoning procedure, that is complete for instance
checking, is developed for SROIQ-RL.
     For the lightweight description logic EL+⊥ , an Answer Set Programming (ASP) ap-
proach has been proposed [35] for defeasible inference in a miltipreference extension
of EL+ ⊥ , in the specific case in which each module only contains the defeasible inclu-
sions 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 [12]. A speci-
ficity relation among concepts is also considered. The ASP encoding exploits asprin
[13], by formulating multipreference entailment as a problem of computing preferred
answer sets, which is proved to be Π2p -complete. A similar encoding has been devel-
oped for defeasible reasoning with weighted conditional EL⊥  ⊥ knowledge bases (in the
two-valued case) [37], a formalism that has been introduced for capturing the logical
semantics of Multilayer Perceptrons [38].
     For EL+ ⊥ 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 EL family [1], the ranking of concepts
determined by the rational closure construction can be computed in polynomial time
in the size of the knowledge base [34, 22]. This suggests that we may expect a Π2p
upper-bound on the complexity of multi-concept lexicographic entailment.
   Acknowledgement: This research is partially supported by INDAM-GNCS Projects
2019 and 2020.


References
 1. F. Baader, S. Brandt, and C. Lutz. Pushing the E L envelope. In Proceedings of the 19th
    International Joint Conference on Artificial Intelligence (IJCAI 2005), pages 364–369, Edin-
    burgh, Scotland, UK, August 2005.
 2. F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, and P.F. Patel-Schneider. The Descrip-
    tion Logic Handbook - Theory, Implementation, and Applications. Cambridge, 2007.
 3. F. Baader and B. Hollunder. Embedding defaults into terminological knowledge representa-
    tion formalisms. J. Autom. Reasoning, 14(1):149–180, 1995.
 4. P. A. Bonatti. Rational closure for all description logics. Artif. Intell., 274:197–223, 2019.
 5. P. A. Bonatti, M. Faella, I. Petrova, and L. Sauro. A new semantics for overriding in descrip-
    tion logics. Artif. Intell., 222:1–48, 2015.
 6. P. A. Bonatti, M. Faella, and L. Sauro. Defeasible inclusions in low-complexity dls. J. Artif.
    Intell. Res. (JAIR), 42:719–764, 2011.
 7. Richard Booth, Giovanni Casini, Thomas Meyer, and Ivan Varzinczak. On rational entail-
    ment for propositional typicality logic. Artif. Intell., 277, 2019.
 8. L. Bozzato, T. Eiter, and L. Serafini. Contextualized knowledge repositories with justifiable
    exceptions. In DL 2014, volume 1193 of CEUR Workshop Proceedings, pages 112–123.
 9. L. Bozzato, T. Eiter, and L. Serafini. Enhancing context knowledge repositories with justifi-
    able exceptions. Artif. Intell., 257:72–126, 2018.
10. L. Bozzato, T. Eiter, and L. Serafini. Justifiable exceptions in general contextual hierarchies.
    In CONTEXT 2019, Trento, Italy, November 20-22, 2019, Proceedings, volume 11939 of
    Lecture Notes in Computer Science, pages 26–39. Springer, 2019.
11. G. Brewka. Preferred subtheories: An extended logical framework for default reasoning. In
    Proceedings of the 11th International Joint Conference on Artificial Intelligence. Detroit, MI,
    USA, August 1989, pages 1043–1048, 1989.
12. G. Brewka. A rank based description language for qualitative preferences. In Proceedings
    of the 16th Eureopean Conference on Artificial Intelligence, ECAI’2004, Valencia, Spain,
    August 22-27, 2004, pages 303–307, 2004.
13. G. Brewka, J. P. Delgrande, J. Romero, and T. Schaub. asprin: Customizing answer set
    preferences without a headache. In Proc. AAAI 2015, pages 1467–1474, 2015.
14. A. Britz and I. Varzinczak. Contextual rational closure for defeasible ALC (extended ab-
    stract). In Proc. 32nd International Workshop on Description Logics, Oslo, Norway, June
    18-21, 2019, 2019.
15. K. Britz, J. Heidema, and T. Meyer. Semantic preferential subsumption. In G. Brewka and
    J. Lang, editors, KR 2008, pages 476–484, Sidney, Australia, September 2008. AAAI Press.
16. K. Britz and I J. Varzinczak. Rationality and context in defeasible subsumption. In Proc.
    10th Int. Symp. on Found. of Information and Knowledge Systems, FoIKS 2018, Budapest,
    May 14-18, 2018, pages 114–132, 2018.
17. G. Casini, T. Meyer, K. Moodley, and R. Nortje. Relevant closure: A new form of defeasible
    reasoning for description logics. In JELIA 2014, LNCS 8761, pages 92–106. Springer, 2014.
18. G. Casini, T. Meyer, I. J. Varzinczak, , and K. Moodley. Nonmonotonic Reasoning in Descrip-
    tion Logics: Rational Closure for the ABox. In DL 2013, volume 1014 of CEUR Workshop
    Proceedings, pages 600–615, 2013.
19. G. Casini and U. Straccia. Rational Closure for Defeasible Description Logics. In T. Jan-
    hunen and I. Niemelä, editors, JELIA 2010, volume 6341 of LNCS, pages 77–90, Helsinki,
    Sept. 2010. Springer.
20. G. Casini and U. Straccia. Lexicographic Closure for Defeasible Description Logics. In
    Proc. of Australasian Ontology Workshop, vol.969, pages 28–39, 2012.
21. G. Casini and U. Straccia. Defeasible inheritance-based description logics. Journal of Artifi-
    cial Intelligence Research (JAIR), 48:415–473, 2013.
22. G. Casini, U. Straccia, and T. Meyer. A polynomial time subsumption algorithm for nominal
    safe ELO⊥ under rational closure. Inf. Sci., 501:588–620, 2019.
23. J. Delgrande and C. Rantsoudis. A preference-based approach for representing defaults in
    first-order logic. In 18th Int. Workshop on Non-Monotonic Reasoning, NMR2020, Sept. 12th
    - 14th, 2020.
24. F. M. Donini, D. Nardi, and R. Rosati. Description logics of minimal knowledge and negation
    as failure. ACM Transactions on Computational Logic (ToCL), 3(2):177–225, 2002.
25. T. Eiter, G. Ianni, T. Lukasiewicz, and R. Schindlauer. Well-founded semantics for descrip-
    tion logic programs in the semantic web. ACM Trans. Comput. Log., 12(2):11, 2011.
26. T. Eiter, G. Ianni, T. Lukasiewicz, R. Schindlauer, and H. Tompits. Combining answer set
    programming with description logics for the semantic web. Artif. Intell., 172(12-13):1495–
    1539, 2008.
27. Hector Geffner and Judea Pearl. Conditional entailment: Bridging two approaches to default
    reasoning. Artif. Intell., 53(2-3):209–244, 1992.
28. Oliver Fernandez Gil. On the Non-Monotonic Description Logic ALC+Tmin . CoRR,
    abs/1404.6566, 2014.
29. L. Giordano and V. Gliozzi. Reasoning about exceptions in ontologies: An approximation
    of the multipreference semantics. In ECSQARU 2019, Belgrade, Serbia, September 18-20,
    2019, Proceedings, volume 11726 of LNCS, pages 212–225. Springer, 2019.
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 Dupré. Defeasible Reasoning in SROEL from Rational En-
    tailment to Rational Closure. Fundam. Inform., 161(1-2):135–161, 2018.
35. L. Giordano and D. Theseider Dupré. An ASP approach for reasoning in a concept-
    aware multipreferential lightweight DL. Theory and Practice of Logic programming, TPLP,
    10(5):751–766, 2020.
36. L. Giordano and D. Theseider Dupré. A framework for a modular multi-concept lexico-
    graphic 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 Dupré. Weighted conditional E L⊥ knowledge bases with
    integer weights: an ASP approach. In ICLP 2021, 2021. To appear.
38. L. Giordano and D. Theseider Dupré. Weighted defeasible knowledge bases and a multi-
    preference 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 Non-
    monotonic 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, edi-
    tor, Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI
    1993), pages 676–681, Chambéry, France, August 1993. Morgan Kaufmann.

</pre>