A MILP-based decision procedure for the (Fuzzy) Description Logic ALCB

Abstract

To overcome the inability of Description Logics (DLs) to represent vague or imprecise information, several fuzzy extensions have been proposed in the literature. In this context, an important family of reasoning algorithms for fuzzy DLs is based on a combination of tableau algorithms and Operational Research (OR) problems, speci cally using Mixed Integer Linear Programming (MILP). In this paper, we present a MILP-based tableau procedure that allows to reason within fuzzy ALCB, i.e., ALC with individual value restrictions. Interestingly, unlike classical tableau procedures, our tableau algorithm is deterministic, in the sense that it defers the inherent non-determinism in ALCB to a MILP solver.

Introduction

Description Logics (DLs for short) [ 2 ] are a family of logics for representing structured knowledge. In the last two decades, DLs have gained even more popularity due to their application in the context of the Semantic Web [ 3 ]. Indeed, the current standard language for specifying ontologies is the Web Ontology Language (OWL 2) [ 18 ], which is based on the DL SROIQ(D) [ 23 ].

Fuzzy DLs have been proposed as an extension to classical DLs with the aim of dealing with fuzzy/vague/imprecise concepts by including elements of fuzzy logic [ 35 ]. In fuzzy DLs, the axioms may not be bivalent, but instead can be satis ed with a certain degree of truth (typically, a truth value in [0; 1]). Since the rst work of J. Yen in 1991 [ 34 ], an important number of works can be found in the literature (good surveys on fuzzy DLs can be found on [ 25,33 ]).

Several families of algorithms to reason with fuzzy DLs have been proposed in the literature. The most important ones are tableau algorithms [ 15,28,29,30 ], tableau algorithms combined with Operational Research (OR) problems [ 8,17 ], automata-based algorithms [ 14,13 ], reduction to classical DLs [ 4,5,6,10,12 ], and reduction to fuzzy logics [ 16,19,22 ].

Some of the existing algorithms already support nominals. A tableau algorithm for Zadeh SHOIQ [ 28 ] and an algorithm to check subsumption in Godel E L++ [ 26 ] are both able to deal with nominals. There are also reductions to classical DLs for fuzzy SROIQ(D) under Zadeh [ 4 ], nite Godel [ 5 ], nite Lukasiewicz [ 10 ], and any nite t-norm [ 6 ]; but also for SHOI for every t-norm not starting with the Lukasiewicz t-norm [ 12 ].

However, to the best of our knowledge, none of the existing OR-based tableau algorithms is able to support nominals so far. This family of algorithms is interesting for several reasons: (i) it is very suitable to manage fuzzy datatypes [ 31 ] or fuzzy concepts without a counterpart in classical DLs, such as fuzzy modi ed concepts [ 31 ] or aggregated concepts [ 11 ]; (ii) it makes it possible to reason with other t-norms di erent than Godel [ 8 ]; and (iii) the arguably most popular fuzzy ontology reasoner fuzzyDL implements one of these algorithms [ 7 ].

The objective of this paper is to start lling this gap by proposing a novel decision procedure for a fuzzy DL with individual value restrictions, namely ALCB. ALCB is the basic DL language ALC [ 31 ] extended with individual value restrictions. Under the restriction that the TBox is acyclic, our algorithm applies for Lukasiewicz, Zadeh fuzzy DLs, and for classical DLs.

The rest of this paper is organised as follows. Section 2 includes some preliminary notions. Section 3 presents our reasoning algorithm and Section 4 a running example. Finally, Section 5 sets out some conclusions and ideas for future work. 2

Fuzzy DLs Basics

In this section we overview some basic de nitions on mathematical fuzzy logic and the fuzzy DL ALCB (see [ 25,33 ] for a more in depth presentation). Mathematical Fuzzy Logic. In Mathematical Fuzzy Logic [ 21 ], the usual convention prescribing that a statement is either true or false is changed and is a matter of degree measured on an ordered scale that is no longer f0; 1g, but e.g., [0; 1]. This degree is called degree of truth of the logical statement in the interpretation I. For us, fuzzy statements have the form h ; i, where 2 (0; 1] and is a statement, encoding that the degree of truth of is greater than or equal to .

