Description Logics and Fuzzy Probability

1 Introduction

Description logics (DLs) have emerged as a widely accepted and used knowledge representation framework. By-andlarge, the semantics of DLs is based on relational structures. This provides a good fit for many applications, but needs to be extended if one requires concepts that involve some form of vagueness, e.g. fuzzy truth degrees. Extensions of the latter kind are commonly subsumed under the term Fuzzy Description Logics [Lukasiewicz and Straccia, 2008]. The prime example here is a logic of 'likes' where the assertion likes(a, b) may (semantically and syntactically) receive a fuzzy truth degree, depending on the strength of affection.

Orthogonal to this, many knowledge representation formalisms have been extended with probabilities, including DLs (overviews are in [Lukasiewicz, 2008; Lutz and Schr¨oder, 2010]) and first-order logics [Halpern, 1990]. Such logics make crisp statements about probabilities, e.g. that the incidence rate of a certain disease exceeds some numerical value. Semantically, this is accommodated by assigning probabilities to concepts that can then be compared, but in contrast to fuzzy logics, these comparisons are bivalent.

The fact that vagueness and probabilistic uncertainty are notions that deserve to be distinguished [Lukasiewicz and Straccia, 2008] does not preclude situations involving both.

Dirk Pattinson

Imperial College London dirk@doc.ic.ac.uk

A point in case is the word probably, a vague qualification of a degree of uncertainty. In crisp logics, this phenomenon has been approached by either giving qualitative axiomatizations of likelihood [Burgess, 1969; Halpern and Rabin, 1987] or by imposing a threshold probability above which events are considered probable [Hamblin, 1959; Herzig, 2003]. In a fuzzy logic over probability distributions, one can define the truth value of probably C for a fuzzy concept C as the expectation of C, read as a [0, 1]-valued random variable. This view goes back to Zadeh [1968] and is also taken in [H´ajek, 2007], where a fuzzy propositional logic of probably is developed and shown to be in PSPACE.

Hajek's reading of probably is global in that it depends on a single probability distribution on the model. Syntactically, this is reflected in the fact that the probably operator cannot be nested. Here, we introduce and analyse fuzzy probabilistic DLs that are interpreted locally, i.e. a distribution is associated to each point in the model, as in [Fagin and Halpern, 1994]. This allows modelling situations where, e.g., the probability of exhibiting a certain symptom depends on the disease. It elevates probability operators to the status of DL operators like existential restriction ∃R, which may be nested ad libitum, for the same reason: a local set of successors is associated to each point in the model.

While the logic of probably provides us with new expressive means for vague knowledge, it is clearly necessary to combine probably with other DL connectives for meaningful applications. To accommodate this, we formulate our results in a more abstract framework that also allows treating fuzzy roles, such as likes, crisp roles, and quantitative uncertainty. We achieve this by using coalgebraic logic, which encapsulates the precise nature of knowledge operators as well as their interpretation, making our results applicable in a wide context by instantiating the more abstract framework.

We work with Łukasiewicz semantics for fuzzy connectives, which avoids some of the counter-intuitive properties of the simpler minimalistic (or Zadeh) fuzzy logic [Kundu and Chen, 1998]. Our main technical results are generic satisfiability algorithms that instantiate to yield the first algorithm for DLs with the probably operator, overcoming difficulties related to unavailability of the finite model property for some reasoning problems; this can be combined modularly with a whole range of DL features involving crisp and fuzzy roles as well as numerical probabilities and nominals. Depending on details of the logic, our algorithms run in NEXPTIME or EXPSPACE, respectively, and in particular match the current best upper bound for Łukasiewicz fuzzy ALC, NEXPTIME as implicit in [Straccia, 2005].

Related Work An overview of fuzzy and (quantitative) probabilistic description logics is given in [Lukasiewicz and Straccia, 2008]. Early research was focused on fuzzy DLs with Zadeh semantics, whose complexity is typically that of their classical counterparts; in fact, the nature of logical consequence does not change much, either [Straccia, 2001; Stoilos et al., 2007]. Fuzzy DLs with Łukasiewicz semantics are perceived to have better logical properties and have therefore received increased recent attention, e.g. [H´ajek, 2005; Straccia, 2005; Bobillo and Straccia, 2011], but appear to have significantly higher complexity. For Łukasiewicz fuzzy ALC with general concept inclusions, even the finite model property fails [Bobillo et al., 2010], so that we focus on acyclic TBoxes.

