=Paper=
{{Paper
|id=Vol-1517/JOWO-15_ontolp_paper_6
|storemode=property
|title=Upward Refinement for Conceptual Blending in Description Logic: An ASP-based Approach and Case Study in EL++
|pdfUrl=https://ceur-ws.org/Vol-1517/JOWO-15_ontolp_paper_6.pdf
|volume=Vol-1517
|dblpUrl=https://dblp.org/rec/conf/ijcai/ConfalonieriSPE15
}}
==Upward Refinement for Conceptual Blending in Description Logic: An ASP-based Approach and Case Study in EL++==
https://ceur-ws.org/Vol-1517/JOWO-15_ontolp_paper_6.pdf
Upward Refinement for Conceptual Blending in Description Logic
— An ASP-based Approach and Case Study in EL++ —
Roberto Confalonieri, Marco Schorlemmer, Enric Plaza
Artificial Intelligence Research Institute, IIIA-CSIC, Spain
{confalonieri,marco,enric}@iiia.csic.es
Manfred Eppe Oliver Kutz, Rafael Peñaloza
International Computer Science Institute, Berkeley, USA Free University of Bozen-Bolzano, Italy
eppe@icsi.berkeley.edu {oliver.kutz,rafael.penaloza}@unibz.it
Abstract We focus on the particular case of the description logic
EL++ (Baader, Brandt, and Lutz 2005; Baader, Brandt, and
Conceptual blending is understood to be a process that serves
a variety of cognitive purposes, including creativity, and has Lutz 2008). This is an excellent starting point for our inves-
been highly influential in cognitive linguistics. In this line tigation for several reasons. First, EL++ is the underpinning
of thinking, human creativity is modeled as a blending pro- logic of the OWL 2 EL Profile, a recommendation of the
cess that takes different mental spaces as input and combines W3C. Second, EL++ offers a good tradeoff between expres-
them into a new mental space, called a blend. According to sivity and efficiency of reasoning. Indeed, the EL++ syntax
this form of combinatorial creativity, a blend is constructed and axioms are considered to be sufficiently expressive to
by taking the existing commonalities among the input men- model large real-world ontologies. Finally, subsumption in
tal spaces—known as the generic space—into account, and an EL++ TBox is computable in polynomial time (Baader,
by projecting their structure in a selective way. Since input Brandt, and Lutz 2005).
spaces for interesting blends are often initially incompatible,
a generalisation step is needed before they can be blended. The generalisation of EL++ concepts has been studied
In this paper, we apply this idea to blend input spaces speci- both in the DLs and in the Inductive Logic Programming
fied in the description logic EL++ and propose an upward re- (ILP) literature, although from different perspectives. Whilst
finement operator for generalising EL++ concepts. We show approaches in DL focus on formalising the computation of
how the generalisation operator is translated to Answer Set a least general generalisation (LGG) (also known as least
Programming (ASP) in order to implement a search process common subsumer) among different concepts as a non-
that finds possible generalisations of input concepts. We ex- standard reasoning task (Baader 2005; Baader, Sertkaya, and
emplify our approach in the domain of computer icons. Turhan 2007; Turhan and Zarrieß 2013), approaches in ILP
are concerned on learning DL descriptions from examples
Introduction (Lehmann and Hitzler 2010). In both cases, however, find-
The upward refinement—or generalisation—of concepts ing a LGG is a challenging task. Its computability depends
plays a crucial role in creative processes for analogical on the type of DL adopted and on the assumptions made over
reasoning and concept invention, in particular conceptual the structure of concept definitions.
blending (Fauconnier and Turner 2002). In blending, one Our work relates to these approaches, but our main moti-
combines two input concepts to invent a new one. In gen- vation for generalising DL concepts is intrinsically different.
eral, however, this cannot be done because the combination Although we do need to be aware of what concepts share
of two concepts may generate an unsatisfiable one due to in order to blend them, it is not necessary (though desir-
contradiction. However, by slightly generalising input con- able) to find a generic space that is also a LGG. A suffi-
cepts we might be able to find a novel and useful combina- ciently specific common subsumer will suffice. With this ob-
tion of both. For instance, a ‘red French sedan’ and a ‘blue jective in mind, we propose an upward refinement operator
German minivan’ can be blended to a ‘red German sedan’ by for generalising EL++ concepts which is inductively defined
generalising the first concept to a ‘red European sedan’ and over the structure of concept descriptions. We discuss some
the second one to a ‘coloured German car’. The least general of the properties typically used to characterise refinement
generalisation of our input concepts—a ‘coloured European operators; namely, finiteness, properness and completeness
car’—serves as an upper bound of the generalisation space (van der Laag and Nienhuys-Cheng 1998). Briefly, a refine-
to be explored, and, in a certain sense, plays the role of the ment operator is said to be finite when it generates a finite set
so call generic space in conceptual blending, which states of refinements; proper, when its refinements are not equiva-
the shared structure of both concepts. lent to the original concept, and complete, when it produces
This paper addresses the formalisation of such a general- all possible refinements of a given concept.
isation process and tackles the following question: How can Particularly, the generalisations produced by our opera-
we define and implement a generalisation operator for de- tor are finite, but they can be sometimes equivalent to the
scription logics (DLs) and what are its desired or necessary concept being generalised (thus, the operator is not proper),
properties in order to use it in the blending process? and they are not all the possible ones (thus, the operator is
concept description interpretation called ABox, which contains extensional knowledge about
A AI ⊆ ∆ I individual objects of the domain. In this paper, we shall fo-
> ∆I cus only on terminological axioms of the form C v D, i.e.
⊥ ∅ general concept inclusions (GCIs), and r1 ◦ · · · ◦ rn v r, i.e.
C uD C I ∩ DI role inclusions (RIs), as well as axioms specifying domain
∃r.C {x ∈ ∆I | ∃y ∈ ∆I . and range restrictions for roles. Table 1 shows the form of
(x, y) ∈ ∧y ∈ C I } these axioms, together with the condition for these to be sat-
axiom satisfaction isfied by an interpretation I. By L(T ) we refer to the set of
CvD C I ⊆ DI all EL++ concept descriptions we can form with the concept
and role names occurring in T .
r1 ◦ · · · ◦ rn v r r1I ; · · · ; rnI ⊆ rI
RIs allow one to specify role hierarchies (r v s) and role
domain(r) v C r I ⊆ C I × ∆I
transitivity (r ◦ r v r). The bottom concept ⊥, in combina-
range(r) v C r I ⊆ ∆I × C I tion with GCIs, allows one to express disjointness of concept
descriptions, e.g. C u D v ⊥ tells that C and D are disjoint.
Table 1: Syntax and semantics of some EL++ contructors An interpretation I is a model of a TBox T iff it satisfies
and axioms. (Note:‘;’ is the usual composition operator in all axioms in T . The basic reasoning task in EL++ is sub-
relation algebra.) sumption. Given a TBox T and two concept descriptions C
and D, we say that C is (strictly) subsumed by D w.r.t. T ,
denoted as C vT D (C @T D), iff C I ⊆ DI (C I ⊆ DI
not complete). As we shall discuss, we sacrifice complete- and C I 6= DI ) for every model I of T . Analogously, given
ness for finiteness (since we do not need to compute a LGG, two roles r, s ∈ Nr , we say that r is (strictly) subsumed by s
strictly speaking), but we need the successive applications w.r.t. T , denoted as r vT s (r @T s), iff rI ⊆ sI (rI ⊆ sI
of the operator to always terminate. We point out, however, and rI 6= sI ) for every model I of T . Finally, an equiva-
how the properness property can be achieved. lence axiom C ≡ D is just an abbreviation for C v D and
We show how part of the upward refinement operator is D v C.
implemented in Answer Set Programming (ASP) (Gelfond
and Kahl 2014) and how we employ the search capabilities EL++ Running Example
of ASP to find a generic space among two EL++ input con- To exemplify our approach, we take the domain of computer
cepts. The ASP search is part of an amalgamation process icons into account. We consider computer icons as combi-
(Ontañón and Plaza 2010) that models conceptual blending. nations of signs (e.g., Document, MagnifyingGlass, Hard-
Throughout the paper, we use an example in the domain of Disk, Pen, etc.) (Confalonieri et al. 2015). Signs are related
computer icon design. by qualitative spatial relations such as above, behind, etc.
In the ontology below, concept names are capitalised
Background and Running Example (e.g. Sign) and role names are written in lower-case
(e.g. hasSign). We assume that a TBox T consists of two
The Description Logic EL++ parts: one part that contains the background knowledge
In DLs, concept and role descriptions are defined inductively about the icon domain Tbk , and another part that contains
by means of concept and role constructors over a finite set the domain knowledge about icon definitions Tdk .
NC of concept names, a finite set Nr of role names, and Generally, an icon is related to different signs by means
(possibly) a finite set NI of individual names. As is com- of the hasSign role.
mon practice, we shall write A, B for concept names, C, D
for concept descriptions, r, s for role names, and a, b, for αbk1 : Icon v Thing
αbk2 : Sign v Thing
individual names.
αbk3 : Document v Sign
The semantics of concept and role descriptions is de- αbk4 : HardDisk v Sign
fined in terms of an interpretation I = (∆I , ·I ), where αbk5 : MagnifyingGlass v Sign
∆I is a non-empty domain and ·I is an interpretation func- αbk6 : Pen v Sign
tion assigning a set AI ⊆ ∆I to each concept name αbk7 : domain(hasSign) v Icon
A ∈ NC , a set rI ⊆ ∆I × ∆I to each role name αbk8 : range(hasSign) v Sign
r ∈ Nr , and an element aI ∈ ∆I for each individual αbk9 : Document u HardDisk v ⊥
name a ∈ NI , which is extended to general concept and ... ...
role descriptions. Table 1 shows the constructors of the de- αbk15 : MagnifyingGlass u Pen v ⊥
scription logic EL++ that are relevant for this paper, to- Sign concepts are disjoint (αbk9 -αbk15 ) and they are
gether with their interpretation. For a complete presenta- related by spatial relationships isAbove, isBehind, isLeft
tion of EL++ we refer to (Baader, Brandt, and Lutz 2005; and isRight that are modelled as roles. These roles are
Baader, Brandt, and Lutz 2008). subsumed by a more generic role that is isInSpatialRelation
A knowledge base usually consists of a finite set T of whose domain and range is the Sign concept. Spatial re-
terminological axioms, called TBox, which contains inten- lationships are transitive as expressed by axioms αbk22 -αbk26 .
sional knowledge defining the main notions relevant to the αbk16 : domain(isInSpatialRelation) v Sign
domain of discourse; and a finite set A of assertional axioms, αbk17 : range(isInSpatialRelation) v Sign
αbk18 : isAbove v isInSpatialRelation Generic Space
αbk19 : isBehind v isInSpatialRelation Icon ⊓ ∃hasSign.Sign ⊓ ∃hasSign.
αbk20 : isLeft v isInSpatialRelation (Sign ⊓ ∃isAbove.Sign)
αbk21 : isRight v isInSpatialRelation Generalisation Generalisation
MGS
αbk22 : isAbove ◦ isAbove v isAbove
... ...
Icon ⊓ ∃hasSign.Sign ⊓ ∃hasSign. Icon ⊓ ∃hasSign.Document ⊓ ∃hasSign.
αbk26 : isInSpatialRelation ◦ isInSpatialRelation v (MagnifyingGlass ⊓ ∃isAbove.Sign) (Sign ⊓ ∃isAbove.Document)
isInSpatialRelation
Given the axioms above, we can describe some icons in the Input 1 Input 2
domain knowledge of a TBox. Icon ⊓ ∃hasSign.HardDisk ⊓ ∃hasSign. Icon ⊓ ∃hasSign.Document ⊓ ∃hasSign.
(MagnifyingGlass ⊓ ∃isAbove.HardDisk)
Example 1. SearchHardDisk is an icon that consists (Pen ⊓ ∃isAbove.Document)
of two signs MagnifyingGlass and HardDisk, where the Blend
MagnifyingGlass sign is above the HardDisk sign. An-
other icon is the EditDocument icon, where the Pen sign is Icon ⊓ ∃hasSign.Document ⊓ ∃hasSign.
(MagnifyingGlass ⊓ ∃isAbove.Document)
above the Document sign. Both icons are shown in Figure 1:
αdk1 : SearchHardDisk ≡ Icon u ∃hasSign.HardDisku
∃hasSign.(MagnifyingGlass u ∃isAbove.HardDisk) Figure 1: Blending the SearchHardDisk and EditDocument
αdk2 : EditDocument ≡ Icon u ∃hasSign.Documentu icon concepts into a new concept representing a preview-
∃hasSign.(Pen u ∃isAbove.Document) document icon.
In the paper, we will show how we can create new EL++
concepts by blending existing concepts in the domain therefore also in L(T ) with the subsumption relation vT
knowledge of a TBox. Specifically, we will see how to gen- for a given EL++ Tbox T .
erate the following concept representing a new blended icon: Given two descriptions C1 , C2 ∈ L(T ), a most gen-
eral specialisation (MGS) is a description Cmgs such that
Icon u ∃hasSign.Document u ∃hasSign. Cmgs vT C1 and Cmgs vT C2 and for any other descrip-
(MagnifyingGlass u ∃isAbove.Document)
tion D satisfying these properties, D vT Cmgs . A least
Intuitively, given two input concepts, a new concept is cre- general generalisation (LGG) is a description Clgg such that
ated by taking the commonalities and some specific parts C1 vT Clgg and C2 vT Clgg and for any other description
of the input concepts into account (Figure 1). For instance, D satisfying these properties, Clgg vT D.
both SearchHardDisk and EditDocument are icons that Intuitively, a MGS is a description that has all the infor-
consist of two signs with one sign above the other one mation in both the original descriptions C1 and C2 , while a
(the generic space). Then, if we keep the MagnifyingGlass LGG contains that which is common to them.
sign from SearchHardDisk and the Document sign from An amalgam of two descriptions is a new description
EditDocument, and we ‘relax’ the HardDisk and Pen that contains parts from these original descriptions. For in-
signs, we can blend the generalised input concepts of stance, an amalgam of ‘a red French sedan’ and ‘a blue Ger-
SearchHardDisk and EditDocument into a new concept rep- man minivan’ is ‘a red German sedan;’ clearly there are al-
resenting a preview-document icon.1 ways multiple possibilities for amalgams, like ‘a blue French
The process of conceptual blending is characterised in minivan’.
terms of amalgamation (Ontañón and Plaza 2010), an ap- For the purposes of this paper we can define an amalgam
proach that has its root in case-based reasoning and focuses of two descriptions as follows:
on the problem of combining solutions coming from mul- Definition 1 (Amalgam). Let T be a Tbox in EL++ . A de-
tiple cases. According to this approach, input concepts are scription Cam ∈ L(T ) is an amalgam of two descriptions
generalised until a generic space is found, and pairs of gen- C1 and C2 (with LGG Clgg ) if there exist two descriptions
eralised versions of the input concepts are ‘combined’ to cre- C10 and C20 such that:
ate blends. 1. C1 vT C10 vT Clgg ,
Computational concept blending by amalgamation 2. C2 vT C20 vT Clgg , and
Formally, the notion of amalgam can be defined in any repre- 3. Cam is a MGS of C10 and C20
sentation language L for which a subsumption relation be- In the next section, we define an upward refinement operator
tween formulas (or descriptions) of L can be defined, and that allows us to find generalisations of EL++ concept de-
scriptions needed for computing the amalgams as described
1
Of course, there are some combinations of generalised in- above, although we may generalise concepts C1 and C2 be-
put concepts that are not interesting. For instance, a concept such as yond the LGG Clgg . We do this to guarantee termination, as
Icon u ∃hasSign.MagnifyingGlass u ∃hasSign.(Pen u ∃isAbove. we shall explain below.
MagnifyingGlass) should be discarded. This issue relates to blend
evaluation and it is not addressed in this paper. We refer the
interested reader to (Confalonieri et al. 2015) where a discussion Refinement Operators
about the use of argumentation to evaluate conceptual blends is Refinement operators are a well known notion in Induc-
presented. tive Logic Programming where they are used to structure
a search process for learning concepts from examples. In cept descriptions as follows:
this setting, two types of refinement operators exist: spe-
cialisation (or downward) refinement operators and general- sub(A) = {A}
isation (or upward) refinement operators. While the former sub(⊥) = {⊥}
constructs specialisations of hypotheses, the latter contructs sub(>) = {>}
generalisations.2
sub(C u D) = {C u D} ∪ sub(C) ∪ sub(D)
Generally speaking, refinement operators are defined over
quasi-ordered sets. A quasi-ordered set is a pair hS, i sub(∃r.C) = {∃r.C} ∪ sub(C)
where S is a set and is a binary relation among elements
of S that is reflexive (a a) and transitive (if a b and
b c then a c). If a b, we say that b is more general Based on sub(T ), we define the upward cover set of atomic
than a, and if also b a we say that a and b are equivalent. concepts and roles. sub(T ) guarantees the following up-
A generalisation refinement operator is defined as follows. ward cover set to be finite.
Definition 2. A generalisation refinement operator γ over Definition 4. Let T be a Tbox in EL++ (with concept names
a quasi-ordered set hS, i is a function such that ∀a ∈ S : from NC ). The set of upward covers3 of an atomic concept
γ(a) ⊆ {b ∈ S | a b}. A ∈ NC ∪ {>, ⊥} and of a role r ∈ Nr with respect to T is
given as:
A refinement operator γ can be classified according to some
desirable properties (van der Laag and Nienhuys-Cheng UpCov(A) ={C ∈ sub(T ) | A @T C (1)
1998). We say that γ is:
and there is no C 0 ∈ sub(T )
• locally finite if the number of generalisations generated such that A @T C 0 @T C}
for any given element by the operator is finite, that is,
∀a ∈ S : γ(a) is finite; UpCov(r) ={s ∈ Nr | r @T s (2)
0
• proper if an element is not equivalent to any of its gener- and there is no s ∈ Nr
alisations, i.e., ∀a, b ∈ S, if b ∈ γ(a), then a and b are not such that r @T s0 @T s}
equivalent;
• complete if there are no generalisations which are not gen- We can now define our generalisation refinement operator
erated by the operator, i.e., ∀a, b ∈ S it holds that if a b, for EL++ as follows:
then b ∈ γ ∗ (a) (where γ ∗ (a) denotes the set of all ele- Definition 5. Let T be a TBox in EL++ . We define the gener-
ments which can be reached from a by means of γ in a alisation operator γ inductively over the structure of concept
finite number of steps). descriptions as shown in Figure 2.
When a refinement operator is locally finite, proper, and Given a refinement operator γ, EL++ concepts are related
complete it is said to be ideal. by refinement paths as follows:
An ideal specialisation refinement operator for EL has
Definition 6. A finite sequence C1 , . . . , Cn of concepts is a
been explored in (Lehmann and Haase 2010). In what fol- γ
lows, we will define a generalisation refinement operator for concept refinement path C1 − → Cn from C1 to Cn of a gen-
EL++ and discuss its properties. eralisation operator γ if C2 ∈ γ(C1 ), . . . , Cn ∈ γ(Cn−1 ).
D can be reached from C by γ if there exists a refinement
A Generalisation Refinement Operator for EL++ path from C to D. γ ∗ (C) denotes the set of all concepts that
can be reached from C by means of γ. Sometimes we write
In any description logic the set of (complex) concept de- C γ D instead of D ∈ γ(C).
scriptions are ordered under the subsumption relation form-
ing a quasi-ordered set. For EL++ in particular they form a That γ is indeed a generalisation refinement operator as de-
bounded meet-semilattice with conjunction as meet opera- fined in Definition 2 can be proven by applying structural
tion and > as greatest element as well as ⊥ as least element. induction on EL++ concepts to show that C γ D implies
C v D, in a similar way as in the proof of Proposition 11
In order to define a generalisation refinement operator for
from (Lehmann and Hitzler 2010).
EL++ we will need some auxiliary definitions.
As far as the properties of γ are concerned, we can ob-
Definition 3. Let T be a TBox in EL++ . The set of subcon- serve the following. Our definition of UpCov for concepts
cepts of T is given as and roles only considers the set of subconcepts present in a
[ Tbox T . On the one hand, this guarantees that γ is finite,
sub(T ) = sub(C) ∪ sub(D) since at each generalisation step, the set of possible gener-
CvD∈T alisations is finite. On the other hand, however, this implies
where sub is inductively defined over the structure of con- 3
Notice that the set of upward covers we define only takes
into account subconcepts already present in the TBox. Therefore,
2
A deeper analysis of refinement operators can be found in strictly speaking, its elements may not be covers with respect to
(van der Laag and Nienhuys-Cheng 1998). subsumption in EL++ .
γ(A) = UpCov(A) γr (∃r.C) = {∃s.C | s ∈ UpCov(r)}
γ(>) = UpCov(>) = ∅ γ C (∃r.C) = {∃r.C 0 | C 0 ∈ γ(C) ∧ C 0 v range(r)}
γ(⊥) = UpCov(⊥)
γ(C u D) = {C 0 u D | C 0 ∈ γ(C)} ∪ {C u D0 | D0 ∈ γ(D)}
γr (∃r.C) ∪ γC (∃r.C) whenever UpCov(r) 6= ∅ or C 6= >
γ(∃r.C) =
{>} otherwise
Figure 2: A generalisation refinement operator for EL++ . range(r) is defined in Table 1.
that γ is not complete, since it cannot find all possible up- In order to find a generic space between two icons, we
ward covers of a concept w.r.t. subsumption in EL++ .4 generalise their definitions using the upward refinement op-
Regarding the properness property, γ is not proper since erator in Figure 2 implemented in ASP.
there exist cases in which the generalisations produced by γ The current status of the implementation considers two
are equivalent to the concept being generalised. One way to types of generalisation: γ(A) that generalises an atomic con-
guarantee the properness of γ is by rewriting the concept that cept by its upward cover and γC (∃r.C) that generalises a
we want to generalise into equivalent normal forms before concept that fills the range of a role. We reserve the com-
and after each generalisation steps. We will investigate how plete implementation of γ as future work. In this setting, the
normalisation can be done as future research. domain knowledge of a TBox T is generalised in a step-wise
For the blending, we are interested in finding a common transition process. In the following, t denotes a step-counter
generalisation G (generic space) between two concepts. that represents the number of modifications made to the do-
main knowledge part of T . Table 2 shows the main EDB and
Example 2. Let us consider the EL++ concepts IDB predicates used in the ASP implementation.
EditDocument and SearchHardDisk defined in Exam-
ple 1. It can be checked that: Modeling EL++ concepts in ASP
γ
For each concept name A ∈ NC in a TBox T , we state the
EditDocument −→ Icon u ∃hasSign.Sign u ∃hasSign. facts:
(Sign u∃isAbove.Sign)
γ
SearchHardDisk −
→ Icon u ∃hasSign.Sign u ∃hasSign. hasConcept(T , A, t) (3a)
(Sign u ∃isAbove.Sign) isAtomicConcept(T , A, t) (3b)
Therefore, G = Iconu ∃hasSign. Sign u ∃hasSign. isBackgroundConcept(T , A) (3c)
(Sign u ∃isAbove.Sign) is a generic space for For each role r ∈ Nr in a TBox T , with domain(r) v C
EditDocument and SearchHardDisk. and range(r) v D, we state the facts:
It is worth to discuss that since γ is not complete, we cannot hasRole(T , r, t) (4a)
guarantee that the generic space between two EL++ con- hasRoleRange(T , r, D, t) (4b)
cepts is a least general generalisation. Nevertheless, since
hasRoleDomain(T , r, C, t) (4c)
the concepts and generalisations that γ finds form a bounded
semilattice, we can ensure that we can always find a generic isBackgroundRole(T , r) (4d)
space between two concepts. We believe that not finding a For each inclusion axiom A v B ∈ T and A, B are atomic
least general generalisation is not a weakness of our ap- concepts, we state the fact:
proach since we are interested in finding a generic space that
allow us to create new EL++ concepts from existing ones by hasP arentConcept(T , A, B, t) (5)
conceptual blending. Similarly, for each role inclusion axiom r v s ∈ T , we state
the fact:
hasP arentRole(T , r, s, t) (6)
Implementing Upward Refinement in ASP
For each inclusion axiom A v C ∈ T , in which A is an
We consider two TBoxes T1 and T2 5 and we assume that atomic concept and C is a complex concept, we call C the
T1 and T2 have the same background knowledge about icon concept definition of A and denote it as ADef within the
domain but different domain knowledge which, in our case, following ASP facts:
contain icon definitions.
hasConcept(T , ADef , t) (7a)
4
For instance, if T contains two axioms A v B, A v C, and isComplexConcept(T , ADef , t) (7b)
we generalise A (in the domain knowledge), then γ(A) = {B, C} hasP arentConcept(T , A, ADef , t) (7c)
while a possible generalisation of A w.r.t. vT is B u C. isBackgroundConcept(T , ADef ) (7d)
5
We assume to have two TBoxes because we want our imple-
mentation to be general, that is, to also work in a scenario in which For each Ci in the complex concept C = C1 u . . . u Cn , we
we align concepts described using different background ontologies. make a case distinction and state the following facts:
EDB predicates Description
spec(T ) A reference to a TBox T
hasConcept(T , C, t) A concept C belongs to a TBox T at step t
hasP arentConcept(T , A, B, t) A concept B subsumes A in a TBox T at step t
isComplexConcept(T , C, t) A concept C is a complex concept in a TBox T at step t
complexCInvolvesCon(T , C, A, t) A concept C contains a concept A in a TBox T at step t
complexCInvolvesRole(T , C, r, A, t) A concept C contains a role r whose range is filled by A in a TBox T at step t
IDB predicates Description
notEqual (T1 , T2 , t) The TBoxes T1 , T2 are not equivalent at step t
conceptsNotEquivalent(T1 , T2 ,, t) The concepts in the TBoxes T1 , T2 are not equivalent at step t
complexCConceptNotEq(T1 , T2 , C, A, t) A concept A in C is not equivalent in the TBoxes T1 , T2 at step t
complexCRoleConceptNotEq(T1 , T2 , C, r, A, t) A concept A filling the role r of C is not equivalent in the TBoxes T1 , T2 at step t
poss(a, T , t) An upward refinement step a is executable in a TBox T at step t
exec(a, T , t) An upward refinement step a is executed in a TBox T at step t
Table 2: Overview of the main EDB and IDB predicates used to formalise the upward refinement process in ASP.
1. if Ci = B: Upward refinement of atomic concepts. A fact
exec(genConcept(C , A, B ), T , t) denotes the general-
complexCInvolvesCon(T , ADef , B, t) (8) isation of a concept A to a concept B in a complex concept
2. if Ci = ∃r.A: C of a TBox T at step t using γA . The precondition rule for
generalising A is:
complexCInvolvesRole(T , ADef , r, A, t) (9)
3. if Ci = ∃r.D: poss(genConcept(C, A, B), T1 , t) ← (11)
hasConcept(T , DDef , t) (10a) not isBackgroundConcept(T1 , C),
isComplexConcept(T , DDef , t) (10b) complexCInvolvesCon(T1 , C, A, t),
complexCInvolvesRole(T , ADef , r, DDef , t) (10c) hasParentConcept(T1 , A, B, t),
isBackgroundConcept(T , DDef ) (10d) complexCConceptNotEq(T1 , T2 , C, A, t),
not exec(genConcept(C, A, B), T2 , t), spec(T2 )
The concepts belonging to the domain knowledge part
Tdk of a TBox T are modeled in a similar way but
without the isBackgroundConcept/3 facts. Besides, we There are several preconditions for generalising an atomic
model the concept > as the fact hasConcept(T , Thing, t), concept in a complex concept C. First, C must not be a
and for each concept name A ∈ NC , which is not background concept since we do not want to modify the
already subsumed by other concept names, we add a background knowledge of a TBox T . Second, the con-
fact hasParentConcept(T , A, Thing, t). We check for cept C involves a concept A that has a parent concept
(in)equality of TBoxes by a rule notEqual (T1 , T2 , t) ← B in the subsumption hierarchy defined by the axioms
conceptsNotEquivalent(T1 , T2 ,, t). The rule is triggered of the TBox. Third, the definition of C in the TBoxes
by additional rules if, for T1 and T2 , at step t, atomic con- is not equivalent (complexCConceptNotEq/4 ). The atom
cepts, roles and complex concepts are not equal. complexCConceptNotEq/4 is true either when one of the
TBoxes does not contain C or when the definitions of (the
Formalising upward refinement in ASP structure of) C are different. Another condition is that C has
not been generalised in the other TBox.
In what follows, we refer to the upward operator types we
implemented as γA and γC . γA stands for the generalisa- We also need a simple inertia rule for generalising a con-
tion of an atomic concept (first row in Fig. 2) and γC for cept in a complex concept. This is as follows:
the generalisation of a concept filling the range of a role.
Each upward refinement operator type is an action; to this noninertial (T , C, A, t) ← exec(genConcept(C, A, ), T , t)
end, we model each operator type via a precondition rule, an (12)
inertia rule, and an effect rule. Preconditions are modelled
with a predicate poss/3 that states when it is possible to ex-
ecute an operator type. Inertia is modelled with a predicate noninertial atoms will cause a concept A to remain in the
noninertial /3 that states when an element of a concept in T complex concept C in a TBox T , as defined via rule (15a).
remains unchanged after the execution of a refinement oper-
ator type. Effect rules model how a refinement operator type Upward refinement of range concepts. A fact
changes a concept in the domain knowledge. We represent exec(genConceptInRole(C , r , A, B ), T , t) denotes
the execution of an upward refinement operator type with the generalisation of a concept A to a concept B when A
atoms exec(γx , T , t), to denote that a generalisation opera- fills the range of a role r in a complex concept C of a TBox
tor type γx ∈ {γA , γC } is applied to T at a step t. T at step t using γC . The precondition rule for generalising
a concept A is: Upward refinement search
poss(genConceptInRole(C, r, A, B), T1 , t) ← (13) We use ASP for finding a generic space and the generalised
versions of the concepts in the domain knowledge of T ,
not isBackgroundConcept(T1 , C),
which can lead to a blend. This is done by successively gen-
complexCInvolvesRole(T1 , C, r, A, t) eralising the concepts in the domain knowledge by means
hasParentConcept(T1 , A, B, t), of the upward operator steps we described in the previous
complexCRoleConceptNotEq(T1 , T2 , C, r, A, t), subsection. Again, this is a first implementation and does
not isNotInRoleRange(T1 , r, B), spec(T2 ), not capture the recursive definition of the upward refinement
not exec(genConceptInRole(C, r, A, B), T2 , t), spec(T2 )
operator that we leave as future work.
A sequence of generalisation operator types defines a re-
The preconditions for generalising a concept filling the role finement path.
of a complex concept C are similar to the case of gener- Definition 7 (Refinement path). Let T be a TBox, let
alising an atomic concept. First, C must not be a back- {γx1 , . . . , γxn } be the set of generalisation steps for T , t1 <
ground concept. Second, C involves a role in which the · · · < tn be refinement steps and γx ∈ {γA , γC }. The set
concept to be generalised has a parent concept in the sub- of atoms P = {exec(γx1 , T , t1 ), · · · , exec(γxn , T , tn )} is a
sumption hierarchy of the TBox. Then, the definitions of refinement path of T .
the concept to be generalised must not be equivalent in the Refinement paths are generated with the following choice
TBoxes. (complexCRoleConceptNotEq/4 ). Another con- rule, that allows one or zero refinement operators per T at
dition is needed in the case of this generalisation, that is, the each step t:
concept that we want to use to generalise the range of a role,
must be in the range of r. This is checked by means of the
atom isNotInRoleRange/3 . Finally, the concept to be gen- 0{exec(a, T , t) : poss(a, T , t)}1 ← (17)
eralised must have not been generalised in the other TBox. not genericReached (t), spec(T )
The inertia rule for generalising a concept that fills the The only generalisations that are executed are those
range of a role in a TBox is analogous to the inertial rule for whose preconditions are satisfied. Refinement paths lead
generalising a concept:
from the input TBoxes to a generic space, which is a gener-
noninertial (T , C, A, t) ← (14) alised TBox that contains the commonalities of the concepts
exec(genConceptInRole(C, A, ), T , t) in the domain knowledge. A generic space is reached, if the
generalised TBoxes are equals. The notEqual predicate is
noninertial atoms will cause a concept A to remain in the used to determine if a generic space is reached.
range of a role as defined via rule (15b).
Inertia. The following rules state which concepts remain notGenericReached (t) ←spec(T1 ), spec(T2 ), (18a)
in a TBox T when they are inertial. notEqual (T1 , T2 , t), T1 6= T2
complexCInvolvesCon(T , C, A, t + 1) ← (15a) ← notGenericReached (t) (18b)
complexCInvolvesCon(T , C, A, t), The constraint (18b) ensures that the generic space is
not noninertial (T , C, A, t) reached in all stable models. The ASP program generates
one stable model for each combination of generalisation
paths that lead to the generic space.
complexCInvolvesRole(T , C, r, A, t + 1) ← (15b)
complexCInvolvesRole(T , C, r, A, t),
Example 3. Let us consider the SearchHardDisk and
EditDocument concepts in Example 1 representing icons
not noninertial (T , C, A, t) in the domain knowledge of two TBoxes SearchHD and
Besides, other inertia rules are needed for expressing that EditDoc. Their refinement paths are:
all the concepts and roles of the background knowledge and
their subsumption relations remain in a TBox T . We omit PSearchHD = {exec(genConceptInRole(SearchHDDef,
them. hasSign, HardDisk, Sign, SearchHD, 0),
Effects. The following rules state which concepts change exec(genConceptInRole(SearchHDDef Def, isAbove,
in a TBox T when they are generalised. HardDisk, Sign), SearchHD, 1)}
complexCInvolvesCon(T , C, B, t + 1) ← (16a) exec(genConcept(SearchHDDef Def,
complexCInvolvesCon(T , C, A, t), M agnif yingGlass, Sign), SearchHD, 2),
exec(genConcept(C, A, B), T , t) PEditDoc = {exec(genConcept(EditDocDef Def, P en, Sign),
EditDoc, 0),
exec(genConceptInRole(EditDocDef, hasSign, Document,
complexCInvolvesRole(T , C, r, B, t + 1) ← (16b) Sign), EditDoc, 1),
complexCInvolvesRole(T , C, r, A, t), exec(genConceptInRole(EditDocDef Def ),
exec(genConceptInRole(C, r, A, B), T , t) isAbove, Document, Sign), EditDoc, 2)}
After applying the respective generalisation operators a Turhan 2013; Turhan and Zarrieß 2013). Generally speak-
generic space is reached. It is easy to check that this cor- ing, since the LGG w.r.t. general TBoxes in the EL fam-
responds to the generic space in Example 2. ily does usually not exist, these approaches propose several
‘workarounds’ for computing it. For instance, (Baader 2003;
Blending EL++ concepts 2005) devises the exact conditions for the existence of the
LGG for cyclic EL-TBoxes based on graph-theoretic gen-
In Definition 1, we defined the blends of two EL++ concepts eralisations. (Baader, Sertkaya, and Turhan 2007) propose
in terms of amalgams. Once a generic space between two an algorithm for computing good LGGs w.r.t. a background
concepts has been determined, blends are created by com- terminology. (Zarrießand Turhan 2013; Turhan and Zarrieß
puting the MGS of pairs of generalised concepts. In EL++ 2013) specify the conditions for the existence of the LGG for
the MGS of two EL++ concepts is just their conjunction. general EL- and EL+ -TBoxes based on canonical models.
Then we will have to normalise this conjunction to obtain As already commented in the introduction, our work relates
the most concise description of the newly created concept. to these approaches, but it is different in spirit, since we do
This is just a rough description of conceptual blending not need to find the LGG between (two) EL++ concepts for
in EL++ , and normalisation for newly created blends still the kind of application we are developing.
needs to be studied in detail (this also relates to the opera- ILP approaches, on the other hand, study the LGG in
tor properness). Blending will also need to consider an in- terms of generalisation and specialisation refinement opera-
terleaved evaluation and generation process in order to find tors. Specialisation rsefinement operators have been defined
the best pairs of generalised concepts for creating interesting for learning DL ontologies (Lehmann and Hitzler 2008;
blends. Lehmann and Haase 2010) and for measuring the similar-
Example 4. Let us consider C1 = SearchHardDisk, C2 = ity of EL concepts (Sánchez-Ruiz et al. 2011; 2013).
EditDocument, G in Example 2 and the refinement paths Finally, some of the approaches that combine ASP for rea-
PSearchHD , PEditDoc in Example 3. The generalisations soning over DL ontologies are (Swift 2004; Eiter et al. 2008;
of C1 and C2 by applying the generalisation steps 0-1 in Ricca et al. 2009).
PSearchHD and step 0 in PEditDoc respectively are:
Conclusion and Future Works
C10 = Icon u ∃hasSign.Sign u ∃hasSign. In this paper, we defined an upward refinement operator for
(MagnifyingGlass u ∃isAbove.Sign) generalising EL++ concepts for conceptual blending. The
C20 = Icon u ∃hasSign.Document u ∃hasSign.
operator works by recursively traversing their descriptions.
(Sign u ∃isAbove.Document)
We discussed the properties of the refinement operator. The
Then, the conjunction C10 u C20 = (Icon u ∃hasSign. operator is finite, can be proper (by allowing a normalisa-
Signu ∃hasSign. (MagnifyingGlass u∃isAbove.Sign)) tion before each refinement step), but it is not complete. We
u (Iconu ∃hasSign.Documentu ∃hasSign. (Sign claimed, however, that completeness is not an essential prop-
u∃isAbove.Document)). C10 u C20 is simplified to ob- erty for our needs, since being able to find a generic space
tain the blend concept Iconu ∃hasSign. Documentu between two EL++ concepts, although not a LGG, is already
∃hasSign.(MagnifyingGlass u∃isAbove.Document) by a sufficient condition for conceptual blending.
normalisation. We presented a first implementation of the refinement op-
Conceptual blending in EL++ as described in this paper is erator in ASP. We showed how to model the description
a special case of blending as modelled in (Bou et al. 2014) of EL++ concepts in ASP and to formalise two refinement
and implemented for CASL theories in (Eppe et al. 2015). operator types for generalising the domain knowledge of a
TBox. The stable models of the ASP program contain the
generalisation steps needed to be applied in order to gener-
Related Work alise two EL++ concepts until a generic space is reached.
There exist several works that relate to ours from different We discussed how the blend of two EL++ concepts, defined
perspectives, that are, approaches to conceptual blending of in terms of their most general specification, can be obtained
ontologies, approaches for finding the LGG in the EL fam- by their conjunction. We exemplified our approach in the
ily, and approaches that uses ASP for reasoning over DL domain of computer icon design.
ontologies. As future works, we plan to continue with the implemen-
Conceptual blending of ontologies in DLs has been ex- tation of the EL++ generalisation operator, to investigate the
plored in (Hois et al. 2010; Kutz et al. 2014) where blends normalisation rules needed for the operator to be proper and
are computed as colimits of algebraic specifications. As for normalising the blends, as well as to implement a con-
such, the blending process is not characterised in terms of ceptual blending algorithm. We also aim at studying the re-
amalgamation, the input concepts are not generalised, and lationship between the category of CASL theories (Mosses
the generic space is assumed to be given. 2004) and signature morphisms and the category of EL++
Several approaches for generalising ontology concepts in concept descriptions and subsumption relation.
the EL family exist in the DLs and ILP literature. We consider the work of this paper to be a fundamental
On the one hand, in DL approaches the LGG is defined in step towards the challenging task of defining and implement-
terms of a non-standard reasoning task over a TBox (Baader ing an upward refinement operator for more expressive DLs
2003; 2005; Baader, Sertkaya, and Turhan 2007; Zarrießand in the context of conceptual blending.
Acknowledgements D., eds., Artificial Intelligence: Methodology, Systems, and
This work is partially supported by the COINVENT project Applications, volume 6304 of LNCS. Springer Berlin Hei-
(FET-Open grant number: 611553). delberg. 263–264.
Kutz, O.; Bateman, J.; Neuhaus, F.; Mossakowski, T.; and
References Bhatt, M. 2014. E pluribus unum: Formalisation, Use-Cases,
Baader, F.; Brandt, S.; and Lutz, C. 2005. Pushing the EL and Computational Support for Conceptual Blending. In
Envelope. In Proceedings of the 19th International Joint Computational Creativity Research: Towards Creative Ma-
Conference on Artificial Intelligence, 364–369. San Fran- chines, Thinking Machines. Atlantis/Springer.
cisco, CA, USA: Morgan Kaufmann Publishers Inc. Lehmann, J., and Haase, C. 2010. Ideal Downward Re-
Baader, F.; Brandt, S.; and Lutz, C. 2008. Pushing the EL finement in the EL Description Logic. In Proc. of the 19th
Envelope Further. In Clark, K., and Patel-Schneider, P. F., Int. Conf. on Inductive Logic Programming, ILP’09, 73–87.
eds., In Proceedings of the OWLED 2008 DC Workshop on Berlin, Heidelberg: Springer-Verlag.
OWL: Experiences and Directions. Lehmann, J., and Hitzler, P. 2008. A Refinement Operator
Baader, F.; Sertkaya, B.; and Turhan, A.-Y. 2007. Comput- Based Learning Algorithm for the ALC Description Logic.
ing the least common subsumer w.r.t. a background termi- In Proceedings of the 17th Int. Conf. on Inductive Logic Pro-
nology. Journal of Applied Logic 5(3):392 – 420. gramming, 147–160. Berlin, Heidelberg: Springer-Verlag.
Lehmann, J., and Hitzler, P. 2010. Concept learning in de-
Baader, F. 2003. Computing the Least Common Subsumer
scription logics using refinement operators. Machine Learn-
in the Description Logic EL w.r.t. Terminological Cycles
ing 78(1-2):203–250.
with Descriptive Semantics. In Ganter, B.; de Moor, A.; and
Lex, W., eds., Conceptual Structures for Knowledge Cre- Mosses, P. D. 2004. CASL Reference Manual – The Com-
ation and Communication, volume 2746 of LNCS. Springer plete Documentation of the Common Algebraic Specifica-
Berlin Heidelberg. 117–130. tion Language, volume 2960 of LNCS. Springer.
Baader, F. 2005. A Graph-Theoretic Generalization of the Ontañón, S., and Plaza, E. 2010. Amalgams: A Formal Ap-
Least Common Subsumer and the Most Specific Concept in proach for Combining Multiple Case Solutions. In Bichin-
the Description Logic EL. In Hromkovič, J.; Nagl, M.; and daritz, I., and Montani, S., eds., Proceedings of the Interna-
Westfechtel, B., eds., Graph-Theoretic Concepts in Com- tional Conference on Case Base Reasoning, volume 6176 of
puter Science, volume 3353 of LNCS. Springer Berlin Hei- LNCS, 257–271. Springer.
delberg. 177–188. Ricca, F.; Gallucci, L.; Schindlauer, R.; DellArmi, T.;
Bou, F.; Eppe, M.; Plaza, E.; and Schorlemmer, M. Grasso, G.; and Leone, N. 2009. OntoDLV: An ASP-based
2014. D2.1: Reasoning with Amalgams. Techni- System for Enterprise Ontologies. Journal of Logic and
cal report, COINVENT Project. http://www.coinvent- Computation 19(4):643–670.
project.eu/fileadmin/publications/D2.1.pdf. Sánchez-Ruiz, A.; Ontañón, S.; González-Calero, P.; and
Confalonieri, R.; Corneli, J.; Pease, A.; Plaza, E.; and Schor- Plaza, E. 2011. Measuring Similarity in Description Logics
lemmer, M. 2015. Using Argumentation to Evaluate Con- Using Refinement Operators. In Ram, A., and Wiratunga,
cept Blends in Combinatorial Creativity. In Proceedings of N., eds., Case-Based Reasoning Research and Development,
the 6th International Conference on Computational Creativ- volume 6880 of LNCS. Springer Berlin. 289–303.
ity, ICCC15. To Appear. Sánchez-Ruiz, A.; Ontañón, S.; González-Calero, P.; and
Eiter, T.; Ianni, G.; Lukasiewicz, T.; Schindlauer, R.; and Plaza, E. 2013. Refinement-Based Similarity Measure
Tompits, H. 2008. Combining answer set programming over DL Conjunctive Queries. In Delany, S., and Ontañón,
with description logics for the semantic web. Artificial In- S., eds., Case-Based Reasoning Research and Development,
telligence 172(1213):1495 – 1539. volume 7969 of LNCS. Springer Berlin. 270–284.
Eppe, M.; Confalonieri, R.; MacLean, E.; Kaliakatsos, M.; Swift, T. 2004. Deduction in Ontologies via ASP. In Lif-
Cambouropoulos, E.; Schorlemmer, M.; and Kühnberger, schitz, V., and Niemelä, I., eds., Logic Programming and
K.-U. 2015. Computational invention of cadences and chord Nonmonotonic Reasoning, volume 2923 of LNCS. Springer
progressions by conceptual chord-blending. In Proceedings Berlin. 275–288.
of the 24th International Joint Conference on Artificial In- Turhan, A., and Zarrieß, B. 2013. Computing the lcs w.r.t.
telligence, IJCAI 2015. To Appear. general EL+ -tboxes. In Proceedings of the 26th Interna-
Fauconnier, G., and Turner, M. 2002. The Way We Think: tional Workshop on Description Logics, 477–488.
Conceptual Blending And The Mind’s Hidden Complexities. van der Laag, P. R., and Nienhuys-Cheng, S.-H. 1998. Com-
Basic Books. pleteness and properness of refinement operators in induc-
Gelfond, M., and Kahl, Y. 2014. Knowledge Representa- tive logic programming. The Journal of Logic Programming
tion, Reasoning, and the Design of Intelligent Agents: The 34(3):201 – 225.
Answer-Set Programming Approach. New York, NY, USA: Zarrieß, B., and Turhan, A.-Y. 2013. Most Specific Gen-
Cambridge University Press. eralizations w.r.t. General EL-TBoxes. In Proceedings of
the 23th International Joint Conference on Artificial Intelli-
Hois, J.; Kutz, O.; Mossakowski, T.; and Bateman, J. 2010.
gence, IJCAI ’13, 1191–1197. AAAI Press.
Towards ontological blending. In Dicheva, D., and Dochev,