Fuzzy logics provide compositional calculi of degrees of truth. The conjunction, disjunction, complement and implication operations are performed in the fuzzy case by a t-norm function , a t-conorm function , a negation function and an implication function ), respectively (see [ 21 ] for de nitions and properties of these functions). A quadruple composed by a t-norm, a t-conorm, an implication function and a negation function determines a fuzzy logic. One usually distinguishes three fuzzy logics, namely Lukasiewicz, Godel, and Product [ 21 ], due to the fact that any continuous t-norm can be obtained as a combination of Lukasiewicz, Godel, and Product t-norm [ 27 ]. It is also usual to consider also Zadeh logic. The combination functions of these logics can be found in Table 1.

It is easy to see that Zadeh fuzzy logic can be expressed using Lukasiewicz fuzzy logic, as min( ; ) = L ( )L ); max( ; ) = 1 min(1 ; 1 ), and )KD = max(1 ; ). This latter implication is called Kleene-Dienes implication. The name of Zadeh fuzzy logic is used following the tradition in the setting of fuzzy DLs, even if the name may lead to confusion because the logic does not usually include Rescher implication, sometimes called Zadeh implication as well. This implication is de ned as = 1 if ; 0 otherwise. The Fuzzy DL ALCB. This logic is obtained by extending fuzzy ALC with individual value restrictions (indicated with the letter B). It is a sublogic of the fuzzy DL presented at [ 32 ]. Let A be a set of concept names (also called atomic concepts), R be a set of role names, and I be a set of individual names. Each role R 2 R is also called an object property. The set of concepts (denoted C; D) is built from concept names A 2 A using connectives and quanti cation constructs over roles R and individuals a 2 I, according to the following syntactic rule: C; D !

A j (atomic concept)

> j (universal concept) ? j (bottom concept) :C j (concept negation) C u D j (concept conjunction) C t D j (concept disjunction) 8R:C j (universal restriction) 9R:C j (existential restriction) 9R:fag j (individual value restriction ) : Now we will de ne the axioms that can be expressed in a fuzzy ontology. A fuzzy knowledge base or fuzzy ontology is a tuple K = hA; T i, where A is an ABox with assertional axioms and T is a TBox with terminological axioms. In the axioms, we will use 2 (0; 1] to denote a truth value. If is omitted, = 1 is assumed.

An ABox A (Assertional Box) is a nite set of concept assertions or role assertions. A concept assertion ha :C; i states that a is an instance of concept C to degree at least . Furthermore, a role assertion h(a1; a2) :R; i indicates that (a1; a2) is an instance of role R to degree at least .

A TBox T (Terminological Box) is a nite set of General Concept Inclusion (GCI) axioms of the form hC v D; i, indicating that C is a sub-concept of D to degree at least . C is called the head and D is the body of the axiom. C = D can be used as a shorthand for both hC v D; 1i and hD v C; 1i. For a concept name A, we say that a de nitional axiom is of the form A = C, while a primitive inclusion axiom is of the form A v C. Furthermore, we say that A1 directly uses A2 w.r.t. T if A1 is the head of some axiom and A2 occurs in its body. Let uses be the transitive closure of the relation directly uses. T is acyclic if it has primitive or de nitional axioms only, a concept name A is the head of at most one de nitional axiom in T , there is no concept name A in the head of both a de nitional and primitive inclusion axiom, and there is no concept name A such that A uses A.

Example 1. We have built a fuzzy wine ontology 3 according to the FuzzyOWL 2 proposal [ 9 ]. Ontologies often use individual value restrictions to state geographical origins. For instance, the fuzzy wine ontology contains the following de nition of Tuscan wines: TuscanWine = Wine u 9locatedIn:fTuscanyRegiong. Now, let us formally specify the semantics. Let us x a fuzzy logic. In classical DLs, an interpretation I maps e.g., a concept C into a set of individuals CI