2 Fuzzy Description Logics by Example

Fuzzy description logics come in many different flavours. Roles may be fuzzy, crisp, or probabilistic, and operators come in various shapes and formats. All extend propositional logic, which we equip with Łukasiewicz semantics throughout this work (see Section 3), and in particular include connectives ⊓ (fuzzy conjunction) and ✄ (fuzzy implication). Beyond this, our logics feature generic modal operators from a given set Λ parametrizing the syntax, to capture various modes of expression; given an operator ♥ ∈ Λ, we can form the concept ♥C from a concept C. For readability, we focus on single roles here, the extension to multiple roles even with structurally different interpretations being straightforward.

We take the interpretation of a concept C to be a map [[C]] : X → [0, 1] that assigns truth values to individuals in the carrier X of a model. If the structure underlying the model is crisp, we use thresholds to define the semantics of operators, given by

so that [[C]]α is the set of those individuals that satisfy concept C with degree at least α.

Fuzzy ALC with crisp roles. The syntax of ALC arises via Λ = {∃}, i.e. we use existential restriction as single operator. Models take the shape (X, ξ, π) where X is a set (of individuals), ξ : X → P(X) determines the relational successors and π is a fuzzy valuation of atomic concepts. Given a concept C with interpretation [[C]] : X → [0, 1], we put

using the threshold notation introduced above. The primary purpose of this logic, called ALCL(C) in the sequel, is to import relational knowledge into a fuzzy setting.

Fuzzy ALC. The syntax of fuzzy ALC is as above (∃ is the only operator) but interpreted over fuzzy relations. Thus, models are of type (X, ξ, π) as above but ξ : X → (X → [0, 1]) is fuzzy and relates x and x′ with degree ξ(x)(x′ ). The interpretation of ∃ now takes the form

where ⊓ is Łukasiewicz conjunction. It agrees with the standard semantics of fuzzy ALC [Lukasiewicz, 2008] (and is compatible with the semantics of ALCL(C)). We call this logic ALCL(F ).

Quantitative fuzzy ALC is interpreted over local probability distributions and asserts likelihoods. We use operators Mp, read 'with probability more than p', where p ∈ [0, 1]∩Q. Again, models take the form (X, ξ, π), but now ξ : X → D(X) associates a discrete probability distribution ξ(x) to each x ∈ X (i.e. D(X) = {μ : X → [0, 1] | ∑x∈X μ(x) = 1}). For a concept C we have

where [[C]] : X → [0, 1]. Informally, if the truth value of MpC at x is α, then the local measure at x assigns probability > p to the set individuals that satisfy C with degree ≥ α, and Mp picks the largest such α. The interpretation of Mp depends on the local probability distributions, thus, e.g., allowing us to model the mentioned fact that the probability of exhibiting a given symptom varies between diseases. E.g., we can express that encephalitis will show up as a headache with probability of more than 0.8 (encephalitis ✄M0.8headache). We use ALCL(Q) to refer to this logic, and ALCL(Qfin) to denote the variant that is interpreted w.r.t. finitely supported probability distributions.

The logic of probably lifts the logic of fuzzy probability [H´ajek, 2007] to a description logic context that allows arbitrary nesting of the probably operator. Syntactically, we have a single operator P (read 'probably'), interpreted over probability distributions as above, where

i.e. PC is the expectation of C under the local distribution ξ(y). Under a causal reading (different from the previous example), headache ✄ Phead trauma asserts the vague probability judgement that an observed head trauma is probably the cause of a headache. We write ALCL(P) for the logic with the probably operator, and ALCL(Pfin) to designate an interpretation over finitely supported distributions.

