We analyze the complexity of subsumption in probabilistic variants of the description logic E L. In the case where probabilities apply only to concepts, we map out the borderline between tractability and EXPTIME-completeness. One outcome is that any probability value except zero and one leads to intractability in the presence of general TBoxes, while this is not the case for classical TBoxes. In the case where probabilities can also be applied to roles, we show PSPACEcompleteness. This result is (positively) surprising as the best previously known upper bound was 2-EXPTIME and there were reasons to believe in completeness for this class.
describes patients having a disease that is infectious with probability at least :25. It
was argued in [
In this paper, we establish a rather complete picture of the complexity of
subsumtion in Prob-DLs based on E L. In the first part, we consider Prob-E L in which
probabilities can only be applied to concepts, but not to roles. In [
In the second part of the paper, we consider Prob-E Lr, where probabilities can be applied to both concepts and roles, concentrating on general TBoxes. While decidability is an open problem for full Prob-E Lr, it was known that subsumption is in 2-EXPTIME and PSPACE-hard in Prob-E Lr>0;=1, where probability values are restricted to zero and one. Since subsumption in the ALC-version of Prob-E Lr>0;=1 is 2-EXPTIME-complete and the complexity of the E L-version and the ALC-version of many-dimensional DLs (such as Prob-DLs) coincides in all known cases, it was thus tempting to conjecture 2-EXPTIME-completeness also of subsumption in Prob-E Lr>0;=1. We show that this is not the case by establishing a tight PSPACE upper bound for subsumption in ProbE Lr>0;=1. This also implies PSPACE-completeness for the two-dimensional DL S5EL, in sharp contrast with the 2-EXPTIME-completeness of S5ALC .
This paper is a workshop version of [
Let NC and NR be countably infinite sets of concept names and role names. Prob-E L is the extension of E L that allows the application of probabilities to concepts, i.e., ProbE L concepts are built according to the rule
C; D ::= > j A j C u D j 9r:C j P pC where A ranges over NC, r over NR, over f<; ; =; ; >g, and p 2 [0; 1]. The concept P pC denotes the class of objects that are an instance of C with probability p. For example, the SNOMED CT concept ‘animal bite by potentially rabid animal’ can be expressed as
When we admit only a few values for and n, we put them in superscript; for example, Prob-E L>0:4;<0:1 denotes the extension of E L with P>0:4C and P<0:1C. Probabilities can be applied to roles using the concept constructors 9P pr:C where and p range over the same values as above, expressing that there is an element satisfying C that is related to the current element by the role name r with probability p. For example, the SNOMED CT concept ‘disease of possible viral origin’ can be modeled as
We denote the extension of Prob-E L with the constructor 9P pr:C with Prob-E Lr. We also consider the restriction Prob-E Lr>0;=1 of Prob-E Lr to probabilities 0 and 1 (both on concepts and roles).
The semantics of the probabilistic DLs is given in terms of a probabilistic interpretation I = ( I ; W; (Iw)w2W ; ), where I is the (non-empty) domain, W a nonempty set of possible worlds, a discrete probability distribution on W , and for each w 2 W , Iw is a classical DL interpretation with domain I . We usually write CI;w for CIw , and likewise for rI;w. For concept names A and role names r, we define the probability – pdI (A) that d 2 – pdI;e(r) that d; e 2
I is an A as (fw 2 W j d 2 AI;wg);
I are related by r as (fw 2 W j (d; e) 2 rI;wg).
Next, we extend pdI (A) to compound concepts C and define the extension CI;w of compound concepts by mutual recursion on C. The definition of pdI (C) is exactly as in the base case, with A replaced by C. The extension of compound concepts is defined as follows:
>I;w = I (9r:C)I;w = fd 2 (C u D)I;w = CI;w \ DI;w
I j 9e:(d; e) 2 rI;w ^ e 2 CI;wg (P pC)I;w = fd 2 (9P pr:C)I;w = fd 2
I j pdI (C) pg I j 9e 2 CI;w : pdI;e(r) pg A general TBox is a finite set of concept inclusions C v D, where C; D are concepts. A classical TBox is a set of concept definitions A C, where A is a concept name and the left-hand sides of concept definitions are unique. Note that cyclic definitions are allowed.
A probabilistic interpretation I satisfies a concept inclusion C v D if CI;w DI;w and a concept definition A C if AI;w = CI;w, for all w 2 W . I is a model of a TBox T if it satisfies all inclusions/definitions in T . A concept C is subsumed by a concept D relative to a TBox T (written T j= C v D) if every model I of T satisfies C v D.
The above definition is the result of transferring the notion of subsumption from
standard DLs to probabilistic DLs in a straightforward way. However, there is an
alternative variant of subsumption that is natural for probabilistic DLs: a concept C is
positively subsumed by a concept D relative to a TBox T (written T j=+ C v D)
if CI;w DI;w for every probabilistic model I = ( I ; W; (Iw)w2W ; ) and every
w 2 W with (w) > 0. Intuitively, classical subsumption is about subsumptions that
are logically implied whereas positive subsumption is about subsumptions that are
certain. For example, when T; is the empty TBox, then T; 6j= P=1A v A, but we can only
have d 2 (P=1A)I;v nAI;v when (v) = 0, thus non-subsumption is only witnessed by
worlds that we are certain to not be the actual world. Consequently, T; j=+ P=1A v A.
In the extension Prob-ALC of Prob-E L with negation studied in [
In [
Theorem 1. For all p 2 (0; 1), (positive) subsumption in Prob-E L p relative to
1. general TBoxes is EXPTIME-hard when
2. the empty TBox is EXPTIME-hard when
2 f=; >; g
2 f ; <g
Matching upper bounds are an immediate consequence of the fact that each logic
ProbE L p is a fragment of the DL Prob-ALCc for which subsumption was proved
EXPTIME-complete in [
First consider = and assume p 0:5. Fix a k > 0 such that k p > 1 and set T = fAi u Aj v P pBij j 1 i < j
kg
C = P pA1 u Dij = P pBij
u P pAk Intuitively, the probabilities stipulated by C sum up to > 1, thus some of the Ai have to overlap, but there is a choice as to which ones these are. Formally, we can show nonconvexity by proving that T j= C v t1 i<j k Dij , but T 6j= C v Dij for any i; j. The comparisons 2 f=; >g can be handled similarly.
Now assume that p > 0:5. We start with the case = > and use a variation of the above. The main idea is to employ P>pC to simulate P>qC, for some q 0:5, which brings us back to a case already dealt with. More precisely, let n > 0 be smallest such that n > 2(11 p) and set q = pn n + 1. An easy computation shows that 0 q < 0:5. Moreover, it can be shown that
P>pX1 u
u P>pXn v P>q(X1 u
u Xn)
which allows us to redo the above reduction with probability q < 0:5. Details are given
in the long version of [
For the remaining cases 2 f<; g, there is a very simple argument for nonconvexity even w.r.t. the empty TBox: we have > v P<pA t P<pP<pA, but neither > v P<pA nor > v P<pP<pA, and likewise when is .
When 2 f=; >; g, the proof of Theorem 1 relies on general TBoxes in a crucial way. It turns out that when we restrict ourselves to classical TBoxes, tractability can be attained even with probabilities other than 0 and 1.
Theorem 2. For all 2 f>; g and p 2 [0; 1], (positive) subsumption in ProbE L p;=1 relative to classical TBoxes is in PTIME.
To prove Theorem 2, we start with positive subsumption. We can assume p > 0 since
subsumption in Prob-E L>0;=1 is in PTIME even with general TBoxes. To prove a
PTIME upper bound, we use a ‘consequence-driven’ procedure similar to the ones in
[
A
P1 u
u Pn u C1 u
u Cm
n; m 0, and where P1; : : : ; Pn are primitive concept names and C1; : : : ; Cm are of
the form P pA, P=1A, and 9r:A with A a defined concept name (note that the top
concept is completely normalized away). It is well-known that such a normalization
can be achieved in polytime, see [
[ P=1B2CA fCBg where, here and in what follows, P ranges over P=1 and P>p. Intuitively, cert(CA) contains concepts that hold with probability 1 whenever A is satisfied in some world. The algorithm starts with the normalized input TBox and then exhaustively applies the completion rules displayed in Figure 1. As a general proviso, each rule can be applied only if it adds a concept that occurs in T and actually changes the TBox, e.g., R1 can only be applied when 9r:B0 occurs in T and 9r:B0 2= CA. Exemplarily, we explain rule R5 in more detail. If all defining concepts CB of B are certain for A, then A v P=1B, thus we can add P=1B to CA. Let T be the result of exhaustive rule application and let CA be the defining concept for A in T , for all concept names A. The ‘only if’ direction requires a careful and surprisingly subtle model construction. Lemma 1. For all defined concept names A; B, we have T j=+ A v B iff CB CA.
It is easy to see that TBox completion requires only polytime: every rule application extends the TBox, but both the number of concept definitions and of conjuncts in each concept definition is bounded by the size of the original TBox.
To prove Theorem 2 for unrestricted subsumption, we provide a Turing reduction from unrestricted subsumption to positive subsumption. We again assume that the input then replace A R2 If P=1B 2 CA TBox is in the described normal form and then exhaustively apply the rules shown in Figure 2, calling the result T with defining concept of the form CA.
Lemma 2. For all defined concept names A; B, we have T j= A v B iff CB CA.
Clearly, the Turing reduction and thus the overall algorithm runs in polytime.
It is interesting to note that the proof of Theorem 2 is based on exactly the same algorithm, for all 2 f ; >g and p 2 (0; 1]. It follows that there is in fact only a single logic Prob-E L p, for all such and p. Formally, given a Prob-E L p-concept C, 2 f ; >g and q 2 (0; 1], let C q denote the result of replacing each subconcept P pD in C with P qD in C and similarly for Prob-E L p-TBoxes T . Theorem 3. For any p; q > 0, ; 2 f>; g, E L p-concepts C; D and -TBox T , we have T j=+ C v D iff T q j=+ C q v D q, and likewise for unrestricted subsumption.
Consequently, the (potentially difficult!) choice of a concrete 2 f ; >g and p 2
(0; 1] is moot. In fact, it might be more intuitive to replace the constructor P pC with
a constructor L C that describes elements which ‘are likely to be a C’, and to replace
P=1C with the constructor C C to describe elements that ‘are certain to be a C’, see e.g.
[
S1 If 9r:B 2 CA, and CB0 then replace A
CB
CA with A S2 If T j=+ cert(CA) v P B
It is a natural question whether the PTIME upper bound for classical TBoxes extends to the case of multiple probability values (except one, which is apparently always uncritical). The following result shows that many combinations of two probability values lead to (non-convexity, thus) intractability, even without any TBox.
Theorem 4. Let 2 f>; g, and p; q 2 [0; 1). Then (positive) subsumption in
ProbqE L< pp2;, qorremlaotrievegetonetrhaelleym(ipiit)y 2TpBox1is<EqX<PTpIM2.E-hard if (i) q = 0, (ii) p 1=2 and
In particular, we cannot combine the constructors P and L mentioned above without
losing tractability. The above formulation of Theorem 4 is actually only a consequence
of a more general (but also more complicated to state) result established in the long
version of [
Adding probabilistic roles to Prob-E L tends to increase the complexity of
subsumption. While for full Prob-E Lr even decidability is open, it was shown in [
We again concentrate on subsumption between concept names and assume that the input TBox is in a certain normal form, defined as follows. A basic concept is a concept of the form >, A, P>0A, P=1A, or 9 :A, where A is a concept name and, here and in what follows, is a role, i.e., of the form r, P>0r, or P=1r with r a role name. Now, every concept inclusion in the input TBox is required to be of the form X1 u
u Xn v X with X1; : : : ; Xn; X basic concepts. It is not hard to show that every TBox can be transformed into this normal form in polynomial time such that (non-)subsumption between the concept names that occur in the original TBox is preserved.
Let T be the input TBox in normal form, CN the set of concept names that occur in T , BC the set of basic concepts in T , and ROL the set of roles in T . Call a role probabilistic if it is of the form P=1r or P>0r. Our algorithm maintains the following data structures: – a mapping Q that associates with each A 2 CN a subset Q(A) BC such that
T j= A v X for all X 2 Q(A); – a mapping Qcert that associates with each A 2 CN a subset Qcert(A) BC such that T j= A v P=1X for all X 2 Qcert(A); – a mapping R that associates with each probabilistic role 2 ROL a binary relation
R( ) on CN such that T j= A v P>0(9 :B) for all (A; B) 2 R( ).
Some intuition about the data structures is already provided above; e.g., X 2 Q(A) means that T j= A v X. However, there is also another view on these structures that will be important in what follows: they represent an abstract view of a model of T , where each set Q(A) describes the concept memberships of a domain element d in a world w with d 2 AI;w and R describes role memberships, i.e., when (A; B) 2 R( ), then d 2 AI;w implies that in some world v with positive probability, d has an element described by Q(B) as an -successor. In this context, Qcert(A) contains all concepts that must be true with probability 1 for any domain element that satisfies A in some world. Note that non-probabilistic roles r and probabilistic roles P=1r are not represented in the R( ) data structure; we will treat them in a more implicit way later on.
The data structures are initialized as follows, for all A 2 CN and relevant roles : Q(A) = f>; Ag
Qcert(A) = f>g
R( ) = ;: The sets Q( ), Qcert( ), and R( ) are then repeatedly extended by the application of various rules. Before we can introduce these rules, we need some preliminaries. As the first step, Figure 3 presents a (different!) set of rules that serves the purpose of saturating a set of concepts . We use cl( ) to denote the set of concepts that is the result of exhaustively applying the displayed rules to , where any rule can only be applied if the added concept is in BC, but not yet in . The rules access the data structure Q( ) introduced above and shall later be applied to the sets Q(A) and Qcert(A), but they will also serve other purposes as described below. It is not hard to see that rule application terminates after polynomially many steps.
R1 If X1 u : : : u Xn v X 2 T and X1; : : : ; Xn 2 then add X to R4 If A 2 R5 If 9r:A 2 R6 If 9 :A 2 R2 If P=1A 2
then add A to R3 If 9P=1r:A 2
then add 9r:A to then add P>0A to then add 9P>0r:A to and B 2 Q(A) then add 9 :B to 1. S = A for some P>0A 2 Q(A1) or S = (r; B) for some (A1; B) 2 R(P>0r); 2. each Ai 2 CN and each i 2 ROL is a probabilistic role, such that An = B; 3. (Ai; Ai 1) 2 R( i) for 1 < i n.
If t is a trace of length n, we use tk, k n, to denote the trace S; A1; 2; : : : ; k; Ak.
Intuitively, the purpose of a trace is to deal with worlds that are generated by concepts
P>0A and 9P>0r:A; there can be infinitely many such worlds as Prob-E Lr>0;=1 lacks
the finite model property, see [
(tn 1)g) if n > 1.
Note that the rules R1 to R6 are used in every step of this inductive definition. The mentioned propagation of information along traces is now as follows: if there is a trace t to B, then any domain element that satisfies B in some world must satisfy the concepts in (t) in some other world. So if for example P>0A 2 (t), we need to add P>0A also to Qcert(B) and to Q(B). Lemma 3. Let T be a Prob-E Lr>0;=1-TBox in normal form and A; B be concept names. Then T j=+ A v B iff, after exhaustive rule application, B 2 Q(A).
We now argue that the algorithm can be implemented using only polynomial space. First, it is easy to see that there can be only polynomially many rule applications: every rule application extends the data structures Q( ), Qcert( ), and R( ), but these structures consist of polynomially many sets, each with at most polynomially many elements. It thus remains to verify that each rule application can be executed using only polyspace, which is obvious for all rules except those involving traces, i.e., S6 and S7. For these rules, we first note that it is not necessary to consider all (infinitely many!) traces. In fact, a straightforward ‘pumping argument’ can be used to show that there is a trace t to B with some relevant concept C 2 (t) iff there is a non-repeating such trace, i.e., a trace t0 of length n such that for all distinct k; ` n, we have (t0k) 6= (t0`). S1 apply R1-R6 to Q(A) and Qcert(A) S2 if P B 2 Q(A)
then add P B to Qcert(A) S3 if C 2 Qcert(A)
then add P=1C and C to Q(A) S4 If 9 :B 2 Q(A) with then add (A; B) to R( ).
then add 9 :B3 to Qcert(A) S6 if t is a trace to B and P A 2
(t) then add P A to Qcert(B) S5 If P>0B1 2 Q(A), (B1; B2) 2 R( ), B3 2 Qcert(B2)
a probabilistic role S7 if t is a trace to B and 9 :A 2
(t) with a probabilistic role
Clearly, the length of non-repeating traces is bounded by 2m, m the size of T . To get to polyspace, we use a non-deterministic approach, enabled by Savitch’s theorem: to check whether there is a trace t to B with C 2 (t), we guess t step-by-step, at each time keeping only a single Ai; i and (ti) in memory. When we reach a situation where Ai = B and C 2 (ti), our guessing was successful and we apply the rule. We also maintain a binary counter of the number of steps that have been guessed so far. As soon as this counter exceeds 2m, the maximum length of non-repeating traces, we stop the guessing and do not apply the rule. Clearly, this yields a polyspace algorithm. Theorem 5. Deciding positive subsumption in Prob-E Lr>0;=1 with respect to general TBoxes is PSPACE-complete.
As a byproduct, the proof of Lemma 3 yields a unique least model (in the sense of Horn logic), thus proving convexity of Prob-E Lr>0;=1. Note that positive subsumption in Prob-E Lr>0;=1 is actually the same as subsumption in the two-dimensional description logic S5EL, which is thus also PSPACE-complete. Using a Turing reduction similar to that shown in Figure 2, we can ‘lift’ the result from positive subsumption to unrestricted subsumption.
Theorem 6. Subsumption in Prob-E Lr>0;=1 relative to general TBoxes is PSPACEcomplete. 5
We have established a fairly complete picture of the complexity of subsumption in ProbE L, although some questions remain open. We speculate that Theorem 2 can be proved also when is = with only minor changes (e.g. rule R3 becomes unsound). It would be interesting to verify the conjecture made below Theorem 4 that (positive) subsumption in Prob-E L p; q relative to classical TBoxes is in PTIME whenever p q p2 and that, otherwise, it is EXPTIME-hard relative to the empty TBox. It is even conceivable that the conjectured PTIME result can be further generalized to any set of probability values P [0; 1] as long as q p2 whenever p; q 2 P and p q. Moreover, variants of Theorem 4 that involve, additionally or exclusively, the case where is = would also be of interest.
Acknowledgements The present work was supported by the DFG project on probabilistic description logics (LU1417/1-1) and DAAD-CONACYT grant 206550.