I , i.e., I maps C into a function CI : I ! f0; 1g (either an individual belongs to the extension of C or does not belong to it). However, in fuzzy DLs, I maps C into a function CI : I ! [0; 1] and, thus, an individual belongs to the extension of C to some degree in [0; 1], i.e., CI is a fuzzy set. Speci cally, a fuzzy interpretation is a pair I = ( I ; I ) consisting of a non-empty (crisp) set I (the domain) and of a fuzzy interpretation function I that assigns:

1. to each atomic concept A a function AI : I ! [0; 1];

2. to each object property R a function RI : I I ! [0; 1]; 3. to each individual a an element aI 2 I such that aI 6= bI if a 6= b (called

Unique Name Assumption, UNA). UNA is often not assumed in DLs. Let x; y 2 I be elements of the domain. The fuzzy interpretation function is extended to complex concepts as follows: >I (x) = 1 ?I (x) = 0 (:C)I (x) = CI (x) (C u D)I (x) = CI (x) (C t D)I (x) = CI (x)

DI (x)

DI (x) (8R:C)I (x) = infy2 I fRI (x; y) ) CI (y)g (9R:C)I (x) = supy2 I fRI (x; y) CI (y)g (9R:fag)I (x) = RI (x; aI ) .

The satis ability of axioms is then de ned by the following conditions: 1. I satis es ha :C; i if CI (aI ) ; 2. I satis es h(a; b) :R; i if RI (aI ; bI ) ; 3. I satis es hC v D; i if infx2 I fCI (x) ) DI (x)g .

Exceptionally, Zadeh fuzzy DLs use Zadeh implication in the semantics of GCIs, since Kleene-Dienes implication produce some counter-intuitive e ects [ 4 ]. Note that classical ALCB is a particular case of this fuzzy ALCB. Finally, I is a model of K i I satis es each axiom in K. 3 http://www.straccia.info/software/FuzzyOWL/ontologies/FuzzyWine.1.0.owl Reasoning tasks. Let K be a fuzzy KB, C; D be fuzzy concepts, and of truth. We can de ne the following reasoning tasks: a degree { Consistency. K is consistent i it has a model, i.e., there is a fuzzy interpretation I satisfying every axiom in K. { Entailment : K entails an axiom h ; i i every model of K satis es h ; i. { Concept satis ability. C is satis able to at least degree (or -satis able) w.r.t. K i there is a model I of K such that CI (x) for some x 2 I . { Concept subsumption. D subsumes C to at least degree (or -subsumes) w.r.t. K i every model of K satis es the axiom hC v D; i. { Best entailment degree (BED). The BED (also called greatest lower bound) of an axiom 2 fa :C; (a; b) :R; C v Dg w.r.t. K is de ned as bed(K; ) = supf : K j= h ; ig, where sup ; = 0.