The logic of generally. This logic, similar to ALCL(P), has a single operator G, read 'generally', or 'with high probability'. Again, models are of the form (X, ξ, π) where ξ : X → D(X). The interpretation of G uses an explicit conversion function h : [0, 1] → [0, 1] (monotone, continuous, and piecewise linear) associating to a probability p the degree h(p) to which p is 'high'. We stipulate that

Here, α is a threshold value for membership in C, and the truth value of GC depends on both this threshold (the left conjunct) and the degree to which the likelihood of membership in C being ≥ α is considered high (the right conjunct). In this logic, denoted by ALCL(G) (and ALCL(Gfin) for its finitely supported semantics), we can express, e.g., that headaches generally respond to analgesics.

Combinations and multiple roles. The heart of the semantics of all logics discussed above is coalgebraic, i.e. models are defined in terms of observations X → TX where T can be varied as needed. This makes it easy to combine features and roles: if roles Ri are interpreted w.r.t. structures of shape X → TiX (i = 1, 2), then models X → T1X × T2X interpret their combination by projecting to the respective component.

3 Preliminaries

To account for various different reasoning principles and compositionality, we parametrize our exposition syntactically over a set Λ of unary modal operators (higher arities are straightforward). The set F(Λ) of concepts is given by

(with C ⊔D := ¬(¬C ⊓¬D) and C ✄D := ¬C ⊔D), where ♥ ∈ Λ and A is an atomic concept. The size |C| of a concept C counts the number of logical operators and atomic concepts in C. As we can emulate atomic concepts by modal operators that ignore their argument, we omit them in the following. Substitutions are maps σ : V → F(Λ) for a typically finite set V of variables; the size of σ is |σ| = ∑v∈V |σ(v)|.

The semantics is then determined by the following data. Firstly, we fix the underlying type of structures by choosing a set functor T, i.e. a construction that assigns to each set X a set TX of clusters over X, and to each map f : X → Y a map Tf : TX → TY , preserving identities and composition. Concepts are interpreted over (coalgebraic) T-models M = (X, ξ) consisting of a set X of states and a map ξ : X → TX assigning to each state x a cluster ξ(x) of successor states. E.g., if TX = [0, 1]X × [0, 1]At where At is a set of atomic concepts, then T-models are fuzzy Kripke models. Second, all operators ♥ ∈ Λ are assigned a fuzzy predicate lifting [[♥]], i.e. a family of maps

that lifts fuzzy subsets of X to fuzzy subsets of TX, subject to the naturality condition [[♥]]X (A ◦ f ) = [[♥]]Y (A) ◦ T f for f : X → Y , A ∈ [0, 1]Y . The extension [[C]]M : X → [0, 1] of a concept C in M = (X, ξ, π) is defined recursively by pointwise application of the underlying propositional connectives according to Łukasiewicz semantics, i.e. [[C ⊓D]](x) = max{0, [[C]](x) + [[D]](x) - 1} and [[¬C]](x) = 1 - [[C]](x), and the clause

We fix Λ, T, and the assignment of liftings throughout, and refer to these data collectively as a logic L.

Example 3.1 (Fuzzy coalgebraic description logics). All examples presented in Section 2 and their modular combinations can be expressed in the coalgebraic framework. E.g. for the probably-operator, TX = D(X) as in Section 2, and we have the lifting

that recovers the semantics introduced in Section 2.

We are concerned with the satisfiability problem for DLs, which comes in a number of variants depending on how we deal with truth values.

Definition 3.2 (Constraints). A comparison operator is one of =,<,>,≤,≥. A constraint σ ▷◁ κ consists of a substitution σ : V → F(Λ), a valuation κ : V → [0, 1], and a comparison operator ▷◁. We say that σ ▷◁ κ is satisfiable if there exists a T -model M = (X, ξ) and a state x ∈ X such that for all v ∈ V , [[σ(v)]]M (x) ▷◁ κ(v). The ▷◁-satisfiability problem is to decide whether a constraint σ ▷◁ κ is satisfiable.

