Complexity Sources in Fuzzy Description Logic

Abstract

In recent years many Fuzzy Description Logics (FDLs) based on in nite t-norms have been proved to be undecidable. On the other hand, several FDLs based on nite t-norms, not only have been proved to be decidable, but they have been proved to belong to the same complexity classes as the corresponding crisp DLs. In light of such results, a question that naturally arises is whether the nite-valued fuzzy framework is no more complex than the crisp-valued formalism. The aim of this work is to analyze some of the complexity sources that are not present in the crisp framework. To this end, we will consider FDL languages with low expressivity that allow us to observe how the need for more complex deciding strategies, not required in the crisp framework, arises in manyvalued FDLs.

Introduction

In recent years many Fuzzy Description Logics (FDLs) based on in nite t-norms have been proved to be undecidable. On the other hand, every FDL based on nite t-norm that has been recently studied, not only has been proved to be decidable, but it has been proved to belong to the same complexity class of the corresponding crisp DL. In light of such results, a question that naturally arises is whether the nite-valued fuzzy framework is no more complex than the crisp-valued formalism. The suspicion is that everything that can be expressed in nite-valued FDLs, can be e ciently reduced to the corresponding crisp DLs.

The aim of this work is to highlight that in the fuzzy framework we have to consider complexity sources that are not present in the crisp framework. In order to analyze this problem, we will consider FDLs where axioms and reasoning tasks use exact values and outline the changes that have to be made in classical tableau-based algorithms in order to cope with such reasoning tasks. In the second part of this work we will give an account on how the fact that Lukasiewicz conjunction is not idempotent impacts on a structural subsumption algorithm for nite Lukasiewicz logic. ? M. Cerami acknowledges support by the ESF project \Podpora vytvaren excelentn ch vyzkumnych tymu u intersektoraln mobility na Univerzite Palackeho v Olomouci II" No. CZ.1.07/2.3.00/30.0041, the project is co- nanced by the European Social Fund and the state budget of the Czech Republic. x y x ) y x ) 0

Minimum (Godel) Product (of real numbers)

min(x; y) x y n 1; if x y n 1; if x y

y; otherwise y=x; otherwise n 1; if x = 0 n 1; if x = 0 0; otherwise 0; otherwise

Table 1. The three main continuous t-norms.

Lukasiewicz max(0; x + y

1)

The present work does not pretend to be an exhaustive account on the complexity sources in many-valued FDLs, but just a starting point towards a systematic study of the complexity issues exclusive to the nite-valued framework. Even though the results presented in this work maintain the same complexity bounds as in the classical cases, they are not a proof that every language whose semantics is based on a nite t-norm is at most as complex as the corresponding classical language.

Preliminaries

Algebras of Truth Values

We will mainly focus our research to the case of nite t-norms.

De nition 1. A t-norm is a binary operation on the real unit interval [0; 1] that is associative, commutative, non-decreasing in both arguments and having 1 as neutral (unit) element. The residuum of a t-norm is a binary operation on [0; 1] such that x y z () x y ) z holds for every x; y; z 2 T . Left continuity of , i.e. the property that for any non-decreasing sequence (xi)i2I and for any y, (Wi xi) y = Wi(xi y) holds, is a su cient and necessary condition for the existence of the residuum of the t-norm . A structure h[0; 1]; ; ); 0; 1i, where is a left-continuous t-norm and ) is its residuum, is called MTL standard chain (see [ 9 ]). This structure is denoted from now on by [0; 1] . Moreover the same structure, where is a continuous t-norm and ) is its residuum, is called BL standard chain (see [ 11 ]). The most used representative of the standard chains (unique up to isomorphisms), are the ones de ned by the so-called Lukasiewicz, product and minimum t-norms and their residua (collected in Table 1). In the FDL literature, it is natural to restrict to so-called witnessed models (see [ 12 ]) when the semantics is based on an in nite algebra. Indeed, the main results reported in Section 3 follow such a restriction.

In the case of Lukasiewicz and Godel t-norms , the operations in Table 1 can be de ned on the domain of a nite subalgebra of [0; 1] . In these cases, we can talk about nite t-norms. So, for every natural number n, Ln and Gn will denote the restriction of Lukasiewicz and Godel t-norms, respectively, to the subalgebra of cardinality n over the domain T = f0; n1 1 ; : : : ; nn 21 ; 1g in the n-valued case. Notice that nite product subalgebras of [0; 1] (of cardinality > 2) do not exist, so a nite product t-norm can not be de ned.