As usual in DLs and fuzzy DLs, reasoning tasks are often mutually inter-de nable and each of the previous tasks can be reduced to the BED. For instance: { K is not consistent i bed(K; a :?) = 1, where a is new individual. Recall that inconsistent ontologies entail everything. { K entails h ; i i bed(K; ) . { C is -satis able w.r.t. K i K [ fha :C; ig is consistent, where a is new individual. Note that consistency has already been reduced to the BED. { D -subsumes C w.r.t. K i bed(K; C v D) . 3

A MILP-based Reasoning Algorithm for ALCB It has recently been shown that reasoning is undecidable for several fuzzy DLs in the presence of GCIs. This is the case e.g. in Lukasiewicz [ 17 ] and Product fuzzy DLs [ 1 ]. However, this is not the case in Zadeh DLs or in Lukasiewicz DLs with an acyclic TBox [ 17 ]. In the following, we will restrict to fuzzy KBs with acyclic TBoxes in classical, Zadeh and Lukasiewicz ALCB. Note that it is enough to study the BED of a concept assertion since bed(K; (a; b) :R) = bed(K; a :9R:fbg) and, in our case, bed(K; C v D) = bed(K; a : :C t D) for a new individual a.

Our algorithm starts by applying some tableau rules that decompose complex concept expressions into simpler ones but also generate a system of inequation constraints [ 31,33 ]. These inequations have to hold in order to respect the semantics of the DL constructors. After all rules have been applied, an optimisation problem must be solved before obtaining the nal solution. This problem has a solution i the fuzzy KB is consistent. In our case, we will end up with a bounded Mixed Integer Linear Programming [ 20 ] (MILP) problem, although in other fuzzy DLs Non Linear optimisation problems can be obtained. A MILP problem consists in minimizing a linear function with respect to a set of constraints that are linear inequations in which rational and integer variables can occur. In our case, MILP problems will be a bounded with rational variables ranging over [0; 1] and integer variables ranging over f0; 1g.

We can assume without loss of generality that role assertions h(a; b) :R; i are replaced by concept assertions ha :9R:fbg; i, and that concepts are in Negation Normal Form (NNF), where the negation only appears before an atomic concept or an individual value restriction. In fact, a fuzzy concept :C can be transformed into NNF by recursively applying these de nitions: nnf(:A) = :A; nnf(:>) = ?; nnf(:?) = >; nnf(::C) = C; nnf(:(CuD)) = :Ct:D; nnf(:(CtD)) = :Cu :D; nnf(:8R:C) = 9R::C; nnf(:9R:C) = 8R::C; nnf(:9R:fag) = :9R:fag.

Algorithm 1 shows how to compute bed(K; a :C). Essentially, we consider an expression of the form ha ::C; 1 xi, where x is a [0; 1]-valued variable; this implies (a :C)I x. Then, we apply some satis ability preserving tableau rules and minimise the original variable x such that all constraints are satis ed, that is, bed(a :C; K) := inf x such that K [ fha ::C; 1 xig is consistent [ 7 ].

Our algorithm use completion-forests since an ABox might contain individuals with arbitrary roles connecting them. A completion-forest F for K is a collection of trees whose distinguished roots are arbitrarily connected by edges. { Each node v is labeled with a set L(v) containing ALCB concepts C or expressions of the forms fog and :fog. If C 2 L(v), we consider a variable xv :C meaning that v is an instance of C to degree greater than or equal to than the value of the variable xv :C . A novelty of this algorithm is the fact that if fog 2 L(v) then we consider a binary variable xv :fo . The intuition is g that xv :fog = 1 i v is interpreted as individual o. Similarly, if :fog 2 L(v) then we consider a binary variable xv ::fog with the opposite meaning, i.e., xv ::fog = 1 i v is not interpreted as individual o. { Each edge hv; wi is labeled with a set L(hv; wi) of roles R and if R 2 L(hv; wi) then we consider a variable x(v;w):R representing the degree of being hv; wi and instance of R.

A node v containing some fag 2 L(v) is called a nominal node. Speci cally, if fag 2 L(v) then v is called an a-nominal node. Note that for a nominal node v, L(v) may contain several faig and :faj g, for 1 i; j n, where n is the number of individuals occurring in K. For example we can have L(v) = ffa1g; fa2g; :fa3g; :fa4gg. The notion of successor is needed when dealing with edges. A node w is an R-successor of node v if R 2 L(hv; wi).

We associate to the forest a set CF of constraints of the form l l0, l = l0, xi 2 [0; 1]; yi 2 f0; 1g, where l; l0 are linear expressions using the variables occurring in the forest. F is then expanded by repeatedly applying the tableau rules in Table 2. Each rule instance is applied at most once, and the rules (N2), (N3) have the lowest priority. This means that they can only be applied when no other rule can be applied, right before solving the MILP problem, and hence the node v has to be one of the ai.

Let us explain Algorithm 1. Firstly, Line 1 adds to the fuzzy KB the assertion ha ::C; 1 xi, involving the variable x that will be minimized. Then, there is some preprocessing: lines 2-4 transform the concepts into NNF, lines 5-7 replace the role assertions with equivalent value restrictions, and lines 8-13 initialise the forest from the axioms in the fuzzy KB by creating a nominal node for each individual. Then, Lines 14-17 apply the tableau rules until no other rule can be applied. Next, lines 18-27 introduce some additional constraints stating the range of each variable ([0; 1] or f0; 1g). Finally, lines 28-33 return the minimised value of x if the optimisation problem has a solution; or a value 1 otherwise.

Algorithm 1 Computing bed(a0 :C0; K) in fuzzy ALCB.

Input: A concept assertion a0 :C0, a fuzzy KB K Output: BED of a0 :C0 with respect to K

Now, let us explain the rationale behind the rules. Rules (>); (?); (A); (u); (t), (8); (9); (v); (=), and (: =) have directly been derived from [ 17,31 ], so we do not comment them further.

According to the (Ass) rule, given an axiom ha :C; i and an a-nominal node v, we add C to L(v) and then add the constraint xv :fag ) xv :C to CF . Since xv :fag is binary, this is equivalent to say that either xv :fag = 0 or xv :C . That is, if v is interpreted as a, then v must belong to concept C with at least degree . Notice that we apply the rule not only to the nominal nodes created during the initialisation phase, but also to all nominal nodes created during the inference process. (8o) and (9o) are similar to the rules managing universal restrictions and existential restrictions. Note that in the (9o) rule, the equation xw:fag ) (xv:9R:fag ) x(v;w):R) 1 encodes the fact that if node w is interpreted as individual a then indeed the truth value of x(v;w):R has to be at least the truth value of xv:9R:fag.

(N1) avoids the inconsistency of having a node both interpreted and not interpreted as the same individual. (N2) deals with the UNA, and guarantees that a nominal node is not interpreted as more than one individual of the ai 2 L(v). Finally, (N3) makes sure that for every a-nominal node in the forest there is exactly one node interpreted as the individual a.

Concerning the MILP encoding of the fuzzy operators for classical, Lukasiewicz and Zadeh logics, we use the same ideas in e.g. [ 17,33 ]. Speci cally, x1 ) x2 z can be encoded as (denoted 7!) f1 x1 x2 zg. In Lukasiewicz, x1 x2 z 7! fx1 + x2 zg, while x1 x2 z 7! fy 1 z; x1 + x2 1 z y; y 2 f0; 1gg, where y is a new variable. In Zadeh, x1 x2 z 7! fx1 z; x2 zg, while x1 x2 z 7! fz x1; z x2; x1 + y z; x2 + (1 y) z; y 2 f0; 1gg, where y is a new variable. For classical DLs, any of the previous encodings is valid as long as we additionally force x1; x2 to be binary. It is convenient to chose those encodings that minimise the number of new variables.

Soundness, completeness, and termination can be proved similarly as in [ 17 ]: Proposition 1. Given a fuzzy KB K in Lukasiewicz, Zadeh, and classical ALCB with an acyclic TBox, Algorithm 1 terminates and correctly computes bed(K; a :C). 4

A Running Example

Example 2. Consider the fuzzy KB K = fb :A; c :B; a :9R:fbg t 9R:fcgg and let us show (the chosen fuzzy logic is irrelevant) that

bed(K; a :9R:A t 9R:fcg) = 1

The axioms of K are already in NNF and there are no role assertions. Furthermore, to compute bed(K; a :9R:A t 9R:fcg), the axiom ha :8R::A u :9R:fcg; 1 xi (1) is added to K. The forest initialisation creates three nodes v1; v2, and v3 being a b-nominal, c-nominal and a-nominal, respectively.

At rst, the (Ass) rule is applied and, thus, 1. A is added to L(v1); 2. B is added to L(v2); 3. 9r:fbg t 9r:fcg and 8R::A u :9R:fcg are added to L(v3); 4. CF contains so far expressions of the form xv:fag ) xv:C , namely xv1:fbg ) xv1:A 1 xv2:fcg ) xv2:B 1 xv3:fag ) xv3:9R:fbgt9R:fcg xv3:fag ) xv3:8R::Au:9R:fcg

