=Paper=
{{Paper
|id=Vol-1193/paper_41
|storemode=property
|title=Complexity Sources in Fuzzy Description Logic
|pdfUrl=https://ceur-ws.org/Vol-1193/paper_41.pdf
|volume=Vol-1193
|dblpUrl=https://dblp.org/rec/conf/dlog/CeramiS14
}}
==Complexity Sources in Fuzzy Description Logic==
https://ceur-ws.org/Vol-1193/paper_41.pdf
Complexity Sources in Fuzzy Description Logic
Marco Cerami1,? and Umberto Straccia2
1
Palacký University in Olomouc, Czech Republic
marco.cerami@upol.cz
2
ISTI-CNR, Pisa, Italy
umberto.straccia@isti.cnr.it
Abstract. In recent years many Fuzzy Description Logics (FDLs) based
on infinite t-norms have been proved to be undecidable. On the other
hand, several FDLs based on finite 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 finite-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 many-
valued FDLs.
1 Introduction
In recent years many Fuzzy Description Logics (FDLs) based on infinite t-norms
have been proved to be undecidable. On the other hand, every FDL based on
finite 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 finite-valued fuzzy framework is no more complex than the
crisp-valued formalism. The suspicion is that everything that can be expressed
in finite-valued FDLs, can be efficiently 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 finite Lukasiewicz logic.
?
M. Cerami acknowledges support by the ESF project “Podpora vytvářenı́ exce-
lentnı́ch výzkumných týmů u intersektorálnı́ mobility na Univerzitě Palackého v
Olomouci II” No. CZ.1.07/2.3.00/30.0041, the project is co-financed by the Euro-
pean Social Fund and the state budget of the Czech Republic.
Minimum (Gödel) Product (of real numbers) Lukasiewicz
x∗y min(x, y) x·y max(0, x + y − 1)
1, if x ≤ y 1, if x ≤ y
n n
x⇒y y, otherwise y/x, otherwise min(1, 1 − x + y)
n n
x⇒0 1, if x = 0 1, if x = 0 1−x
0, otherwise 0, otherwise
Table 1. The three main continuous t-norms.
The present work does not pretend to be an exhaustive account on the com-
plexity sources in many-valued FDLs, but just a starting point towards a sys-
tematic study of the complexity issues exclusive to the finite-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 finite t-norm is at most as complex as the corresponding
classical language.
2 Preliminaries
2.1 Algebras of Truth Values
We will mainly focus our research to the case of finite t-norms.
Definition 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 ∈ T .
of ∗, i.e. the W
Left continuity W property that for any non-decreasing sequence (xi )i∈I
and for any y, ( i xi )∗y = i (xi ∗y) holds, is a sufficient 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 stan-
dard 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 stan-
dard chains (unique up to isomorphisms), are the ones defined 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 infinite algebra. Indeed, the main
results reported in Section 3 follow such a restriction.
In the case of Lukasiewicz and Gödel t-norms ∗, the operations in Table 1
can be defined on the domain of a finite subalgebra of [0, 1]∗ . In these cases,
we can talk about finite t-norms. So, for every natural number n, Ln and Gn
will denote the restriction of Lukasiewicz and Gödel t-norms, respectively, to
1
the subalgebra of cardinality n over the domain T = {0, n−1 , . . . , n−2
n−1 , 1} in the
n-valued case. Notice that finite product subalgebras of [0, 1]Π (of cardinality
> 2) do not exist, so a finite product t-norm can not be defined.
As it has been proved in [16], every t-norm is definable 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 finite t-
norms is the following Proposition.
Proposition 2. Every finite BL-chain is an ordinal sum of isomorphic copies
of Lukasiewicz and Gödel finite chains.
Relying on the result of Proposition 2, we will restrict our study to the case of
Lukasiewicz and Gödel finite chains.
2.2 Syntax
A description signature is a tuple D = hNI , NC , NR i, where NI = {a, b, . . . }
is a countable set of individual names, NC = {A, B, . . . } is a countable set of
atomic concepts or concept names and NR = {R, S, . . . } 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 atomic concept FL0
C uD strong conjunction FL0
∀R.C value restriction FL0
∃R.> restricted existential quantif. FL−
∼A atomic complementation AL
∼C complementation C
C tD strong disjunction U
∃R.C existential quantification E
C→D implication I
where A ∈ NC , and R ∈ 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 finite 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 interpre-
tation function ·I that assigns a fuzzy set AI : ∆I −→ T to each concept name
A ∈ NC , a fuzzy relation RI : ∆I × ∆I −→ T to each role name R ∈ NR and
an object aI ∈ ∆I to each individual name a ∈ NI . The semantics of complex
concepts is a function C I : ∆I −→ T inductively defined as follows:
(∼ C)I (v) := 1 − C I (v)
(C u D)I (v) := C I (v) ∗ DI (v)
(C t D)I (v) := 1 − ((1 − C I (v)) ∗ (1 − DI (v)))
(C → D)I (v) := C I (v) ⇒ DI (v)
(∀R.C)I (v) := inf w∈∆I {RI (v, w) ⇒ C I (w)}
(∃R.C)I (v) := supw∈∆I {RI (v, w) ∗ C I (w)}
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 ≥ ri, (1)
hC(a) ≥ ri. (2)
Moreover, assertion axioms can be asked to take single values only, different than
1 (see [10]), then having the following form:
hC(a) = ri. (3)
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 satisfia-
bility 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 satisfiability, in the first case the question is
whether there is a model I of a (possibly empty) KB, which satisfies 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 satisfies 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 ∈ ∆I in every model I of KB, the implication C I (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 incre-
ment on the strength side is reflected on increased computational costs.
Some consequences of these higher costs have been already studied in the
infinite-valued case. In [5] it is proved, among other things, that language [0, 1]∗ -
IALE (without atomic complementation) with lower bound axioms is unde-
cidable 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, lan-
guage [0, 1]∗ -IALE becomes undecidable with every infinite t-norm [0, 1]∗ but
Gödel 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 finite 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 defined in [19]. There,
a tableau-based algorithm for concept satisfiability in classical ALC has been
defined. 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 finds out
an existentially quantified subconcept ∃R.C and subsequently, it assigns concept
C to the newly added element.
•` •` >
C(u) •
w w
−→
∃R.C(v) • ∃R.C(v) •
On the other hand, when a value restriction ∀R.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.
w•O C(w)•O
−→
∀R.C(v)• ∀R.C(v)•
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.
Tableau-like algorithms for exact value reasoning tasks. Nevertheless, when ex-
act value axioms are allowed, this procedure can not be used any longer. In [12]
algorithms for concept satisfiability (without TBox) w.r.t. an exact value are
provided for languages L-ALC. The algorithm provided in these publication is
based on a reduction to the corresponding propositional logic and is very similar
to the tableaux algorithm provided in [8]. The main difference is that this algo-
rithm works by adding a new element not only when an existentially quantified
subconcept ∃R.C is found, but also when a value restriction ∀R.C has to be
computed.
•` >
C(u),D(u) •
C(w),D(w)
−→
∃R.C(v),∀R.D(v)•
∃R.C(v),∀R.D(v) •
The algorithms provided in [12] is still in the context of infinite-valued FDLs.
But similar procedures are also used in [6] and [4] in the context of finite-valued
FDLs. In [6] an algorithm for solving concept satisfiability to an exact value in
T-IALCE w.r.t. empty knowledge bases is provided, where T stands for any
finite 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 finite 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 quantification ∃R.C or
a value restriction ∀R.C are found. As proved in the cited publications, these
different 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 finite Lukasiewicz
chains, the explanation is quite simple. Due to the properties of finite Lukasiewicz
chains, in fact, we have that, for every interpretation I, v ∈ ∆I and r ∈ Ln :
C I (v) = r iff both C I (v) ≥ r and ¬C I (v) ≥ 1 − r.
In particular, for the case of a value restriction ∀R.C, we have that
∀R.C I (v) = r iff both ∀R.C I (v) ≥ r and ∃R.¬C I (v) ≥ 1 − r.
That is, for deciding exact value reasoning tasks in Ln would be enough to use the
simpler classical-like algorithm, but behind the satisfiability of a value restric-
tion to an exact value, there is the lower bound satisfiability of an existentially
quantified concept hidden. And for each existentially quantified concept a new
element must be added, according to every kind of tableau algorithm.
Finite Gödel chains. In the case of finite Gödel chains Gn , value restrictions and
existentially quantified concepts are not interdefinable 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 ∈ Gn such that 0 < r < 1 and the following concept:
∃R.C → ∀R.C. (4)
That concept (4) is satisfiable at least to a value r means that there exist an
interpretation I and v ∈ ∆I , such that (∃R.C → ∀R.C)I (v) ≥ r. For example,
the Gn -interpretation I1 :
C(w)=1•O
R(v,w)=1
v•
satisfies (4) since (∃R.C → ∀R.C)I1 (v) = 1 ≥ r. But concept (4) is not satisfied
in any x ∈ ∆I1 to an exact value r < 1. Nevertheless, concept (4) is indeed
satisfiable at point v in the Gn -interpretation I2 :
•c C(u)=r
;•
C(w)=1
R(v,w)=1 R(v,u)=1
v•
It can indeed be easily proved that concept (4) can not be satisfied 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 satisfied 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 interpreta-
tion I and v ∈ ∆I such that (∃R.C → ∀R.C)I (v) = r, but v has less than
two R-successors. If v has no R-successors, then it is obvious that (∃R.C →
∀R.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 (∃R.C → ∀R.C)I (v) = r < 1,
then s = (∃R.C)I (v) > (∀R.C)I (v) = r. Therefore both RI (v, w) ∧ C I (w) = s
and RI (v, w) ⇒Gn C I (w) = r. Since RI (v, w) ⇒Gn C I (w) = r < 1, then
we have that RI (v, w) > C I (w) = r. Therefore RI (v, w) ∧ C I (w) = r < s =
RI (v, w) ∧ C I (w), a contradiction. Hence, any point v of a Gn -interpretation I
which satisfies concept (4) to an exact value 0 < r < 1 must have at least two
R-successors. t
u
4 Structural Subsumption Algorithms for Many-valued
FDLs
We address now the possibility of generalizing the structural subsumption algo-
rithm for the classical description language FL− . 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 algo-
rithms to the many-valued framework, as far as we know, until now has been
addressed only in [22] under a semantics different from t-norms, but it has not
still been faced with this kind of semantics. In [7] a structural subsumption al-
gorithm SU BS?[a, b] for deciding concept subsumption in FL− is presented.
The fact that SU BS?[a, b] calculates subsumption in O(n2 ) relies on the fact
that every FL− concept C is equivalent to a FL− concept C ∗ where each value
restriction ∀R. appears at most once for each nesting level. That is, for example
concepts ∀R.(C u D) and ∀R.C u ∀R.D are equivalent.
The structural subsumption algorithm SU BS?[a, b] can be indeed consis-
tently used in order to decide 1-subsumption3 for Gn -FL− . This is due to the
fact that the Gödel t-norm ∧ works well with its residuum ⇒Gn . That is, for
every x, y, z ∈ Gn :
x ⇒Gn (y ∧ z) = (x ⇒Gn y) ∧ (x ⇒Gn z) . (5)
Hence, correctness of algorithm SU BS?[a, b] w.r.t. 1-subsumption problem for
Gn -FL− is due to the fact that (ϕ&ψ) → ϕ is a theorem of Gödel 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 ∈ Ln such that
x ⇒Ln (y ∗Ln z) 6= (x ⇒Ln y) ∗Ln (x ⇒Ln z) . (6)
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 -FL− , concepts ∀R.(C uD) and ∀R.C u∀R.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 ∈ (0, 1). As we will see at the end of this section the notion of (= r)-
subsumption for r ∈ (0, 1) does not make sense in Ln -FL− .
1-subsumption in Ln -FL− . 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 FL− or in Gn -FL− , is not a 1-subsumption in Ln -FL− . Nevertheless,
complex concepts in Ln -FL− can be seen as multisets of simpler concepts, that
is, different occurrences of atomic concepts are now seen as different elements of
a given complex concept.4 This gives us the possibility of still defining structural
subsumption algorithms for Ln -FL− , as showed in the following proposition.
3
Note that subsumption between two concepts in Gn -FL− always takes either value
0 or value 1. Therefore, speaking about (≥ r)- or (= r)-subsumption in Gn -FL−
does not make sense.
4
In what follows, when not otherwise stated, restricted existential quantifications will
be treated as atomic concepts, with the assumption that two concepts ∃R.> and
∃S.> are different occurrences of the same concept iff R = S.
Proposition 4. Let C, D be complex Ln -FL− concepts where just conjunction
u and restricted existential quantification ∃R.> appear. Then C is subsumed by
D iff 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
quantification ∃R.> 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
. . . &ϕ) ∈ {0, 1}. 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 = ∃R.>. In the first
case an interpretation I where ∆I = {v}, AI (v) = n−1 n−2
and B I (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 = {v, w}, RI (v, w) = n−1 n−2
, and
I I
S (v, w) = B (v) = 1 for every atomic concept B and every role name S
different from R. Then C I (v) > DI (v) and, therefore, I is a counterexample
against subsumption of C by D. t
u
This is true up to conjunctions out of the scope of any quantifier. To see how
does it work in the case of more complex concepts, recall that the semantics of
value restrictions is defined 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 ∀R.C, ∀R.D be Ln -FL− concepts. Then ∀R.C is subsumed by
∀R.D iff 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 ∀S.E in C is subsumed by a respectively different occurrence
of a value restriction ∀S.F in D.
From these results, a polynomial time algorithm for deciding 1-subsumption
in Ln -FL− 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 ∀R.F which is a conjunct of
D and, specifically, 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 |C| × |D| different matrices EE,F . The
only non-deterministic problem is to decide whether every value restriction ∀R.F
which is a conjunct of a given subconcept D0 of D is subsumed by a different
value restriction ∀R.E which is a conjunct of a given subconcept C 0 of C. But, as
in [18], instead of checking out this fact for different 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)
1: if there is an occurrence of an atomic or existential conjunct A of D that is not in
C where concept A appears in C strictly less n − 1 times then return 0
2: else
3: EC,D := ∅
4: for all value restriction ∀R.F which is a conjunct of D do
5: for all value restriction ∀R.E which is a conjunct of C do
6: EC,D (∀R.F, ∀R.E) := Ln -SU BS(1, F, E)
7: end for
8: end for
9: if there is a maximal bipartite matching for EC,D then return 1
10: else
return 0
11: end if
12: end if
(≥ r)-subsumption in Ln -FL− . Saying that an Ln -FL− concept C is (≥ r)-
subsumed by another Ln -FL− concept D in degree greater or equal than r
means that in every interpretation I and for every v ∈ ∆I we have that
C I (v) ⇒ DI (v) ≥ r. In order to design a suitable modification of Algorithm
1 that decides (≥ r)-subsumption in Ln -FL− it is worth recalling that under
Lukasiewicz semantics, for every propositional formula ϕ and every propositional
evaluation e, it holds that:
i
e((ϕ& . i. . &ϕ) → (ϕ& . j. . &ϕ)) ∈ [min{1, }, 1] ∩ Ln (7)
j
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 ϕ ∈ {p, q}, that is
(p& . i. . &p&q& . k. . &q) → (p& . j. . &p&q& . .l . &q) (8)
Suppose, without loss of generality, that min{ ji , kl } = ji . Since min{ ji , kl } ≤ i+k
j+l ,
then the minimum assignment for (8) is obtained by a propositional evaluation
e that minimizes e((p& . i. . &p) → (p& . j. . &p)) and assigns value 1 to variable
q. For the same reason, this evaluation is minimal with each number of propo-
sitional variables. In this way, we can perform a first modification of Algorithm
1 by assigning a weight in step 5 to the couples in the set E. A further mod-
ification 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 match-
ing. 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 modified 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 quantified or atomic concepts in E and F respectively. The assign-
ment problem is known to be polynomial and Lukasiewicz t-norm operation is
polynomial on fixed values. This proves that (≥ r)-subsumption in Ln -FL− is
still polynomial.
(= r)-subsumption in Ln -FL− . Finally we address the (= r)-subsumption prob-
lem in Ln -FL− . Indeed, if r ∈ (0, 1), then there is no couple C, D of Ln -FL−
concepts such that C is (= r)-subsumed by D. In order to see this, for each pair
C, D of Ln -FL− concepts, consider the interpretation IC,D defined by:
– ∆IC,D = {v1 , . . . , vmax{deg(C),deg(D)} }, being deg(C) the maximal nesting
degree of concept C,
– AIC,D (v) = 1, for every v ∈ ∆IC,D and every atomic concept A in C or D,
– RIC,D (v, w) = 1, for every v, w ∈ ∆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 -FL− con-
cepts and that C IC,D (v) = 1 and DIC,D (v) = 1 for every v ∈ ∆IC,D . Hence it is
impossible that an Ln -FL− concept C is (= r)-subsumed by another Ln -FL−
concept D in degree equal to r, as
inf {C IC,D (w) ⇒ DIC,D (w)} = 1 > r (9)
w∈∆IC,D
So, IC,D is a counter-example against the existence of (= r)-subsumptions in
Ln -FL− .
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 definable in presence of multiple truth values and the effects
of the fact that Lukasiewicz conjunction is not idempotent. In the first 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 modifications
of the classical structural subsumption algorithm that solve the 1-subsumption
and the lower bound subsumption problems respectively for the language FL−
with semantics based on finite Lukasiewicz t-norm. These enhanced procedures
show that subsumption in Ln -FL− is still polynomial. As future work we plan
to see whether the same modifications 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 finite 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.
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., Peñ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 Artificial Intelligence, Springer-Verlag
(2011)
3. Borgwardt, S., Distel, F., Peñ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 Artificial
Intelligence, vol. 7364, pp. 82–96. Springer-Verlag (2012)
4. Borgwardt, S., Peñaloza, R.: A tableau algorithm for fuzzy description logics over
residuated de morgan lattices. In: Krötzsch, 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., Peñaloza, R.: Undecidability of fuzzy description logics. In: Brewka,
G., Eiter, T., McIlraith, S.A. (eds.) Proceedings of the 13th Conference on Princi-
ples of Knowledge Representation and Reasoning. pp. 232–242 (2012)
6. Bou, F., Cerami, M., Esteva, F.: Concept satisfiability in finite-valued fuzzy de-
scription 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 left-
continuous t-norms. Fuzzy Sets and Systems 124(3), 271–288 (2001)
10. Garcı́a-Cerdañ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. Hájek, P.: Metamathematics of Fuzzy Logic. Kluwer Academic Publisher (1998)
12. Hájek, 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 bipar-
tite 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)
19. Schmidt-Schauss, M., Smolka, G.: Attributive concept descriptions with comple-
ments. Artificial Intelligence 48(1), 1–26 (1991)
20. Sebastiani, S., Straccia, U.: a computationally tractable terminological logic. In:
Proceedings of the 3rd Scandinavian Conference on Artificial 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 Artificial Intelligence
(IJCAI’91). pp. 472–477 (1991)