2.1.1 The basic Description Logic attributive language

Elementary descriptions are atomic concepts and atomic roles (also called concept names and role names), and complex descriptions can be built from them inductively with concept constructors and role constructors. In abstract notation, we use the letters A and B for atomic concepts, the letter R for atomic roles, and the letters C and D for concept descriptions.

Concept descriptions in AL are formed according to the following syntax rule:

C, D → ${\rm{\tf="AgfaRSSB" T}}$ | (universal concept)

⊥ | (bottom concept)

A | (atomic concept)

C ∩ D | (intersection)

∀R.C | (value restriction)

∃R.⊥ (limited existential quantification)

In AL, negation can only be applied to atomic concepts, and only the top concept is allowed in the scope of an existential quantification over a role. In order to define a formal semantics of AL-concepts, we consider an interpretations I that consist of a non-empty set Δ^I (the domain of the interpretation) and an interpretation function •^I, which assigns to every atomic concept A, a set A ^I ⊆ Δ^I, and to every atomic role R, a binary relation R ^I ⊆ Δ^I × Δ^I. The interpretation function is extended to concept descriptions by the following inductive definitions:

$$\displaylines{ & {{{\rm{\tf="AgfaRSSB" T}}}^I} \, = \,{{{\rm{\rDelta }}}^I} \cr & {{ \bot }^I} \, = \,\varnothing \cr & {{(\neg A)}^I} \, = \,{{{\rm{\rDelta }}}^I} \backslash {{A}^I} \cr & {{(C \cap D)}^I} \, = \,{{C}^I} \cap {{D}^I} \cr & {{(\forall R.C)}^I} \, = \,\{ a \in {{{\rm{\rDelta }}}^I} |\forall b.(a,b) \in {{R}^I} \, \rightarrow \,b \in {{C}^I} \} \cr & {{(\exists R. \bot )}^I} \, = \,\{ a \in {{{\rm{\rDelta }}}^I} |\exists b.{}(a,b) \in {{R}^I} \} \cr}$$

The above constructors can be used to build DL KBs for representing the knowledge of an application domain (the ‘world’) by first defining the relevant concepts of the domain (i.e., its terminology), and then using these concepts to specify properties of objects and individuals occurring in the domain (i.e., the world description; Baader et al., Reference Baader, Calvanese and McGuinness2003). Generally speaking, a DL KB comprises two components, the TBox and the ABox. The TBox introduces the terminology, that is, the vocabulary of an application domain, while the ABox contains assertions about named individuals in terms of this vocabulary.

In brief, a TBox T is a finite set of terminology axioms of the form C ⊆ D or C = D. An interpretation I satisfies C ⊆ D if C ^I ⊆ D ^I, and similarly for C = D. An interpretation I is a model of TBox T iff I satisfies all axioms in T. An ABox A is a finite set of assertions of the form C(d) or R(d ₁, d ₂). By the first kind, called concept assertions, one states that d belongs to (the interpretation) C, and by the second kind, called role assertions, one states that d ₂ is a filler of the role R for d ₁. An interpretation I is a model of ABox A iff I satisfies all assertions in A. Furthermore, an interpretation I satisfies a DL knowledge base KB if it satisfies all axioms and assertions in KB.

2.1.2 The family of attributive languages

We obtain more expressive languages if we add further constructors to AL. The following introduce several important constructors, which are often added to AL.

The union of concepts (indicated by the letter U) is written as C ∪ D, and interpreted as

$$ {{(C \cup D)}^I} = {{C}^I} \cup {{D}^I} $$

Full existential quantification (indicated by the letter E) is written as ∃R.C, and interpreted as

$$ {{(\exists R.C)}^I} = \{ a \in {{{\rm{\rDelta }}}^I} |\exists b.(a,b) \in {{R}^I} \wedge b \in {{C}^I} \} $$

Note that ∃R.C differs from ∃R.⊥ in that arbitrary concepts are allowed to occur in the scope of the existential quantifier.

Number restrictions (indicated by the letter N) are written as ⩾nR (at-least restriction) and as ⩽nR (at-most restriction), where n ranges over the non-negative integers. They are interpreted as