Next, the (t) is applied to v3 and, thus,

1. 9R:fbg and 9R:fcg are added to L(v3);

2. xv3:9R:fbg xv3:9R:fcg xv3:9R:fbgt9R:fcg is added to CF .

Then, the (u) rule is applied to v3 and, thus,

1. 8R::A and :9R:fcg are added to L(v3);

2. xv3:8R::A xv3::9R:fcg xv3:8R::Au:9R:fcg is added to CF .

Next, we apply the (9o) rule to 9R:fbg 2 L(v3) and, thus,

1. R is added to L(hv3; v1i);

2. xv1:fbg ) (xv3:9R:fbg ) x(v3;v1):R)

1 is added to CF .

Now we can apply the (8) rule to L(v3) and, thus,

1. :A is added to L(v1); 2. xv3:8R::A x(v3;v1):R ) xv1::A is added to CF .

After that, we can apply the (8o) rule to L(v3) and, thus,

1. :fcg is added to L(v1);

2. xv3::9R:fcg x(v3;v1):R ) xv1::fcg is added to CF .

Then, the (N 1) rule adds fcg to L(v1) and xv1::fcg = 1 xv1:fcg to CF . Since v1 is also a c-nominal node now, we may apply the (Ass) rule to it, so

1. B is added to L(v1);

