key: cord-0780021-6dcghdxf
authors: Jiang, Yuncheng; Wang, Ju; Tang, Suqin; Xiao, Bao
title: Reasoning with rough description logics: An approximate concepts approach
date: 2009-02-15
journal: Inf Sci (N Y)
DOI: 10.1016/j.ins.2008.10.021
sha: 166a625e1b2d7cc35462c02d6b3dd4a1a15e14dd
doc_id: 780021
cord_uid: 6dcghdxf

The current research progress and the existing problems of uncertain or imprecise knowledge representation and reasoning in description logics are analyzed in this paper. Approximate concepts are introduced to description logics based on rough set theory, and a kind of new rough description logic [Formula: see text] (rough description logic based on approximate concepts) is proposed based on approximate concepts. The syntax, semantics and properties of the [Formula: see text] are given. It is proved that the approximate concept satisfiability (definitely satisfiability and possibly satisfiability) reasoning problem and approximate concepts rough subsumption reasoning problem w.r.t. rough TBox in [Formula: see text] may be reduced to the concept satisfiability reasoning problem in (almost) standard ALC (the description logic that provides the Boolean concept constructors plus the existential and universal restriction constructors). The works of this paper provide logic foundations for approximate ontologies and theoretical foundations for reasoning algorithms of more expressive rough description logics including approximate concepts, number restrictions, nominals, inverse roles and role hierarchies.

Description Logics (DLs) [3] are a class of knowledge representation formalisms in the tradition of semantic networks and frames, which can be used to represent the terminological knowledge of an application domain in a structured and formally well-understood way. DL systems provide their users with inference services (like computing the subsumption hierarchy) that deduce implicit knowledge from the explicitly represented knowledge. They are employed in various application domains, such as semantic Web [21, 39] , ontologies [1] , databases [6, 19] , and software engineering [4] . Because classical DLs [3] can only represent and reason on certain or precise knowledge, and cannot represent and reason on uncertain or imprecise knowledge, therefore, some researchers extend classical DLs allowing to express uncertain or imprecise knowledge. At this aspect, three kinds of description logics, i.e., fuzzy DLs, probabilistic DLs, and rough DLs, are proposed.

In what follows, we will use several DLs, hence it is necessary to introduce some notations of DLs firstly. The DL that provides the Boolean concept constructors plus the existential and universal restriction constructors is called ALC [38] , where the Boolean concept constructors are, apart from concept disjunction, concept conjunction and concept negation. In addition to the Booleans, and existential and universal restriction constructors, DLs typically provide concept constructors that form complex concepts. The basic constructors of this kind are qualified number restrictions, unqualified number restrictions, functional number restrictions, nominals, concrete domain [3] . More expressive DLs can be obtained by extending ALC with new concept constructors. For example, the logic obtained from ALC by providing qualified number restrictions is called 0020-0255/$ -see front matter Ó 2008 Elsevier Inc. All rights reserved. doi:10.1016/j.ins.2008. 10.021 ALCQ. On the other hand, adding unqualified, functional number restrictions, nominals, and concrete domains to ALC results in the logics ALCN, ALCF, ALCO, and ACL(D), respectively. Furthermore, besides concept constructors, DLs may provide a set of role constructors such as inversion and transitive closure operator. The logics that extend ALC with inversion and transitive closure operator are called ALCI and ALC + , respectively. In ALC the RBox is required to be empty. Therefore, one way to provide new useful expressivity is to allow different sorts of axioms such as transitivity axioms and role inclusion axioms in the RBox. The extensions of ALC with transitive roles and role inclusion axioms are called ALCR + and ALCH, respectively. The logic ALCHR + is commonly known as SH. The different extensions of SH are commonly denoted by appending the corresponding calligraphic letter (I for role inversion, O for nominals, D for concrete domains, F, N, Q for functional, unqualified and qualified number restrictions, respectively) to the name of the logic. For instance, the extension of SH with inverse roles, nominals, qualified number restrictions and concrete domains is known as SHOIQ(D).

Regarding fuzzy DLs, Straccia [42] presented a fuzzy extension of the description logic ALC (FALC) [38] , combining Zadeh's fuzzy logic [47] [48] [49] with a classical DL. Li et al. [24] presented an extended fuzzy description logic with number restrictions EFALCN (extended fuzzy attributive concept description language with complements and unqualified number restrictions). Stoilos et al. [41] presented fuzzy extensions of description logics SI and SHIN (FSI and FSHIN). Jiang et al. presented fuzzy extensions of description logics ALNUI and SHOIQ (FLNUI [18, 20] and FSHOIQ [17] ). Moreover, all of these fuzzy DLs have the corresponding constraint propagation based tableaux reasoning algorithms.

Regarding probabilistic DLs, Heinsohn [12] presented a probabilistic extension of the description logic ALC [38] , which allows to represent terminological probabilistic knowledge about concepts and roles. Jaeger [16] proposed another probabilistic extension of the description logic ALC [38] , which allows for terminological and assertional probabilistic knowledge about role instances. The work by Koller et al. [23] gave a probabilistic generalization of the CLASSIC description logic, and it is based on inference in Bayesian networks as underlying probabilistic reasoning formalism. Lukasiewicz [28] presented the probabilistic extensions of description logics SHIF(D) and SHOIN(D) (PSHIF(D) and PSHOIN(D)), and gave their reasoning algorithms. PSHIF(D) and PSHOIN(D) allow for expressing rich terminological probabilistic knowledge about concepts and roles as well as assertional probabilistic knowledge about instances of concepts and roles.

Regarding rough DLs, Schlobach et al. [37] introduced the lower and upper approximations based on rough set theory [31] [32] [33] [34] [35] to classical description logics, and presented the rough description logic RDL, where RDL includes universal and existential quantifications, and symmetric, transitive and reflexive roles.

