=Paper=
{{Paper
|id=Vol-2954/paper-21
|storemode=property
|title=Navigating the EL Subsumption Hierarchy
|pdfUrl=https://ceur-ws.org/Vol-2954/paper-21.pdf
|volume=Vol-2954
|authors=Francesco Kriegel
|dblpUrl=https://dblp.org/rec/conf/dlog/Kriegel21
}}
==Navigating the EL Subsumption Hierarchy==
https://ceur-ws.org/Vol-2954/paper-21.pdf
Navigating the EL Subsumption Hierarchy ⋆
Francesco Kriegel
Theoretical Computer Science, Technische Universität Dresden, Dresden, Germany
francesco.kriegel@tu-dresden.de
Abstract. The EL subsumption hierarchy consists of all EL concept
descriptions and is partially ordered by subsumption. In order to nav-
igate within this hierarchy, one can go up to subsumers and down to
subsumees. We analyze how smallest steps can be made. Specifically, we
show how all upper neighbors as well as all lower neighbors of a given
EL concept description can be efficiently computed, where two concepts
are neighbors if one subsumes the other and there is no third concept in
between. We further show that the hierarchy contains very long chains:
there is a sequence of concepts Cn with size linear in n such that each
chain of neighbors from ⊤ to Cn has at least n-fold exponential length.
As applications, we provide a template for determining upper complex-
ity bounds for deciding whether a concept is maximally general or maxi-
mally specific w.r.t. a property, we construct a metric on the set of all EL
concept descriptions, we introduce a similarity measure that fulfills the
triangle inequality, and we conclude that an uninformed search for a tar-
get concept by subsequently computing neighbors or, equivalently, along
an ideal refinement operator is not feasible in practical applications.
Keywords: Description logic · Subsumption · Upper neighbor · Lower
neighbor · Distance measure · Metric · Refinement operator
1 Introduction
The EL subsumption hierarchy consists of all EL concept descriptions and is
partially ordered by subsumption. In order to navigate within this hierarchy,
one can go up to subsumers and down to subsumees. We analyze how smallest
steps can be made. Specifically, we show how all upper neighbors as well as all
lower neighbors of a given EL concept description can be efficiently computed,
where two concepts are neighbors if one subsumes the other and there is no third
concept in between. The complexity for both computation tasks is determined:
while all upper neighbors can be computed in polynomial time, computation of
all lower neighbors needs exponential time.
Secondly, we employ a standard construction from Lattice Theory [6] for
constructing a distance measure (metric) on the set of all EL concept descrip-
tions. Specifically, the distance between two concepts C and D coincides with the
⋆
Francesco Kriegel is funded by DFG in project number 430150274.
Copyright © 2021 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
2 Francesco Kriegel
length of a shortest path in the undirected graph the vertex set of which consists
of all EL concept descriptions and in which neighboring concept descriptions are
connected by an edge. An asymptotic analysis reveals that the distance between
⊤ and ∃ r1 . · · · ∃ rn . (A1 ⊓ · · · ⊓ Ak ) where k ≥ 3 is asymptotically bounded from
below by the n-fold iterated exponential
k
.2 2
..
2
2| {z } .
n times
It follows that the subsumption hierarchy contains very long chains: each chain
of neighbors from ⊤ to ∃ r1 . · · · ∃ rn . (A1 ⊓· · ·⊓Ak ) has n-fold exponential length.
Thirdly, we devise some consequences and applications. We provide a tem-
plate for determining upper complexity bounds for deciding whether a concept
description is maximally specific or maximally general w.r.t. a given property.
We construct a similarity measure on EL concept descriptions that fulfills the
triangle inequality. We conclude that an uninformed search for a target concept
by subsequently computing neighbors or, equivalently, along an ideal refinement
operator is not feasible in practical applications. The latter applies, in particular,
to an approach that tries to learn a target concept [20] as well as to the prob-
lem of computing a maximally strong weakening w.r.t. ≻sub (but only for this
particular weakening relation!) in the context of computing a gentle repair [3].
In addition to citing and rephrasing existing results on the enumeration of
upper neighbors as well as a construction of the distance measure, this article
provides as new contributions an efficient approach to computing lower neighbors
and an asymptotic analysis of the distance measure. Specifically, a contained
result is a previously unpublished, new contribution if and only it is followed
only by a reference to [16]. Proofs can be found in the mentioned references.
2 Preliminaries
The EL Subsumption Hierarchy. We assume basic knowledge of the descrip-
tion logic EL. For a signature Σ := ΣC ∪ ΣR consisting of concept names and role
names, EL concept descriptions are built from Σ by means of the constructors
⊤, ⊓, and ∃, and the set of all concept descriptions is denoted as EL(Σ). We
treat (nested) conjunctions like sets, i.e., nestings, order, and repetitions are not
relevant. Concept names and existential restrictions are also called atoms. Each
concept C is a conjunction of atoms, the top-level conjuncts of C, and we denote
the set of all these atoms as Conj(C). ⊤ is the empty conjunction. The role depth
of a concept is the maximal number of nestings of existential restrictions.
Given two concept descriptions C and D, we say that C is subsumed by D,
written C ⊑∅ D, if C I ⊆ DI for each interpretation I. We use the subscript ∅ to
indicate that we consider subsumption w.r.t. the empty TBox. It is well-known
that the subsumption relation ⊑∅ is a partial order — a reflexive, transitive binary
relation — on the set EL(Σ). Consequently, the quotient of EL(Σ) w.r.t. the
induced equivalence relation ≡∅ is a partially ordered set. In what follows, we
will not distinguish between the equivalence classes and their representatives,
Navigating the EL Subsumption Hierarchy 3
with the consequence that ⊑∅ becomes a partial order — a reflexive, transitive,
antisymmetric binary relation. As representatives we usually take the reduced
concepts, where a concept is reduced if none of its conjunctions contains atoms
that are comparable w.r.t. ⊑∅ . According to [17], each concept has a unique
reduced form to which it is equivalent. The EL subsumption hierarchy is the
partially ordered set (poset) (EL(Σ), ⊑∅ ).
Upper and Lower Neighbors. For a partially ordered set (P, ≤), its neighbor-
hood relation 1 consists of all pairs (p, q) where p < q and there exists no x such
that p < x < q. Usually, if p ≺ q, then one calls p a lower neighbor of q and, vice
versa, q is called an upper neighbor of p.2 We say that ≤ is neighborhood gener-
ated if the transitive closure ≺+ equals the irreflexive part <. Obviously, this is
the case if and only if, for each pair p ≤ q, there is a finite chain of neighbors from
p to q, i.e., there are elements x0 , . . . , xn such that p = x0 ≺ x1 ≺ · · · ≺ xn = q.
Clearly, if the underlying set P is finite, then each partial order on P is
neighborhood generated. However, there are infinite posets where this does not
hold true; even worse, there are cases where ≺ and thus also ≺+ are both empty.
For instance, consider the set R of real numbers with their usual ordering ≤.
It is well known that R is dense in itself, i.e., for each pair x < y, there is
another real number z in between, i.e., such that x < z < y — thus, there are
no neighboring real numbers. Another example of a partially ordered set that is
not neighborhood generated is the set N of all natural numbers augmented with
a greatest element ∞, which then does not have any neighbors.
As an alternative formulation, a partial order ≤ is not neighborhood gen-
erated if and only if there exists a pair p < q such that every finite chain3
p = x0 < x1 < · · · < xn = q can be refined, i.e., there is some index i and an
element y such that xi < y < xi+1 . It follows that ≤ is neighborhood generated if
≤ is bounded, i.e., for each element p, there is a finite upper bound on the lengths
of chains starting with p. Although boundedness is sufficient for neighborhood-
generatedness, it is not necessary: the following result immediately implies that
each unbounded poset can be order-embedded4 into a neighborhood generated
poset, which must be unbounded as well.
Proposition 1. [12], [16, Page 114]. Each poset can be order-embedded into
some neighborhood generated poset.
Proof sketch. Let (P, ≤) be a poset. Firstly, we define the poset (Q, ⊑) by adding
a fresh element between each two ≤-comparable elements of P . It is easy to see
that (Q, ⊑) must be neighborhood generated. Secondly, we can map each element
of P to itself in Q in order to obtain an order-embedding. ⊔
⊓
1
While in [13] the name “neighborhood relation” is used, it is called “covers relation” in
[6] and “one-step relation” in [3]. A further alternative name is “transitive reduction.”
2
Alternative denotations are “lower cover” and “upper cover.”
3
Formally, a chain in a poset (P, ≤) is a subset C ⊆ P such that p ≤ q or q ≤ p for
each two elements p, q ∈ C. It starts with p if p ≤ q for each q ∈ C.
4
An order-embedding h from (P, ≤) into (Q, ⊑) is an injective mapping h : P → Q
such that p ≤ q if and only if h(p) ⊑ h(q) for all p, q ∈ P .
4 Francesco Kriegel
3 Neighbors of EL Concept Descriptions
This section is concerned with the questions whether the subsumption relation is
neighborhood generated and how upper and lower neighbors can be enumerated.
Definition 2. Let C and D be concept descriptions. We call C a lower neighbor
of D and D an upper neighbor5 of C, written C ≺∅ D and D ≻∅ C, respectively,
if6 C ⊏∅ D and there does not exist a concept E such that C ⊏∅ E ⊏∅ D.
Here, we only consider the empty TBox — other types of TBoxes (cycle-
restricted, acyclic, general) as well as two extensions of EL (with ⊥, with greatest
fixed-points) are considered in [16] but left out here due to a lack of space. As
short summary, the subsumption relation is neighborhood generated if the TBox
is cycle-restricted or acylic, but not neighborhood generated for general TBoxes
or if ⊥ or greatest fixed-points are added.
In the proof of Proposition 3.5 in [5] it was shown that the subsumption
relation ⊑∅ is bounded and so we can immediately draw the following conclusion.
Proposition 3. [15, Proposition 2], [16, Proposition 5.1.2]. The subsumption
relation ⊑∅ on EL(Σ) is neighborhood generated.
Next, we show how all upper and all lower neighbors of a given EL concept
description C can be computed. Recall that there is the following recursive char-
acterization of the subsumption relation [5]: C ⊑∅ D if and only if A ∈ Conj(D)
implies A ∈ Conj(C) for each concept name A, and for each existential restriction
∃ r. F ∈ Conj(D), there is ∃ r. E ∈ Conj(C) such that E ⊑∅ F . It follows that,
given a concept description C, we obtain an upper neighbor of C by removing
one concept name from Conj(C) and, vice versa, we get a lower neighbor of C
by adding a concept name to Conj(C) that is not already there.
Dealing with the existential restrictions is more involved. To construct an
upper neighbor, we cannot simply remove an existential restriction ∃ r. D from
Conj(C), since the resulting concept might be too general d— according to the
above characterization of ⊑∅ it holds true that d ∃ r. D ⊏∅ { ∃ r. E | D ≺∅ E }
and so we infer that7 the concept (C \ ∃ r. D) ⊓ { ∃ r. E | D ≺∅ E } is between
C and C \ ∃ r. D. In fact, we can prove that the concept in the middle is always
an upper neighbor of C and further that each upper neighbor is either of this
form or of the form C \ A for some concept name A ∈ Conj(C).
Definition 4. For each reduced EL concept description C, we recursively define
↑G ↑A ↑∃r.D :=
d := { C | G ∈ Conj(C) } where C := C \ A and C
the set Upper(C)
(C \ ∃ r. D) ⊓ { ∃ r. E | E ∈ Upper(D) }.
Proposition 5. [15, Proposition 4], [3, Lemma 22], [16, Proposition 5.1.5]. For
each reduced EL concept description C, the set Upper(C) consists of all upper
neighbors of C (modulo equivalence), i.e., a concept description D is an upper
neighbor of C if and only if there is some D′ ∈ Upper(C) such that D ≡∅ D′ .
5
Alternative denotations could be “direct subsumee” and “direct subsumer.”
6
We write C ⊏∅ D to indicate that C ⊑∅ D and D ̸⊑∅ C.
7
For D ∈ Conj(C), we abbreviate by C \ D the concept description (Conj(C) \ {D}).
d
Navigating the EL Subsumption Hierarchy 5
The mapping G 7→ C ↑G is a bijection from Conj(C) to Upper(C), cf. Propo-
sition 5.1.6 in [16]. Thus, each top-level conjunct of C induces a unique upper
neighbor of C.
Proposition 6. [16, Proposition 5.1.16]. Upper(C) can be computed in quadratic
time (w.r.t. C), each neighbor in Upper(C) has quadratic size (w.r.t. C),
Upper(C) consists of linearly many neighbors (w.r.t. C), and each two different
neighbors in Upper(C) are not equivalent.
An immediate consequence of Proposition 6 is the following result.
Proposition 7. [16, Theorem 5.1.17]. The neighborhood relation ≺∅ can be
decided in polynomial time.
Example 8. Consider the concept C := A⊓∃ r. (B1 ⊓B2 ⊓B3 ). The upper neighbor
induced by the first top-level conjunct A is ∃ r. (B1 ⊓B2 ⊓B3 ). In order to compute
the upper neighbor induced by the second top-level conjunct ∃ r. (B1 ⊓ B2 ⊓ B3 ),
we remove that atom and in its stead add the existential restrictions ∃ r. D where
D ranges over all upper neighbors of B1 ⊓B2 ⊓B3 — we obtain A⊓∃ r. (B1 ⊓B2 )⊓
∃ r. (B1 ⊓ B3 ) ⊓ ∃ r. (B2 ⊓ B3 ) as the second upper neighbor of C.
It remains to investigate how lower neighbors can be obtained by adding an
existential restriction. The above characterization of upper neighbors provides
a first hint: a lower neighbor of a concept C can be obtained by adding an
existential restriction ∃ r. D for which all ∃ r. E for all upper neighbors E of
D are already present in C (in a certain sense). More specifically, we observe
that C ⊓ ∃ r. D is a lower neighbor of C if and only if (L1) C ̸⊑∅ ∃ r. D and
(L2) C ⊑∅ ∃ r. E for eachdupper neighbor E of D, since the concept C ⊓ ∃ r. D is
a lower neighbor of C ⊓ { ∃ r. E | E ∈ Upper(D) }, cf. Proposition 5.
According to the recursive characterization of ⊑∅ and using the notation
Succ(C, r) := { F | ∃ r. F ∈ Conj(C) }, the above Condition (L2) is satisfied if
and only if there is a function ψ : Upper(D) → Succ(C, r) such that ψ(E) ⊑∅ E
for each upper neighbor E of D. This function ψ is injective. (Assume there
would be two different upper neighbors U and V of D such that ψ(U ) = ψ(V ).
We would obtain ψ(U ) ⊑∅ U ⊓ V . Since U ⊓ V is equivalent to D, we would
obtain a contradiction to the above condition (L1).)
By means of the above bijection between Conj(D) and Upper(D) we can
transform ψ to an injective function ϕ : Conj(D) → Succ(C, r) where ϕ(G) ⊑∅
D↑G for each G ∈ Conj(D). Since ϕ is injective, we can invert it and so obtain
a surjective partial mapping8 χ : Succ(C, r) → 7 Conj(D) such that F ⊑∅ D↑χ(F )
for each F ∈ Dom(χ). Since χ is surjective, we conclude that D must be the
conjunction of all atoms in Ran(χ). Furthermore, it is not hard to prove that
F ⊓ χ(F ) is a lower neighbor of F 9 for each F ∈ Dom(χ) and further that
F ′ ⊑∅ χ(F ) for each two different F, F ′ ∈ Dom(χ). We call χ a lowering function
8
For each partial function f : A → 7 B, its domain is Dom(f ) := { a | f (a) is defined }
and its range is Ran(f ) := { f (a) | a ∈ Dom(f ) }.
9
That’s why χ(F ) could be called a lowering atom of F as in [2].
6 Francesco Kriegel
and, to sum up, we have seen that there exists such a lowering function χ if
C ⊓ ∃ r. D is a lower neighbor of C. Actually, the converse direction holds true
as well and we obtain the following formal characterization.
Definition 9. Let C be a reduced EL concept description. We define the follow-
ing by mutual recursion on the role depth of C. Firstly, define the set
Lower(C) := { C ⊓ A | A ∈ ΣC and A ̸∈ Conj(C) }
d
∪ { C ⊓ ∃ r. Ran(χ) | r ∈ ΣR and χ is a lowering function for r } .
Secondly, a lowering function for a role name r is a partial mapping
χ : Succ(C, r) →7 EL(Σ) such that (1) F ⊓χ(F ) ∈ Lower(F ) for each F ∈ Dom(χ),
(2) F ′ ⊑∅ χ(F ) for each two different F, F ′ ∈ Dom(χ), and (3) C ̸⊑∅ ∃ r. Ran(χ).
d
Proposition 10. [16, Corollary 5.1.13]. For each reduced EL concept C, the set
Lower(C) consists of all lower neighbors of C (modulo equivalence), i.e., a con-
cept D is a lower neighbor of C if and only if D ≡∅ D′ for some D′ ∈ Lower(C).
Note that in [2] an efficient non-deterministic algorithm is described that pro-
duces all lower neighbors on its successful computation paths.
Proposition 11. [16, Propositions 5.1.19 and 5.1.21]. Lower(C) can
be computed in exponential time (w.r.t. C and Σ), each neighbor in Lower(C)
has quadratic size (w.r.t. C), Lower(C) consists of at most exponentially many
neighbors (w.r.t. C and Σ), and each two different neighbors in Lower(C) are
not equivalent.
The following example shows that the exponential blow-up cannot be avoided.
Example 12. Fix the signature d Σ consisting only of two role names r and s.
i i
Define
d the concept C n := { ∃ r. D n | i ∈ {1, . . . , n} } for each n ≥ 2 where Dn :=
n n j
{ Ej , Fj | j ∈ {1, . . . , n} \ {i} } ⊓ ∃ r . ⊤ ⊓ ∃ s . ⊤, and Ej := ∃ r . ∃ s. ⊤, and
Fj := ∃ sj . ∃ r. ⊤. There are exponentially many lowering functions for r, namely
the partial functions χ : Succ(Cn , r) → 7 EL(Σ) where Dom(χ) := Succ(Cn , r)
and χ(Dni ) ∈ {Ei , Fi } for each index i ∈ {1, . . . , n}, and these induce the lower
neighbors Cn ⊓ ∃ r. (G1 ⊓ · · · ⊓ Gn ) where each Gi is either Ei or Fi .
4 Distances between EL Concept Descriptions
Using the results from the previous section on neighbors of EL concept descrip-
tions, we are now able to introduce a natural distance measure (metric) on the
set EL(Σ), namely where the distance between two EL concepts C and D is the
length of a shortest path between C and D in the undirected graph with vertex
set EL(Σ) and in which two concepts are connected by an edge if they are neigh-
Navigating the EL Subsumption Hierarchy 7
bors of each other.10 This distance measure fulfills all conditions of a metric, i.e.,
the distance between two concepts is never negative, two concepts have distance
0 if and only if they are equivalent, the distance from C to D equals the distance
from D to C, and the distance between two concepts never exceeds the sum of
the distances with a third concept in the middle (triangle inequality).
In what follows, we will first explore some lattice-theoretic properties of the
partially ordered set (EL(Σ), ⊑∅ ) and then utilize a well-known construction
from Lattice Theory [6] to formally introduce the above mentioned metric. At
the end of this section, an asymptotic analysis of this metric reveals that it can
reach huge values, i.e., computing it is highly infeasible.
First of all, the binary conjunction ⊓ is the infimum operation in the poset
(EL(Σ), ⊑∅ ), i.e., for each two concepts C and D, it holds true that C ⊓ D ⊑∅ C
and C ⊓ D ⊑∅ D, and further E ⊑∅ C and E ⊑∅ D implies E ⊑∅ C ⊓ D for each
concept E. The dual notion is the supremum operation; for each two concepts C
and D, the supremum (or least common subsumer ) C ∨ D satisfies C ⊑∅ C ∨ D
as well as D ⊑∅ C ∨ D, and further C ⊑∅ E and D ⊑∅ E implies C ∨ D ⊑∅ E
for each concept E. According to [4], least common subsumers can be computed
by means of products of graphs/trees, yielding the following recursive formula:
d
C ∨ D ≡∅ { A | A ∈ Conj(C) and A ∈ Conj(D) }
d
⊓ { ∃ r. (E ∨ F ) | ∃ r. E ∈ Conj(C) and ∃ r. F ∈ Conj(D) }.
The existence of the infimum and the supremum operation turns the poset
(EL(Σ), ⊑∅ ) into a lattice. In [16, Proposition 5.2.1] it is shown that this lattice
is distributive, i.e., the equivalences C ⊓ (D ∨ E) ≡∅ (C ⊓ D) ∨ (C ⊓ E) and
C ∨ (D ⊓ E) ≡∅ (C ∨ D) ⊓ (C ∨ E) hold true for each three concepts C, D, E.
Recall that, for each concept C, there is a finite upper bound on the lengths
of chains starting with C [5, proof of Proposition 3.5]. We conclude that, for each
two concepts C and D, every chain from C to D has finite length. According
to [6], it follows that the lattice (EL(Σ), ⊑∅ ) satisfies the Jordan-Dedekind chain
condition, i.e., for each two concepts C and D with C ⊑∅ D, all maximal chains11
from C to D have the same length. It is now straightforward to define the distance
between two concepts C and D with C ⊑∅ D as the length of some maximal
chain from C to D. If the condition C ⊑∅ D is not satisfied, we instead employ the
length of some maximal chain from the infimum C ⊓ D to the supremum C ∨ D.
Proposition 13. [15, Proposition 16], [16, Proposition 5.4.3]. Consider the
mapping d : EL(Σ) × EL(Σ) → N where d(C, D) := n if there exist concepts
E0 , . . . , En such that C ⊓ D = E0 ≺∅ E1 ≺∅ · · · ≺∅ En = C ∨ D. It is well-
defined and it is a metric, i.e., the following properties are fulfilled for all con-
cepts C, D, E: (1) d(C, D) = 0 if and only if C ≡∅ D, (2) d(C, D) = d(D, C),
and (3) d(C, E) ≤ d(C, D) + d(D, E) ( triangle inequality).
10
Note that, in graph theory, it is well-known that the shortest path distance yields a
metric on each undirected graph.
11
A maximal chain is one that cannot be refined, i.e., which is not a strict subset of
another chain.
8 Francesco Kriegel
As shown in [16, Proposition 5.4.4], the distance d(C, D) coincides with the
length of a shortest path from C to D in the undirected graph (V, E) with vertex
set V := EL(Σ) and with edge set E := { {C, D} | C ≺∅ D }. Specifically, it
follows that the distance d(C, D) equals the sum of the lengths of a chain of
neighbors from C to C ⊓ D and of another from D to C ⊓ D.
We close this section with an asymptotic analysis. As a simple example, con-
sider the concept description ∃ r. (A1 ⊓ · · · ⊓ Ak ). Let X1 , . . . , Xℓ be an enumera-
tion of the exponentially
d many
d subsets of {A1 , . . . , Ak } with ⌊ k2 ⌋ elements, and
further let Dm := { ∃ r. Xi | i ∈ {m, . . . , ℓ} } for each index m ∈ {1, . . . , ℓ}.
It follows that ∃ r. (A1 ⊓ · · · ⊓ Ak ) ⊏∅ D1 ⊏∅ D2 ⊏∅ · · · ⊏∅ Dℓ ⊏∅ ⊤ is an expo-
nentially long chain of strict subsumptions, which implies that the distance from
∃ r. (A1 ⊓ · · · ⊓ Ak ) to ⊤ must be at least exponential. Even worse, the following
proposition shows that there exists a sequence of concept descriptions Cn such
that Cn has role depth n (and size linear in n) and the distance from Cn to ⊤
is n-fold exponential.
Proposition 14. [16, Corollary 5.6.9]. Fix a natural number k ≥ 3 and let
A1 , . . . , Ak be different concept names from Σ. Further let ri be a role name
in Σ for each natural number i. The distance from ∃ r1 . · · · ∃ rn . (A1 ⊓ · · · ⊓ Ak )
to ⊤, where n ranges over the natural numbers, is asymptotically bounded from
below by12 the iterated exponential
k
.22
..
2
|2 {z } .
n times
The precondition k ≥ 3 is crucial for the multi-exponential growth. Specifi-
cally, the above distance is only linear if k < 3, cf. Proposition 5.6.12 in [16]. The
below table shows some values of the distance d(⊤, ∃ r1 . · · · ∃ rn . (A1 ⊓ · · · ⊓ Ak )).
k\n 0 1 2 3 4 5 6
0 0 1 2 3 4 5 6
1 1 2 3 4 5 6 7
2 2 4 6 8 10 12 14
3 4 6 20 184756
3 3 8≥ 1 20 ≥ 4 84 ≥ 2 8573 ≥ 3 ?≥ 10 ?≥ 92378
4 6 20 184756 2.33·1055614
4 4 16 ≥ 2 168 ≥ 3 ?≥ 10 ?≥ 92378 ?⪆ 1.16·1055614 ?
5 10 252 3.63·1074
5 5 32 ≥ 2 7581 ≥ 5 ?≥ 126 ?⪆ 1.82·1074 ? ?
6 20 184756 2.33·1055614
6 6 64 ≥ 3 ?≥ 10 ?≥ 92378 ?⪆ 1.16·1055614 ? ?
7 35 4.54·109
7 7 128 ≥ 3 ?≥ 17 ?⪆ 2.27·109 ? ? ?
8 70 1.12·1020
8 8 256 ≥ 4 ?≥ 35 ?⪆ 5.61·1019 ? ? ?
9 126 6.03·1036
9 9 512 ≥ 4 ?≥ 63 ?⪆ 3.02·1036 ? ? ?
10 252 3.63·1074
10 10 1024 ≥ 5 ?≥ 126 ?⪆ 1.82·1074 ? ? ?
12
A function f : N → R is asymptotically bounded from below by a function g : N → R
if there is a constant c ∈ R+ and a number n0 ∈ N such that c · g(n) ≤ f (n) for each
n ≥ n0 .
Navigating the EL Subsumption Hierarchy 9
5 Applications and Consequences
Deciding Minimality and Maximality for a Property. [2, Section 5], [16,
Section 5.1.2]. Let P ⊆ EL(Σ) be a decision problem that is closed under sub-
sumees, i.e., C ∈ P and C ⊒∅ D implies D ∈ P. Further consider the problem
Max(P) that consists of all maximally general concepts in P, i.e., C ∈ Max(P)
if and only if C ∈ P and there is no D such that C ⊏∅ D and D ∈ P.
A deterministic, polynomial time procedure that decides Max(P) is as fol-
lows: (1) On input C, check whether C ∈ P. If not, then reject C. (2) Com-
pute the set Upper(C) from Proposition 5. (3) If there exists an upper neighbor
D ∈ Upper(C) such that D ∈ P, then reject C; otherwise accept C.
We conclude that P ∈ C implies Max(P) ∈ PC for each complexity class C,
which specifically yields that P ∈ P implies Max(P) ∈ P and that P ∈ ΣPn
implies Max(P) ∈ ∆Pn+1 for each number n ∈ N. Furthermore, P ∈ P Space
implies Max(P) ∈ P Space, since PP Space ⊆ P Space [24]. More generally, P ∈ C
implies Max(P) ∈ C for each complexity class C where P Space ⊆ C.
Dually, let P ⊆ EL(Σ) be a decision problem that is closed under subsumers,
i.e., C ∈ P and C ⊑∅ D implies D ∈ P, and consider the problem Min(P) that
consists of all maximally specific concepts in P, i.e., C ∈ Min(P) if and only if
C ∈ P and there is no D such that C ⊐∅ D and D ∈ P.
A non-deterministic, polynomial time procedure that decides the complement
of Min(P) is the following: (1) On input C, check if C ∈ P. If not, then accept C.
(2) Guess a concept D the size of which is quadratic in C. (3) Check if C is an
upper neighbor of D. If not, then accept C. (4) Check if D ∈ P. If yes, then
accept C; otherwise reject C.
It follows that P ∈ C implies Min(P) ∈ co (NPC ) for each complexity class C.
In particular, we infer that P ∈ P implies Min(P) ∈ co NP, and that P ∈ ΣPn
implies Min(P) ∈ ΠPn+1 for each n ∈ N. As co (NPP Space ) ⊆ P Space [24], we
further conclude that P ∈ P Space implies Min(P) ∈ P Space and, more generally,
that P ∈ C implies Min(P) ∈ co C for each complexity class C with P Space ⊆ C.
A Similarity Measure that Fulfills the Triangle Inequality. [16, Sec-
tion 5.5]. Similarity measures quantify the similarity of two objects. In the
context of DLs, usually either concepts or individuals are compared. In an early
article on similarity measures on DL concepts [7], three approaches to defining
such measures are proposed: based on features, based on semantic networks,
and based on information content. However, no concrete measure is devised.
Later, [9] compares existing (concrete) DL similarity measures, divides them into
extensional-based and intentional-based ones, and proposes a new such measure.
A framework for constructing similarity measures between concepts in the mild
extension of EL with simple role inclusions r ⊑ s is developed in [22]. Addition-
ally, an overview on other existing similarity measures and their properties is
provided. Notably, none satisfies the triangle inequality. In [10] a general frame-
work for constructing similarity measures based on concept relaxation operators
(which are similar to upward refinement operators) is introduced. Each such
10 Francesco Kriegel
similarity measure satisfies the triangle inequality.
Different kinds of similarity measures have also been employed in the de-
velopment of novel DLs. For instance, [23] extends an expressive DL by means
to specify degrees of similarity between individuals, but that logic turns out
to be undecidable. So-called threshold DLs are investigated in [1], where (val-
ues of) graded membership functions replace the Boolean membership values 0
and 1. Decidability and computational complexity is determined and it is further
explained how a graded membership function can be obtained from a concept
similarity measure.
In the following, we explain how the distance measure d in Proposition 13
can be transformed into a similarity measure. Firstly, we convert d into a metric
with range [0, 1) and, secondly, we twist the range (i.e., value x becomes 1 − x).
Formally, if f : [0, ∞) → [0, 1) is an order-preserving, sub-additive function, then
the mapping s defined by s(C, D) := 1 − f (d(C, D)) is a similarity measure. For
x y
instance, suitable functions are f (x) := ( 1+x ) for each y > 0 and f (x) := 1 − y x
for each y ∈ (0, 1). Such a similarity measure s fulfills all properties listed in [22]
including the triangle inequality, but not the property of structural dependence.
Potential Uselessness of Ideal Downward Refinement Operators. [16,
Section 5.1.9]. A downward refinement operator takes an object as input and
returns a set of objects that are more specific w.r.t. a given partial order. Such
operators have been employed in inductive logic programming in order to learn
theories from facts [27]. The analysis in [18] reveals that refinement operators
with certain desirable properties cannot exist. In the context of DLs, such an
operator usually maps a concept C to a set of concepts subsumed by C. In [21],
an ideal downward refinement operator in a slight extension of EL is introduced
and, in [20], it is proposed to use this operator to learn EL concepts. A similar
downward refinement operator is described in [25], where it further serves as a
means to defining a similarity measure (by counting refinement steps). Expand-
ing on the latter results, a downward refinement operator on conjunctive queries
(with a fixed set of answer variables) is introduced in [26], which allows for the
definition of a similarity measure in a similar manner.
In [20, Section 2.2] it is stated that “refinement operators are used to structure
a search process for concepts.” While this argument holds true in theory, we
show in the following that utilizing the ideal downward refinement operator, as
introduced in [21], for learning a target concept is not feasible in applications.
Given a TBox T , a downward refinement operator is a function ρ that maps
each concept description to a set of concept descriptions such that D ∈ ρ(C)
implies D ⊑T C.13 Furthermore, ρ is ideal if it additionally fulfills the following
conditions: (1) ρ is finite, i.e., ρ(C) is finite for each C, (2) ρ is proper, i.e.,
D ∈ ρ(C) implies D ̸≡T C, and (3) ρ is complete, i.e., D ⊏T C implies the
existence of concept descriptions E1 , . . . , En such that E1 ∈ ρ(C), E2 ∈ ρ(E1 ),
. . . , En ∈ ρ(En−1 ), and En ≡T D.
There is a connection between the notion of neighbors of concept descrip-
13
By C ⊑T D we indicate that C I ⊆ DI for each model I of T .
Navigating the EL Subsumption Hierarchy 11
tions and ideal downward refinement operators. In what follows, we consider
the particular downward refinement operator ρ∗ in [21, Theorem 1]. Firstly, ρ∗
is defined with respect to TBoxes that may only contain axioms of the follow-
ing forms: concept inclusions A ⊑ B, concept disjointness axioms A ⊓ B ≡ ⊥,
role inclusions r ⊑ s, domain restrictions Dom(r) ⊑ A, and range restrictions
Ran(r) ⊑ A, where A and B are concept names and where r and s are role
names. Secondly, ρ∗ is defined by means of another refinement operator ρ, which
constructs refinements by applying one of four operations to the syntax tree of
the concept description to be refined: (1) add a concept name as label to some
node, (2) refine a concept name that labels a node (i.e., if A ⊑ B is in T , then
a label B can be replaced by A), (3) refine a role name that labels an edge,
and (4) attach a new subtree to some node (see [21] for the concrete definition).
ρ is only weakly complete, i.e., the above condition for completeness is only guar-
anteed for C = ⊤. The refinements of some concept description C w.r.t. ρ∗ are
then defined as the w.r.t. T maximally general concept descriptions D satisfying
the following conditions: (1) there is a sequence of ρ-refinements starting with ⊤
and ending with D, (2) D ⊏T C, and (3) the role depth of D exceeds the role
depth of C by at most 1. Note that, since ρ is weakly complete, the first condi-
tion is redundant. It immediately follows from the required maximal generality
and from Condition (2) that D must be a lower neighbor of C w.r.t. T .14 Fur-
thermore, since ρ∗ is complete, each set ρ∗ (C) must contain all lower neighbors
of C w.r.t. T modulo equivalence. We conclude that ρ∗ is the set of all lower
neighbors of C w.r.t. T modulo equivalence.
For the case where the TBox T is empty, it follows from Proposition 14 that
the search for a particular EL concept description may need a non-elementary
number of consecutive refinement steps with ρ∗ . More specifically, constructing
the target concept ∃ r1 . · · · ∃ rn . (A1 ⊓ · · · ⊓ Ak ) starting from ⊤ by means of ρ∗
needs a number of steps that is asymptotically bounded from below by
k
.22
..
2
|2 {z } .
n times
For the same reason, utilizing the refinement operators in [25, 26] for an
uninformed search is not feasible in practical settings as well.
Computing Maximally Strong Weakenings for Gentle Repairs. In order
to resolve inconsistency or to remove an unwanted consequence, the classical
approach to repairing an ontology is deleting enough axioms from it. More fine-
grained repairs can be obtained by weakening axioms instead of removing them
completely [3, 8, 11, 14, 19, 28].
A general framework for computing gentle repairs by axiom weakening is
developed in [3], where conditions on the weakening relations are formulated that
guarantee termination. Furthermore, an instantiation of the framework for EL is
provided specifically for the case of repairing TBoxes. One proposed weakening
14
C is a lower neighbor of D if C ⊏T D and there is no E such that C ⊏T E ⊏T D.
12 Francesco Kriegel
relation, namely ≻sub , takes a concept inclusion C ⊑ D and weakens it to a
concept inclusion C ⊑ E where D ⊏∅ E and such that C ⊑ E does not entail
C ⊑ D. A so-called maximally strong weakening is, put simply, a weakening that
loses a minimal amount of information, see Definition 17 in [3] for details.
According to Proposition 18 in [3], maximally strong weakenings of a con-
cept inclusion C ⊑ D w.r.t. ≻sub can be effectively computed by a breadth-first
search, namely by traversing the EL subsumption hierarchy above D (all sub-
sumers of D) by means of the neighborhood relation ≺∅ . As already pointed out
after Corollary 25 in [3], the search tree has (n + 1)-fold exponential size where n
is the role depth of D. Now Proposition 14 yields that this search tree can have
n-fold exponential depth — more specifically, if C ⊑ ⊤ is the maximally strong
weakening of C ⊑ ∃ r1 . · · · ∃ rn . (A1 ⊓· · ·⊓Ak ), then computing it by means of the
procedure in Proposition 18 in [3] needs n-fold exponential time. Thus, in order
to utilize the weakening relation ≻sub in implementations, more sophisticated
methods for computing the maximally strong weakenings must be developed.
6 Conclusion
We have analyzed the EL subsumption hierarchy and, in particular, we have
showed how smallest steps can be made when navigating within this hierarchy.
Such a smallest step is either going up to an upper neighbor or going down
to a lower neighbor. We have explained how all neighbors of a given concept
can be computed and we have determined the computational complexity: all
upper neighbors can be obtained in polynomial time, while enumerating all lower
neighbors needs exponential time. By employing a standard construction from
Lattice Theory, we have devised a distance measure (metric) on the set of all EL
concepts. We have further seen that the EL subsumption hierarchy contains very
long chains, since the distance between supposedly simple concepts can easily be
multi-exponential — specifically, the distance between ⊤ and ∃ r1 . · · · ∃ rn . (A1 ⊓
· · · ⊓ Ak ) is n-fold exponential if k ≥ 3 — which directly prohibits its practical
usage. Additionally, we have given some applications and consequences of the
aforementioned results.
In this article, we have looked at subsumption w.r.t. the empty TBox only.
Other types of TBoxes (cycle-restricted, acyclic, general) as well as two exten-
sions of EL (with ⊥, with greatest fixed-points) are considered in [16]. Future
research could investigate more expressive DLs. First investigations show that
similar characterizations of upper and lower neighbors can be developed for FLE.
Since within FLE each EL concept has only EL concepts as subsumers, we im-
mediately obtain that also the FLE subsumption hierarchy must contain chains
of multi-exponential length.
Acknowledgements. The author gratefully thanks both Franz Baader and
Bernhard Ganter for helpful discussions. The author further greatly appreciates
Franz Baader’s valuable comments that helped to improve this article. Also, the
author thanks the anonymous reviewers for their comments and questions.
Navigating the EL Subsumption Hierarchy 13
References
1. Baader, F., Gil, O.F.: Decidability and Complexity of Threshold Description Logics
induced by Concept Similarity Measures. In: Seffah, A., Penzenstadler, B., Alves,
C., Peng, X. (eds.) Proceedings of the Symposium on Applied Computing, SAC
2017, Marrakech, Morocco, April 3-7, 2017. pp. 983–988. ACM (2017)
2. Baader, F., Kriegel, F., Nuradiansyah, A.: Privacy-Preserving Ontology Publishing
for EL Instance Stores. In: Calimeri, F., Leone, N., Manna, M. (eds.) 16th European
Conference on Logics in Artificial Intelligence, JELIA 2019, Rende, Italy, May 7-11,
2019, Proceedings. Lecture Notes in Computer Science, vol. 11468, pp. 323–338.
Springer (2019)
3. Baader, F., Kriegel, F., Nuradiansyah, A., Peñaloza, R.: Making Repairs in Descrip-
tion Logics More Gentle. In: Thielscher, M., Toni, F., Wolter, F. (eds.) Principles
of Knowledge Representation and Reasoning: Proceedings of the Sixteenth Inter-
national Conference, KR 2018, Tempe, Arizona, 30 October - 2 November 2018.
pp. 319–328. AAAI Press (2018)
4. Baader, F., Küsters, R., Molitor, R.: Computing Least Common Subsumers in
Description Logics with Existential Restrictions. In: Dean, T. (ed.) Proceedings of
the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99,
Stockholm, Sweden, July 31 - August 6, 1999. 2 Volumes, 1450 pages. pp. 96–103.
Morgan Kaufmann (1999)
5. Baader, F., Morawska, B.: Unification in the Description Logic EL. Log. Methods
Comput. Sci. 6(3) (2010)
6. Birkhoff, G.: Lattice Theory, Colloquium Publications, vol. 25. American Mathe-
matical Society, Providence, RI, USA (1940)
7. Borgida, A., Walsh, T.J., Hirsh, H.: Towards Measuring Similarity in Description
Logics. In: Horrocks, I., Sattler, U., Wolter, F. (eds.) Proceedings of the 2005 In-
ternational Workshop on Description Logics (DL2005), Edinburgh, Scotland, UK,
July 26-28, 2005. CEUR Workshop Proceedings, vol. 147. CEUR-WS.org (2005)
8. Confalonieri, R., Galliani, P., Kutz, O., Porello, D., Righetti, G., Troquard, N.:
Towards Even More Irresistible Axiom Weakening. In: Borgwardt, S., Meyer, T.
(eds.) Proceedings of the 33rd International Workshop on Description Logics (DL
2020) co-located with the 17th International Conference on Principles of Knowl-
edge Representation and Reasoning (KR 2020), Online Event [Rhodes, Greece],
September 12th to 14th, 2020. CEUR Workshop Proceedings, vol. 2663. CEUR-
WS.org (2020)
9. d’Amato, C., Staab, S., Fanizzi, N.: On the Influence of Description Logics On-
tologies on Conceptual Similarity. In: Gangemi, A., Euzenat, J. (eds.) Knowledge
Engineering: Practice and Patterns, 16th International Conference, EKAW 2008,
Acitrezza, Italy, September 29 - October 2, 2008. Proceedings. Lecture Notes in
Computer Science, vol. 5268, pp. 48–63. Springer (2008)
10. Distel, F., Atif, J., Bloch, I.: Concept Dissimilarity with Triangle Inequality. In:
Baral, C., Giacomo, G.D., Eiter, T. (eds.) Principles of Knowledge Representation
and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014,
Vienna, Austria, July 20-24, 2014. AAAI Press (2014)
11. Du, J., Qi, G., Fu, X.: A Practical Fine-grained Approach to Resolving Incoherent
OWL 2 DL Terminologies. In: Li, J., Wang, X.S., Garofalakis, M.N., Soboroff, I.,
Suel, T., Wang, M. (eds.) Proceedings of the 23rd ACM International Conference
on Conference on Information and Knowledge Management, CIKM 2014, Shanghai,
China, November 3-7, 2014. pp. 919–928. ACM (2014)
14 Francesco Kriegel
12. Ganter, B.: Personal communication (April 2018)
13. Ganter, B., Wille, R.: Formal Concept Analysis - Mathematical Foundations.
Springer (1999)
14. Horridge, M., Parsia, B., Sattler, U.: Laconic and precise justifications in OWL.
In: Sheth, A.P., Staab, S., Dean, M., Paolucci, M., Maynard, D., Finin, T.W.,
Thirunarayan, K. (eds.) The Semantic Web - ISWC 2008, 7th International Se-
mantic Web Conference, ISWC 2008, Karlsruhe, Germany, October 26-30, 2008.
Proceedings. Lecture Notes in Computer Science, vol. 5318, pp. 323–338. Springer
(2008)
15. Kriegel, F.: The Distributive, Graded Lattice of EL Concept Descriptions and its
Neighborhood Relation. In: Ignatov, D.I., Nourine, L. (eds.) Proceedings of the
Fourteenth International Conference on Concept Lattices and Their Applications,
CLA 2018, Olomouc, Czech Republic, June 12-14, 2018. CEUR Workshop Pro-
ceedings, vol. 2123, pp. 267–278. CEUR-WS.org (2018)
16. Kriegel, F.: Constructing and Extending Description Logic Ontologies using Meth-
ods of Formal Concept Analysis. Doctoral thesis, Technische Universität Dresden,
Dresden, Germany (2019)
17. Küsters, R.: Non-Standard Inferences in Description Logics, Lecture Notes in Com-
puter Science, vol. 2100. Springer (2001)
18. van der Laag, P.R.J., Nienhuys-Cheng, S.: Existence and Nonexistence of Complete
Refinement Operators. In: Bergadano, F., Raedt, L.D. (eds.) Machine Learning:
ECML-94, European Conference on Machine Learning, Catania, Italy, April 6-
8, 1994, Proceedings. Lecture Notes in Computer Science, vol. 784, pp. 307–322.
Springer (1994)
19. Lam, J.S.C., Sleeman, D.H., Pan, J.Z., Vasconcelos, W.W.: A fine-grained approach
to resolving unsatisfiable ontologies. J. Data Semant. 10, 62–95 (2008)
20. Lehmann, J.: Learning OWL Class Expressions, Studies on the Semantic Web,
vol. 6. IOS Press (2010)
21. Lehmann, J., Haase, C.: Ideal Downward Refinement in the EL Description Logic.
In: Raedt, L.D. (ed.) Inductive Logic Programming, 19th International Conference,
ILP 2009, Leuven, Belgium, July 02-04, 2009. Revised Papers. Lecture Notes in
Computer Science, vol. 5989, pp. 73–87. Springer (2009)
22. 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)
23. Lutz, C., Wolter, F., Zakharyaschev, M.: Reasoning about Concepts and Similarity.
In: Calvanese, D., Giacomo, G.D., Franconi, E. (eds.) Proceedings of the 2003
International Workshop on Description Logics (DL2003), Rome, Italy September
5-7, 2003. CEUR Workshop Proceedings, vol. 81. CEUR-WS.org (2003)
24. Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1994)
25. Sánchez-Ruiz-Granados, A.A., Ontañón, S., González-Calero, P.A., Plaza, E.: Mea-
suring Similarity in Description Logics Using Refinement Operators. In: Ram, A.,
Wiratunga, N. (eds.) Case-Based Reasoning Research and Development - 19th
International Conference on Case-Based Reasoning, ICCBR 2011, London, UK,
September 12-15, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6880,
pp. 289–303. Springer (2011)
26. Sánchez-Ruiz-Granados, A.A., Ontañón, S., González-Calero, P.A., Plaza, E.:
Refinement-Based Similarity Measure over DL Conjunctive Queries. In: Delany,
Navigating the EL Subsumption Hierarchy 15
S.J., Ontañón, S. (eds.) Case-Based Reasoning Research and Development - 21st
International Conference, ICCBR 2013, Saratoga Springs, NY, USA, July 8-11,
2013. Proceedings. Lecture Notes in Computer Science, vol. 7969, pp. 270–284.
Springer (2013)
27. Shapiro, E.Y.: An Algorithm that Infers Theories from Facts. In: Hayes, P.J. (ed.)
Proceedings of the 7th International Joint Conference on Artificial Intelligence,
IJCAI ’81, Vancouver, BC, Canada, August 24-28, 1981. pp. 446–451. William
Kaufmann (1981)
28. Troquard, N., Confalonieri, R., Galliani, P., Peñaloza, R., Porello, D., Kutz, O.:
Repairing Ontologies via Axiom Weakening. In: McIlraith, S.A., Weinberger, K.Q.
(eds.) Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence,
(AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18),
and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence
(EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018. pp. 1981–1988.
AAAI Press (2018)