2. xv1:fcg ) xv1:B 1 is added to CF .

The (9o) rule is applied next to 9R:fcg 2 L(v3) and, thus,

1. R is added to L(hv3; v2i);

2. xv1:fcg ) (xv3:9R:fcg ) x(v3;v1):R) 3. xv2:fcg ) (xv3:9R:fcg ) x(v3;v2):R)

1 is added to CF ;

1 is added to CF .

As now node v2 has become an R-successor of v3, we may apply the (8) and (8o) rules to L(v3) and, thus, 1. :A is added to L(v2); 2. xv3:8R::A x(v3;v2):R ) xv2::A is added to CF ;

3. :fcg is added to L(v2);

4. xv3::9R:fag x(v3;v2):R ) xv2::fcg is added to CF .

The (N 1) rule adds now adds fcg to L(v2) and xv2::fcg = 1 xv2:fcg to CF . Eventually, rule (N 2) and (N 3) add the following constraints to CF : 1. xv1:fbg + xv1:fcg 1; 2. xv3:fag = 1; 3. xv1:fbg = 1; 4. xv1:fcg + xv2:fcg = 1.

Finally, we have to determine the minimal value of x such that CF is satis able. Therefore, from the last equations, we get immediately that xv1:fbg = 1, xv3:fag = 1; xv1:fcg = 0, and xv2:fcg = 1. Of course, then xv2::fcg = 0 and xv1::A = 0. The assertion a :9R:fbg t 9R:fcg implies that xv3:9R:fbg = 1 or 1 xv3:9R:fcg = 1. If xv3:9R:fbg = 1 then from xv1:fbg ) (xv3:9R:fbg ) x(v3;v1):R) we get that x(v3;v1):R = 1, while if xv3:9R:fcg = 1 from xv2:fcg ) (xv3:9R:fcg ) x(v3;v2):R) 1 we get that x(v3;v2):R = 1. Now, suppose x < 1. From Equation 1, xv3:8R::Au:9R:fcg > 0, and thus xv3:8R::A > 0 and xv3::9R:fcg > 0. If x(v3;v1):R = 1, we get a contradiction with xv1::A = 0, while if x(v3;v2):R = 1, we get a contradiction with xv2::fcg = 0. However, for x = 1 CF is satis able, so our algorithm returns x = 1. Indeed, bed(K; a :9R:A t 9R:fcg) = 1 holds. 5

Conclusions and Future Work

