=Paper=
{{Paper
|id=None
|storemode=property
|title=Transforming Fuzzy Description Logic ALCFL into Classical Description Logic ALCH
|pdfUrl=https://ceur-ws.org/Vol-654/paper2.pdf
|volume=Vol-654
|dblpUrl=https://dblp.org/rec/conf/semweb/Wu10
}}
==Transforming Fuzzy Description Logic ALCFL into Classical Description Logic ALCH==
https://ceur-ws.org/Vol-654/paper2.pdf
Transforming Fuzzy Description Logic ALCF L
into
Classical Description Logic ALCH
Yining Wu
University of Luxembourg, Luxembourg
Abstract. In this paper, we present a satisfiability preserving transfor-
mation of the fuzzy Description Logic ALC F L into the classical Descrip-
tion Logic ALCH. We can use the already existing DL systems to do the
reasoning of ALC F L by applying the result of this paper. This work is
inspired by Straccia, who has transformed the fuzzy Description Logic
fALCH into the classical Description Logic ALCH.
1 Introduction
The Semantic Web is a vision for the future of the Web in which informa-
tion is given explicit meaning, making it easier for machines to automatically
process and integrate information available on the Web. While as a basic com-
ponent of the Semantic Web, an ontology is a collection of information and is
a document or file that formally defines the relations among terms. OWL1 is
a Web Ontology Language and is intended to provide a language that can be
used to describe the classes and relations between them that are inherent in
Web documents and applications. The OWL language provides three increas-
ingly expressive sublanguages: OWL Lite, OWL DL, OWL Full. OWL DL is so
named due to its correspondence with description logics. OWL DL was designed
to support the existing Description Logic business segment and has desirable
computational properties for reasoning systems. According to the corresponding
relation between axioms of OWL ontology and terms of Description Logic, we
can represent the knowledge base contained in the ontology in syntax of DLs.
Description Logics (DLs) [1] have been studied and applied successfully in a
lot of fields. The concepts in classical DLs are usually interpreted as crisp sets,
i.e., an individual either belongs to the set or not. In the real world, the answers to
some questions are often not only yes or no, rather we may say that an individual
is an instance of a concept only to some certain degree. We often say linguistic
terms such as “Very”, “More or Less” etc. to distinguish, e.g. between a young
person and a very young person. In 1970s, the theory of approximate reasoning
based on the notions of linguistic variable and fuzzy logic was introduced and
developed by Zadeh [19–21]. Adverbs as “Very”, “More or Less” and “Possibly”
1
Please visit http://www.w3.org/TR/owl-guide/ for more details.
are called hedges in fuzzy DLs. Some approaches to handling uncertainty and
vagueness in DL for the Semantic Web are described in [10].
A well known feature of DLs is the emphasis on reasoning as a central ser-
vice. Some reasoning procedures for fuzzy DLs have been proposed in [16]. A
transformation of fALCH into ALCH has been presented in [17]. This approach,
however, only works for DLs where modifier concepts are not allowed.
In this paper we consider the fuzzy linguistic description logic ALC F L [7]
which is an instance of the description logic framework L − ALC with the cer-
tainty lattice characterized by a hedge algebra and allows the modification by
hedges. Because the certainty lattice is characterized by a HA, the modifica-
tion by hedges becomes more natural than that in ALCF H [8] and ALCF LH [14]
which extend fuzzy ALC by allowing the modification by hedges of HAs. We will
present a satisfiability preserving transformation of ALC F L into ALCH which
makes the reuse of the technical results of classical Dls for ALC F L feasible.
The remaining part of this paper is organized in the following way. First we
state some preliminaries on ALCH, hedge algebra and ALC F L . Then we present
the transformation of ALC F L into ALCH. Finally we discuss the main result of
the paper and identify some possibilities for further work.
2 Preliminaries
ALCH
We consider the language ALCH (Attributive Language with Complement and
role Hierarchy). In abstract notation, we use the letters A and B for concept
names, the letter R for role names, and the letters C and D for concept terms.
Definition 1. Let NR and NC be disjoint sets of role names and concept names.
Let A ∈ NC and R ∈ NR . Concept terms in ALCH are formed according to the
following syntax rule:
A|⊤|⊥|C ⊓ D|C ⊔ D|¬C|∀R.C|∃R.C
The semantics of concept terms are defined formally by interpretations.
Definition 2. An interpretation I is a pair (∆I , ·I ), where ∆I is a nonempty
set ( interpretation domain) and ·I is an interpretation function which assigns to
each concept name A a set AI ⊆ ∆I and to each role name R a binary relation
RI ⊆ ∆I × ∆I . The interpretation of complex concept terms is extended by the
following inductive definitions:
⊤I = ∆I
⊥I = ∅
(C ⊓ D)I = C I ∩ DI
(C ⊔ D)I = C I ∪ DI
(¬C)I = ∆I \ C I
(∀R.C)I = {d ∈ ∆I | ∀d′ .(d, d′ ) ∈
/ RI or d′ ∈ C I }
(∃R.C) = {d ∈ ∆ | ∃d .(d, d ) ∈ RI and d′ ∈ C I }
I I ′ ′
A concept term C is satisfiable iff there exists an interpretation I such that
C I 6= ∅, denoted by I |= C. Two concept terms C and D are equivalent (denoted
by C ≡ D) iff C I = DI for all interpretation I.
We have seen how we can form complex descriptions of concepts to describe
classes of objects. Now, we introduce terminological axioms, which make state-
ments about how concept terms and roles are related to each other respectively.
In the most general case, terminological axiom have the form C ⊑ D or R ⊑
S, where C, D are concept terms, R, S are role names. This kind of terminological
axioms are also called inclusions. A set of axioms of the form R ⊑ S is called
role hierarchy. An interpretation I satisfies an inclusion C ⊑ D (R ⊑ S) iff
C I ⊆ DI (RI ⊆ S I ), denoted by I |= C ⊑ D (I |= R ⊑ S).
A terminology, i.e., TBox, is a finite set of terminological axioms. An inter-
pretation I satisfies (is a model of) a terminology T iff I satisfies each element
in T , denoted by I |= T .
Assertions define how individuals relate with each other and how individuals
relate with concept terms. Let NI be a set of individual names which is disjoint
to NR and NC . An assertion α is an expression of the form a : C or (a, b) : R,
where a, b ∈ NI , R ∈ NR and C ∈ NC . A finite set of assertions is called ABox.
An interpretation I satisfies a concept assertion a : C iff aI ∈ C I , denoted by
I |= a : C. I satisfies a role assertion (a, b) : R iff (aI , bI ) ∈ RI , denoted by
I |= (a, b) : R. An interpretation I satisfies (is a model of) an ABox A iff I
satisfies each assertion in A, denoted by I |= A.
A knowledge base is of the form hT , Ai where T is a TBox and A is an ABox.
An interpretation I satisfies (is a model of, denoted by I |= K) a knowledge base
K = hT , Ai iff I satisfies both T and A. We say that a knowledge base K entails
an assertion α, denoted K |= α iff each model of K satisfies α. Furthermore, let
T be a TBox and let C, D be two concept terms. We say that D subsumes C
with respect to T (denoted by C ⊑T D) iff for each model of T , I |= C I ⊆ DI .
The problem of determining whether K |= α is called entailment problem; the
problem of determining whether C ⊑T D is called subsumption problem; and the
problem of determining whether K is satisfiable is called satisfiability problem.
Entailment problem and subsumption problem can be reduced to satisfiability
problem.
Linear symmetric Hedge Algebra
In this section, we introduce linear symmetric Hedge Algebras (HAs). For general
HAs, please refer to [12, 11, 13].
Let us consider a linguistic variable TRUTH with the domain dom(TRUTH ) =
{True, False, VeryTrue, VeryFalse, MoreTrue, MoreFalse, PossiblyTrue, . . .}. This
domain is an infinite partially ordered set, with a natural ordering a < b mean-
ing that b describes a larger degree of truth if we consider T rue > F alse. This
set is generated from the basic elements (generators) G = {True, False} by us-
ing hedges, i.e., unary operations from a finite set H = {Very, Possibly, More}.
The dom(TRUTH ) which is a set of linguistic values can be represented as
X = {δc | c ∈ G, δ ∈ H ∗ } where H ∗ is the Kleene star of H, From the alge-
braic point of view, the truth domain can be described as an abstract algebra
AX = (X, G, H, >).
To define relations between hedges, we introduce some notations first. We
define that H(x) = {σx | σ ∈ H ∗ } for all x ∈ X. Let I be the identity hedge,
i.e., ∀x ∈ X.Ix = x. The identity I is the least element. Each element of H is
an ordering operation, i.e., ∀h ∈ H, ∀x ∈ X, either hx > x or hx < x.
Definition 3. [12] Let h, k ∈ H be two hedges, for all x ∈ X we define:
– h, k are converse if hx < x iff kx > x;
– h, k are compatible if hx < x iff kx < x;
– h modifies terms stronger or equal than k, denoted by h ≥ k if hx ≤ kx ≤ x
or hx ≥ kx ≥ x;
– h > k if h ≥ k and h 6= k;
– h is positive wrt k if hkx < kx < x or hkx > kx > x;
– h is negative wrt k if kx < hkx < x or kx > hkx > x.
ALC F L only considers symmetric HAs, i.e., there are exactly two generators
as in the example G = {True, False}. Let G = {c+ , c− } where c+ > c− . c+ and
c− are called positive and negative generators respectively. Because there are
only two generators, the relations presented in Definition 3 divides the set H
into two subsets H + = {h ∈ H | hc+ > c+ } and H − = {h ∈ H | hc+ < c+ }, i.e.,
every operation in H + is converse w.r.t. any operation in H − and vice-versa,
and the operations in the same subset are compatible with each other.
Definition 4. [7] An abstract algebra AX = (X, G, H, >), where H 6= ∅, G =
{c+ , c− } and X = {σc | c ∈ G, σ ∈ H ∗ } is called a linear symmetric hedge
algebra if it satisfies the properties (A1)-(A5).
(A1) Every hedge in H + is a converse operation of all operations in H − .
(A2) Each hedge operation is either positive or negative w.r.t. the others, in-
cluding itself.
(A3) The sets H + ∪ {I} and H − ∪ {I} are linearly ordered with the I.
(A4) If h 6= k and hx < kx then h′ hx < k ′ kx, for all h, k, h′ , k ′ ∈ H and x ∈ X.
(A5) If u ∈/ H(v) and u ≤ v (u ≥ v) then u ≤ hv (u ≥ hv), for any hedge h
and u, v ∈ X.
Let AX = (X, G, H, >) be a linear symmetric hedge algebra and c ∈ G. We
define that, c̄ = c+ if c = c− and c̄ = c− if c = c+ . Let x ∈ X and x = σc, where
σ ∈ H ∗ . The contradictory element to x is y = σc̄ written y = −x.
[12] gave us the following proposition to compare elements in X.
Proposition 5 Let AX = (X, G, H, >) be a linear symmetric HA, x = hn · · · h1 u
and y = km · · · k1 u are two elements of X where u ∈ X. Then there exists an
index j ≤ min{n, m} + 1 such that hi = ki for all i < j, and
(i) x < y iff hj xj < kj xj , where xj = hj−1 · · · h1 u;
(ii) x = y iff n = m = j and hj xj = kj xj .
In order to define the semantics of the hedge modification, we only consider
monotonic HAs defined in [7] which also extended the order relation on H + ∪{I}
and H − ∪ {I} to one on H ∪ {I}. We will use “hedge algebra” instead of “linear
symmetric hedge algebra” in the rest of this paper.
Inverse mapping of hedges
Fuzzy description logics represent the assessment “It is true that Tom is very
old” by
(VeryOld )I (Tom)I = True. (1)
In a fuzzy linguistic logic [19–21], the assessment “It is true that Tom is very
old” and the assessment “It is very true that Tom is old” are equivalent, which
means
(Old )I (Tom)I = VeryTrue, (2)
and (1) has the same meaning. This signifies that the modifier can be moved
from concept term to truth value and vice versa. For any h ∈ H and for any
σ ∈ H ∗ , the rules of moving hedges [11] are as follows,
RT 1 : (hC)I (d) = σc → (C)I (d) = σhc
RT 2 : (C)I (d) = σhc → (hC)I (d) = σc.
where C is a concept term and d ∈ ∆I .
Definition 6. [7] Consider a monotonic HA AX = (X, {c+ , c− }, H, >) and a
h ∈ H. A mapping h− : X → X is called an inverse mapping of h iff it satisfies
the following two properties,
1. h− (σhc) = σc.
2. σ1 c1 > σ2 c2 ⇔ h− (σ1 c1 ) > h− (σ2 c2 ).
where c, c1 , c2 ∈ G, h ∈ H and σ1 , σ2 ∈ H ∗ .
ALC F L
ALC F L is a Description Logic in which the truth domain of interpretations is
represented by a hedge algebra. The syntax of ALC F L is similar to that of ALCH
except that ALC F L allows concept modifiers and does not include role hierarchy.
Definition 7. Let H be a set of hedges. Let A be a concept name and R a role,
complex concept terms denoted by C, D in ALC F L are formed according to the
following syntax rule:
A|⊤|⊥|C ⊓ D|C ⊔ D|¬C|δC|∀R.C|∃R.C
where δ ∈ H ∗ .
In [13], HAs are extended by adding two artificial hedges inf and sup defined
as inf(x) = infimum(H(x)), sup(x) = supremum(H(x)). If H = ∅, H(c+ ) and
H(c− ) are infinite, according to [13] inf(c+ ) = sup(c− ). Let W = inf (True) =
sup (False) and let sup(True) and inf(False) be the greatest and the least ele-
ments of X respectively.
The semantics is based on the notion of interpretations.
Definition 8. Let AX be a monotonic HA such that AX = (X, {True, False}, H, >
). A fuzzy interpretation (f-interpretation) I for ALCF L is a pair (∆I , ·I ), where
∆I is a nonempty set and ·I is an interpretation function mapping:
– individuals to elements in ∆I ;
– a concept C into a function C I : ∆I → X;
– a role R into a function RI : ∆I × ∆I → X.
For all d ∈ ∆I the interpretation function satisfies the following equations
⊤I (d) = sup(True),
⊥I (d) = inf(False),
(¬C)I (d) = −C I (d),
(C ⊓ D)I (d) = min(C I (d), DI (d)),
(C ⊔ D)I (d) = max(C I (d), DI (d)),
(δC)I (d) = δ − (C I (d)),
(∀R.C)I (d) = inf d′ ∈∆I {max(−RI (d, d′ ), C I (d′ ))},
(∃R.C)I (d) = supd′ ∈∆I {min(RI (d, d′ ), C I (d′ ))},
where −x is the contradictory element of x, and δ − is the inverse of the hedge
chain δ.
Definition 9. A fuzzy assertion (fassertion) is an expression of the form hα ⊲⊳
σci where α is of the form a : C or (a, b) : R, ⊲⊳ ∈ {≥, >, ≤, <} and σc ∈ X.
Formally, an f-interpretation I satisfies a fuzzy assertion ha : C ≥ σci (re-
spectively h(a, b) : R ≥ σci) iff C I (aI ) ≥ σc (respectively RI (aI , bI ) ≥ σc).
An f-interpretation I satisfies a fuzzy assertion ha : C ≤ σci (respectively
h(a, b) : R ≤ σci) iff C I (aI ) ≤ σc (respectively RI (aI , bI ) ≤ σc). Similarly
for > and <.
Concerning terminological axioms, an ALC F L terminology axiom is of the
form C ⊑ D, where C and D are ALC F L concept terms. From a semantics
point of view, a f-interpretation I satisfies a fuzzy concept inclusion C ⊑ D iff
∀d ∈ ∆I .C I (d) ≤ DI (d). Two concept terms C, D are said to be equivalent,
denoted by C ≡ D iff C I = DI for all f-interpretations I. Some properties
concerning the hedge modification are showed in the following proposition [7].
Proposition 10 We have the following semantical equivalence:
δ(C ⊓ D) ≡ δ(C) ⊓ δ(D)
δ(C ⊔ D) ≡ δ(C) ⊔ δ(D)
δ1 (δ2 C) ≡ (δ1 δ2 )C.
A fuzzy knowledge base (fKB) is hT , Ai, where T and A are finite sets of termi-
nological axioms and fassertions respectively.
Example 11 A fKB fK = h{A ⊑ ∀R.¬B}, {a : ∀R.C ≥ VeryTrue}i.
An f-interpretation I satisfies (is a model of) a TBox T iff I satisfies each
element in T . I satisfies (is a model of) an ABox A iff I satisfies each element
in A. I satisfies (is a model of) a fKB fK = hT , Ai iff I satisfies both A and T .
Given a fKB fK and a fassertion fα. We say that fK entails fα (denoted fK |= fα)
iff each model of fK satisfies fα.
3 Transforming ALCFL into ALCH
We will introduce a satisfiability preserving transformation from ALCF L into
ALCH in this section. First, we illustrate the basic idea which is similar to the
one in [17] which is the first efforts in this direction. There is also other more
efficient representation in [3].
Consider a monotonic HA AX = (X, {True, False}, H, >). In the following,
we assume that c ∈ {c+ , c− } where c+ = True, c− = False, σ ∈ H ∗ , σc ∈
X and ⊲⊳ ∈ {≥, >, ≤, <}. Assume we have an ALCF L knowledge base, fK =
hT , Ai, where A = {fα1 , fα2 , fα3 , fα4 } and fα1 = ha : A ≥ Truei, fα2 = hb :
A ≥ VeryTruei, fα3 = ha : B ≤ Falsei, and fα4 = hb : B ≤ VeryFalsei
where A, B are concept names. We introduce four new concept names: A≥True ,
A≥VeryTrue , B≤False and B≤VeryFalse . The concept name A≥True represents the
set of individuals that are instances of A with degree greater and equal to True.
The concept name B≤VeryFalse represents the set of individuals that are instances
of B with degree less and equal to VeryFalse. We can map the fuzzy assertions
into classical assertions:
ha : A ≥ Truei → ha : A≥True i,
hb : A ≥ VeryTruei → hb : A≥VeryTrue i,
ha : B ≤ Falsei → ha : B≤False i,
hb : B ≤ VeryFalsei → hb : B≤VeryFalse i.
We also need to consider the relationships among the newly introduced concept
names. Because VeryTrue > True, it is easy to get if a truth value σc ≥ VeryTrue
then σc ≥ True. Thus, we obtain a new inclusion A≥VeryTrue ⊑ A≥True . Sim-
ilarly for B, because VeryFalse < False, a truth value σc ≤ VeryFalse implies
σc ≤ False too. Then the inclusion B≤VeryFalse ⊑ B≤False is obtained.
Now, let us proceed with the mappings. Let fK = hT , Ai be an ALC F L
knowledge base. We are going to transform fK into an ALCH knowledge base
K. We assume σc ∈ [inf(False), sup(True)] and ⊲⊳ ∈ {≥, >, ≤, <}.
The transformation of ABox
In order to transform A, we define two mappings θ and ρ to map all the assertions
in A into classical assertions. Notice that we do not allow assertions of the forms
(a, b) : R < σc and (a, b) : R ≤ σc although they are legal forms of assertions
in ALC F L because they related to ‘negated role’ which is not part of classical
ALCH.
We use the mapping ρ to encode the basic idea we present at the beginning
of this section. The mapping ρ combines the ALC F L concept term, the ⊲⊳ and
the fuzzy value σc together into one ALCH concept term.
Let A be a concept name, C, D be concept terms and R be a role name. For
roles we have simply
ρ(R, ⊲⊳ σc) = R⊲⊳σc .
For concept terms, the mapping ρ is inductively defined on the structures of
concept terms:
For ⊤,
⊤ if ⊲⊳ σc = ≥ σc
⊤ if ⊲⊳ σc = > σc, σc < sup(c+ )
⊥ if ⊲⊳ σc = > sup(c+ )
ρ(⊤, ⊲⊳ σc) =
⊤ if ⊲⊳ σc = ≤ sup(c+ )
⊥ if ⊲⊳ σc = ≤ σc, σc < sup(c+ )
⊥ if ⊲⊳ σc = < σc.
For ⊥,
⊤ if ⊲⊳ σc = ≥ inf(c− )
⊥ if ⊲⊳ σc = ≥ σc, σc > inf(c− )
⊥ if ⊲⊳ σc = > σc
ρ(⊥, ⊲⊳ σc) =
⊤ if ⊲⊳ σc = ≤ σc
⊤ if ⊲⊳ σc = < σc, σc > inf(c− )
⊥ if ⊲⊳ σc = < inf(c− ).
For concept name A,
ρ(A, ⊲⊳ σc) = A⊲⊳σc .
For concept conjunction C ⊓ D,
ρ(C, ⊲⊳ σc) ⊓ ρ(D, ⊲⊳ σc) if ⊲⊳ ∈ {≥, >}
ρ(C ⊓ D, ⊲⊳ σc) =
ρ(C, ⊲⊳ σc) ⊔ ρ(D, ⊲⊳ σc) if ⊲⊳ ∈ {≤, <}.
For concept disjunction C ⊔ D,
ρ(C, ⊲⊳ σc) ⊔ ρ(D, ⊲⊳ σc) if ⊲⊳ ∈ {≥, >}
ρ(C ⊔ D, ⊲⊳ σc) =
ρ(C, ⊲⊳ σc) ⊓ ρ(D, ⊲⊳ σc) if ⊲⊳ ∈ {≤, <}.
For concept negation ¬C,
ρ(¬C, ⊲⊳ σc) = ρ(C, ¬ ⊲⊳ σc̄),
where ¬ ≥ = ≤, ¬ > = <, ¬ ≤ = ≥, ¬ < = >.
For modifier concept δC,
ρ(δC, ⊲⊳ σc) = ρ(C, ⊲⊳ σδc).
For existential quantification ∃R.C,
∃ρ(R, ⊲⊳ σc).ρ(C, ⊲⊳ σc) if ⊲⊳ ∈ {≥, >}
ρ(∃R.C, ⊲⊳ σc) =
∀ρ(R, − ⊲⊳ σc).ρ(C, ⊲⊳ σc) if ⊲⊳ ∈ {≤, <},
where − ≤ = > and − < = ≥.
For universal quantification ∀R.C,
∀ρ(R, + ⊲⊳ σc̄).ρ(C, ⊲⊳ σc) if ⊲⊳ ∈ {≥, >}
ρ(∀R.C, ⊲⊳ σc) =
∃ρ(R, ¬ ⊲⊳ σc̄).ρ(C, ⊲⊳ σc) if ⊲⊳ ∈ {≤, <},
where + ≥ = > and + > = ≥.
θ maps fuzzy assertions into classical assertions using ρ. Let fα be a fassertion
in A, we define it as follows.
a : ρ(C, ⊲⊳ σc) if fα = ha : C ⊲⊳ σci
θ(fα) =
(a, b) : ρ(R, ⊲⊳ σc) if fα = h(a, b) : R ⊲⊳ σci.
Example 12 Let fα = ha : V ery(A ⊓ B) ≤ LessF alsei, then
θ(fα) = a : ρ(V ery(A ⊓ B), ≤ LessF alse)
= a : ρ((A ⊓ B), ≤ LessV eryF alse)
= a : ρ(A, ≤ LessV eryF alse) ⊔ ρ(B, ≤ LessV eryF alse)
= a : A≤LessV eryF alse ⊔ B≤LessV eryF alse .
We extend θ to a set of fassertions A point-wise,
θ(A) = {θ(fα) | fα ∈ A}.
According to the rules above, we can see that |θ(A)| is linearly bounded by |A|.
4 The transformation of TBox
The new TBox is a union of two terminologies. One is the newly introduced TBox
(denoted by T (N fK ) which is the terminology relating to the newly introduced
concept names and role names. The other one is κ(fK, T ) which is reduced by a
mapping κ from the TBox of an ALC F L knowledge base.
The newly introduced TBox
Many new concept names and new role names are introduced when we transform
an ABox. We need a set of terminological axioms to define the relationships
among those new names.
We need to collect all the linguist terms σc that might be the subscript of a
concept name or a role name. It means that not only the set of linguistic terms
that appears in the original ABox but also the set of new linguist terms which
are produced by applying the ρ for modifier concepts should be included. Let A
be a concept name, R be a role name.
X fK = {σc | hα ⊲⊳ σci ∈ A} ∪ {σδc | ρ(δC, ⊲⊳ σc) = ρ(C, ⊲⊳ σδc)}.
such that δC occurs in fK.
We define a sorted set of linguistic terms,
N fK = {inf (False), W, sup (True)} ∪ X fK ∪ {σc̄ | σc ∈ X fK } = {n1 , . . . , n|N fK | }
where ni < ni+1 for 1 ≤ i ≤ |N fK | − 1 and n1 = inf (False), n|N fK | = sup (True).
Let T (N fK ) be the set of terminological axioms relating to the newly intro-
duced concept names and role names.
Definition 13. Let AfK and RfK be the sets of concept names and role names
occurring in fK respectively. For each A ∈ AfK , for each R ∈ RfK , for each
1 ≤ i ≤ |N fK | − 1 and for each 2 ≤ j ≤ |N fK |, T (N fK ) contains
A≥ni+1 ⊑A>ni , A>ni ⊑A≥ni ,
Ani ⊓ A≤ni ⊑⊥ , ⊤⊑A>ni ⊔ A≤ni ,
R≥ni+1 ⊑R>ni , R>ni ⊑R≥ni .
where n ∈ N fK .
ni+1 > ni because N fK is a sorted set. Then if an individual is an instance
of a concept name with degree ≥ ni+1 then the degree is also > ni . The first
terminological axiom shows that if an individual is an instance of A≥ni+1 then
it is an instance of A>ni as well. Similarly, if an individual is an instance of
a concept name with degree ≤ ni then the degree is also < ni+1 . The third
terminological axiom shows that if an individual is an instance of A≤ni then it
is also an instance of A}{ρ(C, ⊲⊳ n) ⊑ ρ(D, ⊲⊳ n)}
S (3)
n∈N fK ,⊲⊳∈{≤,<} {ρ(D, ⊲⊳ n) ⊑ ρ(C, ⊲⊳ n)}
We extend κ to a terminology T point-wise. For all τ ∈ T
κ(fK, T ) = ∪τ ∈T κ(fK, τ ).
The satisfiability preserving theorem
Now we can define the reduction of fK into an ALCH knowledge base, denoted
K(fK),
K(fK) = hT (N fK ) ∪ κ(fK, T ), θ(A)i.
The transformation can be done in polynomial time. The soundness and com-
pleteness of the algorithm is guaranteed by the following satisfiability preserving
theorem.
Theorem 15 Let fK be an ALCF L knowledge base. Then fK is satisfiable iff
the ALCH knowledge base K(fK) is satisfiable.
Proof. Please refer to my thesis [18] which can be download from my homepage.2
5 Discussion
In this paper, we have presented a satisfiability preserving transformation of
ALC F L into ALCH which is with general TBox and role hierarchy. Since all
other reasoning tasks such as entailment problem and subsumption problem
can be reduced to satisfiability problem, this result allows for algorithms and
complexity results that were found for ALCH to be applied to ALC F L .
As for the complexity of the transformation, we know the fact that |θ(A)| is
linearly bounded by |A|, |T (N fK )| = 8|AfK |(|N fK | − 1) + 2|RfK |(|N fK | − 1) and
κ(fK, T ) contains at most 4|T ||N fK |. Therefore, the resulted classical knowledge
base (at most polynomial size) can be constructed in polynomial time.
There exist some reasoners for fuzzy DLs, e.g. FiRE [15], GURDL [5], De-
Lorean [2], GERDS [6], YADLR [9] and fuzzyDL [4]. Among them, fuzzyDL
allows modifiers defined in terms of linear hedges and triangular functions and
DeLorean supports triangularly-modified concept. So if we can transform variety
of fuzzy DLs into classical DLs then we can use the already existing DL systems
to do the reasoning of fuzzy DLs.
6 Acknowledgments
Thank Pascal Hiltzler and Martin Caminada for their comments on this paper.
References
1. Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Pe-
ter F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Imple-
mentation, and Applications. Cambridge University Press, 2003.
2. Fernando Bobillo, Miguel Delgado, and Juan Gómez-Romero. Optimizing the crisp
representation of the fuzzy description logic SROIQ. In URSW, 2007.
2
http://icr.uni.lu/ yining
3. Fernando Bobillo, Miguel Delgado, Juan Gómez-Romero, and Umberto Strac-
cia. Fuzzy description logics under gödel semantics. Int. J. Approx. Reasoning,
50(3):494–514, 2009.
4. Fernando Bobillo and Umberto Straccia. fuzzyDL: An expressive fuzzy description
logic reasoner. In 2008 International Conference on Fuzzy Systems (FUZZ-08).
IEEE Computer Society, 2008.
5. Volker Haarslev, Hsueh-Ieng Pai, and Nematollaah Shiri. Optimizing tableau rea-
soning in alc extended with uncertainty. In Description Logics, 2007.
6. Hashim Habiballa. Resolution strategies for fuzzy description logic. In EUSFLAT
Conf. (2), pages 27–36, 2007.
7. Steffen Hölldobler, Dinh-Khac Dzung, and Tran Dinh-Khang. The fuzzy linguistic
description logic ALCF L . In Proceedings of the Eleventh International Conference
on Information Processing and Management of Uncertainty in Knowledge-Based
Systems (IPMU), pages 2096–2103, 2006.
8. Steffen Hölldobler, Hans-Peter Störr, and Dinh Khang Tran. The fuzzy description
logic ALCF H with hedge algebras as concept modifiers. Journal of Advanced Com-
putational Intelligence and Intelligent Informatics (JACIII), 7(3):294–305, 2003.
9. Stasinos Konstantopoulos and Georgios Apostolikas. Fuzzy-dl reasoning over un-
known fuzzy degrees. In OTM Workshops (2), pages 1312–1318, 2007.
10. Thomas Lukasiewicz and Umberto Straccia. Managing uncertainty and vagueness
in description logics for the semantic web. Journal of Web Semantics, 6:291–308,
2008.
11. Cat-Ho Nguyen, Dinh-Khang Tran, Van-Nam Huynh, and Hai-Chau Nguyen.
Hedge algebras, linguistic-valued logic and their application to fuzzy reasoning.
International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems,
7(4):347–361, 1999.
12. Cat-Ho Nguyen and W. Wechler. Hedge algebras: an algebraic approach to struc-
ture of sets of linguistic truth values. Fuzzy Sets and Systems, 35(3):281–293, 1990.
13. Cat-Ho Nguyen and W. Wechler. Extended hegde algebras and their application to
fuzzy logic. International Journal of Uncertainty, Fuzziness and Knowledge-Based
Systems, 52:259–281, 1992.
14. H.-N. Nguyen S. Hölldobler and D.-K. Tran. The fuzzy description logic ALCF LH .
In Proc. 9th IASTED International Conference on Artificial Intelligence and Soft
Computing, pages 99–104, 2005.
15. N. Simou and S. Kollias. Fire : A fuzzy reasoning engine for impecise knowledge.
K-Space PhD Students Workshop, Berlin, Germany, 14 September 2007, 2007.
16. Umberto Straccia. Reasoning within fuzzy description logics. JAIR, 14:137–166,
2001.
17. Umberto Straccia. Transforming fuzzy description logics into classical description
logics. In Proceedings of the 9th European Conference on Logics in Artificial In-
telligence (JELIA-04), number 3229 in Lecture Notes in Computer Science, pages
385–399, Lisbon, Portugal, 2004. Springer Verlag.
18. Yining Wu. Transforming fuzzy description logic ALCF L into classical description
logic ALCH. Master Thesis, 2007.
19. Lotfi A. Zadeh. The concept of a linguistic variable and its application to approx-
imate reasoning - I. Information Sciences, 8(3):199–249, 1975.
20. Lotfi A. Zadeh. The concept of a linguistic variable and its application to approx-
imate reasoning - II. Information Sciences, 8(4):301–357, 1975.
21. Lotfi A. Zadeh. The concept of a linguistic variable and its application to approx-
imate reasoning- III. Information Sciences, 9(1):43–80, 1975.