Introduction

The Semantic Web is a vision for the future of the Web in which information is given explicit meaning, making it easier for machines to automatically process and integrate information available on the Web. While as a basic component 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 increasingly 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][20][21]. Adverbs as "Very", "More or Less" and "Possibly" 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 service. 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 certainty lattice characterized by a hedge algebra and allows the modification by hedges. Because the certainty lattice is characterized by a HA, the modification by hedges becomes more natural than that in ALC F H [8] and ALC F 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.

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. 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 A I ⊆ ∆ I and to each role name R a binary relation R I ⊆ ∆ I × ∆ I . The interpretation of complex concept terms is extended by the following inductive definitions: We have seen how we can form complex descriptions of concepts to describe classes of objects. Now, we introduce terminological axioms, which make statements about how concept terms and roles are related to each other respectively.

⊤ I = ∆ I ⊥ I = ∅ (C ⊓ D) I = C I ∩ D I (C ⊔ D) I = C I ∪ D I (¬C) I = ∆ I \ C I (∀R.C) I = {d ∈ ∆ I | ∀d ′ .(d, d ′ ) / ∈ R I or d ′ ∈ C I } (∃R.C) I = {d ∈ ∆ I | ∃d ′ .(d, d ′ ) ∈ R I and d ′ ∈ C I } A concept term C is satisfiable iff

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 ⊆ D I (R I ⊆ S I ), denoted by I |= C ⊑ D (I |= R ⊑ S).

A terminology, i.e., TBox, is a finite set of terminological axioms. A knowledge base is of the form T , A 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 = T , A 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 ⊆ D I .

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 meaning 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 using 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 algebraic 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 = 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.(A4) If h = 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 = h n • • • h 1 u and y = k m • • • k 1 u are two elements of X where u ∈ X.

Then there exists an index j ≤ min{n, m} + 1 such that h i = k i for all i < j, and

(i) x < y iff h j x j < k j x j , where x j = h j−1 • • • h 1 u;

(ii) x = y iff n = m = j and h j x j = k j x j .

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][20][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 c 1 > σ 2 c 2 ⇔ h − (σ 1 c 1 ) > h − (σ 2 c 2 ).

where c, c 1 , c 2 ∈ 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 elements 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 ALC F 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 R I : ∆ 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), D I (d)), (C ⊔ D) I (d) = max(C I (d), D I (d)), (δC) I (d) = δ − (C I (d)), (∀R.C) I (d) = inf d ′ ∈∆ I {max(−R I (d, d ′ ), C I (d ′ ))}, (∃R.C) I (d) = sup d ′ ∈∆ I {min(R I (d, d ′ ), C I (d ′ ))},

where −x is the contradictory element of x, and δ − is the inverse of the hedge chain δ.

δ(C ⊓ D) ≡ δ(C) ⊓ δ(D) δ(C ⊔ D) ≡ δ(C) ⊔ δ(D) δ 1 (δ 2 C) ≡ (δ 1 δ 2 )C.

A fuzzy knowledge base (fKB) is T , A , where T and A are finite sets of terminological axioms and fassertions respectively.

Transforming ALC FL into ALCH

We will introduce a satisfiability preserving transformation from ALC F 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 ALC F L knowledge base, fK = T , A , where A = {fα 1 , fα 2 , fα 3 , fα 4 } and fα 1 = a : A ≥ True , fα 2 = b : A ≥ VeryTrue , fα 3 = a : B ≤ False , and fα 4 = b : B ≤ VeryFalse 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:

a : A ≥ True → a : A ≥True , b : A ≥ VeryTrue → b : A ≥VeryTrue , a : B ≤ False → a : B ≤False , b : B ≤ VeryFalse → b : B ≤VeryFalse .

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 . Similarly 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 = T , A 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 ⊤, We extend θ to a set of fassertions A point-wise,

ρ(⊤, ⊲⊳ σc) =                ⊤ if ⊲⊳ σc = ≥ σc ⊤ if ⊲⊳ σc = > σc, σc < sup(c + ) ⊥ if ⊲⊳ σc = > sup(c + ) ⊤ if ⊲⊳ σc = ≤ sup(c + ) ⊥ if ⊲⊳ σc = ≤ σc, σc < sup(c + ) ⊥ if ⊲⊳ σc = < σc. For ⊥, ρ(⊥, ⊲⊳ σc) =                ⊤ if ⊲⊳ σc = ≥ inf(c − ) ⊥ if ⊲⊳ σc = ≥ σc, σc > inf(c − ) ⊥ if ⊲⊳ σc = > σc ⊤ if ⊲⊳ σc = ≤ σc ⊤ if ⊲⊳ σc = < σc, σc > inf(c − ) ⊥ if ⊲⊳ σc = < inf(c − ).θ(A) = {θ(fα) | fα ∈ A}.

According to the rules above, we can see that |θ(A)| is linearly bounded by |A|.

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 | α ⊲⊳ σc ∈ 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 } = {n 1 , . . . , n |N fK | } where n i < n i+1 for 1 ≤ i ≤ |N fK | − 1 and n 1 = inf (False), n |N fK | = sup (True).

Let T (N fK ) be the set of terminological axioms relating to the newly introduced concept names and role names. Definition 13. Let A fK and R fK be the sets of concept names and role names occurring in fK respectively. For each A ∈ A fK , for each R ∈ R fK , 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 , A <nj ⊑A ≤nj , A ≤ni ⊑A <ni+1 , A ≥nj ⊓ A <nj ⊑⊥ , ⊤⊑A ≥nj ⊔ A <nj , A >ni ⊓ A ≤ni ⊑⊥ , ⊤⊑A >ni ⊔ A ≤ni , R ≥ni+1 ⊑R >ni , R >ni ⊑R ≥ni .

where n ∈ N fK . n i+1 > n i because N fK is a sorted set. Then if an individual is an instance of a concept name with degree ≥ n i+1 then the degree is also > n i . 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 ≤ n i then the degree is also < n i+1 . The third terminological axiom shows that if an individual is an instance of A ≤ni then it is also an instance of A <ni+1 . A ≥nj ⊓ A <nj ⊑ ⊥ because there is no individual such that it is an instance of a concept name with degree ≥ n j and with degree < n j at the same time.

T 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) = T (N fK ) ∪ κ(fK, T ), θ(A) .

The transformation can be done in polynomial time. The soundness and completeness of the algorithm is guaranteed by the following satisfiability preserving theorem.

Theorem 15 Let fK be an ALC F 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

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 |θ 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.