9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # AN OVERVIEW OF UNCERTAINTY AND VAGUENESS IN DESCRIPTION LOGICS FOR THE SEMANTIC WEB

I N F S Y S R R

E S E A R C H E P O R T

¨ I NSTITUT F UR I NFORMATIONSSYSTEME

A RBEITSBEREICH W ISSENSBASIERTE S YSTEME

A N OVERVIEW OF U NCERTAINTY AND VAGUENESS IN D ESCRIPTION L OGICS FOR THE S EMANTIC W EB

T HOMAS L UKASIEWICZ and U MBERTO S TRACCIA

INFSYS R ESEARCH R EPORT 1843-06-07 O CTOBER 2006

Institut fur Informationssysteme ¨ AB Wissensbasierte Systeme ¨ Technische Universitat Wien Favoritenstra?e 9-11 A-1040 Wien, Austria Tel: Fax: +43-1-58801-18405 +43-1-58801-18493

sek@kr.tuwien.ac.at www.kr.tuwien.ac.at

INFSYS R ESEARCH R EPORT

INFSYS R ESEARCH R EPORT 1843-06-07, O CTOBER 2006

A N OVERVIEW OF U NCERTAINTY AND VAGUENESS IN D ESCRIPTION L OGICS FOR THE S EMANTIC W EB

O CTOBER 25, 2006

Thomas Lukasiewicz 1

Umberto Straccia 2

Abstract. Ontologies play a crucial role in the development of the Semantic Web as a means for de?ning shared terms in Web resources. They are formulated in web ontology languages, which are based on expressive description logics. Signi?cant research efforts are recently directed towards representing and reasoning with uncertainty and vagueness in ontologies for the Semantic Web. In this paper, we give an overview of probabilistic uncertainty, possibilistic uncertainty, and vagueness in expressive description logics for the Semantic Web.