From above-mentioned statements, we know that rough DLs hang behind fuzzy DLs and probabilistic DLs, because the most expressive fuzzy description logic FSHOIQ [17] is the fuzzy extension of description logic SHOIQ [14] , and the most expressive probabilistic description logic PSHOIN(D) [28] is the probabilistic extension of the description logic SHOIN(D) [13] . However, the rough description logic RDL [37] only includes universal and existential quantifications, and symmetric, transitive and reflexive roles, and cannot deal with number restrictions, nominals, inverse roles and role hierarchies. We will study rough DLs in this paper.

In rough description logic RDL [37] , for every concept C 2 RDL, the corresponding lower approximation C and upper approximation C also are concepts of RDL, i.e., C, C 2 RDL. Moreover, C and C are two different separate concepts, that is to say, C and C are not be integrated into a uniform approximate concept hC; Ci. However, it is well-known that when it is impossible to formally define a concept C, we can often make use of the approximations (the lower approximation C and the upper approximation CÞ together, i.e., approximate concept (or rough set) hC; Ci, to express the concept C in a precise way with explicit formal semantics, in other words, only single lower approximation C or upper approximation C cannot express the concept C in a precise way. Therefore, it is necessary to propose a kind of new reasoning algorithm of rough description logics based on approximate concepts (not single lower approximation or upper approximation). On the other hand, approximate concept corresponds to the notion of rough set in rough set theory [31] [32] [33] [34] [35] , as a uniform concept, approximate concept is applied in ontologies, i.e., approximate concepts based approximate ontologies are presented [8] . It is well-known that description logics are the logic foundations of Web ontology language [2] , i.e., the Web ontology languages are equivalent to description logics in theory. For example, the Web ontology language OWL Lite and OWL DL have a formal semantics and a reasoning support through a mapping to the expressive description logics SHIF(D) and SHOIN(D), respectively, [13] . Comparing with the classical ontologies [10] , there exist same problem in approximate ontologies [8] : what are the logic foundations (or reasoning algorithms) of approximate ontologies? Naturally, we also need a kind of reasoning algorithm of rough description logics based on approximate concepts. That is to say, approximate concepts must be introduced to description logics from a theoretical point of view. The present work may be considered as an attempt in this direction.

The structure of the rest of this paper is as follows. Section 2 briefly introduces requisite notions of description logics and rough set theory. In Section 3, rough description logic RDL AC is proposed based on approximate concepts, and the syntax, semantics, properties, and reasoning algorithms of RDL AC are given. Next, Section 4 will point out related work on rough description logics, and approximate ontologies. Finally, in Section 5, we draw the conclusion and present some topics for future research.

In the current section we will briefly introduce the notions of description logics and rough set theory, recalling some mathematical properties of rough sets theoretic operators.

DLs [3, 37] are a well-studied family of set-description languages which usually come with (some or all) Boolean operators and limited quantification, and which can be extended with additional functionality in a modular way. This way properties on relations (such as symmetry, transitivity or inclusion hierarchies), number restrictions, or even some form of data-types (concrete domains [29] ) are often included. DLs have a well-defined model-theoretic semantics, and the last two decades the computational properties of a wide variety of DLs have been studied. Intuitively, description logics model a domain of interest in terms of concepts and roles, which represent classes of individuals resp. binary relations on classes on individuals.

Formally, we introduce the DL ALC [38] , which is a significant representative of DLs. The general definition of approximations (lower approximation and upper approximation), however, will be independent of any particular DL.

We assume three alphabets of symbols, called primitive concepts (denoted by A, possibly with a subscript), primitive roles (denoted by R, possibly with a subscript) and individuals (denoted by a and b, possibly with a subscript).

A concept (denoted by C and D, possibly with a subscript) of the language ALC is built out of primitive concepts according to the following syntax rules: C; D ! >j ? jAj:CjC u DjC t Dj9R Á Cj8R Á Cj:

These constructs are not all independent. The following equalities hold: > ¼ A t :A, ?¼ :>, C u D ¼ :ð:C t :DÞ, and The interpretation function I is extended to complex concepts of ALC (note that in ALC roles are always atomic) as follows:

Á CÞ I ¼ fx 2 D I j9y 2 D I ; hx; yi 2 R I^y 2 C I g; ð8R Á CÞ I ¼ fx 2 D I j 8y 2 D I ; hx; yi 2 R I ! y 2 C I g.

In a terminology TB (called TBox) the interpretations of concepts can be restricted to the models of TB by axioms of the form C v D or C D. Based on this model-theoretic semantics, concepts can be checked for unsatisfiability: whether they are necessarily interpreted as the empty set. Another useful semantic implication is subsumption of two concepts C and D (a subset relation C I and D I w.r.t. all models I of TB) denoted by TB C v D.

A knowledge base KB ¼ hTB; ABi extends a TBox TB with an assertional component (usually called ABox) AB, which is a set of assertions C(a) and R(a, b) for individual names a, b, a relation R and a concept C. The semantics is a straightforward extension of the previous definition: an interpretation I is a model for a assertion C(a) and R(a, b) if, and only, a I 2 C I and ða I ; b I Þ 2 R I . Then, a knowledge base is consistent, if there is a model for both its TBox and ABox.

The theory of rough set is an extension of set theory, in which a subset of a universe is described by a pair of ordinary sets called the lower and upper approximations [31] [32] [33] [34] [35] . The successful applications of the rough set theory in a variety of problems have amply demonstrated its usefulness and versatility [46] .

In what follows, let us introduce the notion of rough set theory formally. Let U denote a finite and non-empty set called the universe, and let R # U Â U denote an equivalence relation on U. The pair apr ¼ ðU; RÞ is called an approximation space. The equivalence relation R partitions the set U into disjoint subsets. Such a partition of the universe is denoted by U=R. If two elements x, y in U belong to the same equivalence class, we say that x and y are indistinguishable. The equivalence class of R and the empty set / are called the elementary or atomic sets in the approximation space apr ¼ ðU; RÞ.

Given an arbitrary set A # U, it may be impossible to describe A precisely using the equivalence classes of R. In this case, one may characterize A by a pair of lower and upper approximations

Where ½x R ¼ fyjxRyg is the equivalence class containing x. The pair ðaprðAÞ; aprðAÞÞ is called the rough set with respect to A. The lower approximation aprðAÞ is the union of all the elementary sets which are subsets of A, and the upper approximation aprðAÞ is the union of all the elementary sets which have a non-empty intersection with A. An element in the lower approximation necessarily belongs to A, while an element in the upper approximation possibly belongs to A. For any subsets A, B # U, the lower approximation apr satisfies the following properties:

(AL9) aprðAÞ # aprðaprðAÞÞ; (AL10) aprðAÞ # aprðaprðAÞÞ.

And the upper approximation apr satisfies the following properties:

Where $ A ¼ U À A denotes the set complement of A. Moreover, the lower and upper approximations obey the following properties:

aprð$ A [ BÞ # $ aprðAÞ [ aprðBÞ; (ALU) aprðAÞ # aprðAÞ.

In this section, we introduce a rough extension of classical DLs, i.e., we propose the rough description logic RDL AC . In Section 3.1, we will introduce the syntax and approximate concepts (or rough sets) of RDL AC . Next, Section 3.2 will present the semantics and properties of RDL AC . Finally, in Section 3.3, we will give the approximate concept satisfiability and approximate concepts subsumption reasoning algorithms of RDL AC .

Approximate concepts (or rough sets) based rough description logic RDL AC is not restricted to a particular classical description logic, and will be defined for an arbitrary description logic. For the sake of simplicity, we restrict ourselves to classical description logic ALC [38] in the following. That is to say, rough description logic RDL AC is a rough extension of classical description logic ALC. Therefore, the syntax of RDL AC is the extension of the syntax of ALC, i.e., RDL AC concepts (denoted by C or D, possibly with a subscript) are composed inductively according to the following abstract syntax:

where A denotes atomic concept, C and D denote concepts, R denotes role name.

Example 1 (Sepsis Example [37] ). Sepsis is a disease in which the immune system of the patient overreacts to an infection. Due to this reaction the patient becomes severely ill, which easily results in organ failure and eventually death. The cause and underlying cellular pathways of this disease are unclear, which hinders the precise characterization of the sepsis patient. Therefore, a consensus definition of sepsis was established in 1992 to define several stages of sepsis [5] . This definition does not provide a precise definition of sepsis, but gives the criteria for which there was a consensus that they should at least hold for a patient with sever sepsis. These criteria are called as Bone criteria. Patients who accord with Bone criteria may have sepsis, however, this is not necessarily the case. We refer to these patients as being possibly septic. On the other hand, we can define a group of patients that are septic for sure, namely those who fulfill the Bone criteria and have severe multiple organ failure. We refer to these patients as the definitely septic patients and define them as fulfilling the strict criteria.

The following concepts all are concepts of RDL AC :

Septic; Septic; 9diag Á Septic; 9diag Á Septic; 8diag Á ðSeptic [ :SepticÞ:

For any concept C of RDL AC , the pair hC; Ci is called approximate concept w.r.t. C. For example, hSeptic; Septici is an approximate concept w.r.t. Septic. In fact, an approximate concept corresponds to the notion of rough set in rough set theory [31] [32] [33] [34] [35] .

Example 2 (SARS Example). Severe acute respiratory syndrome (or SARS for short) is a respiratory disease in humans which is caused by the SARS coronavirus. The definition of SARS can not be expressed precisely. According to the clinic diagnosis criteria for SARS which was released by the Ministry of Health of the People's Republic of China [25] , there are mainly two kinds of diagnosis criteria for SARS: suspected diagnostic criteria and clinically diagnosed criteria. Obviously, the patients who accord with suspected diagnostic criteria may have SARS, however, this is not necessary the case. Here, we can define the patients who accord with suspected diagnostic criteria as the upper approximation concept of SARS (denoted by SARS).

The patients who accord with clinically diagnosed criteria must have SARS. Here, we can define the patients who accord with clinically diagnosed criteria as the lower approximation concept of SARS (denoted by SARS). Therefore, the approximate concept SARS is a pair hSARS; SARSi, namely, SARS ¼ hSARS; SARSi. Based on the approximate concept hSARS; SARSi, we can further construct the description logic knowledge base about SARS in a precise way with explicit formal semantics.

Since the syntax of RDL AC is the extension of the syntax of classical description logics [3] , therefore, the semantics of rough description logic RDL AC is also the extension of the semantics of classical description logics correspondingly, i.e., the lower approximation concept, the upper approximation concept, and approximate concepts must be interpreted in RDL AC , thus a new binary relation over D I needs to be introduced.

From a semantic point of view, concepts are interpreted as subsets of an abstract domain, while roles are interpreted as binary relations over such a domain. Formally, a rough interpretation I ¼ ðD I ; R $ ; I Þ consists of a domain of interpretation D I , a binary relation R $ over D I , and an interpretation function I , which maps every atomic concept A to a subset of D I and every atomic role R to a subset of D I Â D I .

The interpretation function I is extended to complex concepts of RDL AC as follows (note that in RDL AC roles are always atomic):

Á CÞ I ¼ fx 2 D I j9y 2 D I ; hx; yi 2 R I^y 2 C I g ¼ fx 2 D I jR I ðxÞ \ C I -/g; ð8R Á CÞ I ¼ fx 2 D I j8y 2 D I ; hx; yi 2 R I ! y 2 C I g ¼ fx 2 D I jR I ðxÞ # C I g;

Where R $ is an equivalence relation over D I , R I ðxÞ ¼ fy 2 D I jhx; yi 2 R I g, R $ ðxÞ ¼ fy 2 D I jhx; yi 2 R $ g.

Intuitively, the upper approximation of a concept C covers the elements of a domain with the typical properties of C, whereas the lower approximation contains the prototypical elements of C. Remark 1. Since the concepts of RDL AC are the same as that of RDL [37] , so the interpretation function I of RDL AC is the same as that of the RDL. In what follows, we introduce the semantics interpretation of approximate concepts.

According to the definition of approximate concept, it is easy to know that the interpretation function I should map every approximate concept AC ¼ hC; Ci to a pair over D I , i.e., the interpretation function I is extended to approximate concept AC ¼ hC; Ci of RDL AC as follows: AC I ¼ ðhC; CiÞ I ¼ hðCÞ I ; ðCÞ I i:

For any approximate concepts AC ¼ hC; Ci and AD ¼ hD; Di, according to the properties of the lower approximation and upper approximation (see Section 2.2), it is easy to know that

Therefore, we may roughly recognize that hC u D; C u Di and hC t D; C t Di are also approximate concepts w.r.t. C u D and C t D, respectively, where ðhC u D; C u DiÞ I ¼ hðC u DÞ I ; ðC u DÞ I i ¼ hðCÞ I u ðDÞ I ; ðCÞ I u ðDÞ I i; ðhC t D; C t DiÞ I ¼ hðC t DÞ I ; ðC t DÞ I i ¼ hðCÞ I t ðDÞ I ; ðCÞ I t ðDÞ I i:

Obviously, if concept C is a precise concept, then for any rough interpretation I, we have ðCÞ I ¼ ðCÞ I ¼ C I . Here the approximate concept hC; Ci may be denoted by hC; Ci.

A rough TBox of RDL AC consists of a finite (possibly empty) set of rough assertions. In order to be as general as possible, we assume that every rough assertion has the form a rough inclusion assertion (or simply rough inclusion)

AC v AD or hC; Ci v hD; Di without any restriction on the form of the approximate concepts AC ¼ hC; Ci and AD ¼ hD; Di. A pair of rough inclusions of the form fAC v AD; AD v ACg is often written as AC AD or hC; Ci hD; Di and is called rough equivalence assertion.

An approximate concept AC ¼ hC; Ci in RDL AC is definitely satisfiable iff there exists a rough interpretation I such that We say that an approximate concept AD ¼ hD; Di rough subsumes an approximate concept AC ¼ hC; Ci (or an approximate concept AC ¼ hC; Ci is rough subsumed by an approximate concept AD ¼ hD; Di) w.r.t. TB, written TB C v D, iff for every rough model I of TB, ðCÞ I # ðDÞ I and ðCÞ I # ðDÞ I . An approximate concept AC ¼ hC; Ci is rough equivalent to an approximate concept AD ¼ hD; Di w.r.t. TB, written TB AC AD, iff for every rough model I of TB, ðCÞ I ¼ ðDÞ I and ðCÞ I ¼ ðDÞ I .

Regarding the reasoning problems in RDL AC , it is the same as that of classical description logics, i.e., we only consider the approximate concept satisfiability (definitely satisfiability and possibly satisfiability) reasoning and approximate concepts rough subsumption reasoning in RDL AC . About the approximate concepts implication reasoning of the form AC ! AD or hC; Ci ! hD; Di;

where AC ¼ hC; Ci and AD ¼ hD; Di are two approximate concepts, ? is an implication such as Heyting implication, we do not consider this case which corresponds the implication of rough sets in rough set logic [9, 15] , because:

(1) In DLs (including most extended DLs such as fuzzy DLs, probabilistic DLs and rough DLs), implication reasoning is not considered in general. Subsumption reasoning instead of implication reasoning is often studied. In fact, subsumption reasoning is a special case of implication reasoning. (2) If we consider the implication w.r.t. a rough TBox TB in RDL AC , the implication (entailment) can be defined as follows:

A rough TBox TB entails a rough inclusion AC v AD (denoted by TB AC v AD) iff every rough model of TB also satisfies AC v AD.

It is easy to know that the entailment in RDL AC is similar to that of fuzzy DLs [41, 42] . (3) Of course, we may study the Heyting implication between approximate concepts in RDL AC (this case is similar to the 3-valued Lukasiewicz implication in the case of rough sets). However, in this case, the approximate concept satisfiability is complicated. In particular, things become more complicated when other relations than equivalence relation are considered or when intuitionist (Heyting) implication is defined between approximate concepts in RDL AC . We will study this issue in other paper in detail.

From the properties of the lower approximation and the upper approximation in rough set theory (see Section 2.2 for details), we know that the approximate concepts of RDL AC have properties as follows. Proof. (1) For any rough interpretation I, since ð?Þ I ¼ fx 2 D I j8y 2 D I ; hx; yi 2 R $ ! y 2 ? I g ¼ fx 2 D I jR $ ðxÞ # ? I g, and ? I ¼ /, then we have ð?Þ I ¼ /, so ð?Þ I ¼ ? I .

Since ð?Þ I ¼ fx 2 D I j9y 2 D I ; hx; yi 2 R $^y 2 ? I g ¼ fx 2 D I jR $ ðxÞ \ ? I -/g, and ? I ¼ /, then we have ð?Þ I ¼ /, so ð?Þ I ¼ ? I . Therefore, h?; ?i h?; ?i.

(2) For any rough interpretation I, since ð>Þ I ¼ fx 2 D I j8y 2 D I ; hx; yi 2 R $ ! y 2 > I g ¼ fx 2 D I jR $ ðxÞ # > I g, and > I ¼ D I , then we have ð>Þ I ¼ D I , so ð>Þ I ¼ > I .

Since ð>Þ I ¼ fx 2 D I j9y 2 D I ; hx; yi 2 R $^y 2 T I g ¼ fx 2 D I jR $ ðxÞ \ > I -/g, and > I ¼ D I , then we have ð>Þ I ¼ > I , so ð>Þ I ¼ > I . Therefore, h>; >i h>; >i.

(3) For any rough interpretation I, since Since ðCÞ I ¼ fx 2 D I j8y 2 D I ; hx; yi 2 R $ ! y 2 C I g ¼ fx 2 D I jR $ ðxÞ # C I g;

ðDÞ I ¼ fx 2 D I j8y 2 D I ; hx; yi 2 R $ ! y 2 D I g ¼ fx 2 D I jR $ ðxÞ # D I g;

we have ðCÞ I # ðDÞ I . Since ðCÞ I ¼ fx 2 D I j9y 2 D I ; hx; yi 2 R $^y 2 C I g ¼ fx 2 D I jR $ ðxÞ \ C I -/g; ðDÞ I ¼ fx 2 D I j9y 2 D I ; hx; yi 2 R $^y 2 D I g ¼ fx 2 D I jR $ ðxÞ \ D I -/g; [8] , an approximate ontology AO is constructed as follows (Fig. 1) .

Where elements of the domain {or, r, dr, y, g, gr} stand for colors ''orange red", ''red", ''dark red", ''yellow", ''gold" and ''golden red", respectively. Every node, i.e., every pair, in Fig. 1 is an approximate concept. For example, the pair h{dr}, {or, r, dr}i is an approximate concept. The link between approximate concepts denotes the specialization or generalization relationship. For instance, h{dr}, {or, r, dr}i is more specific than h{or, r, dr}, {or, r, dr}i (is a specialization of h{or, r, dr}, {or, r, dr}i), h{or, r, dr}, {or, r, dr}i is more general than h{dr}, {or, r, dr}i (is a generalization of h{dr}, {or, r, dr}i).

The approximate ontology AO can be translated into the following rough TBox TB of RDL AC : TB ¼ fh?; ?i v hC 1 ; C 1 i; h?; ?i v hC 2 ; C 2 i; h?; ?i v hC 3 ; C 3 i; h?; ?i v hC 4 ; C 4 i; hC 1 ; C 1 i v hC 5 ; C 5 i; hC 2 ; C 2 i v hC 5 ; C 5 i; hC 3 ; C 3 i v hC 6 ; C 6 i; hC 4 ; C 4 i v hC 6 ; C 6 i; hC 5 ; C 5 i v h>; >i; hC 6 ; C 6 i v h>; >ig;

where ? ¼ /, ? ¼ /, C 1 ¼ forg; C 1 ¼ for; r; drg; C 2 ¼ fdrg; C 2 ¼ for; r; drg; C 3 ¼ fyg; C 3 ¼ fy; g; grg; C 4 ¼ fg; grg; C 4 ¼ fg; grg; C 5 ¼ for; r; drg; C 5 ¼ for; r; drg; C 6 ¼ fy; g; grg; C 6 ¼ fy; g; grg; > ¼ for; r; dr; y; g; grg, and > ¼ for; r; dr; y; g; grg. 

The reasoning problems in rough description logic RDL AC are the same as that of classical description logics, i.e., the reasoning problems in rough description logic RDL AC mainly include approximate concept satisfiability (definitely satisfiability and possibly satisfiability) reasoning and approximate concepts rough subsumption reasoning. In this section, we provide the approximate concept satisfiability reasoning and approximate concepts rough subsumption reasoning w.r.t. rough TBox. In the following, it is proved that the approximate concept satisfiability reasoning problem and approximate concepts rough subsumption reasoning problem w.r.t. rough TBox in rough description logic RDL AC may be reduced to concept satisfiability reasoning problem in classical description logics. Therefore, the reasoning problems of satisfiability and rough subsumption of RDL AC may reason automatically by reasoning mechanism of classical description logics.

Given an arbitrary concept C in RDL AC , we define translation function t : RDL AC ! ALC from RDL AC to ALC that fulfills the following conditions, where A denotes an atomic concept, R $ denotes a new role name:

Given an arbitrary approximate concept AC ¼ hC; Ci in RDL AC , we can translate the approximate concept AC ¼ hC; Ci in RDL AC into a concept pair hðCÞ t ; ðCÞ t i in ALC using translation function t .

Given an arbitrary inclusion assertion hC; Ci v hD; Di in RDL AC , we can translate the inclusion assertion hC; Ci v hD; Di in RDL AC into inclusion assertions set fðCÞ t v ðDÞ t ; ðCÞ t v ðDÞ t g in ALC using translation function t .

Given an arbitrary rough TBox TB ¼ fhC 1 ; C 1 i v hD 1 ; D 1 i; . . . ; hC k ; C k i v hD k ; D k ig in RDL AC , we can translate the rough TBox

Obviously, if we restrict our attention to an arbitrary relation (role) R $ (not an equivalence relation) [31] [32] [33] [34] [35] , then we can delete the reflðR $ Þ; symðR $ Þ and transðR $ Þ from the TBox TB t . Here the TB t is a standard ALC TBox.

Example 5 (Sepsis Example cont'd). We can translate RDL AC rough TBox TB in Example 3 into the following (almost) standard ALC TBox TB t : TBox

Example 6 (Approximate Ontology Example cont'd). We can translate RDL AC rough TBox TB in Example 4 into the following (almost) standard ALC TBox TB t : TBox

In the following, we prove the correctness of the translation function t , i.e., we prove that the approximate concept satisfiability (definitely satisfiability and possibly satisfiability) reasoning problem and approximate concepts rough subsumption reasoning problem w.r.t. rough TBox in rough description logic RDL AC may be translated into concept satisfiability reasoning problem in (almost) standard description logic ALC. Let us introduce a preliminary theorem first.

Theorem 2 [37] . Let RDL be the rough extension of a description logic DL with universal and existential quantification, and symmetric, transitive and reflexive roles, T an RDL TBox, and t the above given translation function. An RDL concept C is satisfiable in a rough interpretation w.r.t. T iff C t is DL-satisfiable w.r.t. T t . Formally: T C ?, iff T t C t ?.

By Theorem 2, we may give the approximate concept satisfiability (definitely satisfiability and possibly satisfiability) reasoning problem w.r.t. rough TBox in rough description logic RDL AC as follows (Theorems 3 and 4) .

Theorem 3. Given an approximate concept AC ¼ hC; Ci and a rough TBox TB in rough description logic RDL AC , TB t and hðCÞ t ; ðCÞ t i are the TBox and concept pair in classical description logic ALC obtained from the translation function t , respectively. AC is definitely satisfiable in a rough interpretation w.r.t. TB, iff ðCÞ t is satisfiable in an interpretation w.r.t. TB t .

Proof. We first prove the only-if-direction ()). Since AC ¼ hC; Ci is definitely satisfiable w.r.t. TB, by the definition of definitely satisfiability, there exists a rough model I of TB such that ðCÞ I -/. By Theorem 2, ðCÞ t is satisfiable w.r.t. TB t .

We prove the if-direction (Ü). Since ðCÞ t is satisfiable w.r.t. TB t , so there exists a model I of TB t such that ððCÞ t Þ I -/. By Theorem 2, C is satisfiable w.r.t. TB. By the definition of definitely satisfiability of approximate concept, AC ¼ hC; Ci is definitely satisfiable w.r.t. TB.

This completes the proof of Theorem 3. h Theorem 4. Given an approximate concept AC ¼ hC; Ci and a rough TBox TB in rough description logic RDL AC , TB t and hðCÞ t ; ðCÞ t i are the TBox and concept pair in classical description logic ALC obtained from the translation function t respectively. AC is possibly satisfiable in a rough interpretation w.r.t. TB, iff ðCÞ t is satisfiable in an interpretation w.r.t. TB t .

Proof. We first prove the only-if-direction ()). Since AC ¼ hC; Ci is possibly satisfiable w.r.t. TB, by the definition of possibly satisfiability, there exists a rough model I of TB such that ðCÞ I -/. By Theorem 2, ðCÞ t is satisfiable w.r.t. TB t . We prove the if-direction (Ü). Since ðCÞ t is satisfiable w.r.t. TB t , so there exists a model I of TB t such that ðCÞ I -/. By Theorem 2, C is satisfiable w.r.t. TB. By the definition of possibly satisfiability of approximate concept, AC ¼ hC; Ci is possibly satisfiable w.r.t. TB.

This completes the proof of Theorem 4. h

In the following, we give the approximate concepts rough subsumption reasoning problem w.r.t. rough TBox in rough description logic RDL AC .

Theorem 5. Given a rough TBox TB, and approximate concepts AC ¼ hC; Ci, AD ¼ hD; Di in rough description logic RDL AC , TB AC v AD, iff < C u :D, C u :D > is both definitely unsatisfiable and possibly unsatisfiable w.r.t. TB.

Proof. We first prove the only-if-direction ()). Since TB AC v AD, so for every rough model I of TB, we have ðCÞ I # ðDÞ I and ðCÞ I # ðDÞ I .

We will show that hC u :D; C u :Di is definitely unsatisfiable w.r.t. TB TB first. That is to say, we need prove that for every rough model I of TB, ðC u :DÞ I ¼ /. This can be shown by contradiction.

Assume that there exists a rough model I ¼ ðD I ; R $ ; I Þ of TB, such that ðC u :DÞ I -/. In the following, we prove that there exists an individual x 2 D I , such that x 2 ðCÞ I , but x R ðDÞ I .

Since Therefore, TB 2 AC v AD. This is an obvious contradiction to TB AC v AD. Thus, our assumption is refuted, which completes the proof of ðC u :DÞ I ¼ /.

In the following, we will show that hC u :D; C u :Di is possibly unsatisfiable w.r.t. TB. That is to say, we need prove that for every rough model I of TB, ðC u :DÞ I ¼ /. This can also be shown by contradiction.

Assume that there exists a rough model I ¼ ðD I ; R $ ; I Þ of TB, such that ðC u :DÞ I -/. In the following, we prove that there exists an individual x 2 D I , such that x 2 ðCÞ I , but x R ðDÞ I .

Since Therefore, TB 2 AC v AD. This is an obvious contradiction to TB AC v AD. Thus, our assumption is refuted, which completes the proof of ðC u :DÞ I ¼ /.

We prove the if-direction (Ü). Since hC u :D; C u :Di is both definitely unsatisfiable and possibly unsatisfiable w.r.t. TB, then for every rough model I of TB, we have ðC u :DÞ I ¼ / and ðC u :DÞ I ¼ /.

To show TB AC v AD, it is sufficient to show that for every rough model I of TB, such that ðCÞ I # ðDÞ I and ðCÞ I # ðDÞ I . This can be shown by contradiction. Assume there exists a rough model I ¼ ðD I ; R $ ; I Þ of TB, and an individual x 2 D I , such that (1) x 2 ðCÞ I , and x R ðDÞ I ; or (2) x 2 ðCÞ I , and x R ðDÞ I .

(1) Assume that x 2 ðCÞ I , and x R ðDÞ I . Since x R ðDÞ I , then we have x 2 D I n ðDÞ I ¼ ð:DÞ I . Since x 2 ðCÞ I , we obtain

x 2 ðCÞ I \ ð:DÞ I ¼ ðC u :DÞ I . Therefore ðC u :DÞ I -/. This is an obvious contradiction to ðC u :DÞ I ¼ /. Thus, our assumption is refuted. (2) Assume that x 2 ðCÞ I , and x R ðDÞ I . Since x R ðDÞ I , then we have x 2 D I n ðDÞ I ¼ ð:DÞ I . Since x 2 ðCÞ I , we obtain

x 2 ðCÞ I \ ð:DÞ I ¼ ðC u :DÞ I . Therefore ðC u :DÞ I -/. This is an obvious contradiction to ðC u :DÞ I ¼ /. Thus, our assumption is refuted. This completes the proof of Theorem 5. h

By the definitions of definitely unsatisfiable and possibly unsatisfiable, if approximate concept AC ¼ hC; Ci is possibly unsatisfiable, then AC ¼ hC; Ci is sure to definitely unsatisfiable. The reason is: for every rough model I of TB, it is easy to know that if ðCÞ I ¼ /, then ðCÞ I ¼ /. Therefore, from Theorem 5, we have a simple approximate concepts rough subsumption reasoning algorithm as follows.

Theorem 6. Given a rough TBox TB, and approximate concepts AC ¼ hC; Ci, AD ¼ hD; Di in rough description logic RDL AC , TB AC v AD, iff hC u :D; C u :Di is possibly unsatisfiable w.r.t. TB.

From Theorems 5 and 6, we know that one can reduce the approximate concepts rough subsumption reasoning to approximate concept satisfiability (definitely satisfiability and possibly satisfiability) reasoning in RDL AC .

As an immediate consequence of Theorems 4 and 6, we obtain the following theorem, i.e., one can reduce the approximate concepts rough subsumption reasoning in RDL AC to satisfiability reasoning in (almost) standard ALC.

Theorem 7. Given a rough TBox TB, and approximate concepts AC ¼ hC; Ci, AD ¼ hD; Di in rough description logic RDL AC , TB t and hðCÞ t ; ðCÞ t i, hðDÞ t ; ðDÞ t i are the TBox and concept pairs in classical description logic ALC obtained from the translation function t respectively. TB AC v AD, iff ðC u :DÞ t is unsatisfiable w.r.t. TB t .

Proof. By Theorem 6, TB AC v AD, iff hC u :D; C u :Di is possibly unsatisfiable w.r.t. TB. Theorem 4, hC u :D; C u :Di is possibly unsatisfiable w.r.t. TB, iff C u :D t is unsatisfiable w.r.t. TB t . Therefore, TB AC v AD, iff ðC u :DÞ t is unsatisfiable w.r.t. TB t . This completes the proof of Theorem 7. h From Theorems 3, 4 and 7, we know that the approximate concept satisfiability (definitely satisfiability and possibly satisfiability) reasoning problem and approximate concepts rough subsumption reasoning problem w.r.t. rough TBox in RDL AC may be reduced to the concept satisfiability reasoning problem in (almost) standard ALC [38] . Therefore, the approximate concept satisfiability reasoning and approximate concepts rough subsumption reasoning w.r.t. rough TBox in RDL AC can be implemented by utilizing the tableaux reasoning algorithm in ALC. That is to say, the approximate concept satisfiability reasoning and approximate concepts rough subsumption reasoning w.r.t. rough TBox in RDL AC can be reasoned by utilizing the description logics reasoning systems which have been implemented, such as Pellet [40] , FaCT++ [44] , and Racer [11] . From the definition of the translation function t , translating the approximate concepts or rough TBox in RDL AC into concepts or TBox in ALC, respectively, can be carried out in polynomial time, so the complexity of reasoning in RDL AC is the same as that of the ALC.

Remark 4. RDL AC , the extension to standard DLs such as ALC [38] that we introduce in this paper, allows for precise modeling of vague knowledge using approximate concepts. Technically, RDL AC can be simulated with (almost) standard ALC without added expressiveness. In other words, our RDL AC is strictly speaking not more expressive than classical DLs such as ALC, i.e., the classical DLs are strong enough to cope with notions arising from rough approximations, but the approximate concepts that we introduce are useful modeling devices for uncertain or imprecise knowledge (namely non-crisp concepts) such as Sepsis and SARS (see Section 3.1).

The works described in this paper mainly focus on description logics which can express uncertain or imprecise knowledge. At present, these description logics have rough DLs, fuzzy DLs, and probabilistic DLs [17, 37, 41, 42] . They are the extensions of classical description logics, and these extended description logics can express uncertain or imprecise knowledge. Where fuzzy DLs are fuzzy extensions of classical description logics based on Zadeh's fuzzy logic theory; probabilistic DLs are probabilistic extensions of classical description logics based on probability theory; and rough DLs are rough extensions of classical description logics based on rough set theory. Comparing with fuzzy DLs and probabilistic DLs, the strongpoint of rough DLs is having no use for membership function or priority probability in advance. This paper covers the topics about rough DLs.

The related works about rough DLs are as follows.

Liau [26] incorporates the notion of rough sets into terminological logics, presents a kind of ROugh TErminological Logic ROTEL based on Pawlak rough set theory [31] [32] [33] [34] [35] , and gives the syntax and semantics of the ROTEL. The satisfiability reasoning algorithm of the rough concept theory S ¼ T [ A is given, where T is a set of terminological formulas of the form ½ER ¼ R with R being a role name, E being an indiscernibility relation symbol, and A is a set of assertional formulas. But there are not the concept satisfiability reasoning and concepts subsumption reasoning algorithms in ROTEL. Moreover, ROTEL can not deal with approximate concepts.

Schlobach et al. [37] extend traditional description logics with a simple mechanism to handle approximate concept definitions in a qualitative way based on Pawlak rough set theory [31] [32] [33] [34] [35] , and present a kind of rough description logic RDL, where RDL includes universal and existential quantification, and symmetric, transitive and reflexive roles. The theorem of reducing the concept satisfiability reasoning in RDL to the concept satisfiability reasoning in DL is given. But the subsumption reasoning algorithm of RDL is not given. Moreover, RDL can not deal with approximate concepts, too.

Klein et al [22] present a conservative extension to standard OWL that allows for defining approximations of concepts based on Pawlak rough set theory [31] [32] [33] [34] [35] , i.e., RoughOWL, an extension of OWL with new operators for modeling vague concepts, that does not increase the expressive power of the original languages, and give the syntax and semantics of the RoughOWL. Klein et al. apply this technique in openacademia, a semantics-based system for the management of distributed bibliographic information collected from the Web. But there are not the concept satisfiability reasoning and concepts subsumption reasoning algorithms in RoughOWL. Moreover, RoughOWL also cannot deal with approximate concepts.

Schlobach [36] introduces knowledge discovery in modal and description logics, which process of finding conceptual information from non-purpose built data collections describing properties of particular individuals or situations in expressive modal language based on Pawlak rough set theory [31] [32] [33] [34] [35] . Modal, concept and assertion mining is defined as the task of finding conceptual knowledge from these collections, more precisely modal rules, or description logics TBox axioms. The works of Schlobach are integrating knowledge mining algorithms based on Pawlak rough set theory and knowledge representation method based on modal and description logics, i.e., Schlobach does not present rough description logics.

Doherty et al. [8] propose a framework for specifying, generating and using approximate ontologies based on intuitions from rough set theory. Specifically, a formal framework for defining approximate concepts, ontologies and operations on approximate concepts and ontologies is presented, and algorithms for automatically generating approximate ontologies from traditional crisp ontologies or from data sets together with additional knowledge is presented. However, Doherty's work (which is perhaps the one closest in spirit to our own), is not based on logics (or description logics), so their semantics is non-standard, and approximate concepts are not be integrated in standard ontology language such as description logics. The works described in this paper introduce approximate concepts to description logics based on rough set theory from a theoretical point of view.

Making applications capable of coping with vagueness and imprecision will result in the creation of systems and applications which will provide us with high quality results and answers to complex user defined tasks [41] . To this direction approximate concepts are introduced to description logics based on rough set theory, a kind of new rough description logic RDL AC is proposed based on approximate concepts. The syntax, semantics, properties and reasoning problems of the RDL AC are given. Interestingly, we allow approximate concepts to appear in a rough description logic knowledge base. Although our rough description logic RDL AC is strictly speaking not more expressive than classical DLs such as ALC, the approximate concepts that we introduce are useful modeling devices for uncertain or imprecise knowledge. To the best of our knowledge, the work described in this paper is the first result about integration between description logics and approximate concepts. Therefore, theoretical foundations for reasoning algorithms of more expressive rough description logics including approximate concepts, number restrictions, nominals, inverse roles and role hierarchies are provided by the RDL AC . As far as future directions are concerned, these will include the approximate concept satisfiability and approximate concepts rough subsumption reasoning algorithms of rough description logics including number restrictions, nominals, inverse roles and role hierarchies, and an integration between approximate concepts and fuzzy DLs [17, 41, 42] or probabilistic DLs [12, 28] based on fuzzy rough set theory [27, 30, 43, 50, 51] or probabilistic rough set theory [7, 45, 52] , respectively. Furthermore, additional research effort can be focused on the investigation of the construction of approximate ontologies (or rough TBoxes) using formal concept analysis.

Description logics

Description logics as ontology languages for the semantic Web

Basic description logics

Reasoning on UML class diagrams

Definitions for sepsis and organ failure and guidelines for the use of innovative therapies in sepsis

Description logics for data bases

Measures of general fuzzy rough sets on a probabilistic space

Towards a framework for approximate ontologies

A logic for rough sets

Ontologies: A Silver Bullet for Knowledge Management and Electronic Commerce

Proceedings of the First International Joint Conference on Automated Reasoning (IJCAR 2001)

Probabilistic description logics

From SHIQ and RDF to OWL: the making of a Web ontology language

A tableau decision procedure for SHOIQ

Logic at Work: Essays Dedicated to the Memory of Helena Rasiowa (Studies in Fuzziness and Soft Computing)

Probabilistic reasoning in terminological logics

Fuzzy description logic for semantics representation of the semantic Web

Fuzzy ER modeling with description logics

Description logics based temporal ER model with attribute dependencies

A tableaux decision procedure for fuzzy description logic FALNUI

A semantic Web oriented description logic

Approximate instance unification using RoughOWL: Querying with similarity in openacademia

P-CLASSIC: a tractable probabilistic description logic

On computational complexity of the extended fuzzy description logic with numerical restriction

The Ministry of Health of the People's Republic of China: clinic diagnosis criteria for severe acute respiratory syndrome

Proceedings of the Fourth International Workshop on Rough Sets Fuzzy Sets and Machine Discovery

Generalized rough sets over fuzzy lattices

Expressive probabilistic description logics

Keys, nominals, and concrete domains

Generalized fuzzy rough sets determined by a triangular norm

Rough sets

Rough Sets: Theoretical Aspects of Reasoning about Data

Rough sets and Boolean reasoning

Rough sets: some extensions

Rudiments of rough sets

Knowledge Acquisition in Hybrid Knowledge Representation Systems

Description logics with approximate definitions: Precise modeling of vague concepts

Attributive concept descriptions with complements

A logic foundation for the semantic Web

Pellet: a practical OWL-DL reasoner

Reasoning with very expressive fuzzy description logics

Reasoning within fuzzy description logics

Fuzzy rough set theory for the interval-valued fuzzy information systems

FaCT++ description logic reasoner: system description

Probabilistic rough set approximations

Generalization of rough sets using modal logics

Fuzzy sets

Toward a generalized theory of uncertainty (GTU)-an outline

Is there a need for fuzzy logic

On fuzzy approximation operators in attribute reduction with fuzzy rough sets

On generalized intuitionistic fuzzy rough approximation operators

Probabilistic approach to rough sets

The authors would like to thank the anonymous referees for their valuable comments as well as helpful suggestions from the Editor-in-Chief which greatly improved the exposition of the paper. The works described in this paper are supported by the National Natural Science