As it has been proved in [ 16 ], every t-norm is de nable as ordinal sums of the basics continuous t-norms from Table 1. The result in [ 16 ] is the corresponding result for t-norms of the one that in [ 17 ] has been proved for families of abelian semi-groups. A simple corollary, about the restriction of this result to nite tnorms is the following Proposition.

Proposition 2. Every nite BL-chain is an ordinal sum of isomorphic copies of Lukasiewicz and Godel nite chains.

Relying on the result of Proposition 2, we will restrict our study to the case of Lukasiewicz and Godel nite chains. 2.2

Syntax

A description signature is a tuple D = hNI ; NC ; NRi, where NI = fa; b; : : : g is a countable set of individual names, NC = fA; B; : : : g is a countable set of atomic concepts or concept names and NR = fR; S; : : : g is a countable set of atomic roles or role names. Complex concepts in the FDL languages considered in this work are built inductively from atomic concepts and roles by means of the corresponding subset of the following concept constructors:

C; D !

A C u D 8R:C 9R:>

A

C C t D 9R:C C ! D atomic concept strong conjunction value restriction restricted existential quantif. atomic complementation complementation strong disjunction existential quanti cation implication

F L0 F L0 F L0 F L

AL

C U E I where A 2 NC , and R 2 NR. In the rest of the paper we will refer to the right column of the above table to denote the constructors explicitly present in each language considered. The rules for reading it are the usual one in the framework of DL (see [ 1 ]). 2.3

Semantics

Given a nite chain T = hT; ; ); 0; 1i an interpretation is a pair I = ( I ; I ) consisting of a nonempty (crisp) set I (called domain) and of a fuzzy interpretation function I that assigns a fuzzy set AI : I ! T to each concept name A 2 NC , a fuzzy relation RI : I I ! T to each role name R 2 NR and an object aI 2 I to each individual name a 2 NI . The semantics of complex concepts is a function CI : I ! T inductively de ned as follows: ( C)I (v) := (C u D)I (v) := (C t D)I (v) := (C ! D)I (v) := (8R:C)I (v) := (9R:C)I (v) := 1 CI (v) CI (v) DI (v) 1 ((1 CI (v)) (1 CI (v) ) DI (v) infw2 I fRI (v; w) ) CI (w)g supw2 I fRI (v; w) CI (w)g

DI (v))) 2.4

Axioms and Reasoning Tasks

In the fuzzy framework, axioms are not necessarily asked to take value 1. Rather they can be explicitly asked to take other values. In the literature (see [ 3 ]), there are publications where concept inclusions and assertions are allowed to take a whole set of truth values. Usually, the sets of truth values considered are included between a positive value r > 0 and 1, that is, the graded axioms have the following form: hC v D hC(a) ri; ri: hC(a) = ri: Moreover, assertion axioms can be asked to take single values only, di erent than 1 (see [ 10 ]), then having the following form: Sometimes exact value inclusions have been addressed in the literature, mainly as mathematical problems (for example in [ 10 ]). Indeed, the conditions required by these kinds of axioms are quite anti-intuitive w.r.t. the expected behavior of an inclusion axiom. For this reason we are not considering here.

Besides graded axioms, also graded notions of reasoning tasks like satis ability and subsumption can be considered. Again, these reasoning tasks can be considered either w.r.t. a lower bound (see [21] for an overview), or w.r.t. exact values (see [ 6,12 ]). Speaking about satis ability, in the rst case the question is whether there is a model I of a (possibly empty) KB, which satis es a concept C to a certain degree r0 between a value r and 1. In the second case the question is whether there is a model I of a (possibly empty) KB, which satis es a concept C to a certain degree r. Asking whether concept C is subsumed by concept D w.r.t a (possibly empty) KB to a certain degree r means asking whether, for every element x 2 I in every model I of KB, the implication CI (x) ! DI (x) always takes a value greater or equal than r. Subsumption w.r.t. an exact value is not considered for the same reason as for exact value inclusions above. 3

Lower Bounds vs Exact Values

Intuitively, the information brought by an axiom with an exact value, like (3), can be equivalently expressed by means of a lower bound axiom, like (2), plus a suitable upper bound axiom. For this reason, an exact value axiom is stronger than a lower bound axiom, since it brings with it more information. This increment on the strength side is re ected on increased computational costs.