Dipartimento di Informatica e Sistemistica, Universit` di Roma “La Sapienza”, Via Salaria 113, I-00198 Rome, a Italy; e-mail: lukasiewicz@dis.uniroma1.it. Institut f¨ r Informationssysteme, Technische Universit¨ t Wien, Favoritenu a stra?e 9-11, A-1040 Vienna, Austria; e-mail: lukasiewicz@kr.tuwien.ac.at. 2 ISTI-CNR, Via G. Moruzzi 1, I-56124 Pisa, Italy; e-mail: straccia@isti.cnr.it. Acknowledgements: This work has been partially supported by a Heisenberg Professorship of the German Research Foundation (DFG). Copyright c 2006 by the authors

1

INFSYS RR 1843-06-07

I

Contents

1 Introduction 2 Uncertainty and Vagueness 2.1 Probabilistic Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Possibilistic Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Many-Valued Logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Classical Description Logics 3.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Probabilistic Uncertainty and Description Logics 4.1 Syntax . . . . . . . . . . . . . . . . . . . . . . 4.2 Semantics . . . . . . . . . . . . . . . . . . . . 4.2.1 Preliminaries . . . . . . . . . . . . . . 4.2.2 Consistency . . . . . . . . . . . . . . . 4.2.3 Lexicographic Entailment . . . . . . . 4.3 Related Work . . . . . . . . . . . . . . . . . . 4.3.1 Probabilistic Description Logics . . . . 4.3.2 Probabilistic Web Ontology Languages 4.3.3 Applications in Information Retrieval . 1 2 2 3 4 7 7 8 9 10 11 11 12 13 14 14 15 15

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

5 Possibilistic Uncertainty and Description Logics 16 5.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.2 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 6 Vagueness and Description Logics 6.1 Syntax . . . . . . . . . . . . . . 6.1.1 Fuzzy Datatype Theories 6.1.2 Fuzzy Modi?ers . . . . 6.1.3 Fuzzy Knowledge Bases 6.2 Semantics . . . . . . . . . . . . 6.2.1 Fuzzy Interpretations . . 6.2.2 Best Truth Value Bound 6.3 Related Work . . . . . . . . . . 7 Conclusions 17 17 17 18 18 19 19 22 23 25

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

INFSYS RR 1843-06-07

1

1 Introduction

The Semantic Web [3, 4, 25, 49] has recently attracted much attention, both from academia and industry, and is widely regarded as the next step in the evolution of the World Wide Web. It aims at an extension of the current Web by standards and technologies that help machines to understand the information on the Web so that they can support richer discovery, data integration, navigation, and automation of tasks. The main ideas behind it are to add a machine-readable meaning to web pages, to use ontologies for a precise de?nition of shared terms in web resources, to use KR technology for automated reasoning from web resources, and to apply cooperative agent technology for processing the information of the Web. The development of the Semantic Web proceeds in several hierarchical layers, where the Ontology layer, in form of the OWL Web Ontology Language [49, 120] (recommended by the W3C), is currently the highest layer of suf?cient maturity. OWL consists of three increasingly expressive sublanguages, namely OWL Lite, OWL DL, and OWL Full. Hence, ontologies [29] play a key role in the Semantic Web, and a major effort has been put by the Semantic Web community into this issue. Informally, an ontology consists of a hierarchical description of important and precisely de?ned concepts in a particular domain, along with the description of the properties (of the instances) of each concept. Web content is then annotated by relying on the concepts de?ned in a speci?c domain ontology. OWL Lite and OWL DL are essentially very expressive description logics with an RDF syntax [49]. As shown in [48], ontology entailment in OWL Lite and OWL DL reduces to knowledge base (un)satis?ability in the expressive description logics SHIF(D) and SHOIN (D), respectively. Hence, these expressive description logics play an important role in the Semantic Web, since they are essentially the theoretical counterparts of OWL Lite and OWL DL, respectively. More generally, description logics are a logical reconstruction of frame-based knowledge representation languages, with the aim of providing a decidable ?rst-order formalism with a simple well-established declarative semantics to capture the meaning of the most popular features of structured representation of knowledge. However, classical ontology languages and description logics are less suitable in all those domains where the information to be represented is imperfect, that is, either uncertain, or vague/imprecise, or both. In particular, web content is very likely to be imperfect, and thus there is a strong need to deal with imperfect knowledge in the Semantic Web. This need to deal with uncertainty and vagueness in ontologies for the Semantic Web has been recognized by a large number of research efforts in this direction. In particular, dealing with uncertainty and vagueness in ontologies has been successfully applied in ontology mapping and information retrieval. Due to the rising popularity of description logics and their use, the emergence of dealing with uncertain and vague information is increasingly attracting the attention of many researcher and practitioners towards description logics able to cope with this lack of expressive power. The goal of this paper is to provide an overview of the current state of the art about the management of uncertainty and vagueness in description logics for the Semantic Web, which should help the reader to get insights on main features of the formalisms proposed in the literature. The rest of this paper is organized as follows. In Section 2, we give a brief introduction to uncertainty and vagueness at the propositional level. In Section 3, we describe the classical description logic SHOIN (D), which is the reference language in this paper. Sections 4 and 5 show how to extend classical description logics by probabilistic and possibilistic uncertainty, respectively, while Section 6 describes how to extend classical description logics for the management of vague/imprecise knowledge. In Section 7, we give a summary and an outlook on open research.

2

INFSYS RR 1843-06-07

2 Uncertainty and Vagueness

There has been a long-lasting misunderstanding in the literature of arti?cial intelligence and uncertainty modeling, regarding the role of probability/possibility theory and fuzzy/many-valued theory. A clarifying paper is [19]. We recall here salient notes, which may clarify the role of these theories for the inexpert reader. A standard example that points out the difference between degrees of uncertainty and degrees of truth is that of a bottle [19]. In terms of binary truth values, a bottle is viewed as full or empty. If one accounts for the quantity of liquid in the bottle, one may say the bottle is “half-full” for instance. Under this way of speaking, “full” becomes a fuzzy predicate [125] and the degree of truth of “the bottle is full” re?ects the amount of liquid in the bottle. The situation is quite different when expressing our ignorance about whether the bottle is either full or empty (given that we know only one of the two situations is the true one). To say that the probability that the bottle is full is 0.5 does not mean that the bottle is half full. We recall that under uncertainty theory fall all those approaches in which statements rather than being either true or false, are true or false to some probability or possibility/necessity (for instance, “it will rain tomorrow”). That is, a statement is true or false in any world, but we are “uncertain” about which world to consider as the right one, and, thus, we speak e.g. about a probability distribution or a possibility distribution over the worlds. For instance, we cannot exactly establish whether it will rain tomorrow or not, due to our incomplete knowledge about our world, but we can estimate to which degree this is probable, possible, and necessary. On the other hand, under vagueness/imprecision theory fall all those approaches in which statements (for instance, “the tomato is ripe”) are true to some degree, which is taken from a truth space. That is, an interpretation maps a statement to a truth degree, as we are unable to establish whether a statement is completely true or false due to the involvement of vague concepts, such as “ripe”, which do not have a precise de?nition. For instance, we cannot exactly say whether a tomato is ripe or not, but rather just can say that the tomato is ripe to some degree. Usually, such statements involve so-called vague/fuzzy predicates [125]. Note that vague statements are truth-functional, i.e., the degree of truth of a statement can be calculated from the degrees of truth of its constituents, while uncertain statements cannot be a function of the uncertainties of its constituents [18]. In the following, we illustrate a typical formalization of uncertain statements and vague statements. In the former case, we consider a basic probabilistic/possibilistic logic, while in the latter, we consider a basic many-valued logic.

2.1

Probabilistic Logic

Probabilistic logic has its origin in philosophy and logic. Its roots can be traced back to already Boole in 1854 [6]. There is a wide spectrum of formal languages that have been explored in probabilistic logic, ranging from constraints for unconditional and conditional events to rich languages that specify linear inequalities over events (see especially the work by Nilsson [85], Fagin et al. [24], Dubois and Prade et al. [17, 21, 1, 20], Frisch and Haddawy [26], and the ?rst author [65, 66, 68]; see also the survey on sentential probability logic by Hailperin [33]). Recently, nonmonotonic generalizations of probabilistic logic have been developed and explored; see especially [70] for an overview. In this section, for illustrative purposes, we recall only the simple probabilistic logic described in [85]. We ?rst de?ne probabilistic formulas and probabilistic knowledge bases. We assume a set of basic events Φ = {p1 , . . . , pn } with n 1. We use ⊥ and ? to denote false and true, respectively. We de?ne

INFSYS RR 1843-06-07

3

events by induction as follows. Every element of Φ ∪ {⊥, ?} is an event. If φ and ψ are events, then also ?φ, (φ ∧ ψ), (φ ∨ ψ), and (φ → ψ) are events. We adopt the usual conventions to eliminate parentheses. A probabilistic formula is an expression of the form (φ l), where φ is an event, and l is a real number from the unit interval [0, 1]. Informally, (φ l) says that φ is true with a probability of at least l. For example, (rain tomorrow 0.7) may express that it will rain tomorrow with a probability of at least 0.7. Notice also that (?φ 1 ? u) encodes that φ is true with a probability of at most u. A probabilistic knowledge base K is a ?nite set of probabilistic formulas. We next de?ne worlds and probabilistic interpretations. A world I associates with every basic event in Φ a binary truth value. We extend I by induction to all events as usual. We denote by IΦ the (?nite) set of all worlds for Φ. A world I satis?es an event φ, or I is a model of φ, denoted I |= φ, iff I(φ) = true. A probabilistic interpretation Pr is a probability function on IΦ (that is, a mapping Pr : IΦ → [0, 1] such that all Pr (I) with I ∈ IΦ sum up to 1). Intuitively, Pr (I) is the degree to which the world I ∈ IΦ is probable, i.e., the probability function Pr encodes our “uncertainty” about which world is the right one. The probability of an event φ in Pr , denoted Pr (φ), is the sum of all Pr (I) such that I ∈ IΦ and I |= φ. The following theorem is an immediate consequence of the above de?nitions. Theorem 2.1 For all probabilistic interpretations Pr and events φ and ψ: Pr (φ ∧ ψ) Pr (φ ∧ ψ) Pr (φ ∧ ψ) Pr (φ ∨ ψ) Pr (φ ∨ ψ) Pr (φ ∨ ψ) Pr (?φ) Pr (⊥) Pr (?) = Pr (φ) + Pr (ψ) ? Pr (φ ∨ ψ) min(Pr (φ), Pr (ψ)) max(0, Pr (φ) + Pr (ψ) ? 1) = Pr (φ) + Pr (ψ) ? Pr (φ ∧ ψ) min(1, Pr (φ) + Pr (ψ)) max(Pr (φ), Pr (ψ)) = 1 ? Pr (φ) = 0 = 1

(1)

A probabilistic interpretation Pr satis?es a probabilistic formula (φ l), or Pr is a model of (φ l), denoted Pr |= (φ l), iff Pr (φ) l. We say Pr satis?es a probabilistic knowledge base K, or Pr is a model of K, iff Pr satis?es all F ∈ K. We say K is satis?able iff a model of K exists. A probabilistic formula F is a logical consequence of K, denoted K |= F , iff every model of K satis?es F . We say (φ l) is a tight logical consequence of K iff l is the in?mum of Pr (φ) subject to all models Pr of K. Notice that the latter is equivalent to l = sup{r | K |= (φ r)}. The main decision and optimization problems in probabilistic logic are deciding the satis?ability of probabilistic knowledge bases and logical consequences from probabilistic knowledge bases, as well as computing tight logical consequences from probabilistic knowledge bases, which can be done by deciding the solvability of a system of linear inequalities and by solving a linear optimization problem, respectively. In particular, column generation techniques from operations research have been successfully used to solve large problem instances in probabilistic logic (see especially the work by Jaumard et al. [53] and Hansen et al. [37]).

2.2

Possibilistic Logic

We next recall possibilistic logic; see especially [15]. We ?rst de?ne possibilistic formulas and possibilistic knowledge bases. Possibilistic formulas have the form (φ, P l) or (φ, N l), where φ is an event, and l is

4

INFSYS RR 1843-06-07

a real number from [0, 1]. Informally, such formulas encode to what extent φ is possibly resp. necessarily true. For example, (rain tomorrow , P 0.7) encodes that it will rain tomorrow is possible to degree 0.7, while (father → man, N 1) says that a father is necessarily a man. A possibilistic knowledge base K is a ?nite set of possibilistic formulas. A possibilistic interpretation is a mapping π : IΦ → [0, 1]. Intuitively, π(I) is the degree to which the world I is possible. In particular, every world I such that π(I) = 0 is impossible, while every world I such that π(I) = 1 is totally possible. We say π is normalized iff π(I) = 1 for some I ∈ IΦ . Intuitively, this guarantees that there exists at least one world, which could be considered as the real one. The possibility of an event φ in a possibilistic interpretation π, denoted P oss(φ), is then de?ned by P oss(φ) = max {π(I) | I ∈ IΦ , I |= φ} (where max ? = 0). Intuitively, the possibility of φ is evaluated in the most possible world where φ is true. The dual notion to the possibility of an event φ is the necessity of φ, denoted N ec(φ), which is de?ned by N ec(φ) = 1 ? P oss(?φ). It re?ects the lack of possibility of ?φ, i.e., N ec(φ) evaluates to what extent φ is certainly true. The following theorem follows immediately from the above de?nitions. Theorem 2.2 For all possibilistic interpretations π and events φ and ψ: P oss(φ ∧ ψ) P oss(φ ∨ ψ) P oss(?φ) P oss(⊥) P oss(?) N ec(φ ∧ ψ) N ec(φ ∨ ψ) N ec(?φ) N ec(⊥) N ec(?) = = = = min(P oss(φ), P oss(ψ)) max(P oss(φ), P oss(ψ)) 1 ? N ec(φ) 0 1 (in the normalized case) (2) = min(N ec(φ), N ec(ψ)) max(N ec(φ), N ec(ψ)) = 1 ? P oss(φ) = 0 (in the normalized case) = 1

A possibilistic interpretation π satis?es a possibilistic formula (φ, P l) (resp., (φ, N l)), or π is a model of (φ, P l) (resp., (φ, N l)), denoted π |= (φ, P l) (resp., π |= (φ, N l)) iff P oss(φ) l (resp., N ec(φ) l). The notions of satis?ability, logical consequence, and tight logical consequence for possibilistic knowledge bases are then de?ned in the standard way (in the same way as in the probabilistic case). We refer the reader to [15, 45] for algorithms around possibilistic knowledge bases.

2.3

Many-Valued Logics

In the setting of many-valued logics, the convention prescribing that a proposition is either true or false is changed. A more re?ned range is used for the function that represents the meaning of a proposition. This is usual in natural language when words are modeled by fuzzy sets. For instance, the compatibility of “tall” in the phrase “a tall man” with some individual of a given height is often graded: The man can be judged not quite tall, somewhat tall, rather tall, very tall, etc. Changing the usual true/false convention leads to a new concept of proposition whose compatibility with a given state of facts is a matter of degree, and can be measured on an ordered scale S that is no longer {0, 1}, but e.g. the unit interval [0, 1]. This leads to identifying a “fuzzy proposition” φ with a fuzzy set of possible states of affairs; the degree of membership of a state of affairs to this fuzzy set evaluates the degree of ?t between the proposition and the state of facts

INFSYS RR 1843-06-07

5

Table 1: Properties of t-norms, s-norms, implication functions, and negation functions. properties of t-norms “∧” a∧1=a b c implies a ∧ b a ∧ c a∧b=b∧a a ∧ (b ∧ c) = (a ∧ b) ∧ c properties of implication functions “→” a b implies a → c b → c b c implies a → b a → c 0→b=1 a→1=1 properties of s-norms “∨” a∨0=a b c implies a ∨ b a ∨ c a∨b=b∨a a ∨ (b ∨ c) = (a ∨ b) ∨ c properties of negation functions “?” ?0 = 1 a b implies ?b ?a

it refers to. This degree of ?t is called degree of truth of the proposition φ in the interpretation I (state of affairs). Many-valued logics provide compositional calculi of degrees of truth, including degrees between “true” and “false”. A sentence is now not true or false only, but may have a truth degree taken from a truth 0 1 space S, usually [0, 1] or { n , n , . . . , n } for an integer n 1. In the sequel, we assume S = [0, 1]. n In the many-valued logic that we consider here, many-valued formulas have the form (φ l), where l ∈ [0, 1] [32, 34] (informally, the degree of truth of φ is at least l). For instance, (ripe tomato 0.9) says that we have a rather ripe tomato (the degree of truth of ripe tomato is at least 0.9). From the semantical point of view, a many-valued interpretation I maps each basic proposition pi into [0, 1] and is then extended inductively to all propositions by: I(φ ∧ ψ) I(φ ∨ ψ) I(φ → ψ) I(?φ) = = = = t(I(φ), I(ψ)) s(I(φ), I(ψ)) i(I(φ), I(ψ)) n(I(φ)) ,

(3)

where t, s, i, and n are so-called t-norms, s-norms, implication functions, and negation functions, respectively, which extend classical Boolean conjunction, disjunction, implication, and negation, respectively, to the many-valued case. Several t-norms, s-norms, implication functions, and negation functions have been given in the literature to interpret conjunction (∧), disjunction (∨), negation (?) and implication (→), respectively. An important aspect of such functions is that they satisfy some properties that one expects to hold for the connectives; see Table 1. Usually, → is de?ned as r-implication, that is, a → b = sup {c | a ∧ c b}. Some t-norms, s-norms, implication functions, and negation functions of various fuzzy logics are shown in Table 2. In fuzzy logic, one usually distinguishes three different logics, namely, ?ukasiewicz, G¨ del, and o Product logic; the popular Zadeh logic is a sublogic of ?ukasiewicz logic. Some salient properties of these logics are shown in Table 3. For more properties, see especially [34, 87]. The implication x → y = max(1?x, y) is called Kleene-Dienes implication in the fuzzy logic literature. Note that we have the following inferences: Let a n and a → b m. Then, under Kleene-Dienes implication, we infer that if n > 1 ? m then b m. Under r-implication relative to a t-norm ∧, we infer that b n ∧ m.

6

INFSYS RR 1843-06-07

Table 2: T-norms, s-norms, implication functions, and negation functions of various fuzzy logics. ?ukasiewicz logic max(x + y ? 1, 0) min(x + y, 1) 1 if x y 1 ? x + y otherwise 1?x G¨ del logic o min(x, y) max(x, y) 1 if x y y otherwise 1 if x = 0 0 otherwise Product logic x·y x+y?x·y 1 if x y y/x otherwise 1 if x = 0 0 otherwise Zadeh logic min(x, y) max(x, y) max(1 ? x, y) 1?x

x∧y x∨y x→y ?x

Table 3: Some additional properties of t-norms, s-norms, implication functions, and negation functions of various fuzzy logics.

?ukasiewicz logic x ∧ ?x = 0 x ∨ ?x = 1 ?x. x ∧ x = x ?x. x ∨ x = x ??x = x x → y = ?x ∨ y ?(x → y) = x ∧ ?y ?(x ∧ y) = ?x ∨ ?y ?(x ∨ y) = ?x ∧ ?y G¨ del logic o ?x. x ∧ ?x = 0 ?x. x ∨ ?x = 1 x∧x=x x∨x=x ?x. ??x = x ?x. x → y = ?x ∨ y ?x. ?(x→y) = x∧?y ?(x ∧ y) = ?x ∨ ?y ?(x ∨ y) = ?x ∧ ?y Product logic ?x. x ∧ ?x = 0 ?x. x ∨ ?x = 1 ?x. x ∧ x = x ?x. x ∨ x = x ?x. ??x = x ?x. x → y = ?x ∨ y ?x. ?(x→y) = x∧?y ?(x ∧ y) = ?x ∨ ?y ?(x ∨ y) = ?x ∧ ?y Zadeh logic ?x. x ∧ ?x = 0 ?x. x ∨ ?x = 1 x∧x=x x∨x=x ??x = x x → y = ?x ∨ y ?(x→y) = x∧?y ?(x∧y) = ?x∨?y ?(x∨y) = ?x∧?y

INFSYS RR 1843-06-07

7

The degree of subsumption between two fuzzy sets A and B, denoted A → B, is de?ned as inf x∈X A(x) → B(x), where → is an implication function. Note that if A(x) B(x), for all x ∈ [0, 1], then A → B evaluates to 1. Of course, A → B may evaluate to a value v ∈ (0, 1) as well. A (binary) fuzzy relation R over two countable crisp sets X and Y is a function R : X × Y → [0, 1]. The inverse of R is the function R?1 : Y × X → [0, 1] with membership function R?1 (y, x) = R(x, y), for every x ∈ X and y ∈ Y . The composition of two fuzzy relations R1 : X × Y → [0, 1] and R2 : Y × Z → [0, 1] is de?ned as (R1 ? R2 )(x, z) = supy∈Y R1 (x, y) ∧ R2 (y, z). A fuzzy relation R is transitive iff R(x, z) = (R ? R)(x, z). A many-valued interpretation I satis?es a many-valued formula (φ l) or I is a model of (φ l), denoted I |= (φ l), iff I(φ) l. Note that (?φ ?u) says that the degree of truth of φ is at most u (when ??x = x). The notions of satis?ability, logical consequence, and tight logical consequence for many-valued knowledge bases are then de?ned in the standard way (as in the probabilistic case). We refer the reader to [31, 32, 34] for algorithms deciding logical consequence.

3 Classical Description Logics

In this section, we recall the expressive description logic SHOIN (D), which stands behind the web ontology languages OWL DL [49]. Although several XML and RDF syntaxes for OWL-DL exist, in this paper, we use the traditional description logic notation. For explicating the relationship between OWL DL syntax and description logic syntax, see especially [47, 49]. The purpose of this section is to make the paper self-contained. More importantly, it helps in understanding the differences between classical, probabilistic, possibilistic, and fuzzy SHOIN (D). The reader con?dent with the SHOIN (D) terminology may skip this section.

3.1

Syntax

The description logic SHOIN (D) is a generalization of SHOIN by concrete datatypes, such as strings and integers, using concrete domains [2, 73, 72, 74]. The elementary ingredients are as follows. We assume a set of data values, a set of elementary datatypes, and a set of datatype predicates, each with a prede?ned arity n 1. A datatype is an elementary datatype or a ?nite set of data values. A datatype theory D = (?D , · D ) consists of a datatype domain ?D and a mapping · D that assigns to each data value an element of ?D , to each elementary datatype a subset of ?D , and to each datatype predicate of arity n a relation over ?D of arity n. We extend · D to all datatypes D by {v1 , . . .}D = {v1 , . . .}. For example, over the integers, 20 may be a unary predicate denoting the set of integers greater or equal to 20, and thus Person ? ?age. 20 may denote a person whose age is at least 20. Let A, RA , RC , and I be pairwise disjoint nonempty ?nite sets of atomic concepts, abstract roles, concrete roles, and individuals, respectively. A role is either an abstract role R ∈ RA , the inverse R? of an abstract role R ∈ RA , or a concrete role U ∈ RC (note that concrete roles do not have inverses). An RBox R consists of a ?nite set of transitivity axioms trans(R) and role inclusion axioms of the form R ? S, where either R, S ∈ RA or R, S ∈ RC . The re?exive and transitive closure of the role inclusion relationships in RBox is denoted by ?? . A role not having transitive subroles is a simple role. Concepts are de?ned by induction, using the following syntactic rules, where A is an atomic concept, a1 , . . . , an are individuals, C, C1 , and C2 are concepts, R is an abstract role, S is a simple abstract role,

8

INFSYS RR 1843-06-07

T, T1 , . . . , Tn are concrete roles, D is an n-ary datatype predicate, and n C ?→ ? | ⊥ | A | {a1 , . . . , an } | C1 ? C2 | C1 ? C2 | ?C | ?R.C | ?R.C | ( n S) | ( n S) | ?T1 , . . . , Tn .D | ?T1 , . . . , Tn .D | ( n T ) | ( n T ) For example, we may write the concept Flower ? ?hasPetalWidth.(

20mm

0:

?

40mm )

? ?hasColor .Red

to informally denote the set of ?owers having petal’s dimension within 20mm and 40mm, whose color is red. Here, 20mm and 40mm are datatype predicates. We use (= 1 S) to abbreviate ( 1 S) ? ( 1 S). A TBox T is a ?nite set of concept inclusion axioms C ? D, where C and D are concepts. We often use C = D ∈ T in place of {C ? D, D ? C} ? T . A simple abstract role S is functional if the interpretation of the role S (see below) is always functional. A functional role S can always be obtained from an abstract role by means of the axiom ? ? ( 1 S). Therefore, whenever we say that a role is functional, we assume that ? ? ( 1 S) is in the TBox. An ABox A is a ?nite set of concept assertion axioms a : C, role assertion axioms (a, b) : R, and individual equality (resp., inequality) axioms a ≈ b (resp., a ≈ b). A knowledge base K = (T , R, A) consists of a TBox T , an RBox R, and an ABox A.

3.2

Semantics

An interpretation I = (?I , ·I ) relative to a datatype theory D = (?D , · D ) consists of a nonempty abstract domain ?I , disjoint from ?D , and an interpretation function ·I that assigns to each a ∈ I an element in ?I , to each C ∈ A a subset of ?I , to each R ∈ RA a subset of ?I × ?I , to each T ∈ RC a subset of ?I × ?D , and to every data value, datatype, and datatype predicate the same value as · D . The mapping ·I is extended to all roles and concepts as usual: (S ? ) ?I ⊥I {a1 , . . . , an }I (C1 ? C2 )I (C1 ? C2 )I (?C)I (?R.C)I (?R.C)I ( n S)I ( n S)I

I

= = = = = = = = = = =

{(y, x) | (x, y) ∈ S I } ?I ? {a1 I , . . . , an I } C1 I ∩ C2 I C1 I ∪ C2 I ?I \ C I {x ∈ ?I : RI (x) ? C I } {x ∈ ?I : RI (x) ∩ C I = ?} {x ∈ ?I : #S I (x) n} {x ∈ ?I : #S I (x) n}

and similarly for the other constructs, where RI (x) = {y | (x, y) ∈ RI } and #X denotes the cardinality of the set X. In particular, (?T1 , . . . , Tn .d)I = {x ∈ ?I : [T1 I (x) × . . . × Tn I (x)] ∩ dI = ?} . The satisfaction of an axiom E in an interpretation I = (?I , ·I ), denoted I |= E, is de?ned as follows: I |= C ? D iff C I ? DI , I |= R ? S iff RI ? S I , I |= T ? U iff T I ? U I , I |= trans(R) iff RI

INFSYS RR 1843-06-07

9

is transitive, I |= a : C iff aI ∈ C I , I |= (a, b) : R iff (aI , bI ) ∈ RI , I |= (a, c) : T iff (aI , cI ) ∈ T I , I |= a ≈ b iff aI = bI , I |= a ≈ b iff aI = bI . We say a concept C is satis?able iff there is an interpretation I such that C I = ?. For a set of axioms E, we say I satis?es E iff I satis?es each element in E. We say I is a model of E (resp., E) iff I |= E (resp., I |= E). I satis?es (is a model of) a knowledge base K = (T , R, A), denoted I |= K, iff I is a model of each component T , R, and A. An axiom E is a logical consequence of a knowledge base K, denoted K |= E, iff every model of K satis?es E. According to [47], the entailment, subsumption and the concept satis?ability problem can be reduced to knowledge base satis?ability problem (e.g., (T , R, A) |= a : C iff (T , R, A ∪ {a : ?C}) unsatis?able, also, C is satis?able iff {a : C} is satis?able), for which decision procedures and reasoning tools exists (e.g., RACER [30], FACT [46], and Pellet [89]). Example 3.1 (Car Example) Let us consider the following excerpt of a simple ontology about cars. Let R = ? and let the TBox T contain the following axioms: (= 1 maker ) ? Car (= 1 passenger ) ? Car (= 1 speed ) ? Car Car ? (= 1 maker ) ? (= 1 passenger ) ? (= 1 speed ) ? ? ?maker .Maker ? ? ?passenger .N ? ? ?speed .Km/h

Roadster ? Cabriolet ? ?passenger .{2 } Cabriolet ? Car ? ?topType.SoftTop SportsCar = Car ? ?speed . 245km/h .

Here, the value for speed ranges over the datatype of kilometers per hour Km/h, while the value for passengers ranges over the concrete domain of natural numbers N. The concrete predicate 245km/h is true if the value is at least 245km/h. The ABox A contains the following assertions: mgb : Roadster ? ?maker .{mg} ? ?speed . 170km/h enzo : Car ? ?maker .{ferrari} ? ?speed .>350km/h tt : Car ? ?maker .{audi} ? ?speed .=243km/h . Consider the knowledge base K = (T , R, A). It is then easily veri?ed that, e.g., K |= Roadster ? Car K |= enzo : SportsCar K |= mg : Maker K |= tt : ?SportsCar .

4 Probabilistic Uncertainty and Description Logics

In this section, we recall an important probabilistic generalization of SHOIN (D) towards sophisticated formalisms for reasoning under probabilistic uncertainty in the Semantic Web, called P-SHOIN (D), which has recently been introduced in [71] (note that [71] and [28] also introduce closely related probabilistic generalizations of the description logics SHIF(D) and SHOQ(D), which stand behind the web ontology languages OWL Lite and DAML+OIL, respectively). The syntax of P-SHOIN (D) uses the notion of a conditional constraint from [66] to express probabilistic knowledge in addition to the axioms of SHOIN (D). Its semantics is based on the notion of lexicographic entailment in probabilistic default

10

INFSYS RR 1843-06-07

reasoning [67, 69], which is a probabilistic generalization of the sophisticated notion of lexicographic entailment by Lehmann [57] in default reasoning from conditional knowledge bases. This semantics allows for expressing both terminological probabilistic knowledge about concepts and roles, and also assertional probabilistic knowledge about instances of concepts and roles. It naturally interprets terminological and assertional probabilistic knowledge as statistical knowledge about concepts and roles and as degrees of belief about instances of concepts and roles, respectively, and allows for deriving both statistical knowledge and degrees of belief. As an important additional feature, it also allows for expressing default knowledge about concepts (as a special case of terminological probabilistic knowledge), which is semantically interpreted as in Lehmann’s lexicographic default entailment [57]. The notion of probabilistic lexicographic entailment [67, 69] is a formalism for reasoning from statistical knowledge and degrees of belief, which has very nice features. In particular, it shows a similar behavior as reference-class reasoning in a number of uncontroversial examples. But it also avoids many drawbacks of reference-class reasoning: It can handle complex scenarios and even purely probabilistic subjective knowledge as input, and conclusions are drawn in a global way from all the available knowledge as a whole. Furthermore, it also has very nice nonmonotonic properties, which are essentially inherited from Lehmann’s lexicographic entailment. In particular, it realizes an inheritance of properties along subclass relationships, where more speci?c properties override less speci?c properties, without showing the problem of inheritance blocking (where properties are not inherited to subclasses that are exceptional relative to some other properties). As for general nonmonotonic properties, probabilistic lexicographic entailment satis?es (probabilistic versions of) the rationality postulates by Kraus, Lehmann, and Magidor [56], the property of rational monotonicity, and some irrelevance, conditioning, and inclusion properties. All these quite appealing features carry over to the probabilistic description logic P-SHOIN (D). See especially [69] for further details and background on the notion of probabilistic lexicographic entailment.

4.1

Syntax

We now introduce the notion of a probabilistic knowledge base. It is based on the language of conditional constraints [66], which encode interval restrictions for conditional probabilities over concepts. Every probabilistic knowledge base consists of (i) a PTBox, which is a classical (description logic) knowledge base along with probabilistic terminological knowledge, and (ii) a collection of PABoxes, which encode probabilistic assertional knowledge about a certain set of individuals. To this end, we partition the set of individuals I into the set of classical individuals IC and the set of probabilistic individuals IP , and we associate with every probabilistic individual a PABox. That is, probabilistic individuals are those individuals in I for which we explicitly store some probabilistic assertional knowledge in a PABox. We ?rst de?ne conditional constraints as follows. We assume a ?nite nonempty set C of basic classi?cation concepts (or basic c-concepts for short), which are (not necessarily atomic) concepts in SHOIN (D) that are free of individuals from IP . Informally, they are the relevant description logic concepts for de?ning probabilistic relationships. The set of classi?cation concepts (or c-concepts) is inductively de?ned as follows. Every basic c-concept φ ∈ C is a c-concept. If φ and ψ are c-concepts, then ?φ and (φ ? ψ) are also c-concepts. We often write (φ ? ψ) to abbreviate ?(?φ ? ?ψ), as usual. A conditional constraint is an expression of the form (ψ|φ)[l, u], where φ and ψ are c-concepts, and l and u are reals from [0, 1]. Informally, (ψ|φ)[l, u] encodes that the probability of ψ given φ lies between l and u. We next de?ne the notion of a probabilistic knowledge base. A PTBox PT = (T, P ) consists of a classical (description logic) knowledge base T and a ?nite set of conditional constraints P . Informally, every conditional constraint (ψ|φ)[l, u] in P encodes that “generally, if an object belongs to φ, then it belongs to ψ

INFSYS RR 1843-06-07

11

with a probability between l and u”. In particular, (?R.{o}|φ)[l, u] in P , where o ∈ IC and R ∈ RA , encodes that “generally, if an object belongs to φ, then it is related to o by R with a probability between l and u”. A PABox P is a ?nite set of conditional constraints. A probabilistic knowledge base K = (T, P, (Po )o∈IP ) relative to IP consists of a PTBox PT = (T, P ) and one PABox Po for every probabilistic individual o ∈ IP . Informally, every (ψ|φ)[l, u] in Po , where o ∈ IP , encodes that “if o belongs to φ, then o belongs to ψ with a probability between l and u”. In particular, (?R.{o′ }|φ)[l, u] in Po , where o ∈ IP , o′ ∈ IC , and R ∈ RA , expresses that “if o belongs to φ, then o is related to o′ by R with a probability between l and u”. Informally, a probabilistic knowledge base K = (T, P, (Po )o∈IP ) extends a classical knowledge base T by probabilistic terminological knowledge P and probabilistic assertional knowledge Po about every o ∈ IP . That is, P represents our statistical knowledge about concepts, while every Po represents our degrees of belief about the individual o. Observe that the axioms in T and the conditional constraints in every Po with o ∈ IP are strict (that is, they must always hold), while the conditional constraints in P are defeasible (that is, they may have exceptions and thus do not always have to hold), since T ∪ P may not always be satis?able as a whole in combination with our degrees of belief (and then we ignore some elements of P ). Example 4.1 (Car Example cont’d) We now extend the classical description logic knowledge base T given in Example 3.1 by terminological default, terminological probabilistic, and assertional probabilistic knowledge to a probabilistic knowledge base K = (T, P, (Po )o∈IP ). We assume an additional atomic concept HasFourWheels and an additional datatype role HasColor between cars and the elementary datatype colors, which has a ?nite set of color names as data values. The terminological default knowledge (1) “generally, cars do not have a red color” and (2) “generally, sports cars have a red color”, and the terminological probabilistic knowledge (3) “cars have four wheels with a probability of at least 0.9”, can be expressed by the following conditional constraints in P : (1) (?? HasColor.{red} | Car)[1, 1], (2) (? HasColor.{red} | SportsCar)[1, 1], (3) (HasFourWheels | Car)[0.9, 1] . Suppose we want to encode some probabilistic information about John’s car (which we have not seen so far). Then, the set of probabilistic individuals IP contains the individual John’s car, and the assertional probabilistic knowledge (4) “John’s car is a sports car with a probability of at least 0.8” (we know that John likes sports cars) can be expressed by the following conditional constraint in PJohn’s car : (4) (SportsCar | ?)[0.8, 1] .

4.2

Semantics

In this section, we de?ne the semantics of P-SHOIN (D). After some preliminaries, we introduce the notions of consistency and lexicographic entailment for probabilistic knowledge bases, which are based on the notions of consistency resp. lexicographic entailment in probabilistic default reasoning [67, 69]. 4.2.1 Preliminaries We now de?ne (possible) objects and probabilistic interpretations, which are certain sets of basic c-concepts resp. probability functions on the set of all (possible) objects. We also de?ne the satisfaction of classical knowledge bases and conditional constraints in probabilistic interpretations.

12

INFSYS RR 1843-06-07

A (possible) object o is a set of basic c-concepts φ ∈ C such that {φ(i) | φ ∈ o} ∪ {?φ(i) | φ ∈ C \ o} is satis?able, where i is a new individual. Informally, every object o represents an individual i that is fully speci?ed on C in the sense that o belongs (resp., does not belong) to every c-concept φ ∈ o (resp., φ ∈ C \ o). We denote by OC the set of all objects relative to C. An object o satis?es a classical knowledge base T , or o is a model of T , denoted o |= T , iff T ∪ {φ(i) | φ ∈ o} ∪ {?φ(i) | φ ∈ C \ o} is satis?able, where i is a new individual. An object o satis?es a basic c-concept φ ∈ C, or o is a model of φ, denoted o |= φ, iff φ ∈ o. The satisfaction of c-concepts by objects is inductively extended to all c-concepts, as usual, by (i) o |= ?φ iff o |= φ does not hold, and (ii) o |= φ ? ψ iff o |= φ and o |= ψ. It is not dif?cult to verify that a classical knowledge base T is satis?able iff an object o ∈ OC exists that satis?es T . A probabilistic interpretation Pr is a probability function on OC (that is, a mapping Pr : OC → [0, 1] such that all Pr (o) with o ∈ OC sum up to 1). We say Pr satis?es a classical knowledge base T , or Pr is a model of T , denoted Pr |= T , iff o |= T for every o ∈ OC such that Pr (o) > 0. We de?ne the probability of a c-concept and the satisfaction of conditional constraints in probabilistic interpretations as follows. The probability of a c-concept φ in a probabilistic interpretation Pr denoted Pr (φ), is the sum of all Pr (o) such that o |= φ. For c-concepts φ and ψ such that Pr (φ) > 0, we write Pr (ψ|φ) to abbreviate Pr (φ ? ψ) / Pr (φ). We say Pr satis?es a conditional constraint (φ|ψ)[l, u], or Pr is a model of (ψ|φ)[l, u], denoted Pr |= (ψ|φ)[l, u], iff Pr (φ) = 0 or Pr (ψ|φ) ∈ [l, u]. We say Pr satis?es a set of conditional constraints F, or Pr is a model of F, denoted Pr |= F, iff Pr |= F for all F ∈ F. It is not dif?cult to verify that a classical knowledge base T is satis?able iff there exists a probabilistic interpretation that satis?es T .

4.2.2

Consistency

The notion of consistency for PTBoxes and probabilistic knowledge bases is based on the notion of consistency in probabilistic default reasoning [67, 69]. We ?rst give some preparative de?nitions. A probabilistic interpretation Pr veri?es a conditional constraint (ψ|φ)[l, u] iff Pr (φ) = 1 and Pr (ψ) ∈ [l, u], that is, iff Pr (φ) = 1 and Pr |= (ψ|φ)[l, u]. We say Pr falsi?es (ψ|φ)[l, u] iff Pr (φ) = 1 and Pr |= (ψ|φ)[l, u]. A set of conditional constraints F tolerates a conditional constraint F under a classical knowledge base T iff T ∪ F has a model that veri?es F . A PTBox PT = (T, P ) is consistent iff (i) T is satis?able and (ii) there exists an ordered partition (P0 , . . . , Pk ) of P such that each Pi with i ∈ {0, . . . , k} is the set of all F ∈ Pi ∪ · · · ∪ Pk that are tolerated under T by Pi ∪ · · · ∪ Pk . Informally, the condition (ii) means that P has a natural ordered partition into collections of conditional constraints of increasing speci?cities such that every collection is locally consistent. That is, any inconsistencies can be naturally resolved by preferring more speci?c pieces of knowledge to less speci?c ones. For example, the inconsistency between (?? HasColor.{red} | Car)[1, 1] and (? HasColor.{red} | SportsCar)[1, 1] when reasoning about sports cars is naturally resolved by preferring the latter to the former. We call the above ordered partition (P0 , . . . , Pk ) of P the z-partition of PT . A probabilistic knowledge base K = (T, P, (Po )o∈IP ) is consistent iff PT = (T, P ) is consistent and T ∪ Po is satis?able for all probabilistic individuals o ∈ IP . Informally, the latter says that the strict knowledge in T must be compatible with the strict degrees of belief in Po , for every probabilistic individual o. Example 4.2 (Car Example cont’d) The probabilistic knowledge base K = (T, P, (Po )o∈IP ) of Example 4.1 is consistent, since PT = (T, P ) is consistent, and T ∪ Po is satis?able for every probabilistic individual o ∈ IP = {John’s car}. Observe that the z-partition of (T, P ) is given by (P0 , P1 ), where P0 = {(ψ|φ)[l, u] ∈ P | φ = Car} and P1 = {(ψ|φ)[l, u] ∈ P | φ = SportsCar}.

INFSYS RR 1843-06-07

13

There is an algorithm for deciding whether a PTBox (resp., probabilistic knowledge base) in P-SHOIN (D) is consistent, which is based on a reduction to deciding whether a classical knowledge base in SHOIN (D) is satis?able and to deciding whether a system of linear constraints is solvable [71]. This shows that the two consistency problems in P-SHOIN (D) are both decidable.

4.2.3 Lexicographic Entailment The notion of lexicographic entailment for probabilistic knowledge bases is based on lexicographic entailment in probabilistic default reasoning [67, 69]. In the sequel, let K = (T, P, (Po )o∈IP ) be a consistent probabilistic knowledge base. We ?rst de?ne a lexicographic preference relation on probabilistic interpretations, which is then used to de?ne the notion of lexicographic entailment for sets of conditional constraints under PTBoxes. We ?nally de?ne the notion of lexicographic entailment for deriving statistical knowledge and degrees of belief about probabilistic objects from PTBoxes and probabilistic knowledge bases, respectively. We use the z-partition (P0 , . . . , Pk ) of (T, P ) to de?ne a lexicographic preference relation on probabilistic interpretations Pr and Pr ′ : We say Pr is lexicographically preferable (or lex-preferable) to Pr ′ iff some i ∈ {0, . . . , k} exists such that |{F ∈ Pi | Pr |= F }| > |{F ∈ Pi | Pr ′ |= F }| and |{F ∈ Pj | Pr |= F }| = |{F ∈ Pj | Pr ′ |= F }| for all i < j k. Roughly speaking, this preference relation implements the idea of preferring more speci?c pieces of knowledge to less speci?c ones in the case of local inconsistencies. It can thus be used for ignoring the latter when drawing conclusions in the case of local inconsistencies. A model Pr of a classical knowledge base T and a set of conditional constraints F is a lexicographically minimal (or lex-minimal) model of T ∪ F iff no model of T ∪ F is lex-preferable to Pr .

We de?ne the notion of lexicographic entailment of conditional constraints from sets of conditional constraints under PTBoxes as follows. A conditional constraint (ψ|φ)[l, u] is a lexicographic consequence (or lex-consequence) of a set of conditional constraints F under a PTBox PT , denoted F ? lex (ψ|φ)[l, u] under PT , iff Pr (ψ) ∈ [l, u] for every lex-minimal model Pr of T ∪ F ∪ {(φ|?)[1, 1]}. We say (ψ|φ)[l, u] is lex a tight lexicographic consequence (or tight lex-consequence) of F under PT , denoted F ? tight (ψ|φ)[l, u] under PT , iff l (resp., u) is the in?mum (resp., supremum) of Pr (ψ) subject to all lex-minimal models Pr of T ∪ F ∪ {(φ|?)[1, 1]}. Note that [l, u] = [1, 0] (where [1, 0] represents the empty interval) when no such model Pr exists. Furthermore, for inconsistent PTBoxes PT , we de?ne F ? lex (ψ|φ)[l, u] and lex F ? tight (ψ|φ)[1, 0] under PT for all sets of conditional constraints F and all conditional constraints (ψ|φ)[l, u]. We now de?ne which statistical knowledge and degrees of belief follow under lexicographic entailment from PTBoxes PT and probabilistic knowledge bases K = (T, P, (Po )o∈IP ), respectively. A conditional constraint F is a lex-consequence of PT , denoted PT ? lex F , iff ? ? lex F under PT . We say F lex lex is a tight lex-consequence of PT , denoted PT ? tight F , iff ? ? tight F under PT . A conditional constraint F for a probabilistic individual o ∈ IP is a lex-consequence of K, denoted K ? lex F , iff Po ? lex F lex lex under PT = (T, P ). We say F is a tight lex-consequence of K, denoted K ? tight F , iff Po ? tight F under PT = (T, P ).

Example 4.3 (Car Example cont’d) Consider again the probabilistic knowledge base K = (T, P, (Po )o∈IP ) of Example 4.1. The following are some (terminological default and terminological probabilistic) tight lex-

14

INFSYS RR 1843-06-07

consequences of PT = (T, P ): (?? HasColor.{red} | Car)[1, 1], (? HasColor.{red} | SportsCar)[1, 1], (HasFourWheels | Car)[0.9, 1], (?? HasColor.{red} | Roadster)[1, 1], (HasFourWheels | SportsCar)[0.9, 1], (HasFourWheels | Roadster)[0.9, 1] . Hence, in addition to the sentences (1) to (3) directly encoded in P , we also conclude “generally, roadsters do not have a red color”, “sports cars have four wheels with a probability of at least 0.9”, and “roadsters have four wheels with a probability of at least 0.9”. Observe here that the default property of not having a red color and the probabilistic property of having four wheels with a probability of at least 0.9 are inherited from cars down to roadsters. Roughly, the tight lex-consequences of PT = (T, P ) are given by all those conditional constraints that (a) are either in P , or (b) can be constructed by inheritance along subconcept relationships from the ones in P and are not overridden by more speci?c pieces of knowledge in P . The following conditional constraints for the probabilistic individual John’s car are some (assertional probabilistic) tight lex-consequences of K = (T, P, (Po )o∈IP ), which informally say that John’s car is a sports car, has a red color, and has four wheels with probabilities of at least 0.8, 0.8, and 0.72, respectively: (SportsCar | ?)[0.8, 1], (? HasColor.{red} | ?)[0.8, 1], (HasFourWheels | ?)[0.72, 1] . There is an algorithm for computing tight intervals under lexicographic entailment in P-SHOIN (D), which is based on a reduction to deciding classical knowledge base satis?ability in SHOIN (D) and to solving linear optimization problems [71]. Hence, lexicographic entailment in P-SHOIN (D) is computable.

4.3

Related Work

To our knowledge, there are no other approaches to probabilistic description logics for the Semantic Web in the literature. However, there are several previous approaches to probabilistic description logics without Semantic Web background. Furthermore, there are several probabilistic extensions of web ontology languages in the literature. Finally, there are important applications of probabilistic description logics and probabilistic web ontology languages in the ?eld of information retrieval. In this section, we give an overview of these approaches. 4.3.1 Probabilistic Description Logics

Other approaches to probabilistic description logics can be classi?ed according to the generalized description logics, the supported forms of probabilistic knowledge, and the underlying probabilistic reasoning formalism. Heinsohn [38] presents a probabilistic extension of the description logic ALC, which allows to represent terminological probabilistic knowledge about concepts and roles, and which is essentially based on probabilistic reasoning in probabilistic logics, similar to [85, 1, 26, 66]. Heinsohn [38], however, does not allow for assertional knowledge about concept and role instances. Jaeger’s work [51] proposes another probabilistic extension of the description logic ALC, which allows for terminological and assertional

INFSYS RR 1843-06-07

15

probabilistic knowledge about concepts / roles and about concept instances, respectively, but does not support assertional probabilistic knowledge about role instances (but he mentions a possible extension in this direction). The uncertain reasoning formalism in [51] is essentially based on probabilistic reasoning in probabilistic logics, as the one in [38], but coupled with cross-entropy minimization to combine terminological probabilistic knowledge with assertional probabilistic knowledge. The work by D¨ rig and Studer [22] u presents a further probabilistic extension of ALC, which is based on probabilistic reasoning in probabilistic logics, but which only allows for assertional probabilistic knowledge about concept and role instances, and not for terminological probabilistic knowledge. Jaeger’s recent work [52] focuses on interpreting probabilistic concept subsumption and probabilistic role quanti?cation through statistical sampling distributions, and develops a probabilistic version of the guarded fragment of ?rst-order logic. Koller et al.’s work [55] presents a probabilistic generalization of the C LASSIC description logic. Like Heinsohn’s work [38], it allows for terminological probabilistic knowledge about concepts and roles, but does not support assertional knowledge about instances of concepts and roles. But, in contrast to [38], it is based on inference in Bayesian networks as underlying probabilistic reasoning formalism. Closely related work by Yelland [123] combines a restricted description logic close to FL with Bayesian networks, and applies this approach to market analysis. It allows for terminological probabilistic knowledge about concepts and roles, but does not support assertional knowledge about instances of concepts and roles. 4.3.2 Probabilistic Web Ontology Languages The literature contains several probabilistic generalizations of web ontology languages. Many of these approaches focus especially on combining the web ontology language OWL with probabilistic formalisms based on Bayesian networks. In particular, da Costa [9], da Costa and Laskey [10], and da Costa et al. [11] suggest a probabilistic generalization of OWL, called PR-OWL, which is based on multi-entity Bayesian networks. The latter are a Bayesian logic that combines ?rst-order logic with Bayesian probabilities. Ding et al. [13, 14] propose a probabilistic generalization of OWL, called BayesOWL, which is based on standard Bayesian networks. BayesOWL provides a set of rules and procedures for the direct translation of an OWL ontology into a Bayesian network that supports ontology reasoning, both within and across ontologies, as Bayesian inferences. Ding et al. [88, 14] also describe an application of this approach in ontology mapping. In closely related work, Mitra et al. [84] introduce a technique to enhancing existing ontology mappings by using a Bayesian network to represent the in?uences between potential concept mappings across ontologies. Yang and Calmet [122] present an integration of the web ontology language OWL with Bayesian networks. The approach makes use of probability and dependency-annotated OWL to represent uncertain information in Bayesian networks. Pool and Aikin [90] also provide a method for representing uncertainty in OWL ontologies, while Fukushige [27] proposes a basic framework for representing probabilistic relationships in RDF. Finally, Nottelmann and Fuhr [86] present two probabilistic extensions of variants of OWL Lite, along with a mapping to locally strati?ed probabilistic Datalog. 4.3.3 Applications in Information Retrieval An important research direction deals with the application of probabilistic description logics and probabilistic web ontology languages in enhanced information retrieval techniques. In particular, Mantay et al. [75] propose a probabilistic least common subsumer operation, which is based on a probabilistic extension of the description logic language ALN . They show that applying this approach in information retrieval allows for reducing the amount of retrieved data and thus for avoiding information ?ood. Closely related work by Holi and Hyv¨ nen [39, 40] shows how degrees of overlap between concepts can be modeled and computed o

16

INFSYS RR 1843-06-07

ef?ciently using Bayesian networks based on RDF(S) ontologies. Such degrees of overlap indicate how well an individual data item matches the query concept, and can thus be used for measuring the relevance in information retrieval tasks. In another closely related work, Udrea et al. [119] explore the use of probabilistic ontologies in relational databases. They propose to extend relations by associating with every attribute a constrained probabilistic ontology, which describes relationships between terms occurring in the domain of that attribute. An extension of the relational algebra then allows for an increased recall in information retrieval. Finally, Weikum et al. [121] and Thomas and Sheth [117] describe the use of probabilistic ontologies in information retrieval from a more general perspective.

5 Possibilistic Uncertainty and Description Logics

Similar to probabilistic extensions of description logics, possibilistic extensions of description logics have been developed by Hollunder [45] and Dubois et al. [16] and especially applied in information retrieval by Liau and Fan [63]. In the sequel, we implicitly assume the description logic SHOIN (D) as underlying description logic, but any other (decidable) description logic can be used as well.

5.1

Syntax

A possibilistic axiom is of the form (α, P l) or (α, N l), where α is a classical description logic axiom, and l is a real number from [0, 1]. A possibilistic RBox (resp., TBox, ABox) is a ?nite set of possibilistic axioms (α, P l) or (α, N l), where α is an RBox (resp., TBox, ABox) axiom. A possibilistic knowledge base K = (R, T , A) consists of a possibilistic RBox R, a possibilistic TBox T , and a possibilistic ABox A. The following example from [45] illustrates possibilistic knowledge bases. Example 5.1 (Car Example cont’d) The following possibilistic knowledge base K = (R, T , A) encodes some possibilistic knowledge about cars and rich people. Let R = ?. The TBox T represents the possibilistic terminological knowledge that “every person owning a Porsche is either rich or a car fanatic with a necessity of at least 0.8” and “every rich person is a golfer with a possibility of at least 0.7”: T = {(?owns.Porsche ? richPerson ? carFanatic, N 0.8), (richPerson ? golfer , P 0.7)} .

Furthermore, the ABox A expresses the possibilistic assertional knowledge that “Tom owns a 911 with necessity 1”, “a 911 is a Porsche with necessity 1”, and “Tom is not a car fanatic with a necessity of at least 0.7”: A = {((Tom, 911) : owns, N 1), (911 : Porsche, N 1), (Tom : ?carFanatic, N 0.7)} .

5.2

Semantics

Let I denote the set of all classical description logic interpretations. A possibilistic interpretation is a mapping π : I → [0, 1]. In the sequel, we assume that π is normalized, that is, that π(I) = 1 for some I ∈ I. The possibility of a description logic axiom α in a possibilistic interpretation π, denoted P oss(α), is then de?ned by P oss(α) = max {π(I) | I ∈ I, I |= α} (where max ? = 0), and the necessity of α, denoted N ec(α), is de?ned by N ec(α) = 1 ? P oss(?α).

INFSYS RR 1843-06-07

17

A possibilistic interpretation π satis?es a possibilistic axiom (α, P l) (resp., (α, N l)), or π is a model of (α, P l) (resp., (α, N l)), denoted π |= (α, P l) (resp., π |= (α, N l)) iff P oss(α) l (resp., N ec(α) l). The notions of satis?ability, logical entailment, and tight logical entailment for possibilistic knowledge bases are then de?ned in the standard way. As shown by Hollunder [45], deciding logical consequences and thus also deciding satis?ability and computing tight logical consequences can be reduced to deciding logical consequences in description logics. Example 5.2 (Car Example cont’d) Consider again the possibilistic knowledge base K of Example 5.2. It is not dif?cult to verify that K is satis?able and logically implies that “Tom is a golfer with a possibility of at least 0.7”, that is, K |= (Tom : golfer , P 0.7) .

6 Vagueness and Description Logics

In this section, we de?ne fuzzy SHOIN (D), using the fuzzy operators of Section 2.3. We recall here the semantics given in [109, 112] (see also [95]).

6.1

Syntax

We have seen that SHOIN (D) allows to reason with concrete datatypes, such as strings and integers, using so-called concrete domains. In our fuzzy approach, concrete domains may be based on fuzzy sets as well. 6.1.1 Fuzzy Datatype Theories A fuzzy datatype theory D = (?D , · D ) is de?ned in the same way as a classical datatype theory except that · D now assigns to every n-ary datatype predicate an n-ary fuzzy relation over ?D . For instance, as for SHOIN (D), the predicate 18 may be a unary crisp predicate over the natural numbers denoting the set of integers smaller or equal to 18, i.e., 18 : Natural → [0, 1] and

18 (x)

=

1 if x 18 0 otherwise .

So, Minor = Person ? ?age.

18

(4)

de?nes a person, whose age is less or equal to 18, i.e., it de?nes a minor. On the other hand, concerning non crisp fuzzy domain predicates, we recall that in fuzzy set theory and practice, there are many functions for specifying fuzzy set membership degrees. However, the triangular, the trapezoidal, the L-function (left-shoulder function), and the R-function (right-shoulder function) are simple, but most frequently used to specify membership degrees. The functions are de?ned over the set of non-negative rationals Q+ ∪ {0} (see Fig. 1). Using these functions, we may then de?ne, for instance, Young : Natural → [0, 1] to be a fuzzy concrete predicate over the natural numbers denoting the degree of youngness of a person’s age. The concrete fuzzy predicate Young may be de?ned as Young(x) = L(x; 10, 30). So, YoungPerson = Person ? ?age.Young denotes a young person. (5)

18

INFSYS RR 1843-06-07

(a)

(b)

(c)

(d)

Figure 1: (a) Trapezoidal function; (b) Triangular function; (c) L-function; (d) R-function

6.1.2

Fuzzy Modi?ers

We allow modi?ers in fuzzy SHOIN (D). Fuzzy modi?ers, like very, more or less and slightly, apply to fuzzy sets to change their membership function. Formally, a modi?er is a function fm : [0, 1] → [0, 1]. For √ instance, we may de?ne very(x) = x2 and slightly(x) = x. Modi?ers have been considered, for instance, in [44, 118]. From a syntactical point of view, if M is a new alphabet for modi?er symbols, m ∈ M is a modi?er, and C is a SHOIN (D) concept, then m(C) is fuzzy concept as well. For instance, by referring to Example 3.1, we may de?ne the concept of sports car as the concept SportsCar = Car ? ?speed .very(High) , (6)

where very is a concept modi?er, with membership function very(x) = x2 , and High is a fuzzy concrete predicate over the domain of speed expressed in kilometers per hour and may be de?ned as High(x) = R(x; 80, 250). 6.1.3 Fuzzy Knowledge Bases

The syntax of fuzzy SHOIN (D) concepts is as follows: C ?→ ? | ⊥ | A | {a1 , . . . , an } | C1 ? C2 | C1 ? C2 | ?C | m(C) ?R.C | ?R.C | ( n S) | ( n S) | ?T1 , . . . , Tn .D | ?T1 , . . . , Tn .D | ( n T ) | ( n T ) . Concerning axioms and assertions, similarly to [103], we de?ne fuzzy axioms as follows: Let be n ∈ (0, 1].

INFSYS RR 1843-06-07

19

A fuzzy RBox R is a ?nite set of SHOIN (D) transitivity axioms trans(R) and fuzzy role inclusion axioms of the form α n , α n , α > n , and α > n , where α is a SHOIN (D) role inclusion axiom. A fuzzy TBox T is a ?nite set of fuzzy concept inclusion axioms α n , α n , α > n , and α < n , where α is a SHOIN (D) concept inclusion axiom. A fuzzy ABox A consists of a ?nite set of fuzzy concept and fuzzy role assertion axioms of the form α n , α n , α > n , or α < n , where α is a SHOIN (D) concept or role assertion. As for the crisp case, A may also contain a ?nite set of individual (in)equality axioms a ≈ b and a ≈ b, respectively. For instance, a : C 0.1 , (a, b) : R 0.3 , R ? S 0.4 , or C ? D 0.6 are fuzzy axioms. Informally, from a semantical point of view, a fuzzy axiom α n constrains the membership degree of α to be at most n (similarly for , >, <). Hence, jim : YoungPerson 0.2 says that jim is a YoungPerson with degree at least 0.2. On the other hand, a fuzzy concept inclusion axiom of the form C ? D n says that the subsumption degree between C and D is at least n. A SHOIN (D) fuzzy knowledge base K = (T , R, A) consists of a fuzzy TBox T , a fuzzy RBox R, and a fuzzy ABox A.

6.2

Semantics

The semantics extends [103]. The main idea is that concepts and roles are interpreted as fuzzy subsets of an interpretation’s domain. Therefore, SHOIN (D) axioms, rather being satis?ed (true) or unsatis?ed (false) in an interpretation, become a degree of truth in [0, 1]. In the following, we use ∧, ∨, ? and → in in?x notation, in place of a t-norm t, s-norm s, negation function n, and implication function i. 6.2.1 Fuzzy Interpretations A fuzzy interpretation I = (?I , ·I ) relative to a fuzzy datatype theory D = (?D , · D ) consists of a nonempty set ?I (called the domain), disjoint from ?D , and of a fuzzy interpretation function ·I that coincides with · D on every data value, datatype, and fuzzy datatype predicate, and it assigns ? to each abstract individual a ∈ I an element in ?I ; ? to each abstract concept C ∈ A a function C I : ?I → [0, 1]; ? to each abstract role R ∈ RA a function RI : ?I × ?I → [0, 1]; ? to each abstract functional role R ∈ RA a partial function RI : ?I × ?I → [0, 1] such that for all x ∈ ?I there is an unique y ∈ ?I on which RI (x, y) is de?ned; ? to each concrete role T ∈ RC a function RI : ?I × ?D → [0, 1]; ? to each concrete functional role T ∈ RC a partial function tI : ?I × ?D → [0, 1] such that for all x ∈ ?I there is an unique v ∈ ?D on which T I (x, v) is de?ned; The mapping ·I is extended to roles and concepts as speci?ed in the following table (where x, y ∈ ?I and v ∈ ?D ): (S ? ) (x, y) = S I (y, x) ?I (x) = 1

I

? to each modi?er m ∈ M the modi?er function fm : [0, 1] → [0, 1].

20

INFSYS RR 1843-06-07

⊥I (x) {a1 , . . . , an }I (x) (C1 ? C2 )I (x) (C1 ? C2 )I (x) (?C)I (x) (m(C))I (x) (?R.C)I (x) (?R.C)I (x) ( n S)I (x)

= = = = = = = = =

0

n I i=1 ai = x C1 I (x) ∧ C2 I (x) C1 I (x) ∨ C2 I (x) ?C I (x))

fm (C I (x)) inf y∈?I RI (x, y) → C I (y) supy∈?I RI (x, y) ∧ C I (y) n I sup {y1 , . . . , yn } ? ?I i=1 S (x, yi )

|{y1 , . . . , yn }| = n

( n S)I (x) = ?( n + 1 S)I (x) (?T1 , . . . , Tn .D)I (x) = inf y1 ,...,yn ∈?D I ( n Ti I (x, yi )) → DI (y1 , . . . , yn ) i=1 (?T1 , . . . , Tn .D)I (x) = supy1 ,...,yn ∈?D I ( n Ti I (x, yi )) ∧ DI (y1 , . . . , yn ) . i=1 We comment brie?y some points. The semantics of ?R.C (?R.C)I (d) = supy∈?I RI (x, y) ∧ C I (y) is the result of viewing ?R.C as the open ?rst order formula ?y.FR (x, y) ∧ FC (y) (where F is the obvious translation of roles and concepts into ?rst-order logic (FOL)) and the existential quanti?er ? is viewed as a disjunction over the elements of the domain. Similarly, (?R.C)I (x) = inf y∈?I RI (x, y) → C I (y) is related to the open ?rst order formula ?y.FR (x, y) → FC (y), where the universal quanti?er ? is viewed as a conjunction over the elements of the domain. However, unlike the classical case, in general, we do not have that (?R.C)I = (??R.?C)I . For instance, it holds in ?ukasiewicz logic, but not in G¨ del logic. o Also interesting is that (see [35]) the axiom ? ? ?(?R.A) ? (??R.?A) has no classical model. However, in [35], it is shown that in G¨ del logic it has no ?nite model, but has an in?nite model. o Another point concerns the semantics of number restrictions. The semantics of the concept ( n S) ( n S)I (x) = sup

{y1 , . . . , yn } ? ?I |{y1 , . . . , yn }| = n n I i=1 S (x, yi )

is the result of viewing (

n

n S) as the open ?rst order formula yi = y j .

1 i<j n

?y1 , . . . , yn .

i=1

S(x, yi ) ∧

That is, there are at least n distinct elements that satisfy to some degree S(x, yi ). This guarantees us that ?S.? ≡ ( 1 S). The semantics of ( n S) is de?ned in such a way to guarantee the classical relationship ( n S) ≡ ?( n + 1 S). An alternative de?nition for the ( n S) and the ( n S) constructs may rely on the scalar cardinality of a fuzzy set. However, we prefer to stick on the formulation, which derives directly from its FOL translation.

INFSYS RR 1843-06-07

21

Finally, the mapping ·I is extended to non-fuzzy axioms as speci?ed in the following table (where a, b ∈ I): (R ? S)I (T ? U )I (C ? D)I (a : C)I ((a, b) : R)I = = = = = inf x,y∈?I RI (x, y) → S I (x, y) inf x,y∈?I T I (x, y) → U I (x, y) inf x∈?I C I (x) → DI (x) C I (aI ) RI (aI , bI ) .

Note here that e.g. the semantics of a concept inclusion axiom C ? D is derived directly from its FOL translation, which is of the form ?x.FC (x) → FD (x). This de?nition is clearly different from the approaches in which C ? D is viewed as ?x.C(x) D(x). This latter approach has the effect that the subsumption relationship is a classical {0, 1} relationship, while the in former approach subsumption is determined up to a certain degree in [0, 1]. The notion of satisfaction of a fuzzy axiom E by a fuzzy interpretation I, denoted I |= E, is de?ned as follows: I |= trans(R), iff ?x, y ∈ ?I .RI (x, y) = supz∈?I RI (x, z) ∧ RI (z, y). I |= α n , where α is a role inclusion or concept inclusion axiom, iff αI n. Similarly, for the other relations , < and >. I |= α n , where α is a concept or a role assertion axiom, iff αI n. Similarly, for the other relations , <, >. We say that a concept C is satis?able iff there is an interpretation I and an individual x ∈ ?I such that C I (x) > 0. Finally, I |= a ≈ b iff aI = bI and I |= a ≈ b iff aI = bI . For a set of fuzzy axioms E, we say that I satis?es E iff I satis?es each element in E. We say that I is a model of E (resp. E) iff I |= E (resp. I |= E). I satis?es (is a model of) a fuzzy knowledge base K = (T , R, A), denoted I |= K, iff I is a model of each component T , R and A, respectively. A fuzzy axiom E is a logical consequence of a knowledge base K, denoted K |= E iff every model of K satis?es E. The interesting point is that according to our semantics, e.g., a minor is a young person to a certain degree and is obtained without explicitly mentioning it. This inference can not be achieved in classical SHOIN (D). Similarly, by referring to Example 3.1, we will have that the car tt will be a sports car to a certain degree. Therefore, unlike Example 3.1, tt is now closely a sport car, as it should be. The following two examples highlight these points. Example 6.1 (Car Example cont’d) Example 3.1 illustrates an evident dif?culty in de?ning the class of sport cars. Indeed, it is highly questionable why a car whose speed is 243km/h is not a sport car anymore. The point is that essentially, the higher the speed the more closely a car is a sports car, which makes the concept of sports car rather a fuzzy concept, i.e., vague concept, rather than a crisp one. In the next section, we will see how to represent such concepts more appropriately. Let us now reconsider Example 3.1, where all axioms of the TBox and ABox are asserted with degree 1, i.e., are of the form α 1 . We replace the de?nition of SportsCar with De?nition (6). Then, we have that (under ?ukasiewicz logic) K |= SportsCar ? Car K |= enzo : SportsCar 1 1 K |= mgb : SportsCar 0.63 K |= tt : SportsCar 0.97 .

Note how the maximal speed limit of the mgb car ( 170km/h ) induces an upper limit, 0.53, of the membership degree. Neither this inference is possible in classical SHOIN (D), nor the one involving tt.

22

INFSYS RR 1843-06-07

Example 6.2 Consider the knowledge base K with de?nitions (4) and (5). Then under ?ukasiewicz logic we have that (see [108]) K |= K |= Minor ? YoungPerson YoungPerson ? Minor 0.6 0.4

which are relationships not captured with classical SHOIN (D). 6.2.2 Best Truth Value Bound

Finally, given K and an axiom α, where α is neither a transitivity axiom, nor an individual (in) equality axiom, it is of interest to compute α’s best lower and upper degree value bounds (Best Truth Value Bound (BTVB)). The greatest lower bound of α w.r.t. K (denoted glb(K, α)) is glb(K, α) = sup{n | K |= α lub(K, α) = inf{n : K |= α n }, n }, while the least upper bound of α with respect to K (denoted lub(K, α) is where sup ? = 0 and inf ? = 1. Determining the lub and the glb is called the Best Degree Bound (BDB) problem. For instance, the consequences in Examples 6.1 and 6.2 are the best possible degree bounds. Furthermore, note that, lub(Σ, a : C) = ?glb(Σ, a : ?C) , (7)

i.e., the lub can be determined through the glb (and vice-versa). Similarly, lub(Σ, (a, b) : R) = ?glb(Σ, a : ??R.{b}) holds. Also, note that, Σ |= α n iff glb(Σ, α) n, and similarly Σ |= α n iff lub(Σ, α) n hold. Another similar concept is the best satis?ability bound of a concept C and amounts to determine glb(K, C) = sup sup {C I (x) | I |= K} .

I x∈?I

Essentially, among all models I of the knowledge base, we are determining the maximal degree of truth that the concept C may have over all individuals x ∈ ?I . Example 6.3 Consider the knowledge base K in Example 3.1. Assume, that a car seller sells an Audi TT for $31500, as from the catalog price. A buyer is looking for a sports-car, but wants to pay not more than around $30000. In classical DLs no agreement can be found. The problem relies on the crisp condition on the seller’s and the buyer’s price. A more ?ne grained approach would be (and usually happens in negotiation) to consider prices as concrete fuzzy sets instead. For instance, the seller may consider optimal to sell above $31500, but can go down to $30500. The buyer prefers to spend less than $30000, but can go up to $32000. We may represent these statements by means of the following axioms (see Figure 2): AudiTT Query = SportsCar ? ?hasPrice.R(x; 30500, 31500) = SportsCar ? ?hasPrice.L(x; 30000, 32000)

Then we may ?nd out that the highest degree to which the concept C = AudiTT ? Query is satis?able is 0.75 (the possibility that the Audi TT and the query matches is 0.75). That is, glb(K, C) = 0.75 and corresponds to the point where both requests intersects (i.e., the car may be sold at $31250). Problems such as determining the glb can be solved by relying on mixed integer linear programming as done in [106, 107] and in the fuzzyDL system (accessible from Umberto Straccia’s home page).

INFSYS RR 1843-06-07

23

Figure 2: The soft price constraints.

6.3

Related Work

Several ways of extending DLs using the theory of fuzzy logic have been proposed in the literature. The ?rst work is due to Yen [124] who considered a sub-language of ALC, FL? [7, 58]. However, it already informally talks about the use of modi?ers and concrete domains. Though, the unique reasoning facility, the subsumption test, is a crisp yes/no question. Tresp [118] considered fuzzy ALC extended with a special form of modi?ers, which are a combination of two linear functions: min, max and 1 ? x membership functions has been considered and a sound and complete reasoning algorithm testing the subsumption relationship has been presented. Similarly to Straccia’s work [106, 107], a linear programming oracle is needed. Assertional reasoning has been considered by Straccia [100, 102, 103], where fuzzy assertion axioms have been allowed in fuzzy ALC (with min, max and 1?x functions), concept modi?ers and fuzzy concrete domains are not allowed however ([102] reports a four-valued variant of fuzzy ALC). He also introduced the BTVB problem and provided a sound and complete reasoning algorithm based on completion rules. In the same spirit, H¨ lldobler et al. [41, 43, 44, 42] extend Straccia’s fuzzy ALC with concept modi?ers of the o form fm (x) = xβ , where β > 0. A sound and complete reasoning algorithm for the graded subsumption problem, based on completion rules, is presented. Straccia’s works [105, 111, 116] are essentially as [103], except that now the truth space is a complete lattice rather than [0, 1]. Sanchez and Tettamanzi [91, 92, 93] start addressing the issue of alternative semantics of quanti?ers in fuzzy ALC (without the assertional component). Essentially, fuzzy quanti?ers allow to state sentences such as FaithfulCustomer ? (Most)buys. LowCalorieFood denoting “the set of individuals that mostly by low calorie food”. Hajek [35, 36] considers ALC under arbitrary t-norm and reports, among others, a procedure deciding |= C ? D 1 and deciding whether C ? D 1 is satis?able, by a reduction to the propositional BL logic, for which a Hilbert style axiomatization exists [34] (but see also [36] for complexity of rational Pavelka logic and see [5], which reports some complexity results for reasoning in fuzzy DLs). Straccia [104] provides a translation of fuzzy ALC with GCI’s into classical ALC. The translation is modular and, thus, it is expected that it can be extended to more expressive DLs as well. The idea is to

24

INFSYS RR 1843-06-07

translate a fuzzy assertion of the form a : C n into a crisp assertion a : Cn with intended meaning “a is instance of C to degree at least n”. It then uses GCI’s to correctly relate the Cn . For instance, C0.7 ? C0.6 is used to say that whenever an individual is instance of C to degree at least 0.7 then it is also instance of C to degree at least 0.6. The translation is at most quadratic in the size of the knowledge base. The idea has further been considered by [61, 62], which essentially provide a crisp language in which expressions of the form e.g. a : ?R0.8 .C0.9 are allowed, with intended meaning: “if a has an R-successor to degree at least 0.8 then this successor is also an instance of C to degree at least 0.9”. Other extension of fuzzy DLs, mainly concern their integration with logic programming, which we however do not report here (see, e.g. [116, 113, 111]). Also, Kang et al. [54] extends fuzzy DLs by allowing comparison operators, e.g., allowing to state that “Tom is more tall than Tim”. Another interesting extension is [16], which combines fuzzy DLs with possibility theory. Essentially, as a : C n is Boolean (either an interpretation satis?es it or not), we can build on top of it an uncertainty logic, which is based on possibility theory in [16]. From a reasoning point of view, no calculus exists yet checking satis?ability of fuzzy SHOIN (D) knowledge bases, though there exist an implementation for fuzzy SHIF(D) (the fuzzyDL system) supporting Zadeh semantics, ?ukasiewicz semantics and classical semantics. Usually, the semantics used for fuzzy DLs follows the so-called Zadeh semantics, but where the concept inclusion is crisp, i.e., C ? D is viewed as ?x.C(x) D(x). [44, 118] report a calculus for the case of ALC [94] with modi?ers and simple TBox under Zadeh semantics. No indication for the BTVB problem is given. [100, 103] reports a calculus for ALC and simple TBox under Zadeh semantics and addresses the BTVB problem. [104] shows how the satis?ability problem and the BTVB problem can be reduced to classical ALC and, thus, can be resolved by means of a tools like FACT and RACER. [96, 97] show results providing a tableaux calculus for fuzzy SHIN without GCIs and under the Zadeh semantics, by adapting similar techniques developed for the classical counterpart. Fuzzy GCIs under Zadeh semantics can be managed as described in [98]. Ultimately, we expect that the techniques developed for classical SHOIN (D) can be extended to the work of [103] as [96, 97] already show. Also interesting is the work [60], which provides a tableaux for fuzzy SHI with GCI’s. On the other hand side, fuzzy tableaux algorithms under Zadeh semantics, seem not to be suitable to be adapted to other semantics, such as ?ukasiewicz logic. Even more problematic is the fact that they are unable to deal with fuzzy concrete domains. However, despite these negative results, recently [107, 106] reports a calculus for ALC(D) whenever the connectives, the modi?ers and the concrete fuzzy predicates are representable as a bounded Mixed Integer Linear Program (MILP). For instance, ?ukasiewicz logic satis?es these conditions as well as the membership functions for concrete fuzzy predicates we have presented in this paper. Additionally, modi?ers should be a combination of linear functions. In that case the calculus consists of a set of constraint propagation rules and an invocation to an oracle for MILP. The method has been extended to fuzzy SHIF(D) (the DL behind OWL-Lite) and a reasoner, called fuzzyDL, has been implemented and is available from Straccia’s Web page (though, a paper describing the algorithm has not yet been published). FuzzyDL supports more features than we have described in this work, whose description go beyond the scope of this work. The use of MILP for reasoning in fuzzy DLs is not surprising as their use for automated deduction in many-valued logics is well- known [31, 32]. A new problem for fuzzy DLs is the top-k retrieval problem. While in classical semantics a tuple satis?es a query or does not satisfy the query, in fuzzy DLs a tuple may satisfy a query to degree. Hence, for instance, given a conjunctive query over a fuzzy DLs knowledge base, it is of interest to compute just the top-k answers. While in relational databases this problem is a current research area (see, e.g. [23, 50, 59]), almost nothing is known for the case of ?rst-order knowledge bases in general (but see [114]) and DLs in

INFSYS RR 1843-06-07

25

particular. The only works we are aware of are [110, 115] dealing with the problem of ?nding the top-k result over a DL-Lite [8] knowledge bases. We conclude by pointing out that fuzzy DLs has ?rst been proposed for logic-based information retrieval. [81] summarizes many previous works on the same argument [82, 83, 76, 77, 78, 79, 78, 80, 96, 99, 101, 101, 102], which originated from the idea to annotated textual documents with graded DL sentences [82]. Other applications are [64] and [12].

7 Conclusions

Handling uncertainty and vagueness has started to play an important role in ontologies and description logics for the Semantic Web. In this paper, we have ?rst provided a brief introduction to uncertainty and vagueness at the propositional level. We have then given an overview of probabilistic uncertainty, possibilistic uncertainty, and vagueness in expressive description logics for the Semantic Web. An interesting topic of future research is the integration of the above forms of uncertainty and vagueness in a single description logic for the Semantic Web. Another issue for future research is the integration of probabilistic, possibilistic, and fuzzy description logics with rule-based languages for the Semantic Web.

References

[1] S. Amarger, D. Dubois, and H. Prade. Constraint propagation with imprecise conditional probabilities. In Proceedings UAI-1991, pages 26–34. Morgan Kaufmann, 1991. [2] F. Baader and P. Hanschke. A schema for integrating concrete domains into concept languages. In Proceedings IJCAI-1991, pages 452–457. Morgan Kaufmann, 1991. [3] T. Berners-Lee. Weaving the Web. Harper, San Francisco, 1999. [4] T. Berners-Lee, J. Hendler, and O. Lassila. The Semantic Web. The Scienti?c American, 284(5):34–43, 2001. [5] P. Bonatti and A. Tettamanzi. Some complexity results on fuzzy description logics. In V. Di Ges` , F. Masulli, u and A. Petrosino, editors, Fuzzy Logic and Applications, volume 2955 of LNCS, pages 19–24. Springer, 2006. [6] G. Boole. An Investigation of the Laws of Thought, on which are Founded the Mathematical Theories of Logic and Probabilities. Walton and Maberley, London, 1854. (reprint: Dover Publications, New York, 1958). [7] R. J. Brachman and H. J. Levesque. The tractability of subsumption in frame-based description languages. In Proceedings AAAI-1984, pages 34–37. AAAI Press, 1984. [8] D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. DL-Lite: Tractable description logics for ontologies. In Proceedings AAAI-2005, pages 602–607. AAAI Press / MIT Press, 2005. [9] P. C. G. da Costa. Bayesian semantics for the Semantic Web. PhD thesis, George Mason University, Fairfax, VA, USA, 2005. [10] P. C. G. da Costa and K. B. Laskey. PR-OWL: A framework for probabilistic ontologies. In Proceedings FOIS-2006, 2006. [11] P. C. G. da Costa, K. B. Laskey, and K. J. Laskey. PR-OWL: A Bayesian ontology language for the Semantic Web. In Proceedings URSW-2005, pages 23–33, 2005. [12] M. d’Aquin, J. Lieber, and A. Napoli. Towards a semantic portal for oncology using a description logic with fuzzy concrete domains. In E. Sanchez, editor, Fuzzy Logic and the Semantic Web, Capturing Intelligence, pages 379–393. Elsevier, 2006. [13] Z. Ding and Y. Peng. A probabilistic extension to ontology language OWL. In Proceedings HICSS-2004, 2004.