Note that a constraint σ ▷◁ κ is essentially a conjunction ∧v∈V σ(v) ▷◁ κ(v). Evidently, ▷◁-satisfiability reduces to ≤- satisfiability for ▷◁ ∈ {=,≥}, and >-satisfiability reduces to <-satisfiability. None of ≤-satisfiability and <-satisfiability seem to reduce to the other. Note that <-satisfiability subsumes the dual of the validity problem, i.e. to decide whether a formula is always satisfied with truth degree 1.

4 Generic Closed Interval Satisfiability

We now develop generic reasoning procedures for coalgebraic fuzzy description logics, which we mainly instantiate to fuzzy probability. A substantial technical role is played by the distinction between closed and open truth degree intervals, i.e. <-satisfiability and ≤-satisfiability. Our generic algorithms are of high complexity (NEXPTIME and EXPSPACE) but match existing algorithms for fuzzy ALC, which produce exponential-size mixed integer linear programming problems [Straccia, 2005]. The model constructions that witness correctness of our algorithms remove operators layer-by-layer, leading to the following notion of decomposition.

Definition 4.1 (Top-level decomposition). A top-level decomposition of a substitution σ : V → F(Λ) is a decomposition σ = σ♯σ♭ where σ♭ : W → F(Λ), σ♯ : V → Prop(Λ(W)), and every variable in W occurs exactly once in σ♯ . Here, Λ(W) = {♥w | w ∈ W} are operator-prefixed formulas over W, and for any set Z, Prop(Z) denotes propositional combinations of elements of Z. This determines σ♯ , σ♭ uniquely up to renaming the variables in W.

In other words, the arguments of the top-most modal operators in σ are replaced with variables from W in σ♯ , and σ♭ records which formulas these variables stand for.

Definition 4.2 (Theory of a substitution). Let σ : V → F(Λ) be a substitution. The theory of σ is the set

That is, Th(σ) records the possible joint truth values that the formulas σ(v) can attain.

Definition 4.3 (Local constraints and models). A local constraint Γ = (γ, σ ▷◁ κ) over sets V,W of variables consists of a set γ ⊆ (V → [0, 1]) of valuations for V , a substitution σ : W → Prop(Λ(V )), a valuation κ : W → [0, 1], and a comparison operator ▷◁. A local model M = (X, τ, t) over V consists of a set X, a valuation τ : V → (X → [0, 1]), and a cluster t ∈ TX. We say that Γ is satisfiable if there exists M as above such that M |= Γ in the sense that for all x ∈ X, τ T (x) ∈ γ, where τ T (x)(v) = τ(v)(x), and for all w ∈ W, [[σ(w)]]M ▷◁ κ(w). Here, evaluation [[φ]]M of φ ∈ Prop(Λ(V )) over M is defined by extending the assignment

to (Łukasiewicz) propositional combinations.

Definition 4.4 (Local small model properties). We say that L has the local finite (polysize) ▷◁-model property for a comparison operator ▷◁ if whenever a local constraint (γ, σ ▷◁ κ) is satisfiable, then it is satisfiable in a local model (X, τ, t) with X finite (|X| polynomially bounded in |σ|).

Remark 4.5. It is clear that the local finite (polysize) ▷◁- model properties for ▷◁ ∈ {=,≤,≥} are equivalent, similarly for ▷◁ ∈ {<,>}. Moreover, the local finite (polysize) ≤-model property implies the local finite (polysize) <-model property. It is unlikely that the converse holds; a possible counterexample is precisely ALCL(P ) (Example 4.6). Moreover, despite the implication between the respective local small model properties, it does not seem to be the case that <-satisfiability can easily be reduced to ≤-satisfiability.

Example 4.6. It follows from results of [H´ajek, 2007] that ALCL(P) has the local polysize <-model property. The proof relies on continuity arguments and on approximating infinite sums by finite partial sums. Essentially the same arguments work for the other probabilistic logics ALCL(Q), ALCL(G). No similar result is known for ≤ in place of <, even relaxing polysize to finite. Of course, the local finite ≤-model property trivially holds for any finitely branching logic, including the finitely branching probabilistic logics ALCL(Xfin) for X ∈ {Q, P, G}; the local polysize ≤-model property then follows by results from linear programming as carried out for P in [H´ajek, 2007].