In this paper we have proposed the rst algorithm based on OR to reason with fuzzy DLs including individual value restrictions. In particular, we have proposed an algorithm to compute the BED in classical, Zadeh, and Lukasiewicz ALCB if the TBox is acyclic. The algorithm could be extended to the case of general TBoxes using blocking. A relevant property of the algorithm is that only one optimisation problem has to be solved, deferring the inherent non-determinism in ALCB to the optimisation problem solver.

Future work will include the extension of the algorithm to more expressive fuzzy DLs, such as SHIF B(D). Up to know, SHIF (D) is current the most expressive fuzzy DL for which there is an implementation of an OR-algorithm (the fuzzyDLsystem). On the one hand, adding inverse roles to the language seems challenging because of the possibility of having inverse functional role axioms. On the other hand, it would also be interesting to have unrestricted nominals to arbitrarily form complex concept expressions. Another possible extension is considering fuzzy nominals of the form f =og that can be used to describe fuzzy sets by enumeration of their elements [ 4 ].

Last but not least, we are aware that the current proposal is not optimal in the handling of nominal nodes, as several a-nominal nodes may occur in a completion-forest. We plan to adapt and implement the well-known node merging technique developed for classical DLs, such as for SHOIQ [ 24 ], to the fuzzy case as well, analyse the overall computational complexity and experiment the algorithm within fuzzyDL.

References

1. F. Baader , S. Borgwardt , and R. Pen ~aloza. On the decidability status of fuzzy ALC with general concept inclusions . Journal of Philosophical Logic , In press.

2. F. Baader , D. Calvanese , D. McGuinness , D. Nardi , and P. F. Patel- Schneider, editors. The Description Logic Handbook: Theory , Implementation, and Applications . Cambridge University Press, 2003 .