26

INFSYS RR 1843-06-07

[14] Z. Ding, Y. Peng, and R. Pan. BayesOWL: Uncertainty modeling in Semantic Web ontologies. In Z. Ma, editor, Soft Computing in Ontologies and Semantic Web, volume 204 of Studies in Fuzziness and Soft Computing. Springer, 2006. [15] D. Dubois, J. Lang, and H. Prade. Possibilistic logic. In D. M. Gabbay, C. J. Hogger, and J. A. Robinson, editors, Handbook of Logic in Arti?cial Intelligence and Logic Programming, volume 3, pages 439–513. Clarendon Press, Oxford, 1994. [16] D. Dubois, J. Mengin, and H. Prade. Possibilistic uncertainty and fuzzy features in description logic: A preliminary discussion. In E. Sanchez, editor, Capturing Intelligence: Fuzzy Logic and the Semantic Web. Elsevier, 2006. [17] D. Dubois and H. Prade. On fuzzy syllogisms. Computational Intelligence, 4(2):171–179, 1988. [18] D. Dubois and H. Prade. Can we enforce full compositionality in uncertainty calculi? In Proceedings AAAI1994, pages 149–154. AAAI Press, 1994. [19] D. Dubois and H. Prade. Possibility theory, probability theory and multiple-valued logics: A clari?cation. Ann. Math. Artif. Intell., 32(1–4):35–66, 2001. [20] D. Dubois, H. Prade, L. Godo, and R. L. de M` ntaras. Qualitative reasoning with imprecise probabilities. J. a Intell. Inf. Syst., 2:319–363, 1993. [21] D. Dubois, H. Prade, and J.-M. Touscas. Inference with imprecise numerical quanti?ers. In Z. W. Ras and M. Zemankova, editors, Intelligent Systems, chapter 3, pages 53–72. Ellis Horwood, 1990. [22] M. D¨ rig and T. Studer. Probabilistic ABox reasoning: Preliminary results. In Proceedings DL-2005, pages u 104–111, 2005. [23] R. Fagin. Combining fuzzy information: An overview. SIGMOD Rec., 31(2):109–118, 2002. [24] R. Fagin, J. Y. Halpern, and N. Megiddo. A logic for reasoning about probabilities. Inf. Comput., 87:78–128, 1990. [25] D. Fensel, W. Wahlster, H. Lieberman, and J. Hendler, editors. Spinning the Semantic Web: Bringing the World Wide Web to Its Full Potential. MIT Press, 2002. [26] A. M. Frisch and P. Haddawy. Anytime deduction for probabilistic logic. Artif. Intell., 69(1–2):93–122, 1994. [27] Y. Fukushige. Representing probabilistic knowledge in the Semantic Web. In Proceedings of the W3C Workshop on Semantic Web for Life Sciences, 2004. [28] R. Giugno and T. Lukasiewicz. P-SHOQ(D): A probabilistic extension of SHOQ(D) for probabilistic ontologies in the Semantic Web. In Proceedings JELIA-2002, volume 2424 of LNCS, pages 86–97. Springer, 2002. [29] N. Guarino. Formal ontology, conceptual analysis and knowledge representation. Int. J. Hum.-Comput. Stud., 43(5–6):625–640, 1995. [30] V. Haarslev and R. M¨ ller. RACER system description. In Proceedings IJCAR-2001, volume 2083 of LNCS, o pages 701–706. Springer, 2001. [31] R. H¨ hnle. Many-valued logics and mixed integer programming. Ann. Math. Artif. Intell., 12(3–4):231–263, a 1994. [32] R. H¨ hnle. Advanced many-valued logics. In D. M. Gabbay and F. Guenthner, editors, Handbook of Philoa sophical Logic, 2nd Edition, volume 2. Kluwer, Dordrecht, Holland, 2001. [33] T. Hailperin. Sentential Probability Logic: Origins, Development, Current Status, and Technical Applications. Associated University Presses, London, UK, 1996. [34] P. H? jek. Metamathematics of Fuzzy Logic. Kluwer, 1998. a [35] P. H? jek. Making fuzzy description logics more expressive. Fuzzy Sets and Systems, 154(1):1–15, 2005. a [36] P. H? jek. What does mathematical fuzzy logic offer to description logic? In E. Sanchez, editor, Capturing a Intelligence: Fuzzy Logic and the Semantic Web. Elsevier, 2006.

INFSYS RR 1843-06-07

27

[37] P. Hansen, B. Jaumard, G.-B. D. Nguets? , and M. P. de Arag? o. Models and algorithms for probabilistic and e a Bayesian logic. In Proceedings IJCAI-1995, pages 1862–1868. Morgan Kaufmann, 1995. [38] J. Heinsohn. Probabilistic description logics. In Proceedings UAI-1994, pages 311–318. Morgan Kaufmann, 1994. [39] M. Holi and E. Hyv¨ nen. A method for modeling uncertainty in Semantic Web taxonomies. In Proceedings o WWW-2004, pages 296–297. ACM Press, 2004. [40] M. Holi and E. Hyv¨ nen. Modeling degrees of conceptual overlap in Semantic Web ontologies. In Proceedings o URSW-2005, pages 98–99, 2005. [41] S. H¨ lldobler, T. D. Khang, and H.-P. St¨ rr. A fuzzy description logic with hedges as concept modi?ers. In o o Proceedings InTech/VJFuzzy-2002, pages 25–34, 2002. [42] S. H¨ lldobler, N. H. Nga, and T. D. Khang. The fuzzy description logic ALC F LH . In Proceeedings DL-2005, o 2005. [43] S. H¨ lldobler, H.-P. St¨ rr, and T. D. Khang. The fuzzy description logic ALCF H with hedge algebras as o o concept modi?ers. Journal of Advanced Computational Intelligence and Intelligent Informatics, 7(3):294–305, 2003. [44] S. H¨ lldobler, H.-P. St¨ rr, and T. D. Khang. The subsumption problem of the fuzzy description logic ALCF H . o o In Proceedings IPMU-2004, pages 243–250, 2004. [45] B. Hollunder. An alternative proof method for possibilistic logic and its application to terminological logics. Int. J. Approx. Reasoning, 12(2):85–109, 1995. [46] I. Horrocks. Using an expressive description logic: FaCT or ?ction? In Proceedings KR-1998, pages 636–649. Morgan Kaufmann, 1998. [47] I. Horrocks and P. Patel-Schneider. Reducing OWL entailment to description logic satis?ability. J. Web Sem., 1(4):345–357, 2004. [48] I. Horrocks and P. F. Patel-Schneider. Reducing OWL entailment to description logic satis?ability. In Proceedings ISWC-2003, volume 2870 of LNCS, pages 17–29, 2003. [49] I. Horrocks, P. F. Patel-Schneider, and F. van Harmelen. From SHIQ and RDF to OWL: The making of a web ontology language. J. Web Sem., 1(1):7–26, 2003. [50] I. F. Ilyas, W. G. Aref, and A. K. Elmagarmid. Supporting top-k join queries in relational databases. In Proceedings VLDB-2003, pages 754–765. Morgan Kaufmann, 2003. [51] M. Jaeger. Probabilistic reasoning in terminological logics. In Proceedings KR-1994, pages 305–316. Morgan Kaufmann, 1994. [52] M. Jaeger. Probabilistic role models and the guarded fragment. In Proceedings IPMU-2004, pages 235–242, 2004. Extended version in International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 14(1), 43–60, 2006. [53] B. Jaumard, P. Hansen, and M. P. de Arag? o. Column generation methods for probabilistic logic. ORSA J. a Comput., 3:135–147, 1991. [54] D. Kang, B. Xu, J. Lu, and Y. Li. Reasoning for a fuzzy description logic with comparison expressions. In Proceeedings DL-2006, 2006. [55] D. Koller, A. Levy, and A. Pfeffer. P-C LASSIC: A tractable probabilistic description logic. In Proceedings AAAI-1997, pages 390–397. AAAI Press / MIT Press, 1997. [56] S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artif. Intell., 14(1):167–207, 1990. [57] D. Lehmann. Another perspective on default reasoning. Ann. Math. Artif. Intell., 15(1):61–82, 1995. [58] H. J. Levesque and R. J. Brachman. Expressiveness and tractability in knowledge representation and reasoning. Computational Intelligence, 3:78–93, 1987.

28

INFSYS RR 1843-06-07

[59] C. Li, K. C.-C. Chang, I. F. Ilyas, and S. Song. RankSQL: Query algebra and optimization for relational top-k queries. In Proceedings ACM SIGMOD-2005, pages 131–142. ACM Press, 2005. [60] Y. Li, B. Xu, J. Lu, and D. Kang. Discrete tableau algorithms for SHI. In Proceeedings DL-2006, 2006. [61] Y. Li, B. Xu, J. Lu, D. Kang, and P. Wang. Extended fuzzy description logic ALCN. In Proceedings KES-2005, volume 3684 of LNCS, pages 896–902. Springer, 2005. [62] Y. Li, B. Xu, J. Lu, D. Kang, and P. Wang. A family of extended fuzzy description logics. In Proc. COMPSAC2005, pages 221–226. IEEE Computer Society, 2005. [63] C.-J. Liau and Y. Y. Yao. Information retrieval by possibilistic reasoning. In Proceedings DEXA-2001, volume 2113 of LNCS, pages 52–61. Springer, 2001. [64] O. Liu, Q. Tian, and J. Ma. A fuzzy description logic approach to model management in R&D project selection. In Proceedings PACIS-2004, 2004. [65] T. Lukasiewicz. Local probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events. Int. J. Approx. Reasoning, 21(1):23–61, 1999. [66] T. Lukasiewicz. Probabilistic deduction with conditional constraints over basic events. J. Artif. Intell. Res., 10:199–241, 1999. [67] T. Lukasiewicz. Probabilistic logic programming under inheritance with overriding. In Proceedings UAI-2001, pages 329–336. Morgan Kaufmann, 2001. [68] T. Lukasiewicz. Probabilistic logic programming with conditional constraints. ACM Trans. Comput. Log., 2(3):289–339, 2001. [69] T. Lukasiewicz. Probabilistic default reasoning with conditional constraints. Ann. Math. Artif. Intell., 34(1– 3):35–88, 2002. [70] T. Lukasiewicz. Weak nonmonotonic probabilistic logics. Artif. Intell., 168(1–2):119–161, 2005. [71] T. Lukasiewicz. Probabilistic description logics for the Semantic Web. Technical Report INFSYS RR-184306-04, Institut f¨ r Informationssysteme, Technische Universit¨ t Wien, June 2006. Submitted for journal publiu a cation. [72] C. Lutz. Reasoning with concrete domains. In Proceedings IJCAI-1999, pages 90–95. Morgan Kaufmann, 1999. [73] C. Lutz. Description logics with concrete domains — A survey. In P. Balbiani, N.-Y. Suzuki, F. Wolter, and M. Zakharyaschev, editors, Advances in Modal Logics, volume 4. King’s College Publications, 2003. [74] C. Lutz. NEXP TIME-complete description logics with concrete domains. ACM Trans. Comput. Logic, 5(4):669–705, 2004. [75] T. Mantay, R. M¨ ller, and A. Kaplunova. Computing probabilistic least common subsumers in description o logics. In Proceedings KI-1999, volume 1701 of LNCS, pages 89–100. Springer, 1999. [76] C. Meghini, F. Sebastiani, and U. Straccia. Designing effective retrieval engines for multimedia document repositories. In AI*IA 1996 Workshop on Access, Extraction and Integration of Knowledge, pages 67–70, 1996. [77] C. Meghini, F. Sebastiani, and U. Straccia. Reasoning about form, content and uncertainty for multimedia document retrieval. In Proceedings of the 2nd International Workshop on Logic and Uncertainty in Information Retrieval, pages 57–58, 1996. [78] C. Meghini, F. Sebastiani, and U. Straccia. Modelling the retrieval of structured documents containing texts and images. In Proceedings ECDL-1997, volume 1324 of LNCS, pages 325–344. Springer, 1997. [79] C. Meghini, F. Sebastiani, and U. Straccia. The terminological image retrieval model. In Proceedings ICIAP1997, volume 1311 of LNCS, pages 156–163. Springer, 1997. [80] C. Meghini, F. Sebastiani, and U. Straccia. A system for the fast prototyping of multidimensional image retrieval. In Proceedings IEEE ICMCS-1999, volume 2, pages 603–609. IEEE Computer Society, 1999.

INFSYS RR 1843-06-07

29

[81] C. Meghini, F. Sebastiani, and U. Straccia. A model of multimedia information retrieval. J. ACM, 48(5):909– 970, 2001. [82] C. Meghini, F. Sebastiani, U. Straccia, and C. Thanos. A model of information retrieval based on a terminological logic. In Proceedings ACM SIGIR-1993, pages 298–307. ACM Press, 1993. [83] C. Meghini and U. Straccia. A relevance terminological logic for information retrieval. In Proceedings ACM SIGIR-1996, pages 197–205. ACM Press, 1996. [84] P. Mitra, N. F. Noy, and A. Jaiswal. OMEN: A probabilistic ontology mapping tool. In Proceedings ISWC-2005, volume 3729 of LNCS, pages 537–547. Springer, 2005. [85] N. J. Nilsson. Probabilistic logic. Artif. Intell., 28(1):71–88, 1986. [86] H. Nottelmann and N. Fuhr. Adding probabilities and rules to OWL Lite subsets based on probabilistic Datalog. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 14(1):17–42, 2006. [87] V. Nov? k. Which logic is the real fuzzy logic? Fuzzy Sets and Systems, 157(5):635–641, 2005. a [88] R. Pan, Z. Ding, Y. Yu, and Y. Peng. A Bayesian network approach to ontology mapping. In Proceedings ISWC-2005, volume 3729 of LNCS, pages 563–577. Springer, 2005. [89] B. Parsia, E. Sirin, M. Grove, and R. Alford. Pellet. Available at www.mindswap. org/2003/pellet/. [90] M. Pool and J. Aikin. KEEPER and Prot? g? : An elicitation environment for Bayesian inference tools. In e e Proceedings of the Workshop on Prot? g? and Reasoning held at the 7th International Prot? g? Conference, e e e e 2004. [91] D. Sanchez and A. Tettamanzi. Generalizing quanti?cation in fuzzy description logics. In Proceedings 8th Fuzzy Days in Dortmund, 2004. [92] D. Sanchez and A. Tettamanzi. Reasoning and quanti?cation in fuzzy description logics. In Fuzzy Logic and Applications, volume 3849 of LNCS, pages 81–88. Springer, 2005. [93] D. Sanchez and A. Tettamanzi. Fuzzy quanti?cation in fuzzy description logics. In E. Sanchez, editor, Capturing Intelligence: Fuzzy Logic and the Semantic Web. Elsevier, 2006. [94] M. Schmidt-Schau? and G. Smolka. Attributive concept descriptions with complements. Artif. Intell., 48(1):1– 26, 1991. [95] G. Stoilos, G. Stamou, V. Tzouvaras, J. Pan, and I. Horrocks. Fuzzy OWL: Uncertainty and the Semantic Web. In Proceedings of the International Workshop of OWL: Experiences and Directions, 2005. [96] G. Stoilos, G. Stamou, V. Tzouvaras, J. Z. Pan, and I. Horrock. A fuzzy description logic for multimedia knowledge representation. In Proceedings of the International Workshop on Multimedia and the Semantic Web, 2005. [97] G. Stoilos, G. B. Stamou, V. Tzouvaras, J. Z. Pan, and I. Horrocks. The fuzzy description logic f -SHIN . In Proceedings URSW-2005, pages 67–76, 2005. [98] G. Stoilos, U. Straccia, G. Stamou, and J. Pan. General concept inclusions in fuzzy description logics. In Proceedings ECAI-2006, pages 457–461. IOS Press, 2006. [99] U. Straccia. Document retrieval by relevance terminological logics. In Proceedings MIRO-1995, Workshops in Computing. BCS, 1995. [100] U. Straccia. A fuzzy description logic. In Proceedings AAAI-1998, pages 594–599. AAAI Press / MIT Press, 1998. [101] U. Straccia. Foundations of a Logic based approach to Multimedia Document Retrieval. PhD thesis, Department of Computer Science, University of Dortmund, Dortmund, Germany, June 1999. [102] U. Straccia. A framework for the retrieval of multimedia objects based on four-valued fuzzy description logics. In F. Crestani and G. Pasi, editors, Soft Computing in Information Retrieval: Techniques and Applications, pages 332–357. Physica (Springer), Heidelberg, Germany, 2000. [103] U. Straccia. Reasoning within fuzzy description logics. J. Artif. Intell. Res., 14:137–166, 2001.

30

INFSYS RR 1843-06-07

[104] U. Straccia. Transforming fuzzy description logics into classical description logics. In Proceedings JELIA2004, volume 3229 of LNCS, pages 385–399. Springer, 2004. [105] U. Straccia. Uncertainty in description logics: A lattice-based approach. In Proceedings IPMU-2004, pages 251–258, 2004. [106] U. Straccia. Description logics with fuzzy concrete domains. In Proceedings UAI-2005, pages 559–567. AUAI Press, 2005. [107] U. Straccia. Fuzzy ALC with fuzzy concrete domains. In Proceeedings DL-2005, pages 96–103, 2005. [108] U. Straccia. Fuzzy description logics with concrete domains. Technical Report 2005-TR-03, Istituto di Scienza e Tecnologie dell’Informazione, Consiglio Nazionale delle Ricerche, Pisa, Italy, 2005. [109] U. Straccia. Towards a fuzzy description logic for the Semantic Web (preliminary report). In Proceedings ESWC-2005, volume 3532 of LNCS, pages 167–181. Springer, 2005. [110] U. Straccia. Answering vague queries in fuzzy DL-Lite. In Proceedings IPMU-2006, pages 2238–2245, 2006. [111] U. Straccia. Description logics over lattices. International Journal of Uncertainty, Fuzziness and KnowledgeBased Systems, 14(1):1–16, 2006. [112] U. Straccia. A fuzzy description logic for the Semantic Web. In E. Sanchez, editor, Fuzzy Logic and the Semantic Web, Capturing Intelligence, chapter 4, pages 73–90. Elsevier, 2006. [113] U. Straccia. Fuzzy description logic programs. In Proceedings IPMU-2006, pages 1818–1825, 2006. [114] U. Straccia. Towards top-k query answering in deductive databases. In Proceedings IEEE SMC-2006. IEEE Computer Society, 2006. [115] U. Straccia. Towards top-k query answering in description logics: The case of DL-Lite. In Proc. JELIA-2006, volume 4160 of LNCS, pages 439–451. Springer, 2006. [116] U. Straccia. Uncertainty and description logic programs over lattices. In E. Sanchez, editor, Fuzzy Logic and the Semantic Web, Capturing Intelligence, chapter 7, pages 115–133. Elsevier, 2006. [117] C. Thomas and A. Sheth. On the expressiveness of the languages for the Semantic Web — Making a case for “A little more”. In E. Sanchez, editor, Fuzzy Logic and the Semantic Web, Capturing Intelligence, pages 3–20. Elsevier, 2006. [118] C. Tresp and R. Molitor. A description logic for vague knowledge. In Proceedings ECAI-1998, pages 361–365. J. Wiley & Sons, 1998. [119] O. Udrea, Y. Deng, E. Hung, and V. S. Subrahmanian. Probabilistic ontologies and relational databases. In Proceedings CoopIS/DOA/ODBASE-2005, volume 3760 of LNCS, pages 1–17. Springer, 2005. [120] W3C. OWL web ontology language overview, 2004. W3C Recommendation (10 Feb. 2004). Available at www.w3.org/TR/2004/REC-owl-features-20040210/. [121] G. Weikum, J. Graupmann, R. Schenkel, and M. Theobald. Towards a statistically Semantic Web. In Proceedings ER-2004, volume 3288 of LNCS, pages 3–17. Springer, 2004. [122] Y. Yang and J. Calmet. OntoBayes: An ontology-driven uncertainty model. In Proceedings IAWTIC-2005, pages 457–463. IEEE Press, 2005. [123] P. M. Yelland. An alternative combination of Bayesian networks and description logics. In Proceedings KR2000, pages 225–234. Morgan Kaufmann, 2000. [124] J. Yen. Generalizing term subsumption languages to fuzzy logic. In Proceedings IJCAI-1991, pages 472–477. Morgan Kaufmann, 1991. [125] L. A. Zadeh. Fuzzy sets. Information and Control, 8(3):338–353, 1965.

- An overview of tableau algorithms for description logics
- PROBABILISTIC DESCRIPTION LOGICS FOR THE SEMANTIC WEB
- An Intelligent Database Application for the Semantic Web
- Approaches to Semantic Web Services An Overview and Comparisons
- Well-founded semantics for description logic programs in the semantic web
- What is an Analogue for the Semantic Web and Why is Having One Important 1
- Semantic Web Technologies Executive Overview
- Reflections on Modelling Vagueness in Description Logics
- COMBINING ANSWER SET PROGRAMMING WITH DESCRIPTION LOGICS FOR THE SEMANTIC WEB
- An Introduction to Description Logics
- A uniform framework for concept definitions in description logics
- Handling imprecise knowledge with fuzzy description logics
- latex模板
- ctex Latex 论文写作利器
- the semantic features of literature

更多相关文章：
更多相关标签：