In everyday life, it seems that when we observe something, then, while searching for explanations, we assume some explanation more plausible to others, simply because of our contextual background. Recently, a contextual reasoning approach has been presented, which takes into account this contextual background and allows us to specify context within the logic. This approach is embedded into the Weak Completion Semantics, a Logic Programming approach that aims at adequately modeling human reasoning tasks. As this approach extends the underlying three-valued Łukasiewicz logic, some formal properties of the Weak Completion Semantics do not hold anymore. In this paper, we investigate the effects of this extension with respect to former results. In particular, we present some interesting results about the complexity of contextual abduction.
Let us consider the following scenario, extended from the original version in [Cum95] and discussed in [SMVss]: If the brakes are pressed, then the car slows down. If the brakes are not ok, then car does not slow down. If the car accelerates, then the car does not slow down. If the road is slippery, then the car does not slow down. If the road is icy, then the road is slippery. If the road is downhill, then the car accelerates. If the car has snow chains on the wheels, then the road is not slippery for the car. If the car has snow chains on the wheels and the brakes are pressed, then the car does not accelerate when the road is downhill. [SvL08] proposed to introduce licenses for inferences when modeling conditionals in human reasoning and [SMVss] suggested to make these conditionals exception-tolerant in logic programs, by modeling the first conditional in the scenario above as If the brakes are pressed and nothing abnormal is the case, then the car slows down. Accordingly, we apply this idea to all conditionals in the previous scenario:
If the brakes are pressed (press) and nothing abnormal is the case (¬ab1), then the car slows down (slow down). If the brakes are not ok (¬brakes ok), then something abnormal is the case w.r.t. ab1. If the car accelerates (accelerate), then something abnormal is the case w.r.t. ab1. If the road is slippery (slippery), then something abnormal is the case w.r.t. ab1. If the road is icy (icy road) and nothing abnormal is the case (ab2), then the road is slippery. If the road is downhill (downhill) and nothing abnormal is the case (ab3), then the car accelerates (accelerate). If the car has snow chains (snow chain), then something abnormal is the case w.r.t. ab2. If the car has snow chains (snow chain) and the brakes are pressed (press), then something abnormal is the case w.r.t. ab3. ∗ The authors are mentioned in alphabetical order. According to [SMVss], when reasoning with such a scenario, abnormalities should be ignored, unless there is some reason to assume them to be true. As already observed and questioned by Reiter [Rei80], the issue is whether it is possible to specify a logic-based mechanism that allows us to avoid explicitly considering all exceptions in order to derive a conclusion w.r.t. the usual case.
In this paper, we aim at modeling this idea within a the logic programming approach, the Weak Completion Semantics [HK09a] and with the help of contextual reasoning [DHP17]. The Weak Completion Semantics [Ho¨l15] originates from [SvL08], which unfortunately had some technical mistakes. These were corrected in [HK09a], by using the threevalued Łukasiewicz logic. Since then, the Weak Completion Semantics has been successfully applied – among others – to the suppression task [DHR12], the selection task [DHR13], the belief-bias effect [PDH14a, PDH14b, Die17], to reasoning about conditionals [DH15, DHP15] and to spatial reasoning [DHH15]. [DHW14] shows the correspondence between WCS and the Well-founded Semantics [VGRS91] and that the Well-founded Semantics does not adequately model Byrne’s suppression task.
As has been shown recently in [DHP17] modeling the famous Tweety example [Rei80] under the Weak Completion Semantics leads to undesired results, namely that all exception cases have to be stated explicitly false. [DHP17] proposes to extend the underlying three-valued Łukasiewicz Semantics by a context connective and presents a contextual abductive reasoning approach.
The above introduced scenario is similar to Reiter’s goal when he discussed the Tweety example, in the sense that it describes exception cases, which we don’t want to explicitly consider.
Consider Pcar, a logic program representation of the previous described scenario, including the abnormality predicates:
Suppose that we observe the brakes are pressed, i.e. O1 = {press}: Under the WCS, we cannot derive from Pcar ∪ O1 that slow down is true, because we don’t know whether ab1 is false, which in turn cannot be derived to be false, because we don’t know whether the road is slippery, the brakes are ok or the car accelerates. We need to explicitly state that press and brakes ok are true whereas icy road, downhill and snow chain have to be assumed false such that we can derive that slow down is true. However, if there is no evidence to assume that ab1, ab2 and ab3 are true, we would like to assume the usual case, i.e. , we would like to avoid specifying explicitly that all abnormalities are not true.
Consider Pcar again with the observation that the car does not slow down, i.e. O2 = {¬slow down}. We can either explain this observation by assuming that the brakes are not pressed, E2 = {press ← ⊥}, that the road is icy, E3 = {icy road ← >}, that the brakes are not ok, E4 = {brakes ok ← ⊥} or that the road is downhill and the car has no snow chain, E5 = {downhill ← >, snow chain ← ⊥}. We would like to express that the explanation that describes the usual case seems more likely: In this case E2 is the preferred explanation, as usually, when the car does not slow down, then the brakes are not pressed. Only if there is some evidence that something abnormal is the case, i.e. if we observe that something else would suggest one of the other explanations, then some other explanation can be considered. For instance if we observe additionally that the road is slippery, we would prefer E3 over the other explanations, or if we additionally observe that the road is downhill, we would prefer E5 to the other explanations.
Let us now consider the completion of Pcar together with the observation that the brakes are pressed (press ← >) which consists of the following equivalences: slow down
ab1 press ↔ ↔ ↔ press ∧ ¬ab1. slippery slippery ∨ ¬brakes ok ∨ accelerate. accelerate >. ab2 ab3 ↔ ↔ ↔ ↔ icy road ∧ ¬ab2. icy road downhill ∧ ¬ab3 ∨ ⊥. downhill snow chain ∨ ⊥. brakes ok snow chain ∧ press ∨ ⊥. snow chain ↔ ↔ ↔ ↔ ⊥. ⊥. ⊥. ⊥.
The clauses at the very right assume the closed world assumption with respect to the atoms which are not the head of any clause in Pcar. Even though the third equivalence in the first column ispress ↔ >, we derive from the completion of Pcar that brakes ok is assumed to be false, which in turn makes ab1 true, and therefore leads us to conclude that slow down is false. However, in the usual case we would like to derive the contrary, namely that slow down is true.
The two examples above show that neither the Weak Completion Semantics nor Completion Semantics can adequately model our intention. The contextual abductive reasoning approach presented in [DHP17] proposes a way of modeling the usual case, i.e. ignoring abnormalities if there is no evidence to assume them to be true, and expressing a preference among explanations. This approach takes Pereira and Pinto’s inspection points [PP11] in abductive logic programming as >. ⊥. (1) (2) (3) starting point. In this paper we investigate several problems in terms of complexity theory, and contrast these results with properties from abductive reasoning without context. 2
We assume that the reader is familiar with logic and logic programming. The general notation and terminology is based on [Llo84] and [Ho¨l09]. 2.1
Contextual Logic Programs
A (propositional) contextual logic program P is a finite set of clauses.
L1 ∧ . . . ∧ Lm ∧ ctxt(Lm+1) ∧ . . . ∧ ctxt(Lm+p).
A is an atom and the Li with 1 ≤ i ≤ m + p are literals The atom A is called head of the clause and the subformula to the right of the implication symbol is called body of the clause. Clauses of the form (1) are called rules, clauses of the form (2) are called facts and clauses of the form (3) are called assumptions. A is called head and L1 ∧ . . . ∧ Lm ∧ ctxt(Lm+1) ∧ . . . ∧ ctxt(Lm+p) as well as > and ⊥ are called bodies of the corresponding clauses. A (contextual) program is a set of clauses. A is defined in P iff P contains a clause with head A. A is undefined in P iff A is not defined in P . The set of all atoms that are undefined in P is denoted by undef(P ). The definition of A in P is defined as def(A, P ) = {A ← body | A ← body is a rule or a fact occurring in P }. ¬A is assumed in P iff P contains an assumption with head A and def(A, P ) = 0/ . We will omit the word ‘contextual’ when we refer to (logic) programs, if not stated otherwise.
to literals and expressions of the form ctxt(L) as follows, where L is a literal and A an atom: `(¬A) = `(A) and `(ctxt(L)) = `(L). A contextual program P is acyclic with respect to a level mapping iff for every A ← L1 ∧ . . . ∧ Lm ∧ ctxt(Lm+1) ∧ . . . ∧ ctxt(Lm+p) ∈ P we find that `(A) > `(Li) for all 1 ≤ i ≤ m + p. A contextual program P is acyclic iff it is acyclic with respect to some level mapping.
2. For all A which are undefined inP , add A ← ⊥. 3. Replace all occurrences of ← by ↔.
then the resulting set is the weak completion of P , denoted by wc P [HK09b]. The just introduced concepts are clarified by Example 1.
Example 1. Consider P = {s ← r, r ← ¬p ∧ q, q ← ⊥, s ← >}. The first two clauses are rules, the third is an assumption and the fourth is a fact. s, r, q and t are defined, whereas p is not defined in P , i.e. p ∈ undef(P ). P is acyclic, as it is acyclic with respect to the following level mapping: `(s) = 2, `(r) = 1 and `(p) = `(q) = 0. The weak completion of P is wc P = {s ↔ r ∨ >, r ↔ ¬p ∧ q, q ↔ ⊥}. 2.2
Three-Valued Łukasiewicz Logic Extended by the Context Connective We consider the three-valued Łukasiewicz logic, for which the corresponding truth values are >, ⊥ and U, which mean true, false and unknown, respectively. A three-valued interpretation I is a mapping from atoms(P ) to the set of truth values {>, ⊥, U}, and is represented as a pair I = hI>, I⊥i of two disjoint sets of atoms, where
I> = {A | I(A) = >} and I⊥ = {A | I(A) = ⊥}.
Atoms which do not occur in I> ∪ I⊥ are mapped to U. The truth value of a given formula under I is determined according to the truth tables in Table 1. A three-valued model M of P is a three-valued interpretation such that M (A ← body) = > for each A ← body ∈ P . Let I = hI>, I⊥i and J = hJ>, J⊥i be two interpretations. I ⊆ J iff I> ⊆ J> and I⊥ ⊆ J⊥. I is a minimal model of P iff for no other model J of P it holds that J ⊆ I. I is the least model of P iff it is the only minimal model of P . Example 2 shows the models of the program in Example 1.
Example 2. The program P from Example 1 has different models, such as I1 = h{s}, {q, r}i, I2 = h{s, p}, {q, r}i and I3 = h{s, q}, {q, r, p}i, . . . . I1 is the least model of P . Note that I3 is not a model of the weak completion of P .
J> = {A | there is A ← body ∈ P such that I(body) = >},
J⊥ = {A | there is A ← body ∈ P and for all A ← body ∈ P , we find thatI(body) = ⊥}.
The least fixed point of Φ given P is denoted by lfp ΦP , if it exists.1 Acyclic programs admit several nice properties:
from any interpretation, and the least fixed point is a model of P [DHP17]. We define P |=wcs F iff P is acyclic and lfp ΦP |= F.
of the weak completion of P , which always exists. As Example 3 shows this does not hold for contextual programs: The weak completion of contextual programs might have more than one minimal model.
Example 3. Consider P = {s ← r, r ← ¬p ∧ q, q ← ctxt(¬p)}. Its weak completion is wc P = {s ↔ r, r ↔ ¬p ∧ q, q ↔ ctxt(¬p)}. The least fixed point of ΦP is h{s}, {q, r}i, which is a minimal model of wc P . However, yet another minimal model of wc P is h{q, r}, {p, s}i.
ΦP starting with this minimal model, then we will compute lfp ΦP . As lfp ΦP is unique and the only supported minimal model of wc P , we defineP |=wcs F iff F holds in the least fixed point ofΦP . 2.4
Complexity Classes A decision problem is a problem where the answer is either yes or no. P is the class of the decision problems that are solvable in polynomial time. NP is the class of decision problems, where the yes answers can be verified in polynomial time. Given that CONP = {L | L ∈ NP}, a language L is in the class DP iff there are two languages L1 ∈ NP and L2 ∈ CONP such that L = L1 ∩ L2. PSPACE is the class of decision problems that can be solved in polynomial space, without any time bounds. EXP is the class of the decision problems solvable in exponential time. The relation of the four classes is P ⊆ NP ⊆ DPPSPACE ⊆ EXP. A natural correspondence to the decision problem is the word problem, where the word problem deals with the question Does word w belong to language L? Here, a word is a finite string over the alphabetΣ and a language is a possibly infinite set of words overΣ, where Σ∗ denotes every word over Σ.
Let R be a binary relation on strings. R is balanced if (x, y) ∈ R implies |y| ≤ |x|k for some k ≥ 1. Let L ⊆ Σ∗ be a language. L ∈ NP iff there is a polynomially decidable and a polynomial balanced relation R such that L = {x | (x, y) ∈ R for some y } [Pap94].
A language L is polynomial-time reducible to a language L0, denoted as L ≤p L0 if there is a polynomial-time computable function f : Σ∗ 7→ Σ∗ such that for every x ∈ Σ∗, x ∈ L iff f (x) ∈ L0. Reductions are transitive, i.e. if L1 ≤p L2 and L2 ≤p L3 then L1 ≤p L3 for all languages L1, L2 and L3. Given that C is a complexity class, we say that a language L is C-hard if L ≤p L0 for all L0 ∈ C. L is C-complete if L is in C and L is C-hard.
A contextual abductive framework is a tuple hP , A, |=wcsi, consisting of an acyclic contextual program P , a set of abducibles A ⊆ AP and the entailment relation |=wcs. The set of abducibles AP is defined as
{A ← > | A is undefined inP or A is head of an exception clause in P } ∪ {A ← ⊥ | A is undefined inP and ¬A is not assumed in P }, where an exception clause is of the form ab j ← body, 1 ≤ j ≤ m.
Let an observation O be a non-empty set of ground literals. Abductive reasoning can be characterized as the problem to find an explanationE ⊆ A such that O can be inferred by P ∪ E by deductive reasoning. Often, explanations are restricted to be basic and that they are consistent with P . An explanation E is basic, if E cannot be explained by other facts or assumptions, i.e. E can only be explained by itself. It is easy to see that given an acyclic logic program P and that E ⊆ A, the resulting program P ∪ E is acyclic as well. Further, as the ΦP operator always yields a least fixed point for acyclic programs, P ∪ E is guaranteed to be consistent. We will impose a further restriction on explanations such that explanations do not allow to change the context of the observation. Formally, this is defined using the following relation: Definition 4. The strongly depends on – relation w.r.t. P is the smallest transitive relation with the following properties: 2. If L strongly depends on L0, then ¬L strongly depends on L0.
3. If L strongly depends on L0, then L strongly depends on ¬L0.
Example 5. Given P = {p ← r, p ← ctxt(q)}, p strongly depends on r and ¬r, ¬p strongly depends on r and ¬r. p does not strongly depend on q, neither on ctxt(q).
We formalize the abductive reasoning process as follows: Definition 6. Given the contextual abductive framework hP , A, |=wcsi E is a contextual explanation of O given P iff E ⊆ A, P ∪ E |=wcs O, and for all A ← > ∈ E and A ← ⊥ ∈ E there exists an L ∈ O, such that L strongly depends on A.
In the following, we abbreviate the contextual abductive framework, by referring to the abductive problem AP = hP , A, Oi. E is an explanation for the abductive problem AP = hP , A, Oi iff E is a contextual explanation of O given P .
Notice that P ∪ E is consistent since the resulting program is acyclic, and therefore a least fixed point ofΦP exists. We demonstrate the formalism by Example 7.
Example 7. Let us consider again Pcar from the introduction and recall that, if we know that ‘the brakes are pressed’ is true i.e. press ← >, then under the Weak Completion Semantics, we cannot derive from P ∪ {press ← >} that ‘slow down’ is true, because we don’t know whether the road is slippery, the brakes are OK or the car accelerates. Let us adapt Pcar, by Pccatrxt, as follows:
By iterating ΦPccatrxt until the least fixed point is reached, we obtain the following model:
h0/ , {ab1, ab2, ab3}i Note that all abnormality predicates are false, as nothing is known about ‘slippery’, ‘brakes ok’, ‘accelerate’ and ‘snow chain’. According to the truth table for ctxt in Table 1, ‘ctxt(slippery)’, ‘ctxt(brakes ok)’, ‘ctxt(accelerate)’, ‘ctxt(snow chain)’ and ‘ctxt(press)’ are evaluated to false under h0/ , 0/ i, which in turn makes ‘ab1’, ‘ab2’ and ‘ab3’ false. Assume that we observe O1 = {press}. A contextual explanation E1 for O1 has to be a subset of the set of abducibles A. A consists of the following facts and assumptions: E1 = {press ← >} is the only contextual explanation for O1. The least fixed point of the program together with the corresponding explanation is as follows:
lfp (ΦP ∪E1 ) = h{slow down, press}, {ab1, ab2, ab3}i.
Assume now, that we observe that the car does not slow down, i.e. O2 = {¬slow down}. Accordingly, the only contextual explanation for O2 is E2 = {press ← ⊥}. lfp (ΦP ∪E2 ) is as follows:
h0/ , {slow down, press, ab1, ab2, ab3}i, and indeed this model entails ‘¬slow down’. Note that neither E3 = {icy road ← >} nor E4 = {brakes ok ← ⊥} can be contextual explanations for O2, because the additional condition for contextual explanations, that ‘for all A ← > ∈ E and for all A ← ⊥ ∈ E there exists an L ∈ O, such that L strongly depends on A,’ does not hold: ‘¬slow down’ strongly depends on ‘press’ but it does not strongly depend on ‘brakes ok’ neither does it strongly depend on ‘icy road’.
Assume now that additionally to O2, we observe that the road is slippery:
O3 = O2 ∪ {slippery}.
As ‘slippery’ strongly depends on ‘icy road’, E3 is a contextual explanation for O3. lfp (ΦPccatrxt∪E3 ) is as follows: h{icy road, slippery, ab1, }, {slow down, ab2, ab3}i, entails both ‘¬slow down’ and ‘slippery’. Furthermore, E3 is the only contextual explanation for O3. 4
A contextual abductive problem A = hP , A, Oi is consistent if there is an explanation for O. We will now investigate the complexity of deciding consistency. First, we show that computing the least fixed point of ΦP for acyclic contextual programs can be done in polynomial time. From this, we can easily show that consistency is in NP. Hardness follows analogously to [HPW11].
consider contextual programs. For instance, for logic programs that do not contain the context connective, ctxt, the least fixed point of ΦP is monotonously increasing if we add facts and assumptions whose head is undefined. Unfortunately, this does not hold for contextual programs as the following example demonstrates: Example 8. Consider P = {p ← ctxt(r)}, where lfp ΦP = h0/ , {p}i. However, h0/ , {p}i 6⊆ h{r, p}, 0/ i = lfp ΦP ∪{r←>}
Example 9. Consider P = {p ← ctxt(q)}, I1 = h0/ , 0/ i h0/ , {p, q}i = I2, and F = {q ← >}.
Then ΦP (I1) = h0/ , {p, q}i h{q}, {p}i = ΦP ∪F (I2). However, lfp ΦP (I1) = h0/ , {p, q}i h{p, q}, 0/ i = lfp ΦP ∪F (I2).
resp.) after the nth application of ΦP starting from the empty interpretation, and `(A) ≤ n, then A remains true (false, resp.). We defineΦP ↑ 0 = h0/ , 0/ i and ΦP ↑ (n + 1) = ΦP (ΦP ↑ n) for all n ∈ N.
Lemma 10. Let P be a logic program that is acyclic w.r.t. a level mapping `. Let In = hIn>, In⊥i = ΦP ↑ n for all n ∈ N. If n < m, then: In> ∩ {A | `(A) ≤ n} ⊆ Im> and In⊥ ∩ {A | `(A) ≤ n} ⊆ Im⊥.
Proof. We show the claim by induction on n. For the induction base case, the claim follow straightforward since I0> = 0/ and I0⊥ = 0/ . For the induction step, assume that the claim holds for n:
In> ∩ {A | `(A) ≤ n} ⊆ Im> In⊥ ∩ {A | `(A) ≤ n} ⊆ Im⊥ for all m ∈ N with n < m, for all m ∈ N with n < m.
(4) (5) • To show: In>+1 ∩ {A | `(A) ≤ n + 1} ⊆ Ik> for all k ∈ N with n + 1 ≤ k.
1. We show it by contradiction, i.e. assume that i) A ∈ In>+1, ii) `(A) ≤ n + 1 and iii) A 6∈ Ik>. 2. As i), there is A ← body ∈ P with the property that In(body) = >. 3. As P is acyclic, `(L) < `(A) for all literals L appearing in body. For all L the following holds: (a) if L = B, then B ∈ In> and as ii) `(B) < n, by (4), B ∈ Ik>−1.
(b) if L = ¬B, then B ∈ In⊥ and as ii) `(B) < n, by (5), B ∈ Ik⊥−1. • To show: In⊥+1 ∩ {A | `(A) ≤ n + 1} ⊆ Ik⊥ for all k ∈ N with n + 1 ≤ k. (a) if L = B, then B ∈ In⊥ and as ii) `(B) < n, by (4), B ∈ Ik⊥−1.
(b) if L = ¬B, then B ∈ In> and as ii) `(B) < n, by (5), B ∈ Ik>−1.
3. By 2a and 2b follows that Ik−1(body) = ⊥ for all A ∈ body ∈ P . Accordingly, A ∈ Jk⊥ which contradicts iii). Proposition 11. Computing lfp ΦP can be done in polynomial time for acyclic logic programs P .
that ΦP ↑ n = ΦP ↑ m for all m > n. We show that n is polynomially restricted in P as follows: The number of atoms appearing in P is polynomially restricted in the length of the string P . Consequently, we can assume a maximum level m such that `(A) ≤ m for all atoms A appearing in P . We now compute ΦP ↑ m which can be done in polynomial time. By
Theorem 12. Deciding, whether a contextual problem hP , A, Oi has an explanation is NP-complete. Proof. We first show that the problem belongs to NP, and afterwards we show NP-hard.
To show NP-membership, observe that explanations are polynomially bounded by the abductive framework. Then, showing NP-membership only requires to show that checking whether a set E is an explanation. This is done as follows:
This can be done in polynomial time [Phi10]. 2. P ∪ E |=wcs O,
Computing M = lfp ΦP ∪E can be done in polynomial time (Proposition 11). The last step is to check whether P ∪ E |=wcs L for all L ∈ O, can be done as follows. For all literals L ∈ O, if L = A, then check if A ∈ I> and if L = ¬A, then check if A ∈ I⊥ 3. for all A ← > ∈ E and for all A ← ⊥ ∈ E , respectively, there exists L ∈ O such that L strongly depends on A ← > and A ← ⊥, respectively.
The strongly depends on relation for every two literals can be checked in |P | steps, and thus the computation can be done in polynomial time.
It remains to show that consistency is NP-hard. As already consistency with no context connective is NPhard [HPW11], it easily follows that consistency is NP-hard. 5
We are not only interested in deciding whether an observation can be explained, but what can be inferred from the possible explanations. We distinguish between skeptical and credulous reasoning: Given an abductive problem AP = hP , A, Oi, F follows skeptically from AP iff AP is consistent, and for all explanations E for AP it holds that P ∪ E |=wcs F. The formula F follows credulously from AP iff there exists an explanation E of AP and P ∪ E |=wcs F. Proposition 13. Deciding if P ∪ E |=wcs F does not hold for all explanations E given AP is NP-complete. Proof. To show that the problem is in NP, we guess a E ⊆ A for AP and check in polynomial time whether E is an explanation for O and whether P ∪ E 6|=wcs F. This can be done in polynomial time.
To show that the problem is NP-hard, we can use the result from Theorem 12, by reducing consistency to the problem above, i.e. reduce the question whether a contextual problem hP , A, Oi has an explanation to the question whether there exists an explanation E such that P ∪ E 6|=wcs ¬(A ← A) for all A ∈ atoms(P ) given AP. The correctness of the construction follows from the fact that for every interpretation I, it holds that I 6|= ¬(A → A).
Proposition 14. Let L ⊆ Σ∗ be a language. Then L is NP-complete iff L is CONP-complete.
Proof. See [Pap94, Proposition 10.1].
Proposition 15. Deciding if P ∪ E |=wcs F holds for all explanations E given AP is CONP-complete. Proof. The opposite problem is shown to be NP-complete by Proposition 13. By Proposition 14, deciding the above problem is CONP-complete.
Theorem 16. The question, whether F follows skeptically from an abductive problem hP , A, Oi is DP-complete. Proof. We first show that the problem belongs to DP, and afterwards we show that it is DP-hard. Let AP = hP , A, Oi be an abductive problem and F a formula. P ∪ E |=wcs F for all explanations E for AP iff i.) AP is consistent and ii.) F follows from all explanations E for AP.
By Theorem 12, i.) is in NP and by Proposition 15, ii.) is in CONP. Hence, deciding whether F follows skeptically from AP is in DP.
Let P be a decision problem in DP. P consists of two decision problems P1 and P2, where P1 ∈ NP and P2 ∈ CONP by the definition of the class DP. By Theorem 12, i.) is NP-complete, thus we know that P1 is polynomially reducible to consistency. By Proposition 15 ii.) is CONP-complete, thus P2 is polynomially reducible to it. Hence, P can be polynomially reduced to the combined problem i) and ii.). Hence, whether F follows skeptically from hP , A, Oi is DPhard. 6
Often, one is interested in reasoning w.r.t. minimal explanations, i.e. there is no other contextual explanation E 0 ⊂ E for an observation O. If explanations are monotonic, i.e. the addition of further facts and assumptions are still an explanation, then checking minimality can be done in polynomial time [HPW11]: It is enough to check that E \ {A ← ⊥} and E \ {A ← >} is not an explanation for all A ← > ∈ E and A ← ⊥ ∈ E . Unfortunately, we cannot even guarantee that explanations are monotonic for logic programs without the context operator as Example 17 shows. However, if the set of abducibles is restricted to the set of facts and assumptions w.r.t. the undefined atoms inP , i.e. A = {A ← > | A ∈ undef(P )} ∪ {A ← ⊥ | A ∈ undef(P )} then explanations are indeed monotonic [HPW11].
Example 17. Given P = {p ← q ∧ r, p ← ¬q, q ← ⊥} and observation O = {p}. E1 = {q ← >, r ← >} is an explanation for O. E1 ⊃ {q ← >} is not an explanation for O, where E2 = 0/ ⊆ {q ← >} ⊆ E1 is again an explanation for O.
Yet, restricting the the set of abducibles, does not make explanations monotonic if we consider contextual programs, as Example 18 shows.
Example 18. Given P = {p ← q, p ← ctxt(r)} and observation O = {p}. Then, E = {q ← >} is a contextual explanation for O, but {q ← >, r ← >} ⊃ E not anymore, because r does not strongly depend on p.
As Example 19 shows, given that E is a contextual explanation for O, we cannot simply iterate over all A ← > ∈ E (A ← ⊥ ∈ E , resp.) and check whether E \ {A ← >} (E \ {A ← ⊥, resp.) is a contextual explanation for O. If this would be the case, then we could decide whether E is a minimal contextual explanation in polynomial time [Phi10]. Instead, we might have to check all subsets of E , for which there are 2|E| many, i.e. this might have to be done exponentially in time. Example 19. Consider the following program P : p ← r ∧ ¬t.
t ← ctxt(q) t ← ctxt(s) p ← r ∧ q ∧ s.
Assume that we try to contextually explain the observation O = {p}: E1 = {r ← >} and E2 = {r ← >, q ← >, s ← >} are both contextual explanations for O. As E1 ⊂ E2 holds, E1 is a minimal contextual explanation, whereas E2 is not. However, note that none of E2 \ {r ← >}, E2 \ {q ← >} or E2 \ {s ← >} is a contextual explanation for O.
Still, we can show an upper bound for the complexity of deciding minimality: Theorem 20. The question, whether a set E is a minimal explanation for an abductive problem hP , A, Oi is in PSPACE. Proof. Given that hP , A, Oi is an abductive problem, we need to check all subsets of E , in order to decide whether E is a minimal explanation for O. As we don’t need to store the subsets of E as soon as we have tested them, deciding whether
7
This paper investigates contextual abductive reasoning, a new approach embedded within the Weak Completion Semantics. We first show with the help of an example the limitations of the Weak Completion Semantics, when we want to express the preference of the usual case over the exception cases. Furthermore, we cannot syntactically specify contextual knowledge in the logic programs as they have been presented so far.
After that, we introduce contextual programs together with contextual abduction, we show how the previous limitations can be solved. This contextual reasoning approach allows us to indicate contextual knowledge and express the preference among explanations, depending on the context.
However, as has already be shown previously in [DHP17], some advantageous properties which hold for programs under the Weak Completion Semantics, do not hold for contextual programs. For instance, the ΦP operator is not necessarily monotonic. Furthermore, if a contextual program contains a cycle, it might not even have a fixed point.
mial time for acyclic contextual programs. Thereafter, we show that whether an observation has a contextual explanation, is NP-complete. Furthermore, by examining the complexity of skeptical reasoning, deciding whether something follows skeptically from an observation is DP-complete. Unfortunately, explanations might not be monotonic in contextual abduction anymore, a property that holds in abduction for non-contextual programs [HPW11]. We can however show that deciding whether a contextual explanation is minimal lies in PSPACE.
The approach discussed here brings up a number of interesting questions: In the end of Section 2.3, we have shown that the weak completion of contextual programs might have more than only one minimal model. It seems that a possible characterization for the model computed by the ΦP operator, is the only minimal model for which all undefined atoms inP are mapped to unknown. Yet, another aspect which arises from Section 6, is whether skeptical reasoning with minimal explanations is PSPACE-hard. Further, we would like to investigate how a development of a neural network perspective for reasoning with contextual programs could be done.
The Graduate Academy at TU Dresden supported Tobias Philipp.