Some consequences of these higher costs have been already studied in the in nite-valued case. In [ 5 ] it is proved, among other things, that language [0; 1] IALE (without atomic complementation) with lower bound axioms is undecidable when the algebra of truth values [0; 1] is a t-norm whose ordinal sum begins with a Lukasiewicz chain. But, if exact value axioms are allowed, language [0; 1] -IALE becomes undecidable with every in nite t-norm [0; 1] but (1) (2) (3) Godel as algebra of truth values. This result is enhanced by the results in [ 3 ] and [ 2 ]. In [ 3 ] it is proved that, when just lower bound axioms are allowed, language -SHOI without complementation is linearly reducible to classical SHOI and, therefore, its computational complexity is the same as in the classical case. In [ 2 ] on the other hand, it is proved that the simpler -ALE becomes undecidable if assertions with exact value are allowed.

Tableau-like algorithms for lower bound reasoning tasks. But even though the presence of exact value axioms does not lead to undecidability in the case of FDLs valued on a nite algebra, it indeed leads to an increase of the computational costs. In order to understand how these computational costs increase, we have to recall the basic completion rules for fresh constraint trees de ned in [19]. There, a tableau-based algorithm for concept satis ability in classical ALC has been de ned. The same algorithm has been subsequently used, expanded for more expressive languages and reasoning tasks (see [ 14 ]) and generalized to the fuzzy framework (see [ 8 ]). As we can see in [19], the classical tableau algorithm, while building the tableau interpretation, adds a new element every time it nds out an existentially quanti ed subconcept 9R:C and subsequently, it assigns concept C to the newly added element.