Fuzzy ALC (ALCL(F)) and ALCL(C) do have the local finite ≤-model property, which can be proved rather easily from the fact that solvability of systems Ax ≤ b of linear inequalities (for a matrix A and a vector b) is closed under infima in b; again, the polysize sharpening follows. (For ALCL(F), the local finite ≤-model property follows alternatively from results of [H´ajek, 2005], which however employ heavy-weight methods from fuzzy first-order model theory.)

Theorem 4.7 (Local reduction). Let σ : V → F(Λ) be a substitution with top-level decomposition σ = σ♯σ♭ , let ▷◁∈ {=, <, >, ≤, ≥}, and let κ : V → [0, 1] be a valuation. Then σ ▷◁ κ is satisfiable iff the local constraint

is satisfiable.

In the presence of the local finite ≤-model property, the local reduction theorem immediately implies a shallow tree model property. While in the classical case and in the very similar case of Zadeh logics [Straccia, 2001] the tree structure of models can often be exploited to obtain PSPACE decision procedures that explore one branch of the tree at time, this does not seem to be possible for Łukasiewicz logics, in which the branches are arithmetically entangled. We thus state only the arising exponential model property:

Corollary 4.8 (Exponential model property). Let L have the local polysize ≤-model property. Then every satisfiable constraint σ ≤ κ is satisfiable in a model with at most exponentially many states in |σ|.

One then typically obtains a translation of the satisfiability problem into an exponential sized constraint in a suitable formalism, depending on the nature of the modalities:

Definition 4.9. We say that L is polynomially existential firstorder if for every finite set X,

1. the set TX of clusters over X can be represented by a polynomial-sized existential first-order formula φX over the reals (i.e. TX ∼= {(y1, . . . , yn) | φ(y1, . . . , yn)}), and

2. for every ♥ ∈ Λ and every comparison operator ▷◁, the formula [[♥]]X (A)(t) ▷◁ a is expressible as an existential first-order formula over the reals in the variables a and Ax, x ∈ X, the latter representing the truth values A(x), and additional variables yi describing t ∈ TX according to 1., of polynomial size in |X|.

If, additionally, all atoms in the mentioned first-order formulas are linear inequalities, then L is polynomially MILP.

Example 4.10. The logic ALCL(P) is polynomially existential first-order: μ ∈ D(X) ⊓ [[P]]X (A)(μ) = a is expressed by the existential (in fact, quantifier-free) first-order formula

involving variables a and Ax as in Definition 4.9 and variables μx representing probabilities μ(x); the size |φX| is clearly polynomial in |X|. The logics ALCL(X), for X ∈ {C, F, Q, G}, are even polynomially MILP.

Since mixed integer linear programming is in NP and the existential fragment of the first order logic of the reals is in PSPACE [Canny, 1988], we obtain

Corollary 4.11 (Complexity of ≤-satisfiability). Let Lhave the local polysize ≤-model property, and let ▷◁ ∈ {<,≤}. Then ▷◁-satisfiability is in EXPSPACE if L is polynomially existential first-order, and in NEXPTIME if L is polynomially MILP.

Example 4.12. By the above, ▷◁-satisfiability in ALCL(C) and ALCL(F) is in NEXPTIME for ▷◁ ∈ {<,≤}. For fuzzy ALC (ALCL(F)), this is exactly the complexity of the existing algorithms [Straccia, 2005]; we do not know of any matching lower bound. Moreover, ▷◁-satisfiability for ▷◁ ∈ {<,≤} in the finitely branching probabilistic logics ALCL(Xfin) is in EXPSPACE for X = P , and in NEXPTIME for X ∈ {Q, G}.

5 Generic Open Interval Reasoning

We now analyse the case where the local finite ≤-model property and hence Corollary 4.8 are not available, a case that we are particularly interested in as it includes the general forms of the probabilistic logics ALCL(X), X ∈ {Q, P,G}. The main reason for studying the infinitely branching case instead of just assuming finite branching is to ensure that restricting to the finite does not introduce artifacts into the mechanisms of logical consequence (see, e.g., [Schockaert et al., 2009] for the effects of just restricting Łukasiewicz semantics to finitely many values).