$${{({\geqslant}nR)}^I} = \{ a \in {{{\rm{\rDelta }}}^I} |\# \{ b|(a,b) \in {{R}^I} \} {\geqslant}n\} $$

and

$${{({\leqslant}nR)}^I} = \{ a \in {{\rDelta }^I} |\# \{ b|(a,b) \in {{R}^I} \} {\leqslant}n\} $$

respectively, where ‘#{}’ denotes the cardinality of a set. From a semantic view point, the coding of numbers in number restrictions is immaterial. However, for the complexity analysis of inferences it can matter whether a number n is represented in binary (or decimal) notation or by a string of length n, since binary (decimal) notation allows for a more compact representation.

The negation of arbitrary concepts (indicated by the letter C, for ‘complement’) is written as ¬C, and interpreted as

$${{(\neg C)}^I} = {{{\rm{\Delta }}}^I} \backslash {{C}^I} $$

Extending AL by any subset of the above constructors yields a particular AL-language. We name each AL-language by a string of the form:

$$AL[U][E][N][C]$$

where a letter in the name stands for the presence of the corresponding constructor. For instance, ALEN is the extension of AL by full existential quantification and number restrictions. Moreover, since the union (U) and full existential quantification (E) can be expressed using negation (C), the letters UE in language names will be replaced by the letter C. For instance, we shall write ALC instead of ALUE and ALCN instead of ALUEN.

2.1.3 The more expressive Description Logics

There are several possibilities for extending AL in order to obtain a more expressive DL. The three most prominent are adding additional concept constructors, adding role constructors, and formulating restrictions on role interpretations. For these extensions, we introduce a naming scheme. Basically, each extension is assigned a letter or symbol:

• • For concept constructors, the letters/symbols are written after the starting AL;

• • For role constructors, we write the letters/symbols as superscripts;

• • For restrictions on the interpretation of roles as subscripts.

• • As an example, a DL called ALCQI_{R +}, extends AL with the concept constructors negation (C) and qualified number restrictions (Q), the role constructor inverse (I), and the restriction that some roles are transitive(_{R +}).

Below, we start with the third case, since we need to refer to restrictions on roles when defining certain concept constructors.

Restrictions on role interpretations: These restrictions enforce the interpretations of roles to satisfy certain properties, such as functionality and transitivity. We consider these two prominent examples in more detail. Others would be symmetry or connections between different roles.

• • Functional roles: Here one considers a subset N_F of the set of role names N_R, whose elements are called features. An interpretation must map features f to functional binary relations f ^I ⊆ Δ^I × Δ^I. AL extended with features is denoted by AL_f.

• • Transitive roles: Here one considers a subset N_{R +} of N_R. Role names R ∈ N_{R +} are called transitive roles. An interpretation must map transitive roles R ∈ N_{R +} to transitive binary relations R ^I ⊆ Δ^I × Δ^I. AL extended with transitive roles is denoted by AL_{R +}.

All the DLs mentioned until now contain the concept constructors such as intersection (C ∩ D) and value restriction (∀R.C) as a common core. DLs that allow for intersection of concepts and existential quantification (but not value restriction) are collected in the EL-family. The only constructors available in EL are intersection of concepts (C ∩ D) and existential quantification (∃R.⊥). Extensions of EL are again obtained by adding appropriate letters/symbols. Moreover, in order to avoid very long names for expressive DLs, the abbreviation S was introduced for ALC_{R +}, that is, DL that extends ALC by transitive roles. Prominent members of the S-family are SIN (which extends ALC_{R +} with number restrictions and inverse roles), SHIF (which extends ALC_{R +} with role hierarchies, inverse roles, and number restrictions of the form ⩽1R), and SHIQ (which extends ALC_{R +} with role hierarchies, inverse roles, and qualified number restrictions). Actually, DLs SIN, SHIF, and SHIQ are somewhat less expressive than indicated by their name since the use of roles in number restrictions is restricted: roles that have a transitive sub-role must not occur in number restrictions.

2.1.4 Description Logics with data type representation

A drawback that all DLs introduced until now share is that all the knowledge must be represented on the abstract logical level. In many applications, one would like to be able to refer to concrete domains and predefined predicates on these domains when defining concepts, such as one wants to define the concept ‘Minor’ using the axiom Minor = Person ∩ ∃age.⩽₁₈. To solve the problem, Baader and Hanschke (Reference Baader and Hanschke1991a) integrated concrete domains into concept languages, and the definition of concrete domain was given and a tableau-based algorithm for deciding consistency of ALC(D)-ABoxes for admissible D was introduced. The algorithm has an additional rule that treats existential predicate restrictions according to their semantics. The main new feature is that, in addition to the usual ‘abstract’ clashes, there may be concrete ones, that is, one must test whether the given combination of concrete predicate assertions is non-contradictory. This is the reason why we must require that the satisfiability problem for D is decidable. As described by Baader and Hanschke (Reference Baader and Hanschke1991b), the algorithm is not in PSpace. Using techniques similar to the ones employed for ALC it can be shown, however, that the algorithm can be modified such that it needs only polynomial space (Lutz, Reference Lutz1999), provided that the satisfiability procedure for D is in PSpace. In the presence of acyclic TBoxes, reasoning in ALC(D) may become NExpTime-hard even for rather simple concrete domains with a polynomial satisfiability problem (Lutz, Reference Lutz2001).

The more expressive DLs SHN(D) ⁻ (Haarslev & Möller, Reference Haarslev and Möller2001) and SHOQ(D) (Horrocks & Sattler, Reference Horrocks and Sattler2001), which can represent data information, are proposed. Although SHN(D) ⁻ and SHOQ(D) are rather expressive, they also have a very serious limitation on data types, that is, they do not support customized data types. It has been pointed out that many potential users will not adopt them unless the limitation is overcome. Pan and Horrocks release a series of papers about data types to solve the problem (Pan & Horrocks, Reference Pan and Horrocks2006; Pan, Reference Pan2007). In the two papers, they summarize the limitations of OWL data typing and propose the data type approach. For example, SHIQ(G) and SHOQ(G) DLs presented by Pan (Reference Pan2007) and Pan and Horrocks (Reference Pan and Horrocks2006) can support user-defined data type and user-defined data type predicates.

3.1.1 The fuzzy Description Logic FALC

The FALC (Straccia, Reference Straccia1998, Reference Straccia2001) is considered as the basic fuzzy DL, thus we introduce its syntax, semantics, KB, and reasoning problems in detail.

Definition 1 (syntax). Let N_I, N_C, and N_R be three disjoint sets: N_I is a set of individual names, N_C is a set of fuzzy concept names, and N_R is a set of fuzzy role names. FALC-concepts are defined as follows (where A ∈ N_C, R ∈ N_R):

$$C,D \rightarrow \bot |{\rm{\tf="Arial" T}}|A|\neg C|C \cap D|C \cup D|\exists R.C|\forall R.C$$

Definition 2 (semantics). The semantics of FALC is defined by a fuzzy interpretation FI = 〈Δ^FI, •^FI〉 where Δ^FIis a non-empty set and •^FIis a function which maps every d ∈ N_I to an element d ^FI ∈ Δ^FI , maps every A ∈ N_C into a function A ^FI: Δ^FI → [0, 1], and maps every R ∈ N_R into a function R ^FI: Δ^FI × Δ^FI → [0, 1]. Furthermore, for any FALC-concepts C and D, R ∈ N_R, and d, d′ ∈ Δ^FI , we have:

$$\displaylines{ & {{{\rm{\tf="Arial" T}}}^{FI}} (d) = 1 \cr & {{ \bot }^{FI}} (d) = 0 \cr & {{(\neg C)}^{FI}} (d) = 1\, - \,{{C}^{FI}} (d) \cr & {{(C \cap D)}^{FI}} (d) = \min \{ {{C}^{FI}} (d),{}{{D}^{FI}} (d)\} \cr & {{(C \cup D)}^{FI}} (d) = \max \{ {{C}^{FI}} (d),{}{{D}^{FI}} (d)\} \cr & {{(\forall R.C)}^{FI}} (d) = {{\inf }_{d^{\prime} \in {{{\rm{\rDelta }}}^{FI}} }}\{ \max \{ 1\, - \,{{R}^{FI}} (d,d^{\prime}),{{C}^{FI}} (d^{\prime})\} \} \cr & {{(\exists R.C)}^{FI}} (d) = {{\sup }_{d^{\prime} \in {{{\rm{\rDelta }}}^{FI}} }}\{ \min \{ {{R}^{FI}} (d,d^{\prime}),{{C}^{FI}} (d^{\prime})\} \} \cr}$$

With the introduction of fuzzy sets into the classical ALC, the form of the KB is changed accordingly:

Definition 3 (knowledge base). An FALC knowledge base K is composed of a TBox T and an ABox A:

• • A TBox T is a finite set of terminology axioms of the form C ⊆ D or C = D. An interpretation FI satisfies C ⊆ D iff for any d ∈ Δ^FI , C ^FI(d) ⩽ D ^FI(d), and similarly for C = D. FI is a model of TBox T iff FI satisfies all axioms in T.

• • An ABox A is a finite set of assertions of the form〈α ∞ n〉. Here∞ ∈ {>, ⩾, <, ⩽}, n ∈ [0, 1], α is either of the form d: C or (d ₁, d ₂): R. Especially, in order to give a uniform format of the ABox, we define: when n = 1, the form〈α ⩾ 1〉 is equivalent to〈α = 1〉. Concretely speaking,〈d: C ⩾ 1〉 means that d is determinately an individual of C; 〈(d ₁, d ₂): R ⩾ 1〉 means that (d ₁, d ₂) determinately has the relationship R. An interpretation FI satisfies〈d: C ∞ n〉 iff C ^FI(d ^FI) ∞ n and satisfies 〈(d ₁, d ₂): R ∞ n〉 iff R ^FI(d ₁^FI, d ₂^FI) ∞ n. FI is a model of ABox A iff FI satisfies all assertions in A.

• • A fuzzy interpretation FI satisfies a knowledge base K if it satisfies all axioms and assertions in K.

Now, we introduce the reasoning problems of FALC, including satisfiability, subsumption, consistency, entailment, and so on.

Definition 4 (reasoning problems). An FALC knowledge base K is satisfiable iff there exists a fuzzy interpretation FI, which satisfies all axioms and assertions in K. An FALC-concept C is satisfiable w.r.t. a Tbox T iff there exists some model FI of T for which there is some d ∈ Δ^FIsuch that C ^FI(d) = n, and n ∈ (0, 1]. Let C and D be two FALC-concepts, we say that C is subsumed by D w.r.t. T if for every model FI of T it holds that, ∀d ∈ Δ^FI , C ^FI(d) ⩽ D ^FI(d). An FALC Abox A is consistent w.r.t. T if there is a model FI of T, which is also a model of A. Furthermore, given an axiom or assertion ψ, an FALC knowledge base K entails ψ, written K |= ψ, iff all models of K also satisfy ψ. Moreover, given an FALC knowledge base K and a fuzzy assertion α, the greatest lower bound of α w.r.t. K is glb(K, α) = sup{n : K |= α ⩾ n}, where supØ = 0.

The problem of concept satisfiability can be reduced to the problem of ABox consistency, and the problems of subsumption and entailment can be reduced to the problem of KB satisfiability (Straccia, Reference Straccia2001; Stoilos et al., Reference Stoilos, Stamou, Pan, Tzouvaras and Horrocks2007). Furthermore, in the presence of only simple TBoxes (A Tbox T is called simple if it neither includes cyclic nor General Concept Inclusions (GCIs), that is, axioms are the form A ⊆ C or A ≡ C, where A is a concept name that is never defined by itself either directly or indirectly, and A appears at most once at the left hand side.) (Baader et al., Reference Baader, Calvanese and McGuinness2003; Stoilos et al., Reference Stoilos, Stamou, Pan, Tzouvaras and Horrocks2007), all the problems above can be reduced to ABox consistency w.r.t. an empty TBox. The reasoning algorithm and its decidability for FALC have been introduced in detail (Straccia, Reference Straccia2001; Bobillo et al., Reference Bobillo, Bou and Straccia2011). Moreover, Hajek (Reference Hajek2005) studied the problems of satisfiability, validity, and subsumption of FALC-concepts. Haarslev et al. (Reference Haarslev, Pai and Shiri2006) introduced a generic framework, which allows representing several existing extensions of DLs with uncertainty in a uniformed manner, and used FALC as an example to illustrate how it can represent uncertainty and reasoning services in the frameworks considered.

3.1.2 The fuzzy Description Logic ALC_FM

In Tresp and Molitor (Reference Tresp and Molitor1998), an extension of ALC to many-valued logics called ALC_FM was proposed, where the construct called membership manipulators (Yen, Reference Yen1991) also appeared, which are applied to concepts. Examples of manipulators could be ‘mostly’, ‘more or less’, or ‘very’. For example, if Tall is a concept (standing for the fuzzy set of all tall persons), then VeryTall, which is obtained by applying the manipulator Very to the concept Tall, is a new concept (standing for the fuzzy set of all very tall persons). Intuitively, the manipulators modify the membership degree functions of the concepts. In our example, the membership function for VeryTall should have its largest values at larger heights than the membership function for Tall. Formally, the semantics of manipulators is defined by a function that maps membership degree functions to membership degree functions (Tresp & Molitor, Reference Tresp and Molitor1998).

Now, let us consider what kind of inference problems are of interest in this context (i.e., Yen, Reference Yen1991; Tresp & Molitor, Reference Tresp and Molitor1998). Yen (Reference Yen1991) considered crisp subsumption of fuzzy concepts, that is, given two concepts C, D defined in the fuzzy DL, the author was interested in the question whether C ^FI(d) ⩽ D ^FI(d) for all fuzzy interpretations FI and d ∈ Δ^FI. Thus, the subsumption relationship itself is not fuzzified. To this end, the author described a structural subsumption algorithm for a rather small fuzzy DL, which is almost identical to the subsumption algorithm for the corresponding classical DL. In contrast, Tresp and Molitor (Reference Tresp and Molitor1998) were interested in determining fuzzy subsumption between fuzzy concepts, that is, given concepts C, D, they want to know to which degree C is a subset of D. The complete reasoning algorithms can be found by Tresp and Molitor (Reference Tresp and Molitor1998) and Yen (Reference Yen1991), respectively.

3.1.3 The fuzzy Description Logics with hedges

The fuzzy extensions of ALC language were also considered in other approaches (Hölldobler et al., Reference Hölldobler, Khang and Störr2002, Reference Hölldobler, Störr and Tran2003, Reference Hölldobler, Störr and Khang2004, Reference Hölldobler, Nga and Khang2005), where a concept constructor hedges (an algebraic approach to structures of sets of linguistic domains of linguistic truth variables (Cat Ho & Wechler, Reference Cat Ho and Wechler1990)) were included in the extended languages. The fuzzy DLs ALC_FH (Hölldobler et al., Reference Hölldobler, Khang and Störr2002, Reference Hölldobler, Störr and Tran2003, Reference Hölldobler, Störr and Khang2004) and ALC_FLH (Hölldobler et al., Reference Hölldobler, Nga and Khang2005) were presented, respectively, where primitive concepts were modified by means of hedges. ALC_FH and ALC_FLH are strictly more expressive than FALC defined by Straccia (Reference Straccia1998). Moreover, the authors showed that a linearly ordered set of hedges primitive concepts can be modified to any desired degree by prefixing them with appropriate chains of hedges. The authors also defined the decision procedures for the unsatisfiability problems in ALC_FH and ALC_FLH, and discussed truth bounds, expressivity as well as complexity issues.

In addition, in Dinh-Khac et al. (Reference Dinh-Khac, Hölldobler and Tran2006), a fuzzy linguistic DL called ALC_FL was proposed, which is an instance of L-ALC (DLs over lattices (Straccia, Reference Straccia2006d)). Beside constructors of L-ALC, ALC_FL allows the modification by hedges. Furthermore, the ambiguity of the hedge application in ALC_FH and ALC_FLH is solved in ALC_FL. In all these approaches, above tableaux decision procedures were presented for performing reasoning services.

In summary, the fuzzy extension to ALC can be used as a basis both for extending existing DL-based systems and for further research. In the latter case, there are several open points. For instance, it is not clear yet how to reason both in the case of fuzzy specialization of the general form C ⊆ D and in the case that cycles are allowed in a fuzzy KB. Another interesting topic for further research concerns the semantics of fuzzy connectives. While for a huge number of proposals given in the literature their impact from a semantics point of view is well understood, the question how they impact from a computational complexity and algorithms point of view remains still open. For example, Meghini et al. (Reference Meghini, Sebastiani and Straccia1997) proposed a preliminary fuzzy DL, which lacks reasoning algorithm, as a modeling tool for multimedia document retrieval.

3.2.1 Fuzzy Description Logics with number restrictions

The number restrictions include the unqualified number restrictions N and qualified number restrictions Q. Currently, there have been several approaches for extending fuzzy ALC with number restrictions. In Li et al. (Reference Li, Xu, Lu, Kang and Wang2005c), a fuzzy DL called f-ALCN was presented, and the authors provided reasoning for f-ALCN by using the idea of the reduction in order to annotate the concepts and roles of the crisp DL ALCN. Moreover, in Lu et al. (Reference Lu, Xu, Li, Kang and Wang2005), an extended fuzzy ALCN and designed tableau algorithms for that were given. In addition, in Zhao et al. (Reference Zhao, Boley and Du2009), a fuzzy DL named fuzzy ALCHIN and an algorithm for consistency checking of KBs in the proposed language were proposed.

Approach toward more expressive DL was presented by Sánchez and Tettamanzi (Reference Sánchez and Tettamanzi2004), where the DL is called ALCQ_F ⁺. It includes fuzzy quantifiers, which allows for the definition of fuzzy quantifiers of the absolute and relative kind by means of piecewise linear functions on N and Q ∩ [0, 1], respectively, is a new novel idea for fuzzy DLs. Furthermore, in Sánchez and Tettamanzi (Reference Sánchez and Tettamanzi2006), the same authors introduced the reasoning procedures for ALCQ_F ⁺, where in order to reason about instances, the semantics of quantified expressions are defined based on recently developed measures of the cardinality of fuzzy sets. Moreover, a procedure was described to calculate the fuzzy satisfiability of a fuzzy assertion, which is a very important reasoning task. Besides, the procedure also considers several different cases and provides direct solutions for the most frequent types of fuzzy assertions. In addition, Sánchez and Tettamanzi (Reference Sánchez and Tettamanzi2006) defined independence of fuzzy assertions and obtained some results that speed up the calculation of fuzzy satisfiability in some (the most common) cases. More recently, Stoilos et al. (Reference Stoilos, Stamou and Kollias2008a) investigated on the problem of reasoning with qualified cardinality restrictions in fuzzy DLs, extending previous results on simple number restrictions, and thus presented a tableaux algorithm for the fuzzy DL f-ALCIQ. The other efforts for extending fuzzy DLs with number restrictions (such as f_KD-SHIN and fuzzy SHOIQ) can be found in Section 3.2.3.

The extensions with fuzzy quantifiers greatly increase the expressive power of DLs, but make reasoning hard. As a solution, Dragoni and Tettamanzi (Reference Dragoni and Tettamanzi2007) propose to use non-exact evolutionary algorithms to solve concept satisfiability. In fact, not just the reasoning, the semantics of qualified number restrictions is still open to discussion, as pointed by Bobillo and Straccia (Reference Bobillo and Straccia2008a), where a new semantics is also introduced.

3.2.2 The more expressive fuzzy Description Logics with inverse roles/transitive roles/nominals

The fuzzy DL FALC and its some extensions above can effectively express fuzzy knowledge, but they provide limited representation and reasoning ability. For example, they only contain some simple operators, such as conjunction, intersection, negation, value restriction, and existential quantification, which cannot represent and reason on more complex fuzzy knowledge (e.g., the inverse of roles and the transitive roles). Therefore, some scholars have carried out researches on more expressive fuzzy DLs, such as f_KD-SI (Stoilos et al., Reference Stoilos, Stamou and Tzouvaras2005a), f_KD-SHIN (Stoilos et al., Reference Stoilos, Stamou and Tzouvaras2005b), f-SHOIN (Stoilos et al., Reference Stoilos, Stamou and Tzouvaras2005c), f-SHOIQ (Stoilos et al., Reference Stoilos, Stamou and Pan2006a), and f-SROIQ (Stoilos & Stamou, Reference Stoilos and Stamou2007) as follows.

In order to represent and reason on more complex fuzzy knowledge, two very expressive fuzzy DLs f_KD-SI and f_KD-SHIN were presented. Stoilos et al. (Reference Stoilos, Stamou and Tzouvaras2005a) proposed the fuzzy DL f_KD-SI by extending the DL language SI with fuzzy set theory. The combination of transitive and inverse roles can capture knowledge about part-whole relationships and aggregated objects. Both these properties fit well into the framework of knowledge-based multimedia processing where both part-whole relationships, as well as, imprecise and vague knowledge appear in applications like multimedia information retrieval and processing. In more detail, Stoilos and Stamou (Reference Stoilos and Stamou2009) investigated the reasoning problems for fuzzy SI (f-SI) under arbitrary continuous fuzzy operators, and proved decidability of the fuzzy DLs, such as f_L-SI, f_P-SI. Furthermore, Stoilos et al. (Reference Stoilos, Stamou and Tzouvaras2005b) provided an extension of the above f_KD-SI to an even more expressive fuzzy DL, namely f_KD-SHIN, which is also the extension of fuzzy ALC with transitive role axioms (S), inverse roles (I), role hierarchies (H), and number restrictions (N). More importantly, Stoilos et al. (Reference Stoilos, Stamou, Pan, Tzouvaras and Horrocks2007) showed the semantics as well as sound, complete and terminating reasoning algorithms for both of the extended languages f_KD-SI and f_KD-SHIN, where the authors also investigated the applicability of blocking strategies, like dynamic blocking and pair-wise blocking. Moreover, in Gu et al. (Reference Gu, Lv, Gao and Shi2007), a fuzzy DL called ef-SHIN was introduced to support reasoning of fuzzy ontology.

In particular, the RBox will be added into the f_KD-SHIN KB, that is, an f_KD-SHIN KB consists of a TBox, an ABox, and an RBox, where the TBox and ABox have been introduced in Section 3.1.1. An f_KD-SHIN RBox is a finite set of fuzzy transitive role axioms of the form Trans(R) and fuzzy role inclusion axioms of the form R ⊆ S, where R, S are f_KD-SHIN-roles. A fuzzy interpretation FI satisfies Trans(R) if ∀x, z ∈ Δ^FI, R ^FI(x, z) ⩾ sup_{y ∈Δ}^FI {min(R ^FI(x, y), R ^FI(y, z))}, while it satisfies R ⊆ S if ∀x, z ∈ Δ^FI, R ^FI(x, z) ⩽ S ^FI(x, z). A fuzzy interpretation FI satisfies an f_KD-SHIN RBox iff it satisfies all fuzzy axioms in the RBox; in this case, we say that FI is a model of this RBox.

Moreover, a fuzzy extension of the corresponding DL of the ontology description language OWL DL, called f-SHOIN(D), was developed by Straccia (Reference Straccia2005a, Reference Straccia2006a), while no reasoning algorithms were given. Furthermore, in order to provide reasoning for fuzzy OWL web ontology language, in Stoilos et al. (Reference Stoilos, Stamou and Tzouvaras2005c, Reference Stoilos, Stamou and Pan2010), the authors considered the DL f-SHOIN by discarding data types D constructor. The authors gave the syntax, semantics, and a tableau procedure for f-SHOIN, and also presented a reduction technique from fuzzy OWL to f-SHOIN to provide reasoning support for fuzzy OWL ontologies. In addition, Bobillo et al. (Reference Bobillo, Delgado and Gómez-Romero2006) presented a sound fuzzy extension of SHOIN including fuzzy nominals and fuzzy GCIs, and also presented a reasoning preserving procedure to reduce an f-SHOIN KB into a crisp one.

In addition, in Stoilos et al. (Reference Stoilos, Stamou and Pan2006a), the syntax and semantics of fuzzy SHOIQ were presented and the properties of the semantics of transitivity, qualified cardinality restrictions, and reasoning capabilities were investigated. Furthermore, Stoilos and Stamou (Reference Stoilos and Stamou2007) extended the current state-of-the-art on fuzzy extensions to Semantic Web languages by presenting the syntax and semantics of the fuzzy SROIQ as well as the abstract, XML syntax, and semantics of a fuzzy extension to OWL 1.1. Moreover, the authors also provided reasoning support for a fuzzy version of fuzzy SROIQ by extending well-known reduction techniques of fuzzy DLs to classical DLs for the additional axioms and constructors of fuzzy SROIQ.

3.2.3 Fuzzy Description Logics with fuzzy data type

In order that fuzzy DLs can represent and reason on the concrete knowledge in the real-world applications, several fuzzy DLs with fuzzy concrete domains (D) and fuzzy data type group (G) have been proposed as follows.

The Semantic Web is expected to process knowledge information and data information in an intelligent and automatic way. But recent research has shown that the OWL ontology language is very limited in representing fuzzy data information. To this end, Straccia (Reference Straccia2005b, Reference Straccia2005c, Reference Straccia2005d) proposed a fuzzy DL called fuzzy ALC(D) (ALC extended with concrete domains), where the representation of concept membership functions and fuzzy modifiers are allowed, together with an inference procedure based on a mixture of a tableaux and bounded mixed integer programming. A reasoning algorithm for fuzzy ALCF(D) with GCIs and explicit membership functions was proposed by Bobillo and Straccia (Reference Bobillo and Straccia2009b, Reference Bobillo and Straccia2009d), Bobillo and Straccia (Reference Bobillo and Straccia2007), and Straccia and Bobillo (Reference Straccia and Bobillo2007).

The more expressive DL, which can support fuzzy concrete domains was shown by Straccia (Reference Straccia2005a), where the language is the fuzzy extension of SHOIN(D), which is the corresponding DL of the ontology description language OWL DL. It shows that the representation and reasoning capabilities of fuzzy SHOIN(D) go clearly beyond classical SHOIN(D). The following interesting features are considered in fuzzy SHOIN(D): (i) concrete domains are fuzzy sets; (ii) fuzzy modifiers are allowed; and (iii) entailment and subsumption relationships may hold to some degree in the unit interval [0, 1]. A fuzzy concrete domain D is a pair 〈Δ_D, φ_D〉, where Δ_D is an interpretation domain and φ_D is the set of fuzzy domain predicates d with a predefined arity n and an interpretation d ^D: Δ_D ⁿ → [0, 1]. Furthermore, a fuzzy interpretation FI with respect to a fuzzy concrete domain D is a pair FI = (Δ^FI, ^FI) consisting of a non-empty set Δ^FI (called the domain), disjoint from Δ_D, and of a fuzzy interpretation function ^FI that assigns each concrete individual to an element in Δ_D; assigns each abstract individual to an element in Δ^FI; assigns each abstract concept C to a function C ^FI: Δ^FI → [0, 1]; assigns each abstract role R to a function R ^FI: Δ^FI × Δ^FI → [0, 1]; assigns each data type role T to a function T ^FI: Δ^FI × Δ_D → [0, 1]; assigns each n-ary predicate p to the fuzzy relation p ^D: Δ_D ⁿ → [0, 1], which means the relationship of data types v ₁,…,v_n satisfies predicate p in a degree in [0, 1]. The detail reviews about fuzzy SHOIN(D) can be found in Lukasiewicz and Straccia (Reference Lukasiewicz and Straccia2008) and Straccia (Reference Straccia2005a).

Moreover, in Bobillo et al. (Reference Bobillo, Delgado and Gómez-Romero2009), Bobillo and Straccia (Reference Bobillo and Straccia2009c), and Bobillo (Reference Bobillo2008), the authors proposed the fuzzy extension of OWL 2 language, that is, fuzzy SROIQ(D), and also presented a reasoning preserving procedure to obtain a crisp representation for the fuzzy SROIQ(D). Based on the presentation of fuzzy DLs with fuzzy concrete domain, the fuzzy data information in the Semantic Web can be represented.

Furthermore, in order to support fuzzy customized data type information, a new kind of fuzzy DL called F-ALC(G) was proposed by Wang and Ma (Reference Wang and Ma2008), which can not only support the representation and reasoning of fuzzy concept knowledge, but also support fuzzy data information with customized fuzzy data types and customized fuzzy data type predicates.

3.2.4 The other fuzzy Description Logics with cut sets/fuzzy rough sets/fuzzy truth values

In the real-world applications, one wants to express using ∀R _0.9.C _0.6 the set of individuals that are related with degree 0.9 using role R with some individual that belongs to concept C with degree at least 0.6, that is, the fuzzy DLs allow for the cut sets of fuzzy concepts/roles.

To this end, by introducing the cut sets of fuzzy concepts and fuzzy roles as atomic concepts and atomic roles, and inheriting the concept and role constructors from DLs, Lu et al. (Reference Lu, Xu, Li and Kang2006) and Li et al. (Reference Li, Xu, Lu, Kang and Wang2005a) proposed a family of the so-called extended fuzzy DLs (EFDLs), which use α-cuts as atomic concept and roles. The definitions of syntax, semantics, reasoning tasks, and reasoning properties are given for EFDLs. In particular, EFDLs and FALC (Straccia, Reference Straccia1998) are fuzzy DLs with same concept constructors and different fuzzily methods, and the former supports more powerful presentation of fuzzy concepts. Furthermore, Lu et al. (Reference Lu, Li, Zhou and Kang2008a) presented sound and complete tableau algorithms for EFDLs, and proved the complexity is PSPACE-complete. Subsequently, based on the cut sets, several works also proposed different extension of DLs and reasoning algorithms for fuzzy ALCH (Kang et al., Reference Kang, Lu, Xu, Li and He2005; Li et al., Reference Li, Lu, Xu, Kang and Jiang2005b), fuzzy ALCN (Li et al., Reference Li, Xu, Lu, Kang and Wang2005c).

Furthermore, in order that the fuzzy DLs can support the expression of comparisons between fuzzy membership degrees, for example, it is a familiar description that ‘John is taller than Tom’, which can be seemed as a comparison between two fuzzy membership degrees, it is necessary to extend fuzzy DLs with the ability of expressing comparison expressions. Toward this goal, in Lu et al. (Reference Lu, Kang, Zhang, Li and Zhou2008b), the authors EFDLs with the fuzzy comparison cuts, and the extended language was called FCDLs. Also, the syntax, semantics, and reasoning algorithms for FCDLs were provided in detail.

Moreover, Bobillo and Straccia (Reference Bobillo and Straccia2009a) and Jiang et al. (Reference Jiang, Tang, Wang and Tang2009a, Reference Jiang, Wang, Deng and Tang2009b, Reference Jiang, Wang, Tang and Xiao2009c) provided a simple solution to join fuzzy DLs and rough DLs, and studied how to combine fuzzy DLs with fuzzy rough sets, that is, fuzzy rough DLs. In particular, Bobillo and Straccia (Reference Bobillo and Straccia2009a) presented a very expressive fuzzy rough extension of the DL SROIQ(D), the logic behind the language OWL 2. In addition, Bobillo and Straccia (Reference Bobillo and Straccia2009e) allowed fuzzy DL sentences to be qualified with fuzzy truth values, and, thus, allow expressions such as ‘Tina is young is very true’ and ‘Tina is young is almost true’. The syntax, semantics, and reasoning algorithms for the extended languages were provided.

According to the statements above, some important existing fuzzy DLs can be summarized in Table 2. Notice that, however, it does not mean that Table 2 covers all publications in the research area and gives complete descriptions.

4.1.1 Reasoning techniques for fuzzy Description Logics

So far, kinds of reasoning techniques for different fuzzy DLs have been proposed. Moreover, the reasoning complexity of some fuzzy DLs was investigated by Bonatti and Tettamanzi (Reference Bonatti and Tettamanzi2005) and the optimization techniques for fuzzy DLs were discussed by Simou et al. (Reference Simou, Mailis, Stoilos and Stamou2010). In general, the reasoning techniques can be summarized in three categories: tableau-based reasoning technique, reasoning technique for GCIs, and reduction to crisp DLs.

Besides, Keller and Heymans (Reference Keller and Heymans2008) introduced a new class of inference procedures into fuzzy DLs reasoning, that is, the fixpoint-based decision procedure for deciding knowledge-based satisfiability in the fuzzy DL FALC.

4.1.2 Fuzzy Description Logic reasoners

DLs serve as the theoretical counterpart of the Semantic Web and provide reasoning supports for it, and the DL reasoners are the basic supporting bodies for the Semantic Web coming into use. Therefore, in order to implement the automatic reasoning of fuzzy DLs, kinds of reasoners based on different fuzzy DLs have been put forward as will be introduced in the following.

In recent years, a series of reasoners, such as FaCT, RACER, and Pellet (Baader et al., Reference Baader, Calvanese and McGuinness2003), have been developed based on the classic DLs. These reasoners are very efficient and soundness for ontology reasoning. Pellet, for example, is an OWL-DL reasoner with good performance, extensive middleware, and a number of unique features. Also there are some other reasoners such as Jess, Jena, KOAN2, Cerebra, cwm, Euler, surnia, SWI, E-wallet, MSPASS (OWL Implementations, 2001), which are based on classic DLs and toward OWL. Most of classical reasoners mentioned above have been updated for several versions and have good reliability, robustness, and running efficiency. Some versions of them have been commercialized.

However, these classical reasoners cannot support the representation and reasoning of fuzzy ontologies and fuzzy DLs. With the extensive and in-depth application of intelligent systems, the processing of fuzzy, and uncertain information in the real world is becoming an essential part of intelligent systems (Straccia, Reference Straccia2001; Stoilos et al., Reference Stoilos, Stamou, Pan, Tzouvaras and Horrocks2006c, Reference Stoilos, Simous, Stamou and Kollias2007; Cimianoet et al., Reference Cimiano, Haase, Ji, Mailis, Stamou, Stoilos, Tran and Tzouvaras2008; Lukasiewicz & Straccia, Reference Lukasiewicz and Straccia2008). It is imperative to develop fuzzy reasoners, which can process fuzzy ontologies and fuzzy DLs.

Table 4 lists the existing fuzzy reasoners that can support the processing of fuzzy and uncertain information. In Table 4, PDLP (Li et al., Reference Li, Liu, Tao, Zhang, Zhou and Yu2006c) is a reasoner based on the probability DL for dealing with uncertain information, while the rest are used to deal with fuzzy information based on fuzzy DLs.

Table 4

The comparisons of the current fuzzy and probabilistic DL reasoners

DLs = Description Logics.

In summary, for the implementation of fuzzy reasoners, there are two strategies: one is to translate the fuzzy DL into the classic DL and then call the classic DL reasoner for reasoning, for example, DeLorean in Table 4 and the reasoning technology mentioned by Straccia (Reference Straccia2004a). Another strategy is to directly implement fuzzy reasoners based on the tableau algorithm of the corresponding fuzzy DL, for example, the reasoners in Table 4 except for DeLorean and SoftFacts. The latter strategy has the advantage that the optimized technology can be adopted according to the specific fuzzy DL, and their efficiency in the implementation can be enhanced.

Through comparison of the reasoners in Table 4, it can be found that these reasoners can support the particular fuzzy DL. The existing reasoners in Table 4 can support the representation and reasoning of fuzzy concept knowledge, fuzzy concrete domain, or fuzzy customized data type and predicates. The relationships of the reasoning capacity among parts of these fuzzy reasoners are shown in Figure 1. In Figure 1, U means human knowledge. The dotted circle, solid circle, and dotted and solid circles in Figure 1 denote FRESG reasoner and two fuzzy reasoners 1 and 2, respectively.

Figure 1

The relationships among existing fuzzy Description Logic reasoners

In Figure 1, C stands for f-ALC that all fuzzy reasoners can support; E stands for the DLs that support fuzzy concrete domain D, such as FuzzyDL in Table 4; F stands for the DLs that support fuzzy customized data type and fuzzy customized data type predicates G, such as FRESG in Table 4; B stands for the remaining part with the same reasoning abilities of reasoner 1 and reasoner 2 in addition to f-ALC; A and D stands for the unique part of reasoner 1 and 2 in reasoning capacity, respectively.