w ` On the other hand, when a value restriction 8R:C is found, no new element is added to the tableau interpretation under construction, but concept C is assigned to the already existing elements, if any.

As we can see for example in [ 8 ], the same procedure can be used for solving acyclic knowledge base consistency in the context of language Ln-ALC, when just lower bound axioms are allowed. The algorithms provided in [ 12 ] is still in the context of in nite-valued FDLs. But similar procedures are also used in [ 6 ] and [ 4 ] in the context of nite-valued FDLs. In [ 6 ] an algorithm for solving concept satis ability to an exact value in T-IALCE w.r.t. empty knowledge bases is provided, where T stands for any nite t-norm. In [ 4 ] an algorithm for solving knowledge base consistency to an exact value in language T-SHI w.r.t. local ABoxes is provided, where T stands for any nite residuated De Morgan lattice. Again, the interesting feature of the procedures provided in [ 6 ] and [ 4 ] is the fact that they add a new element to the tableaux-like structure both when an existential quanti cation 9R:C or a value restriction 8R:C are found. As proved in the cited publications, these di erent algorithms do not increase the computational complexity classes their languages belong to, w.r.t. the classes of the classical DL equivalent languages or to the classes of the corresponding FDL languages where just either lower bound axioms or lower bound reasoning tasks are considered. Nevertheless it translates into greater computational costs, in the sense that the size of the model to be built is greater. This means that the algorithm builds a greater propositional theory in the case of [ 6 ] and a greater constraint set in the case of [ 4 ]. Finite Lukasiewicz chains. In the case of FDLs based on nite Lukasiewicz chains, the explanation is quite simple. Due to the properties of nite Lukasiewicz chains, in fact, we have that, for every interpretation I, v 2 I and r 2 Ln: CI (v) = r i both CI (v) r and :CI (v) 1

In particular, for the case of a value restriction 8R:C, we have that 8R:CI (v) = r i both 8R:CI (v) r and 9R::CI (v) 1

That is, for deciding exact value reasoning tasks in Ln would be enough to use the simpler classical-like algorithm, but behind the satis ability of a value restriction to an exact value, there is the lower bound satis ability of an existentially quanti ed concept hidden. And for each existentially quanti ed concept a new element must be added, according to every kind of tableau algorithm. Finite Godel chains. In the case of nite Godel chains Gn, value restrictions and existentially quanti ed concepts are not interde nable by means of the negation. Nevertheless, here we want to prove, by means of a counter-example, that the classical-like algorithms can not be used in presence of exact value reasoning tasks. Indeed, consider r 2 Gn such that 0 < r < 1 and the following concept: 9R:C ! 8R:C: That concept (4) is satis able at least to a value r means that there exist an interpretation I and v 2 I , such that (9R:C ! 8R:C)I (v) r. For example, the Gn-interpretation I1:

C(w)=1 O

R(v;w)=1

v satis es (4) since (9R:C ! 8R:C)I1 (v) = 1 r. But concept (4) is not satis ed in any x 2 I1 to an exact value r < 1. Nevertheless, concept (4) is indeed satis able at point v in the Gn-interpretation I2:

C(w)=1c

C(u)=r; R(v;w)=1

R(v;u)=1 v It can indeed be easily proved that concept (4) can not be satis ed to an exact value 0 < r < 1 in any point v of a Gn-interpretation I with less than two R-successors.

Proposition 3. If concept (4) is satis ed to an exact value 0 < r < 1 in a point v of a Gn-interpretation I, then v has at least two R-successors. Proof. Suppose, in search of a contradiction, that there exist an interpretation I and v 2 I such that (9R:C ! 8R:C)I (v) = r, but v has less than two R-successors. If v has no R-successors, then it is obvious that (9R:C ! 8R:C)I (v) = 1 > r, so let us see the case when v has just one R-successor.

Let w be the unique R-successor of v. Since (9R:C ! 8R:C)I (v) = r < 1, then s = (9R:C)I (v) > (8R:C)I (v) = r. Therefore both RI (v; w) ^ CI (w) = s and RI (v; w) )Gn CI (w) = r. Since RI (v; w) )Gn CI (w) = r < 1, then we have that RI (v; w) > CI (w) = r. Therefore RI (v; w) ^ CI (w) = r < s = RI (v; w) ^ CI (w), a contradiction. Hence, any point v of a Gn-interpretation I which satis es concept (4) to an exact value 0 < r < 1 must have at least two R-successors. tu 4

Structural Subsumption Algorithms for Many-valued

FDLs

We address now the possibility of generalizing the structural subsumption algorithm for the classical description language F L . This language is interesting for us because, as it has been proved in [ 7 ], it has a polynomial time subsumption problem. Moreover, the problem of generalizing structural subsumption algorithms to the many-valued framework, as far as we know, until now has been addressed only in [22] under a semantics di erent from t-norms, but it has not still been faced with this kind of semantics. In [ 7 ] a structural subsumption algorithm SU BS?[a; b] for deciding concept subsumption in F L is presented. The fact that SU BS?[a; b] calculates subsumption in O(n2) relies on the fact that every F L concept C is equivalent to a F L concept C where each value restriction 8R: appears at most once for each nesting level. That is, for example concepts 8R:(C u D) and 8R:C u 8R:D are equivalent.

The structural subsumption algorithm SU BS?[a; b] can be indeed consistently used in order to decide 1-subsumption3 for Gn-F L . This is due to the fact that the Godel t-norm ^ works well with its residuum )Gn . That is, for every x; y; z 2 Gn: (5) (6) x )Gn (y ^ z) = (x )Gn y) ^ (x )Gn z) : Hence, correctness of algorithm SU BS?[a; b] w.r.t. 1-subsumption problem for Gn-F L is due to the fact that ('& ) ! ' is a theorem of Godel logic, while completeness can be easily deduced from the fact that, if SU BS?[a; b] returns a negative answer, then a counter-example to 1-subsumption can be easily found.

Unfortunately, the same result does not hold between Lukasiewicz t-norm Ln and its residuum )Ln . That is, there are x; y; z 2 Ln such that x )Ln (y Ln z) 6= (x )Ln y) Ln (x )Ln z) : As an example, if we take x = y = z = 0:8, then we have that x )Ln (y Ln z) = 0:8 6= 1 = (x )Ln y) Ln (x )Ln z). Since the residuum plays a fundamental role in the semantics of value restrictions in FDL, we have as a consequence that in Ln-F L , concepts 8R:(C uD) and 8R:C u8R:D are not equivalent. Nevertheless, the overall complexity of the subsumption problem does not increase. In order to see it, we will consider separately 1-subsumption and ( r)-subsumption for r 2 (0; 1). As we will see at the end of this section the notion of (= r)subsumption for r 2 (0; 1) does not make sense in Ln-F L . 1-subsumption in Ln-F L . The possibility of applying structural algorithms to a given calculus is due to the fact that concept conjunctions can be considered as sets of concepts. Since Lukasiewicz conjunction is not idempotent, complex concepts where just u appears as concept constructor can not be seen as sets of atomic concepts. In this sense, an inclusion like A v A u A which is valid in classical F L or in Gn-F L , is not a 1-subsumption in Ln-F L . Nevertheless, complex concepts in Ln-F L can be seen as multisets of simpler concepts, that is, di erent occurrences of atomic concepts are now seen as di erent elements of a given complex concept.4 This gives us the possibility of still de ning structural subsumption algorithms for Ln-F L , as showed in the following proposition. 3 Note that subsumption between two concepts in Gn-F L always takes either value 0 or value 1. Therefore, speaking about ( r)- or (= r)-subsumption in Gn-F L does not make sense. 4 In what follows, when not otherwise stated, restricted existential quanti cations will be treated as atomic concepts, with the assumption that two concepts 9R:> and 9S:> are di erent occurrences of the same concept i R = S.

Proposition 4. Let C; D be complex Ln-F L concepts where just conjunction u and restricted existential quanti cation 9R:> appear. Then C is subsumed by D i every occurrence of a conjunct A that appears in D, also appears in C, where A appears in C strictly less than n 1 times.

Proof. Let C; D be complex concepts where just conjunction u and existential quanti cation 9R:> appear. The right to left direction is trivial due to the fact that ('& ) ! ' is a theorem of Ln and, for every propositional evaluation e, it holds that e('& n: : :1 &') 2 f0; 1g. The left to right direction can be proved by contradiction. Suppose that there exists an occurrence of a conjunct A that appears in D but not in C, where A appears in C strictly less than n 1 times. We have two cases: either A is an atomic concept or A = 9R:>. In the rst case an interpretation I where I = fvg, AI (v) = nn 21 and BI (v) = 1 for B 6= A gives us an example against subsumption of C by D. In the second case, consider an interpretation I where I = fv; wg, RI (v; w) = nn 12 , and SI (v; w) = BI (v) = 1 for every atomic concept B and every role name S di erent from R. Then CI (v) > DI (v) and, therefore, I is a counterexample against subsumption of C by D. tu This is true up to conjunctions out of the scope of any quanti er. To see how does it work in the case of more complex concepts, recall that the semantics of value restrictions is de ned by means of the residuum )Ln of the Lukasiewicz t-norm. This operation is monotonic in the second argument which is again a complex conjunction. So, from Proposition 4 we easily obtain Corollary 5. Corollary 5. Let 8R:C; 8R:D be Ln-F L concepts. Then 8R:C is subsumed by 8R:D i every occurrence of an atomic concept A in D, also is in C, where the number of occurrences of A in C is strictly less than n 1, and every occurrence of a value restriction 8S:E in C is subsumed by a respectively di erent occurrence of a value restriction 8S:F in D.

From these results, a polynomial time algorithm for deciding 1-subsumption in Ln-F L can be obtained. The following Algorithm 1 is an adaption of the procedure for solving tree inclusion presented in [ 18 ] to the FDL case. Soundness and completeness of Algorithm 1 follow from Proposition 4 and Corollary 5. On the other hand, the fact that Algorithm 1 is polynomial can be showed as in [ 18 ]. Indeed, steps 1 and 5 can be performed in linear time and each matrix EE;F is at most quadratic on the size of the largest concept between C and D. Please note that EE;F contains a row for each value restriction 8R:F which is a conjunct of D and, speci cally, if there are multiple occurrences of the same expression then there are multiple rows for them. The same observation applies for the columns in EE;F . Moreover, there are at most jCj jDj di erent matrices EE;F . The only non-deterministic problem is to decide whether every value restriction 8R:F which is a conjunct of a given subconcept D0 of D is subsumed by a di erent value restriction 8R:E which is a conjunct of a given subconcept C0 of C. But, as in [ 18 ], instead of checking out this fact for di erent non-deterministic guesses, a suitable procedure for the bipartite matching problem (see [ 13 ] for example) can give an answer in polynomial time.

Algorithm 1 Ln-SU BS(1; D; C)

( r)-subsumption in Ln-F L . Saying that an Ln-F L concept C is ( r)subsumed by another Ln-F L concept D in degree greater or equal than r means that in every interpretation I and for every v 2 I we have that CI (v) ) DI (v) r. In order to design a suitable modi cation of Algorithm 1 that decides ( r)-subsumption in Ln-F L it is worth recalling that under Lukasiewicz semantics, for every propositional formula ' and every propositional evaluation e, it holds that: i e(('& : i: : &') ! ('& : j: : &')) 2 [minf1; g; 1] \ Ln j (7) That is, the value of formula ' in every propositional model, is constrained by the relation between the respective occurrences of p in both sides of the implication. Now, consider a formula of the form of (7) where ' 2 fp; qg, that is (p& : i: : &p&q& :k: : &q) ! (p& : j: : &p&q& : :l : &q) (8) Suppose, without loss of generality, that minf ji ; kl g = ji . Since minf ji ; kl g ij++kl , then the minimum assignment for (8) is obtained by a propositional evaluation j e that minimizes e((p& : i: : &p) ! (p& : : : &p)) and assigns value 1 to variable q. For the same reason, this evaluation is minimal with each number of propositional variables. In this way, we can perform a rst modi cation of Algorithm 1 by assigning a weight in step 5 to the couples in the set E. A further modi cation of Algorithm 1 consists in substituting, in step 8, a procedure for the assignment problem (see for example [ 15 ]) instead of the one for bipartite matching. Once obtained a maximal weighted matching, there should be checked that the Lukasiewicz conjunction of the weights is still greater or equal than value r. All the steps of the modi ed algorithm are still polynomial. Indeed assigning a weight to a couple E; F of concepts is just a matter of counting the occurrences of the same quanti ed or atomic concepts in E and F respectively. The assignment problem is known to be polynomial and Lukasiewicz t-norm operation is polynomial on xed values. This proves that ( still polynomial. r)-subsumption in Ln-F L is (= r)-subsumption in Ln-F L . Finally we address the (= r)-subsumption problem in Ln-F L . Indeed, if r 2 (0; 1), then there is no couple C; D of Ln-F L concepts such that C is (= r)-subsumed by D. In order to see this, for each pair C; D of Ln-F L concepts, consider the interpretation IC;D de ned by: { IC;D = fv1; : : : ; vmaxfdeg(C);deg(D)gg, being deg(C) the maximal nesting degree of concept C, { AIC;D (v) = 1, for every v 2 IC;D and every atomic concept A in C or D, { RIC;D (v; w) = 1, for every v; w 2 IC;D and every atomic role R in C or D. It is clear that such an interpretation exists for each pair C; D of Ln-F L concepts and that CIC;D (v) = 1 and DIC;D (v) = 1 for every v 2 IC;D . Hence it is impossible that an Ln-F L concept C is (= r)-subsumed by another Ln-F L concept D in degree equal to r, as w2 IC;D fCIC;D (w) ) DIC;D (w)g = 1 > r inf (9) So, IC;D is a counter-example against the existence of (= r)-subsumptions in Ln-F L . 5

Conclusions

In this paper we have tried to give an account on some complexity sources that, additionally to the ones that are inherited from classical Description Logics, are proper of the many-valued framework. In particular we have analyzed the additional work that is required from a procedure that is asked to solve reasoning tasks that are only de nable in presence of multiple truth values and the e ects of the fact that Lukasiewicz conjunction is not idempotent. In the rst case, in Section 3 we have summarized the results existing in the literature. Moreover we have tried to explain by means of examples why algorithms for deciding reasoning tasks related to an exact value appear to be more complex than those algorithms for the same reasoning tasks related to a lower bound or to the crisp case. In the second case, we have described a couple of non trivial modi cations of the classical structural subsumption algorithm that solve the 1-subsumption and the lower bound subsumption problems respectively for the language F L with semantics based on nite Lukasiewicz t-norm. These enhanced procedures show that subsumption in Ln-F L is still polynomial. As future work we plan to see whether the same modi cations to the structural subsumption algorithms that we provide here, can be extended to other languages that, in the classical case also use these kinds of algorithms. An example of these languages is the one presented in [20] about ALN . It would be also interesting to study how the behavior of structural subsumption algorithms generalizes to the case of more general nite t-norms, from the base cases studied here. Another direction for future works is a more systematic settlement of the method sketched in the present work for outlining complexity shifts in the many-valued case. 19. Schmidt-Schauss, M., Smolka, G.: Attributive concept descriptions with complements. Arti cial Intelligence 48(1), 1{26 (1991) 20. Sebastiani, S., Straccia, U.: a computationally tractable terminological logic. In: Proceedings of the 3rd Scandinavian Conference on Arti cial Intelligence. pp. 307{ 315. IOS Press (1991) 21. Straccia, U.: Foundations of Fuzzy Logic and Semantic Web Languages. Chapman & Hall (2013) 22. Yen, J.: Generalizing term subsumption languages to fuzzy logic. In: Reiter, R., Myopoulos, J. (eds.) Proc. of the 12th Int. Joint Conf. on Arti cial Intelligence (IJCAI'91). pp. 472{477 (1991)

References

1. Baader , F. , Calvanese , D. , McGuinness , D. , Nardi , D. , Patel-Schneider , P. : The Description Logic Handbook { Theory, Interpretation and Application . Cambridge University Press ( 2003 )

2. Baader , F. , Pen~aloza, R.: On the undecidability of fuzzy description logics with gcis and product t-norm . In: Tinelli, C. , Sofronie-Stokkermans , V. (eds.) Proceedings of the 8th International Symposium Frontiers of Combining Systems (FroCos 2011 ). pp. 55 { 70 . No. 6989 in Lecture Notes in Arti cial Intelligence , Springer-Verlag ( 2011 )

3. Borgwardt , S. , Distel , F. , Pen~aloza, R.: How fuzzy is my fuzzy description logic ? In: Gramlich, B. , Miller , D. , Sattler , U . (eds.) Proceedings of the 6th International Conference on Automated Reasoning (IJCAR 2012). Lecture Notes in Arti cial Intelligence , vol. 7364 , pp. 82 { 96 . Springer-Verlag ( 2012 )

4. Borgwardt , S. , Pen~aloza, R.: A tableau algorithm for fuzzy description logics over residuated de morgan lattices . In: Krotzsch, M. , Straccia , U . (eds.) Proceedings of the 6th International Conference on Web Reasoning and Rule Systems (RR 2012). Lecture Notes in Computer Science , vol. 7497 , pp. 9 { 24 . Springer ( 2012 )

5. Borgwardt , S. , Pen~aloza, R.: Undecidability of fuzzy description logics . In: Brewka, G. , Eiter , T. , McIlraith , S.A . (eds.) Proceedings of the 13th Conference on Principles of Knowledge Representation and Reasoning . pp. 232 { 242 ( 2012 )

6. Bou , F. , Cerami , M. , Esteva , F. : Concept satis ability in nite-valued fuzzy description logics is pspace-complete (extended abstract) . In: Terui, K. , Preining , N. (eds.) Proceedings of the Conference on Logic, Algebras and Truth Degrees 2012 ( LATD 2012) . pp. 44 { 48 ( 2012 )

7. Brachman , R.J. , Levesque , H.J.: The tractability of subsumption in frame based description languages . In: Proceedings of AAAI-84 , Austin, TX. pp. 34 { 37 ( 1984 )

8. Cerami , M. , Straccia , U. : On the (un)decidability of fuzzy description logics under lukasiewicz t-norm . Information Sciences 227 , 1 { 21 ( 2013 )

9. Esteva , F. , Godo , L. : Monoidal t-norm based logic: towards a logic for leftcontinuous t-norms . Fuzzy Sets and Systems 124 ( 3 ), 271 { 288 ( 2001 )

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

11. Hajek , P. : Metamathematics of Fuzzy Logic. Kluwer Academic Publisher ( 1998 )

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

13. Hopkroft , J.E. , Karp , R.M.: An n5=2 algorithm for maximum matchings in bipartite graphs . SIAM Journal on Computing 2 , 225 { 231 ( 1973 )

14. Horrocks , I. , Sattler , U. : A description logic with transitive and inverse roles and role hierarchies . Journal of Logic and Computation 9 ( 3 ), 385 { 410 ( 1999 )

15. Kuhn , H.W.: The hungarian method for the assignment problem . Naval Research Logistic Quarterly 2 , 83 { 97 ( 1955 )

16. Ling , C.H. : Representation of associative function . Publ. Mth. Debrecen 12 , 182 { 212 ( 1965 )

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

18. Reyner , S.W.: An analysis of a good algorithm for the subtree problem . SIAM Journal on Computing 6 ( 4 ), 730 { 732 ( 1977 )