=Paper=
{{Paper
|id=Vol-2123/paper22
|storemode=property
|title=The Distributive, Graded Lattice of EL Concept Descriptions and its Neighborhood Relation
|pdfUrl=https://ceur-ws.org/Vol-2123/paper22.pdf
|volume=Vol-2123
|authors=Francesco Kriegel
|dblpUrl=https://dblp.org/rec/conf/cla/Kriegel18
}}
==The Distributive, Graded Lattice of EL Concept Descriptions and its Neighborhood Relation ==
https://ceur-ws.org/Vol-2123/paper22.pdf
The Distributive, Graded Lattice of EL Concept
Descriptions and its Neighborhood Relation
Francesco Kriegel[0000−0003−0219−0330]
Institute of Theoretical Computer Science,
Technische Universität Dresden, Dresden, Germany
francesco.kriegel@tu-dresden.de
Abstract. For the description logic EL, we consider the neighborhood relation
which is induced by the subsumption order, and we show that the corresponding
lattice of EL concept descriptions is distributive, modular, graded, and metric.
In particular, this implies the existence of a rank function as well as the
existence of a distance function.
Keywords: Description logic · Distributive lattice · Modular lattice · Graded
lattice · Metric lattice · Rank function · Distance function · Neighborhood
relation · Upper neighbor · Lower neighbor
1 Introduction
Description Logics [3] are a family of well-founded languages for knowledge repre-
sentation with a strong logical foundation as well as a widely explored hierarchy of
decidability and complexity of common reasoning problems. The several reasoning tasks
allow for an automatic deduction of implicit knowledge from given explicitly represented
facts and axioms, and many reasoning algorithms have been developed. Description
Logics are utilized in many different application domains, and in particular provide
the logical underpinning of Web Ontology Language (OWL) [7] and its profiles.
EL is an example of a description logic with tractable reasoning problems, i.e., the usual
inference problems can be decided in polynomial time, cf. Baader, Brandt, and Lutz in [2].
From a perspective of lattice theory, EL has not been deeply explored yet. Of course, it is
apparent that the subsumption v with respect to some TBox T constitutes a quasi-order.
Furthermore, in description logics supremums in the corresponding ordered set are usually
called least common subsumers, and these exist in all cases if either no TBox is present, or
if greatest fixed-point semantics are applied. Apart from that not much is known about
the lattice of EL concept descriptions. In this document, we shall consider the neighbor-
hood relation which is induced by the subsumption order, and we shall show that the lat-
tice of EL concept descriptions is distributive, modular, graded, and metric. In particular,
this implies the existence of a rank function as well as the existence of a distance function.
2 The Description Logic EL
In this section we shall introduce the syntax and semantics of the light-weight description
logic EL [3,2]. Throughout the whole document assume that Σ is a signature, i.e.,
c paper author(s), 2018. Proceedings volume published and copyrighted by its editors.
Paper published in Dmitry I. Ignatov, Lhouari Nourine (Eds.): CLA 2018, pp.
267–278, Department of Computer Science, Palacký University Olomouc, 2018.
Copying permitted only for private and academic purposes.
268 Francesco Kriegel
Σ = ΣC ] ΣR is a disjoint union of a set ΣC of concept names and a set ΣR of role
names. An EL concept descriptionover Σ is a term that is constructed by means of
the following inductive rule where A ∈ ΣC and r ∈ ΣR.
E
C ::= > | A | C u C | r. C
The set of all EL concept descriptions over Σ is denoted by EL(Σ). The size ||C|| of
an EL concept description C is the number of nodes in its syntax tree, and we can
recursively define it as follows: ||>|| := 1, ||A|| := 1, ||C u D|| := ||C|| + 1 + ||D||, and
E
|| r. C|| := 1 + ||C||. A concept inclusion is an expression C v D where both the
premise C as well as the conclusion D are concept descriptions. A terminological box
(abbrv. TBox) is a finite set of concept inclusions.
An interpretation I := (∆I , ·I ) over Σ consists of a non-empty set ∆I , called the
domain, and an extension function ·I that maps concept names A ∈ ΣC to subsets
AI ⊆ ∆I and maps role names r ∈ ΣR to binary relations rI ⊆ ∆I × ∆I . Then,
the extension function is canonically extended to all EL concept descriptions by the
following definitions.
⊥I := ∅ >I := ∆I (C u D)I := C I ∩ DI
( r. C)I := { d ∈ ∆I | e ∈ ∆I : (d, e) ∈ rI and e ∈ C I }
E E
A concept inclusion C v D is valid in I if C I ⊆ DI . We then also refer to I as a
model of C v D, and denote this by I |= C v D. Furthermore, I is a model of a TBox
T , symbolized as I |= T , if each concept inclusion in T is valid in I. The relation |=
is lifted to TBoxes as follows. A concept inclusion C v D is entailed by a TBox T ,
denoted as T |= C v D, if each model of T is a model of C v D too. We then also say
that C is subsumed by D with respect to T . A TBox T entails a TBox U, symbolized
as T |= U, if T entails each concept inclusion in U, or equivalently if each model of
T is also a model of U. In case T = ∅ we may ommit the prefix ”∅ |=”. However, then
we have to carefully interpret an expression C v D—it either just denotes a concept
inclusion, i.e., an axiom, without stating where it is valid; or it expresses that C is
subsumed by D (w.r.t. ∅), i.e., C I ⊆ DI is satisfied in all interpretations I.
Two EL concept descriptions C and D are equivalent with respect to T , and we
shall write T |= C ≡ D, if T |= {C v D, D v C}. As a further abbreviation, let
T |= C v D if both T |= C v D and T |6 = C w D, and we then say that C is strictly
p
subsumed by D with respect to T . In the sequel of this document we may also write
C ≤T D instead of T |= C ≤ D where ≤ is some suitable relation symbol, e.g., v.
It is not hard to find EL concept descriptions that are equivalent, i.e., have the
same extension in all interpretations, but are not equal. It is therefore helpful for
technical details to have a unique normal form for EL concept descriptions. According
to [4,9] an EL concept description C can be transformed into a reduced form that is
equivalent to C by exhaustive application of the reduction rule D u E → 7 D whenever
∅ |= D v E to the subconcepts of C (modulo commutativity and associativity of u).
It is immediately clear that each EL concept description C is essentially a conjunction
of other EL concept descriptions that are no conjunctions. In particular, ifdwe define
Conj(C) as the set of all top-level conjuncts in C, then C has the form Conj(C)
(modulo commutativity and associativity of u).
It is readily verified that the subsumption v∅ constitutes a quasi-order on EL(Σ).
Hence, the quotient of EL(Σ) with respect to the induced equivalence ≡∅ is an ordered
The Distributive, Graded Lattice of EL Concept Descriptions 269
set. In what follows we will not distinguish between the equivalence classes and their
representatives. Furthermore, > is the greatest element, and the quotient set EL(Σ)/≡∅
is a lattice that we shall symbolize by EL(Σ). It is easy to verify that the conjunction
u corresponds to the finitary infimum operation. In a description logic allowing for
disjunctions t, it dually holds true that the disjunction t corresponds to the finitary
supremum operation. Unfortunately, this does not apply to our considered description
logic EL. As an obvious solution, we can simply define the notion of a supremum
specifically tailored to the case of EL concept descriptions as follows. The supremum
or least common subsumer (abbrv. LCS) of two EL concept descriptions C and D is
an EL concept description E with the following properties.
1. ∅ |= {C v E, D v E}
2. For each EL concept description F , if ∅ |= {C v F, D v F }, then ∅ |= E v F .
Since all least common subsumers of C and D are unique up to equivalence, we may
denote a representative of the corresponding equivalence class by C ∨ D. It is well
known that LCS-s always exist in EL; in particular, the least common subsumer C ∨ D
can be computed, modulo equivalence, by means of the following recursive formula.
l
C ∨D = (ΣC ∩ Conj(C) ∩ Conj(D))
l E E E
u { r. (E ∨ F ) | r ∈ ΣR, r. E ∈ Conj(C), and r. F ∈ Conj(D) }
It is easy to see that the equivalence ≡∅ is compatible with both u and ∨. Of course,
the definition of a LCS can be extended to an arbitrary number of arguments in the
W way, and we shall then denote the LCS of the concept descriptions Ct, t ∈ T ,
obvious
by { Ct | t ∈ T }.
3 The Neighborhood Problem
In this section we consider the neighborhood problem for EL. We have already seen that
the set of EL concept descriptions constitutes a lattice. It is only natural to consider
the question whether there exists a neighborhood relation which corresponds to the
subsumption order. Remark that for an order relation ≤ on some set P its neighborhood
relation or transitive reduction is defined as
≺ := \ ( ◦ ) = { (p, q) | p q and there exists no x such that p x q }.
Clearly, if P is finite, then the transitive closure ≺+ equals the irreflexive part .
However, there are infinite ordered sets where this does not hold true; even worse,
R
there are cases where ≺+ is empty. Consider, for instance, the set of real numbers
R
with their usual ordering ≤. It is well-known that is dense in itself, that is, for each
pair x y, there is another real number z such that x z y—thus, there are
no neighboring real numbers. In general, we say that ≤ is neighborhood generated if
≺+ = is satisfied. Clearly, ≤ is a neighborhood generated order relation if, and only
if, there is a finite path p = x0 ≺ x1 ≺ . . . ≺ xn = q for each pair p ≤ q. An alternative
formulation is the following. ≤ is not neighborhood generated if, and only if, there exists
some pair p q such that every finite path p = x0 x1 . . . xn = q can be refined,
that is, there is some index i and an element y such that xi y xi+1. Of course, if
270 Francesco Kriegel
the order relation ≤ is bounded, i.e., for each element p ∈ P , there exists a finite upper
bound on the lengths of -paths issuing from p, then ≤ is neighborhood generated.
In the sequel of this section, we shall address the neighborhood problem from different
perspectives. We first consider the general problem of existence of neighbors, and then
provide means for the computation of all upper neighbors and of all lower neighbors,
respectively, in the cases where these exist. As it will turn out, neighbors only exist
for all concept descriptions in the description logic EL without any TBox. The presence
of either a TBox or of the bottom concept description ⊥ prevents the existence of
neighbors for some concept descriptions. Furthermore, the extensions of EL with greatest
fixed-point semantics also allow for the construction of concept descriptions that do not
possess neighbors. Eventually, a complexity analysis shows that deciding neighborhood
in EL is in P, and that all upper neighbors of an EL concept description can be
computed in deterministic polynomial time.
Definition 1. Consider a signature Σ, let T be a TBox over Σ, and further assume
that C and D are concept descriptions over Σ. Then, C is a lower neighbor or a most
general strict subsumee of D with respect to T , denoted as T |= C ≺ D, if the following
statements hold true.
1. T |= C v D
p
2. For each concept description E over Σ, it holds true that T |= C v E v D implies
T |= E ≡ C or T |= E ≡ D.
Additionally, we then also say that D is an upper neighbor or a most specific strict
subsumer of C with respect to T , and we may also write T |= D C.
We first observe that neighborhood of concept descriptions is not preserved by the
concept constructors. It is easy to see that ∅ |= A u B ≺ A. However, it holds true that
E E E E E E
∅ |= r. (A u B) v r. A u r. B v r. A, which shows ∅ |6 = r. (A u B) ≺ r. A.
p
p
Furthermore, we have that ∅ |= A u B u (A u B) ≡ A u (A u B), and consequently
∅ |6 = A u B u (A u B) ≺ A u (A u B). There are according counterexamples when
neighborhood with respect to a non-empty TBox is considered.
It is easily verified that neighborhood with respect to the empty TBox ∅ does not
coincide with neighborhood w.r.t. a non-empty TBox T . For instance, ∅ |= A ≺ > holds
true, but {> v A} |= A ≡ >. For the converse direction, consider the counterexample
where {A v B, B v A} |= A u B ≺ > and ∅ |= A u B v A v >.
p
p
3.1 The Empty TBox
Since Baader and Morawska showed in [4, Proof of Proposition 3.5] that v∅ is bounded,
we can immediately draw the following conclusion.
Proposition 2. The subsumption relation v∅ is neighborhood generated.
After this first promising result, we continue with describing the neighborhood
relation ≺∅. For this purpose, we define Upper(C) := { D | C ≺∅ D } as the set of all
upper neighbors of a concept description C, and accordingly Lower(C) contains exactly
all lower neighbors of C.
There is a well-known recursive characterization of v∅ as follows: C v∅ D if, and only
E
if, A ∈ Conj(D) implies A ∈ Conj(C) for each concept name A, and for each r. F ∈
E
Conj(D), there is some r. E ∈ Conj(C) such that E v∅ F . With the help of that we can
prove that there is the following necessary condition for neighboring concept descriptions.
The Distributive, Graded Lattice of EL Concept Descriptions 271
Lemma 3. Let C and D be some reduced EL concept descriptions over a signature
Σ. If ∅ |= C ≺ D, then exactly one of the following statements holds true.
1. There is a concept name A ∈ ΣC such that ∅ |= C ≡ D u A.
2. It holds true that Conj(C) ∩ ΣC = Conj(D) ∩ ΣC, and there is exactly one ex-
E
istential restriction r. E ∈ Conj(C) such that for all existential restrictions
E
s. F ∈ Conj(D), it holds true that r = s and ∅ |= E v F imply ∅ |6 = E ≡ F .
By means of the previous lemma we can deduce the following two propositions that
describe the sets Upper(C) and Lower(C).
Proposition 4. For each reduced EL concept description C over some signature Σ,
the following recursive equation is satisfied (modulo equivalence).
l
Upper(C) = { Conj(C) \ {A} | A ∈ Conj(C) }
l E E E
∪{ Conj(C) \ { r. E} ∪ { r. F | F ∈ Upper(E) } | r. E ∈ Conj(C) }
E E
For instance, consider the concept description A u r. B u s. (A u B). It is in
E E E
reduced form and has three upper neighbors, namely r. B u s. (A u B), A u r. > u
E E E E
s. (A u B), and A u r. B u s. A u s. B.
Proposition 5. For every EL concept description C over some signature Σ, the
following equation is satisfied (modulo equivalence).
Lower(C) = { C u A | A ∈ ΣC and ∅ |6 = C v A }
( E)
E r ∈ ΣR, D is most general such that ∅ |6 = C v r. D,
∪ C u r. D E
and ∅ |= C v r. E for all E with ∅ |= D ≺ E
While the recursive characterization of Upper in Proposition 4 immediately yields
a procedure for enumerating all upper neighbors of a given concept description, the
situation is not that apparent for lower neighbors. We can, however, constitute a
procedure for computing lower neighbors by means of Proposition 5. Let C be an EL
concept description over some signature Σ. Proceed as follows.
1. For each concept name A ∈ ΣC with ∅ |6 = C v A, output C u A as a lower neighbor
of C.
2. For each role name r ∈ ΣR, recursively proceed as follows.
(a) Let D := >. E
(b) While ∅ |= C v r. D, replace D with a lower neighbor of D.
E E
(c) If ∅ |= C v r. E for all E with ∅ |= D ≺ E, then output C u r. D as a
lower neighbor of C.
Eventually, we finish our investigations of ≺∅ with a complexity analysis. Using
induction on the role depth of C, we can prove that, for each reduced EL concept
description C, the set Upper(C) can be computed in deterministic time O(||C||2). It
is then apparent that the following proposition holds true.
Proposition 6. The neighborhood relation ≺∅ can be decided in polynomial time, that
is, ≺∅ ∈ P, and the mapping Upper is computable in deterministic polynomial time.
272 Francesco Kriegel
3.2 The Bottom Concept Description
Now consider the extension of EL with the bottom concept description ⊥ the semantics
of which is defined as ⊥I := ∅ for any interpretation I. Then v∅ is not bounded, since
the following infinite chain exists.
E E E E E
∅ |= ⊥ v . . . v ( r.)n+1 > v ( r.)n > v . . . v r. r. > v r. > v >
p
p
p
p
p
p
p
However, w∅ is still well-founded, since whenever a chain starts with ⊥, then the second
element must be a satisfiable concept description, that is, some C with C ≡ 6 ∅ ⊥, after
which the chain can only have a bounded number of elements. Furthermore, v∅ is not
neighborhood generated, as ⊥ does not have any upper neighbors. To see this, consider
E
a concept description C such that ⊥ v∅ C; it then follows that ⊥ v∅ C u r. C v∅ C.
p
p
p
3.3 A Non-Empty TBox
A similar situation arises when considering subsumption with respect to a non-empty
TBox T . Firstly, consider the simple signature Σ where ΣC := {A} and ΣR := {r}
E E
and define the TBox T := {> v r. >, A v r. A}. We obtain that the quotient
E
N
EL(Σ)/≡T consists of the classes [( r.)n A] for n ∈ , and of the class [>]. Furthermore,
these concept descriptions are linearily ordered as follows.
E E E E E E
T |= A v r. A v r. r. A v r. r. r. A v . . . v >
p
p
p
p
p
Consequently, > does not have lower neighbors, and we also conclude that vT is not
bounded and wT is not well-founded.
Secondly, we show that there is a TBox T and a concept description without any
upper neighbors with respect to vT . We try to keep things simple, and consider a rather
small signature, namely Σ defined by ΣC := {A, B} and ΣR := {r}, and we define a
E E
TBox by T := { r. A v A, B v A, B ≡ r. B}. It can be shown that, for each EL(Σ)
N
concept description C, either C is equivalent to B w.r.t. T or there exists an n ∈ such
E
that T |= B v ( r.)n A v C, i.e., B does not have upper neighbors with respect to T .
p
p
Proposition 7. There is some TBox T for which the subsumption relation vT is not
neighborhood generated.
3.4 Greatest Fixed-Point Semantics
Unfortunately, the situation is also not rosy for extensions of EL with greatest fixed-point
semantics [1,11]. It then also holds true that v∅ is neither bounded nor neighborhood gen-
erated, and w∅ is not well-founded. One culprit is a concept description which represents
E
a cycle, for instance ν X. r. X, the extension of which is maximal w.r.t. the property
of containing elements that have some other element in that extension as an r-successor.
4 The Distributive, Graded Lattice of EL Concept
Descriptions
The goal of this section is to explore the properties of the lattice of EL concept descrip-
tions ordered by subsumption with respect to the empty TBox. In particular, Blyth [5,
The Distributive, Graded Lattice of EL Concept Descriptions 273
Chapters 4 and 5] shows that it suffices to investigate whether this lattice is distributive
and of locally finite length, such that as an immediate corollary we then obtain that
also the Jordan-Dedekind chain condition is satisfied, which states that for each pair
C v∅ D, all maximal chains in the intervall [C, D] have the same length. Furthermore,
this length can then be utilized to define a distance between C and D, and in particular
to measure a distance from each concept description C to the top concept description
>, which we call the rank of C.
Lemma 8. For each signature Σ, the lattice EL(Σ) is distributive, i.e., for all concept
descriptions C, D, E ∈ EL(Σ), it holds true that
∅ |= C u (D ∨ E) ≡ (C u D) ∨ (C u E),
and ∅ |= C ∨ (D u E) ≡ (C ∨ D) u (C ∨ E).
Lemma 9. For each signature Σ, the lattice EL(Σ) is of locally finite length, that is,
for all concept descriptions C, D ∈ EL(Σ) with ∅ |= C v D, every chain in the interval
[C, D] has a finite length.
According to Blyth [5, Chapters 4 and 5], the following statements are obtained as
immediate consequences of Lemmas 8 and 9.
Corollary 10. 1. For each signature Σ, the lattice EL(Σ) is modular, i.e., for all
concept descriptions C, D, E ∈ EL(Σ), it holds true that
∅ |= (C u D) ∨ (C u E) ≡ C u (D ∨ (C u E)),
∅ |= (C ∨ D) u (C ∨ E) ≡ C ∨ (D u (C ∨ E)),
∅ |= C v D implies ∅ |= C ∨ (E u D) ≡ (C ∨ E) u D,
and ∅ |= C w D implies ∅ |= C u (E ∨ D) ≡ (C u E) ∨ D.
2. For each signature Σ, the lattice EL(Σ) is both upper and lower semi-modular,
i.e., for all concept descriptions C, D ∈ EL(Σ), it holds true that
∅ |= C u D ≺ C if, and only if, ∅ |= D ≺ C ∨ D.
3. For each signature Σ, the lattice EL(Σ) satisfies the Jordan-Dedekind chain con-
dition, i.e., for all concept descriptions C, D ∈ EL(Σ) with ∅ |= C v D, it holds
p
true that all maximal chains in the interval [C, D] have the same length.
The notion of a rank function can be defined for ordered sets. The following definition
specifically tailors this notion for the lattice EL(Σ).
Definition 11. An EL rank function is a mapping |·|: EL(Σ) → N with the following
properties.
1. |>| = 0
2. ∅ |= C ≡ D implies |C| = |D| (equivalence closed)
3. ∅ |= C v D implies |C| |D| (strictly order preserving)
p
4. ∅ |= C ≺ D implies |C| + 1 = |D| (neighborhood preserving)
For an EL concept description C, we say that |C| is the rank of C.
274 Francesco Kriegel
Proposition 12. For each C ∈ EL(Σ), let |C| := 0 if ∅ |= C ≡ >, and otherwise set
E
|C| := max{ n + 1 | D1, . . . , Dn ∈ EL(Σ): ∅ |= C ≺ D1 ≺ . . . ≺ Dn ≺ > }.
Then, | · | is an EL rank function.
Since EL(Σ) satisfies the Jordan-Dedekind chain condition, we infer that in order
to compute the rank |C| of an EL concept description C over Σ with ∅ |6 = C ≡ >,
we simply need to find one chain ∅ |= C ≺ D1 ≺ D2 ≺ . . . ≺ Dn ≺ >, and then it
follows that |C| = n + 1. Furthermore, |C| = 0 if ∅ |= C ≡ >.
Corollary 13. For each signature Σ, the lattice EL(Σ) is graded.
The next lemma provides an equation for the rank of a conjunction of n concept descrip-
tions. By induction over n, it follows from Lemma 9, Corollary 10, and [5, Theorem 4.6].
Lemma 14. Let C be a set of n EL concept descriptions over Σ. Then, the following
equation holds true.
l Xn X_
| C| = (−1)i+1 · | D|
i=1 D∈(Ci )
E E
Let C = A1 u. . .uAm u r1. C1 u. . .u rn. Cn be a reduced EL concept description.
Then its rank can be computed as follows, cf. Lemma 14.
E E
|C| = |A1 u . . . u Am u r1. C1 u . . . u rn. Cn|
E E
= |A1 u . . . u Am| + | r1. C1 u . . . u rn. Cn| − |>|
E E
= m + | r1. C1 u . . . u rn. Cn|
E E
Furthermore, it holds true that ∅ |= r. C ∨ s. D ≡ > if r = 6 s. It follows that we
can further simplify the rank computation as follows.
E E l l E
| r1. C1 u . . . u rn. Cn| = | { { ri. Ci | i ∈ {1, . . . , n} and ri = r } | r ∈ ΣR }|
X l E
= | { ri. Ci | i ∈ {1, . . . , n} and ri = r }|
r∈ΣR
The rank of the conjunction of existential restrictions can be computed by means of
Lemma 14, and finally it is readily verified that the rank of one existential restriction
E
r. C satisfies the following equation.
E l E
| r. C| = 1 + | { r. D | ∅ |= C ≺ D }|
Definition 15. An EL metric or EL distance function is a mapping d: EL(Σ) ×
N
EL(Σ) → with the following properties.
1. d(C, D) ≥ 0 (non-negative)
2. d(C, D) = 0 if, and only if, ∅ |= C ≡ D (equivalence closed)
The Distributive, Graded Lattice of EL Concept Descriptions 275
>
|C ∨ D|
|C| |D|
C ∨D
|C u D|
nC nD
C D
mC mD
C uD
Fig. 1. Obtaining a distance function from the rank function
3. d(C, D) = d(D, C) (symmetric)
4. d(C, E) ≤ d(C, D) + d(D, E) (triangle inequality)
We then also say that d(C, D) is the distance between C and D.
Lemma 14 for the case n = 2 yields that in the rectangle shown in Figure 1 opposite
edges have the same length, where length means length of a maximal chain between the
endpoints. It is easy to see that |CuD| = |C|+mC = |D|+mD and |C∨D| = |C|−nC =
|D|−nD . Thus, we infer that mC = |C uD|−|C| = |D|−|C ∨D| = nD , and similarily
that mD = nC . Consequently, we can define an EL distance function in the following way.
Proposition 16. For all C, D ∈ EL(Σ), define
d(C, D) := |C u D| − |C ∨ D|.
Then, d is an EL metric.
We can justify the name of a distance function as follows. If we consider the graph
of EL concept descriptions such that edges exist exactly between neighboring concept
descriptions, that is, if we consider the graph (EL(Σ), ≺∅ ∪ ∅), then the distance
d(C, D) is the length of a shortest path between C and D.
Corollary 17. EL(Σ) is a metric lattice, i.e., a lattice which is also a metric space.
It is easy to verify that EL(Σ) is complete, not bounded, not precompact, not com-
pact, locally compact, proper if Σ is finite, neither connected nor path connected, and
separable. The induced topology τd is perfectly normal Hausdorff or T6. Furthermore, all
subsets are both open and closed, and all mappings f : EL(Σ) → (X, d0) are continuous.
W
Lemma 18. Let C ∈ EL(Σ), then d(C, Upper(C)) = |Upper(C)|.
According the the previous lemma, we can compute ranks as follows.
1. Let D := C and r := 0.
276 Francesco Kriegel
2. While ∅ |6 = D ≡ >, computeWthe set Upper(D) of upper neighbors of D, set
r := r + |Upper(D)| and D := Upper(D).
3. Return r.
In [6] Ecke, Peñaloza, and Turhan defined the notion of a concept similarity measure
as a function of type EL(Σ) × EL(Σ) → [0, 1], and then considered so-called relaxed
instances of concept descriptions with respect to ontologies. Simply speaking, a is a
relaxed instance of C if there is a concept that is similar enough to C and has a as an
instance. It is straight-forward to consider these relaxed instances also with respect to
the distance function we have just introduced. More formally, we define them as follows.
Definition 19. Consider an interpretation I over some signature Σ and a concept
N D
description C ∈ EL(Σ), and let n ∈ . Then, the expression ≤ n. C is called a
relaxed concept description, and its extension is defined by
[
( ≤ n. C)I := { DI | D ∈ EL(Σ) and d(C, D) ≤ n }.
D
Suppose that O is an ontology over some signature Σ, and further let a ∈ ΣI be
N
an individual name, C ∈ EL(Σ) a concept description, and n ∈ . We then say that
a is a relaxed instance of C with respect to O and distance threshold n, denoted as
O |= a @
D D
− ≤ n. C, if it holds true that aI ∈ ( ≤ n. C)I for each model I of O.
For transforming our distance function d into a similarity function s: EL(Σ) ×
EL(Σ) → [0, 1] we can proceed as follows. We begin with transforming d into a
metric with range [0, 1). For that purpose, we choose an order-preserving, sub-additive
function f : [0, ∞) → [0, 1) with ker(f) = {0}. Note that a function f : [0, ∞) → R
is sub-additive if f 00 < 0 and f(0) = 0. Then f ◦ d is such a metric with range [0, 1).
Suitable functions are the following.
x x y
– f: x→
7 1+x or more generally f : x →
7 ( 1+x ) for y > 0
1
– f: x→ 7 1 − yx for y ∈ (0, 1)
7 1 − 2x or more generally f : x →
Then, s := 1 − f ◦ d is a similarity function on EL(Σ). It is easy to verify that then
s satifies the following properties which have been defined by Lehmann and Turhan
in [10], for all EL concept descriptions C, D, E over Σ.
1. s(C, D) = s(D, C) (symmetric)
2. 1 + s(C, D) ≥ s(C, E) + s(E, D) (triangle inequality)
3. ∅ |= C ≡ D implies s(C, E) = s(D, E) (equivalence invariant)
4. ∅ |= C ≡ D if, and only if, s(C, D) = 1 (equivalence closed)
5. ∅ |= C v D v E implies s(C, D) ≥ s(C, E) (subsumption preserving)
6. ∅ |= C v D v E implies s(C, E) ≤ s(D, E) (reverse subsumption preserving)
However, as it turns out such a similarity measure 1 − f ◦ d does not satisfy the property
of structural dependance. For instance, consider a signature Σ without role names and
N
such that ΣC := {A} ∪ { Bn | n ∈ }. It is now readily verified that
l l
(1 − f ◦ d)(A u { B` | ` ≤ n }, { B` | ` ≤ n }) = 1 − f(1)
N
for all n ∈ , and since f(1) > 0 we conclude that the sequence does not converge
to 1 for n → ∞.
The Distributive, Graded Lattice of EL Concept Descriptions 277
For extending our rank function | · | and our distance function d to EL⊥, we can
simply define |⊥| := ∞, d(⊥, ⊥) := 0, and d(⊥, C) := d(C, ⊥) := ∞ for ∅ |= C ≡ 6 ⊥.
When transforming the extended metric into a similarity measure then two concept
descriptions have a similarity of 0 if, and only if, exactly one of them is unsatisfiable. In
EL without the bottom concept description ⊥, a similarity of 0 can never occur when
utilizing the above construction.
We close this section with some first investigations on the complexities of decision
problems and computation problems related to the introduced rank function. So far, it
is unknown whether the rank function can be tractably computed, i.e., in deterministic
polynomial time. However, if |C| is computed in the naı̈ve way by constructing an
arbitrary chain of neighbors from C to > and then determinining its length, at least deter-
ministic exponential time with respect
d to the size of C is necessary. To see this, consider
E
N
the concept description Cn := r. {A1, . . . , An} for each n ∈ . It is well-known that
there are exponentially many subsets of {A1, . . . , An} with b n2 c elements; let X1, . . . , X`
d E d
be an enumeration of these, and define Dm := { r. Xi | i ∈ {m, . . . , `} }. Clearly,
then Cn v∅ D1 v∅ D2 v∅ . . . v∅ D` v∅ > is an exponentially long chain of strict
p
p
p
p
p
subsumptions. We conclude that |Cn| is at least exponential in n.
Given a concept description C and a natural number n (in binary encoding), then
we can decide in triple exponential time whether the rank of C is equal to n, at most n,
or at least n. A procedure can construct a chain of n neighbors and then check whether
> is reached. If n is fixed, then this requires only deterministic polynomial time.
5 Conclusion
We have investigated the neighborhood problem for the description logic EL and some of
its variants. We found that existence of neighbors can in general only be guaranteed for
the case of EL without a TBox, without the bottom concept description, and without
greatest fixed-point semantics. The presence of a TBox, the bottom concept description,
or greatest fixpoint semantics allow for the construction of concept descriptions that
do not have neighbors in certain directions. For the case of EL we proposed sound
and complete procedures for deciding neighborhood as well as for computing all upper
neighbors and all lower neighbors, respectively. Furthermore, we have shown that
deciding neighborhood and computing all upper neighbors requires only deterministic
polynomial time. The complexity of computing all lower neighbors is currently an open
question; possibly there exists a less expensive procedure than the one presented here.
As further results, we have proven that the lattice of EL concept descriptions is
distributive, modular, graded, and metric. In particular, this means that there exists a
rank function as well as a distance function on this lattice. Some first complexity results
on problems related to these rank and distance functions were found. However, the
exact complexities are currently unknown; we do not know whether the presented upper
bounds are sharp, and lower bounds are also not available. This implies that there could
possibly exist faster procedures for computing ranks and distances than those introduced
in this document. In particular, better formulas for computing or approximating ranks
of EL concept description should be sought. Some initial experiments could lead to the
claim that the rank of an EL concept description with role depth n, that is, for which
the nesting depth of existential quantifiers is n, could be n-exponential in the size of C.
278 Francesco Kriegel
As an important consequence we infer that the algorithm NextClosures [8] can be
utilized for enumerating canonical bases of closure operators in EL.
Other possible future research could consider extensions to more expressive descrip-
tion logics. Of course, these logics should be considered without TBoxes for deciding
existence of neighbors in general. Eventually, a further direction for future research is a
more fine-grained characterization of existence of neighbors. That is, given a description
logic where neighbors need not exist in general, how can we decide whether a concept
description has neighbors and how can we enumerate these?
Acknowledgements The author gratefully thanks both Franz Baader and Bernhard
Ganter for fruitful discussions on neighborhood generated orders, and furthermore
thanks the anonymous reviewers for their constructive hints and helpful remarks.
References
1. Baader, F.: Terminological Cycles in a Description Logic with Existential Restrictions.
In: Gottlob, G., Walsh, T. (eds.) IJCAI-03, Proceedings of the Eighteenth International
Joint Conference on Artificial Intelligence, Acapulco, Mexico, August 9-15, 2003. pp.
325–330. Morgan Kaufmann (2003)
2. Baader, F., Brandt, S., Lutz, C.: Pushing the EL Envelope. In: Kaelbling, L.P., Saffiotti,
A. (eds.) IJCAI-05, Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, Edinburgh, Scotland, UK, July 30 - August 5, 2005. pp. 364–369.
Professional Book Center (2005)
3. Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic.
Cambridge University Press (2017)
4. Baader, F., Morawska, B.: Unification in the Description Logic EL. Logical Methods
in Computer Science 6(3) (2010)
5. Blyth, T.S.: Lattices and Ordered Algebraic Structures. Universitext, Springer London,
1st edn. (2005)
6. Ecke, A., Peñaloza, R., Turhan, A.: Similarity-based Relaxed Instance Queries. Journal
of Applied Logic 13(4), 480–508 (2015)
7. Hitzler, P., Krötzsch, M., Rudolph, S.: Foundations of Semantic Web Technologies.
Chapman and Hall/CRC Press (2010)
8. Kriegel, F.: NextClosures with Constraints. In: Huchard, M., Kuznetsov, S. (eds.)
Proceedings of the Thirteenth International Conference on Concept Lattices and Their
Applications, Moscow, Russia, July 18-22, 2016. CEUR Workshop Proceedings, vol. 1624,
pp. 231–243. CEUR-WS.org (2016)
9. Küsters, R.: Non-Standard Inferences in Description Logics, Lecture Notes in Computer
Science, vol. 2100. Springer (2001)
10. Lehmann, K., Turhan, A.: A Framework for Semantic-Based Similarity Measures for ELH-
Concepts. In: del Cerro, L.F., Herzig, A., Mengin, J. (eds.) Logics in Artificial Intelligence
- 13th European Conference, JELIA 2012, Toulouse, France, September 26-28, 2012.
Proceedings. Lecture Notes in Computer Science, vol. 7519, pp. 307–319. Springer (2012)
11. Lutz, C., Piro, R., Wolter, F.: Enriching EL-Concepts with Greatest Fixpoints. In: Coelho,
H., Studer, R., Wooldridge, M. (eds.) ECAI 2010 - 19th European Conference on Artificial
Intelligence, Lisbon, Portugal, August 16-20, 2010, Proceedings. Frontiers in Artificial
Intelligence and Applications, vol. 215, pp. 41–46. IOS Press (2010)