In the absence of the local finite ≤-model property, we focus on <-satisfiability, which then brings topological and metric concepts into play [H´ajek, 2007]. Recall that a function f : X → Y between metric spaces is k-Lipschitz continuous for k ∈ R if d(f(x), f(y)) ≤ kd(x, y) for all x, y ∈ X (where we denote both metrics by d). It is one of the pleasant features of Łukasiewicz semantics that its operators are Lipschitz continuous (unlike for G¨odel or product logic). For a set X, we regard the set X → [0, 1] as a metric space, equipped with the supremum metric.

Definition 5.1 (Lipschitz logics). We say that L is Lipschitz if for every ♥ ∈ Λ there exists k♥ ∈ Q (pspace computable from ♥) such that for every every t ∈ TX, the map (X → [0, 1]) → V , A ↦→ [[♥]]X (A)(t) is k♥-Lipschitz continuous.

(Computability of Lipschitz constants is usually not an actual issue, and in fact often all operators are 1-Lipschitz.)

Example 5.2. All logics of Section 2 are Lipschitz. To see this for ALCL(P), let μ ∈ D(X) be a discrete probability distribution on a set X. We claim that [[P]]X (A)(μ) is 1Lipschitz in A: We have [[P]]X (A)(μ) = ∑x∈X μ(x)A(x), so if A,A′ : X → [0, 1] such that d(A,A′ ) < ε, then |[[P ]]X (A)(μ) - [[P ]]X (A′ )(μ)| < ∑x∈X μ(x)ε = ε.

The following facts are particular for Łukasiewicz semantics.

Lemma 5.3. Let L be Lipschitz. Then for every substitution σ : V → Prop(Λ(W)) and every t ∈ TX, the map (W → (X → [0, 1])) → (V → [0, 1]) sending τ to λa ∈ V. [[σ(a)]]τ (t) is Lipschitz continuous.

Lemma 5.4. Let L be Lipschitz. Then Th(σ) is a compact subset of V → [0, 1] for every substitution σ : V → F(Λ).

Recall that given ε > 0 and a subset A of a metric space (X, d), Uϵ(A) = {x ∈ X | d(y,A) < ϵ}, where d(y,A) = supa∈A d(y, a). By Lemma 5.4, local reduction leads back to ≤-satisfiability; we escape from this by

Theorem 5.5 (Local ε-reduction). Let L be Lipschitz and have the local finite <-model property, and let σ : V → F(Λ) be a substitution, V finite. Then there exists k, pspace computable from σ, such that for all valuations κ : V → [0, 1], the constraint σ < κ is satisfiable iff the local constraint

is satisfiable for some ε > 0.

Proof sketch. Let k be the Lipschitz constant of σ♯ (Lemma 5.3). Then 'only if' is trivial; 'if' relies on compactness (Lemma 5.4) and the local finite <-model property.

Theorem 5.6. Let L be Lipschitz and have the local polysize model property. Then <-satisfiability (and hence validity) is in EXPSPACE if L is polynomially first order, and in NEXPTIME if L is polynomially MILP.

Proof. By recursive translation of σ < κ into an exponential size existential first-order formula over the reals; the upper bounds then follow as in Corollary 4.11. The core step in the translation is local ε-reduction, in which k is explicitly computed while ε is just existentially quantified. The recursive call is then based on the observation that in the notation of Theorem 5.5 and Definition 4.3, τ T (x) ∈ Uε(Th(σ♭ )) is equivalent to satisfiability of the constraint σ♭ < τ T (x)+ε∧ σ♭ > τ T (x) - ε.

Example 5.7. By Theorem 5.6, <-satisfiability in the general forms of the probabilistic logics ALCL(X) is in EXPSPACE for X = P , and in NEXPTIME for X ∈ {Q, G}, i.e. although G is intuitively similar to P, it is computationally simpler.