3. T. Berners-Lee , J. Hendler , and O. Lassila. The semantic web . The Scienti c American , 284 ( 5 ): 34 { 43 , 2001 .

4. F. Bobillo , M. Delgado , and J. Gomez-Romero . Crisp representations and reasoning for fuzzy ontologies . International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems , 17 ( 4 ): 501 { 530 , 2009 .

5. F. Bobillo , M. Delgado , J. Gomez-Romero , and U. Straccia . Fuzzy description logics under Godel semantics . International Journal of Approximate Reasoning , 50 ( 3 ): 494 { 514 , 2009 .

6. F. Bobillo , M. Delgado , J. Gomez-Romero , and U. Straccia. Joining G odel and Zadeh fuzzy logics in fuzzy description logics . International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems , 20 : 475 { 508 , 2012 .

7. F. Bobillo and U. Straccia . fuzzyDL: An expressive fuzzy description logic reasoner . In Proceedings of the 17th IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2008) , pages 923 { 930 , June 2008 .

8. F. Bobillo and U. Straccia . Fuzzy description logics with general t-norms and datatypes . Fuzzy Sets and Systems , 160 ( 23 ): 3382 { 3402 , 2009 .

9. F. Bobillo and U. Straccia . Fuzzy ontology representation using OWL 2 . International Journal of Approximate Reasoning , 52 : 1073 { 1094 , 2011 .

10. F. Bobillo and U. Straccia . Reasoning with the Lukasiewicz fuzzy description logic SROIQ . Information Sciences , 181 : 758 { 778 , 2011 .

11. F. Bobillo and U. Straccia . Aggregation operators for fuzzy ontologies . Applied Soft Computing , 13 : 3816 { 3830 , 2013 .

12. S. Borgwardt , F. Distel , and R. Pen ~aloza. How fuzzy is my fuzzy description logic? In B . Gramlich , D. Miller , and U. Sattler, editors, Proceedings of the 6th International Joint Conference on Approximated Reasoning (IJCAR 2012 ), volume 7364 of Lecture Notes in Arti cial Intelligence , pages 82 { 96 . Springer-Verlag, 2012 .

13. S. Borgwardt , F. Distel , and R. Pen ~aloza. Decidable Godel description logics without the nitely-valued model property . In Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR 2014 ). AAAI Press, 2014 .

14. S. Borgwardt and R. Pen ~aloza. The complexity of lattice-based fuzzy description logics . Journal on Data Semantics , 2 ( 1 ):1{ 19 , 2013 .

15. S. Borgwardt and R. Pen ~aloza. Consistency reasoning in lattice-based fuzzy description logics . International Journal of Approximate Reasoning , In press.

16. M. Cerami , A. Garc a-Cerdan~a, and F. Esteva . On nitely-valued fuzzy description logics . International Journal of Approximate Reasoning , In press.

17. M. Cerami and U. Straccia . On the (un)decidability of fuzzy Description Logics under Lukasiewicz t-norm . Information Sciences , 227 :1{ 21 , 2013 .

18. B. Cuenca-Grau , I. Horrocks , B. Motik , B. Parsia , P. F. Patel-Schneider , and U. Sattler . OWL 2: The next step for OWL . Journal of Web Semantics , 6 ( 4 ): 309 { 322 , 2008 .

19. A. Garc a-Cerdan~a, E. Armengol, and F. Esteva . Fuzzy Description Logics and t-norm based fuzzy logics . International Journal of Approximate Reasoning , 51 ( 6 ): 632 { 655 , 2010 .

20. M. K. H. Salkin . Foundations of Integer Programming . North-Holland, 1988 .

21. P. Hajek . Metamathematics of Fuzzy Logic. Kluwer, 1998 .

22. P. Hajek . Making fuzzy description logic more general . Fuzzy Sets and Systems , 154 ( 1 ):1{ 15 , 2005 .

23. I. Horrocks , O. Kutz , and U. Sattler . The even more irresistible SROIQ . In Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR 2006 ), pages 57 { 67 . AAAI Press, 2006 .

24. I. Horrocks and U. Sattler . A tableau decision procedure for SHOIQ . Journal of Automated Reasoning , 39 ( 3 ): 249 { 276 , 2007 .

25. T. Lukasiewicz and U. Straccia . Managing uncertainty and vagueness in description logics for the semantic web . Journal of Web Semantics , 6 : 291 { 308 , 2008 .

26. T. P. Mailis , G. Stoilos, N. Simou , G. B. Stamou , and S. D. Kollias . Tractable reasoning with vague knowledge using fuzzy EL++ . Journal of Intelligent Information Systems , 39 : 399 { 440 , 2012 .

27. P. S. Mostert and A. L. Shields . On the structure of semigroups on a compact manifold with boundary . Annals of Mathematics , 65 ( 1 ): 117 { 143 , 1957 .

28. G. Stoilos and G. Stamou . Reasoning with fuzzy extensions of OWL and OWL 2. Knowledge and Information Systems , In press.

29. G. Stoilos, G. Stamou, J. Z. Pan , V. Tzouvaras , and I. Horrocks . Reasoning with very expressive fuzzy description logics . Journal of Arti cial Intelligence Research , 30 ( 8 ): 273 { 320 , 2007 .

30. U. Straccia . Reasoning within fuzzy description logics . Journal of Arti cial Intelligence Research , 14 : 137 { 166 , 2001 .

31. U. Straccia. Description logics with fuzzy concrete domains . In Proceedings of the 21st Conference on Uncertainty in Arti cial Intelligence (UAI 2005 ), pages 559 { 567 . AUAI Press, 2005 .

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

33. U. Straccia. Foundations of Fuzzy Logic and Semantic Web Languages . CRC Studies in Informatics Series. Chapman & Hall , 2013 .

34. J. Yen . Generalizing term subsumption languages to fuzzy logic . In Proceedings of the 12th International Joint Conference on Arti cial Intelligence (IJCAI 1991 ), pages 472 { 477 , Sydney , Australia, 1991 .

35. L. A. Zadeh . Fuzzy sets . Information and Control , 8 ( 3 ): 338 { 353 , 1965 .