Remark 5.8. The combination of logics as discussed at the end of Section 2 inherits the respective conditions of Theorem 5.6 and Corollary 4.11 from its constituents, so that the combination of logics satisfying the relevant assumptions is decidable in NEXPTIME or EXPSPACE, respectively.

Remark 5.9 (Reasoning with acyclic TBoxes). As usual, it is unproblematic to deal with acyclic TBoxes by on-the-fly expansion [Lutz, 1999] without affecting complexity.

Satisfaction operators and ABox reasoning For the sake of readability, we have omitted ABox reasoning from the presentation so far. It is easy to extend our results to cover not only ABoxes, but even nominals i, j, . . . taken from a fixed set N, and satisfaction operators @i, i ∈ N. Nominals are designated atomic concepts which are interpreted as crisp singletons, i.e. individual states in a model, which are then called named states. Concepts @iC evaluate to the truth value of C in the state i. We can then express concept assertions C(i) ▷◁ a, where C is a concept, i ∈ N, and a ∈ [0, 1], by conjuncts @iC ▷◁ a in a constraint. By using nominals in concepts, we can express also role assertions; e.g., in fuzzy ALC, (@i∃R. j) ▷◁ a is equivalent to R(i, j) ≥ a (and we can indeed also express role constraints of the form R(i, j) ≤ a, which are excluded, e.g., in [Straccia, 2005]). We do not impose the unique name assumption; distinctness of nominals i, j is expressed by (@i¬j) ≥ 1 or by (@i¬j) > 0.

The extension of our results to the arising fuzzy coalgebraic hybrid logic follows the lines of [Myers et al., 2009]. This requires adapting the notion of local constraint and local model to accommodate nominals, and restructuring the local reduction theorem. Details are omitted for lack of space; we note only that where the truth values of subformulas of the target formula and the ABox at named states are nondeterministically guessed in the crisp setting, we instead introduce existentially quantified real variables in the fuzzy setting. With these modifications, the generic complexity results obtained so far (Corollary 4.11, Theorem 5.6) extend to the hybrid case, and their instantiation to our example logics requires only minor adaptation of the proofs of the local small model properties. Taking into account modularity (Remark 5.8), we obtain the following specific upper complexity bounds:

1. Fuzzy ALCO: Reasoning with ABoxes and acyclic TBoxes in the fuzzy version of the description logic ALCO (ALC with nominals) is in NEXPTIME, even when satisfaction operators are included. To our knowledge, this logic was not previously known to be decidable (previous algorithms for fuzzy description logics with nominals [Bobillo and Straccia, 2011] are limited to the finitely-valued version of Łukasiewicz semantics).

2. Fuzzy probability: The upper bound NEXPTIME remains valid if we extend fuzzy ALCO with crisp roles, quantitative probability operators Mp, and the generally operator G. If we add the probably operator P, the upper bound jumps to EXPSPACE. Here, the comparison operators admissible in the ABox are the same as for satisfiability checking, i.e. unrestricted in the finitely branching case, and >, < in the countably branching case.

6 Conclusion

We have shown decidability of fuzzy description logics with an operator probably and variations thereof, generalizing previous results on a propositional fuzzy logic of probably [H´ajek, 2007] to a full-blown description logic featuring nested probability operators, ABoxes, acyclic TBoxes, and nominals, as well as crisp and fuzzy relational roles. The key tool here is an extension of the generic framework of coalgebraic logic [Myers et al., 2009] to the fuzzy setting, which not only enables us to prove results that apply to whole ranges of logics at once, but also allows us to use modularity results in order to obtain results for combined logics that mix various modal operators for free. An important new technical aspect that is brought into play here is the use of metric concepts such as compactness and Lipschitz continuity.

Although no tight lower bounds are known, there appears to be a substantial hitch in computational complexity caused by the arithmetic character of Łukasiewicz semantics. In future research, we will investigate the prospect of optimized reasoning in Łukasiewicz description logics, e.g. using column generation [Klinov and Parsia, 2009]. Moreover, we intend to extend the range of reasoning services, in particular to top-k query answering [Lukasiewicz and Straccia, 2007], which would, e.g., determine which candidates are most likely to be suitable for a given job.