# focused_inference_and_system_p__4a4e8bf5.pdf Focused Inference and System P Marco Wilhelm and Gabriele Kern-Isberner Department of Computer Science, TU Dortmund, Dortmund, Germany marco.wilhelm@tu-dortmund.de, gabriele.kern-isberner@cs.tu-dortmund.de We bring in the concept of focused inference into the field of qualitative nonmonotonic reasoning by applying focused inference to System P. The idea behind drawing focused inferences is to concentrate on knowledge which seems to be relevant for answering a query while completely disregarding the remaining knowledge even at the risk of missing some meaningful information. Focused inference is motivated by mimicking snap decisions of human reasoners and aims on rapidly drawing still reasonable inferences from large sets of knowledge. In this paper, we define a series of query-dependent, syntactically-driven focused inference relations, elaborate on their formal properties, and show that the series converges against System P. We take advantage of this result in form of an anytime algorithm for drawing inferences which is accompanied by a thorough complexity analysis. Introduction Knowledge-based systems (Rajendra and Sajja 2009) represent a subfield of artificial intelligence the essence of which is to infer novel information of high quality from usually uncertain or vague knowledge bases. System P (Adams 1975; Kraus, Lehmann, and Magidor 1990) constitutes a wellestablished standard of formal quality criteria which is used to evaluate such nonmonotonic inferences of knowledgebased systems. A drawback of high quality inference formalisms is that they are typically based on rich epistemic structures which are computationally expensive. Hence, it is of great interest from both an epistemic and a computational point of view to focus on relevant knowledge when drawing inferences. The most radical way of focusing on knowledge is to disregard the remaining knowledge completely. Surprisingly, there is only few work which investigates this idea of focusing on knowledge resp. of limiting beliefs (cf., e.g., (Kern-Isberner and Brewka 2017; Schwering 2017; Lakemeyer and Levesque 2020; Rosales and Jaakkola 2005; Chechetka and Guestrin 2010)). Certainly, one reason is that the high quality of inferences cannot be guaranteed in general when ignoring information. Nevertheless, in order to counter ever-growing knowledge bases and time limitation in real-time applications of knowledge-based systems, it is necessary to develop pragmatic inference strategies. Copyright 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. In this paper, we define a notion of knowledge in focus which depends on a syntactical distance to the query, investigate formal properties of inferences that are drawn from knowledge in focus, and provide an anytime algorithm which calculates focused inferences and converges against System P. A complexity analysis shows that our algorithm is able to compute System P inferences faster than direct computations if the relevant knowledge is syntactically close to the query. Preliminaries We consider a propositional language L which is defined over a finite set of (propositional) variables Σ. Formulas in L are variables or negations ( A), conjunctions (A B), or disjunctions (A B) of formulas A, B L. We abbreviate A with A, and A B with AB. The semantics of formulas is given by interpretations I : L {0, 1} as usual in propositional logics. Classical entailment between formulas A, B is defined by A |= B iff I(A) = 1 implies I(B) = 1 for all interpretations I. If both A entails B and B entails A, then A and B are logically equivalent, written A B. Tautologies (formulas that are true in all interpretations) are denoted with and contradictions (formulas that are false in all interpretations) with . Conditionals (B|A) with A, B L are formal representations of default options of the form If A holds, then usually B holds, too. and lead to a three-valued evaluation: 1 iff I(AB) = 1 (verification) 0 iff I(AB) = 1 (falsification) u iff I(A) = 1 (non-applicability) . A semantics of conditionals is provided by ranking functions over possible worlds (Spohn 2012). Here, possible worlds are simply propositional interpretations represented by complete conjunctions of literals, i.e. positive or negated variables. The set of all possible worlds is denoted with Ω(Σ). A ranking function κ : Ω(Σ) N0 maps possible worlds to a degree of implausibility and is normalized by the requirement κ 1(0) = . Hence, κ 1(0) is the set of the most plausible worlds. Ranking functions are extended to formulas A by κ(A) = min{κ(ω) | ω Ω(Σ), ω |= A} and to formulas A by κ(A) = . A ranking function κ is a model of a conditional, written κ |= (B|A), iff κ(AB) < κ(AB) or A . The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21) Input: Knowledge base Output: Z-partition of if is consistent; empty list otherwise 1 output [ ] 2 while = 3 4 for r 5 if tolerates r then {r} 6 if = then output [ ] and break 7 output output.append( ) 8 \ 9 return output Algorithm 1: Consistency test for a knowledge base which returns the Z-partition of in case of consistency. A finite set of conditionals is called knowledge base. With Σ( ) we denote the signature that is induced by the knowledge base , i.e., Σ( ) is the set of variables which are mentioned in at least one conditional in . Analogously, we write Σ(X) for the signature of X, whether X is a formula, a conditional, or a query. A ranking function over Ω(Σ( )) is a model of a knowledge base iff it is a model of every conditional in . A knowledge base is consistent iff it has at least one model. Otherwise, it is inconsistent. A query ?A | B with A, B L asks whether B can be inferred from A. The answer depends on the underlying inference formalism which reflects the reasoner s inference behavior. Here, we rely on the nonmonotonic inference relation | L L which is defined wrt. a knowledge base : A | B iff κ |= (B|A) for all models κ of . For any fixed inference relation | x , we denote the respective instance of the query ?A | B by ?A | x B. The instance ?A | B is answered with true iff A | B holds and with false otherwise. The inference relation | is of high relevance in nonmonotonic reasoning as it is a semantical characterization of System P (Adams 1975; Kraus, Lehmann, and Magidor 1990) which provides an important standard for plausible nonmonotonic inference. Definition 1 (System P). Let | L L be an inference relation, and let A, B, C L. Then, System P is the collection of the following inference rules: A | A, (Reflexivity) AB | C, A | B imply A | C, (Cut) A | B, A | C imply AB | C, (Cautious Monotony) A | B, B |= C imply A | C, (Right Weakening) A | C, B | C imply A B | C, (Or) A B, B | C imply A | C. (Left Logical Equivalence) The inference relation | satisfies System P iff it satisfies all inference rules in System P. It is well known that A | B holds iff {(B|A)} is inconsistent (Goldszmidt and Pearl 1991). (In-)consistency of a knowledge base can be decided with Algorithm 1 which makes use of the notions tolerance and Z-partition.1 A knowledge base tolerates a conditional r = (B|A) iff there is a possible world in which r is verified and no conditional from is falsified, i.e., iff AB V (B |A ) (A B ) is satisfiable. An ordered partition ( 0, 1, . . . , m) of is a tolerance partition of iff, for i = 0, . . . , m, every conditional in i is tolerated by Sm j=i j. We call m the rank of the tolerance partition. The Z-partition of is the unique tolerance partition of where the rank is minimal. Proposition 1. (Goldszmidt and Pearl 1991) A knowledge base is consistent iff it has a tolerance partition. Consequently, A | B holds iff Algorithm 1 applied to {(B|A)} returns no Z-partition, i.e., iff it returns an empty list. Algorithm 1 takes O(| |2)-many SAT tests. Focused Inference When drawing inferences in practice, human reasoners typically do not take their whole knowledge into account but focus on that part of their knowledge which they rate as relevant for the query. Ignoring knowledge which is suspected of being irrelevant reduces complexity and allows humans to make snap decisions in a short period of time. On the downside, if one narrows the focus too much, then one probably misses information which turns out to be relevant in the end. The vast majority of formal approaches to nonmonotonic reasoning does not provide the feature of focusing on a certain part of knowledge. While most approaches certainly aim on working out the relevant knowledge, they usually do not disregard irrelevant knowledge completely but give lower weight to it. This way of handling relevance is meaningful when drawing very well-considered inferences but results in rather costly calculations. One possibility of disregarding irrelevant knowledge completely is provided by the concept of syntax splitting (Parikh 1999). The idea behind syntax splitting is to partition the knowledge base into syntactically independent subsets and to exploit only those subsets that are syntactically linked to the query when drawing inferences. Formally, ( 1, . . . , m) is a syntax splitting of a knowledge base iff { 1, . . . , m} is a partition of and {Σ( 1), . . . , Σ( m)} is a partition of Σ( ). Example 1. Consider = {r1, . . . , r6} from Table 1. { penguin, amphibian} is a syntax splitting of because {Σ( penguin), Σ( amphibian)} = {{b, f, p, w}, {a, s}} is a partition of Σ( ). Due to {p, f} Σ( amphibian) = , the knowledge in amphibian should be irrelevant when asking for ?f | p, i.e. if flying individuals are usually not penguins. We later show that this is indeed the case in System P and the query ?f | p can be answered solely based on penguin. Syntax splitting is a powerful tool when organizing knowledge bases which address several rather independent topics. However, in practice, knowledge bases are usually fully connected and syntax splitting becomes futile as the finest syntax splitting of a fully connected knowledge base is { }. 1Z-partitions are named after System Z (Pearl 1990) as they can be used to establish System Z. Conditional Meaning and appearance r1 = (b| ) An individual is usually a bird. r2 = (f|b) Birds are usually able to fly. r3 = (w|b) Birds usually have wings. bird = {r1, r2, r3} r4 = (b|p) Penguins are usually birds. r5 = (f|p) Penguins are usually not able to fly. penguin = {r1, . . . , r5} r6 = (a|s) Salamanders are usually amphibians. amphibian = {r6} r7 = (e|b) Birds usually lay eggs. r8 = (e|a) Amphibians usually lay eggs. oviparous = {r1, . . . , r8} Table 1: Conditionals that are used in the examples. Example 2. We recall the knowledge bases penguin and amphibian from Example 1. Adding the knowledge that both birds and amphibians usually lay eggs results in the knowledge bases bird {r7} and amphibian {r8} (cf. Table 1) which are no longer syntactically separated as they share the variable e, and performing syntax splitting on the whole knowledge base = bird {r7} amphibian {r8} does not create added value. Nevertheless, the knowledge about amphibians should still not be relevant for the query ?f | p. Example 2 suggests that syntax splitting is too coarse in some cases. For this reason, we work out more precise foci on knowledge. In compliance with syntax splitting, we define foci on a syntactical level, i.e., a focus is a set of variables. This makes foci easy to compute. Definition 2 (Direct Focus; Knowledge in Focus). Let be a knowledge base, and let A L. The direct focus on A is and the knowledge in the direct focus on A is 0(A) = {r | Σ(r) F0(A) = }. According to Definition 2, the focus F0(A) is the signature of the formulas in A and 0(A) consists of those conditionals from which share at least one variable with A. When drawing inferences we are interested in the knowledge that is linked to a query ?A | B and, hence, we focus on A = {A, B}. The focus F0(A, B)2 solely consists of those variables that are mentioned in the query ?A | B and therefore is the smallest reasonable focus for answering this query. Example 3. Consider oviparous (cf. Table 1). The direct focus on the query ?f | p is F0(f, p) = {f, p} and the knowledge in this focus is 0(f, p) = {(f|b), (b|p), (f|p)}. The idea of knowledge in focus can be generalized by iteration: In the focus F1 not only conditionals are taken into 2Note that we omit set braces if the set occurs as the only argument of a mapping in order to shorten expressions. account which are directly linked to the query but also conditionals that share variables with other conditionals which are directly linked to the query, and so on. Definition 3 (Iterated Focus; Iterated Knowledge in Focus). Let be a knowledge base, and let A L. For i N, the i-th focus on A is Fi( , A) = F0(A) [ r i 1(A) Σ(r), which depends on the (i 1)-th knowledge in focus on A, namely i 1(A). The i-th knowledge in focus on A is i(A) = {r | Σ(r) Fi( , A) = }. We omit the argument in Fi( , A) and write Fi(A) instead if the respective knowledge base is clear from the context. Example 4. We abbreviate = oviparous (cf. Table 1). The first iterated foci on the query ?f | p and the knowledge in these foci are F1(f, p) = {b, f, p}, 1(f, p) = {r1, . . . , r5, r7}, F2(f, p) = {b, e, f, p, w}, 2(f, p) = 1(f, p) {r8}, F3(f, p) = Σ \ {s}, 3(f, p) = oviparous, F4(f, p) = Σ. One has Fi(A) Fi+1(A) and i(A) i+1(A) for i N0 and A L. Because every focus and knowledge in focus is bounded above by a finite set, namely by Σ resp. , the series (Fi(A))i N0 and ( i(A))i N0 become stationary after at most min{|Σ|, | |}-many iterations. The limits are i N0 Fi(A), Example 5. Consider oviparous and the query ?f | p (cf. Example 4). One has F (f, p) = F4(f, p) = Σ and (f, p) = 3(f, p) = oviparous. Note that the focus in the limit F and the knowledge in the focus in the limit are not necessarily Σ resp. but are the focus and the knowledge in focus which are obtained by syntax splitting. Definition 4 (Focused Inference). Let be a knowledge base. For i N 0 , we define the focused inference relation | i = {(A, B) L L | A | i(A,B) B}. If A | i B holds, we say that B follows from A in the i-th focus. Every query instance ?A | i B can be answered based on an inference relation which satisfies System P, namely | i(A,B) . However, this does not mean that | i satisfies System P because the focus of i(A, B) is query-dependent and the inference relation which is selected to answer the query can differ from query to query. Example 6. From = oviparous (cf. Table 1) the inference f | 0 p can be drawn because = 0(f, p) {(p|f)} = {(f|b), (b|p), (f|p), (p|f)} is inconsistent (no conditional in is tolerated by ). Some further inferences that can be drawn from by direct applications of inference rules from System P are a b | 0 e, bf | 0 w, and p | 0 b f. An inference that cannot be drawn in the direct focus is w | 0 f because 0(f, w) {(f|w)} = {(f|b), (w|b), (f|p), (f|w)} is consistent (consider any ranking function with κ 1(0) = {bfpw} and κ 1(1) = {bfpw}). However, w | 1 f holds because 1(f, w) {(f|w)} = penguin {r7} {(f|w)} is inconsistent: In the most plausible worlds b holds (due to r1) and then f (due to r2) and w (due to r3) hold as well. From an intuitive point of view, the inference behavior of | i should become better with increasing i, i.e., the larger the focus is and, hence, the more knowledge is taken into account. In the next section, we investigate this conjecture based on formal criteria. Formal Properties of Focused Inference We investigate the quality of the focused inference relations | i for i N 0 with regard to System P. We begin with the inference relation | . Before we show that | equals | and, hence, satisfies System P, we prove some technical lemmas. Lemma 1. Let 1 and 2 be knowledge bases, and let A, B L. Then, A | 1 B and 1 2 imply A | 2 B. This property is known as the semi-monotony of | . Proof. From A | 1 B it follows that 1 {(B|A)} is inconsistent. As every superset of an inconsistent knowledge base is inconsistent and 1 {(B|A)} 2 {(B|A)} holds, 2 {(B|A)} is inconsistent, too. Consequently, it follows that A | 2 B is true as well. We now show that the models of syntactically independent knowledge bases 1 and 2 define a model of 1 2. Lemma 2. Let be a consistent knowledge base which syntactically splits into { 1, 2}, and let κi : Ω(Σ( i)) N0 be a model of i for i = 1, 2. Then, the sum of both, i.e. (κ1 + κ2)(ω1ω2) = κ1(ω1) + κ2(ω2), is a model of . Proof. Let A be a formula which is defined over Σ1. Then, (κ1 + κ2)(A) = min ω1ω2|=A ω1 Ω(Σ( 1)), ω2 Ω(Σ( 2)) (κ1 + κ2)(ω1ω2) = min ω1|=A ω1 Ω(Σ( 1)), ω2 Ω(Σ( 2)) κ1(ω1) + κ2(ω2) = min ω1|=A, ω1 Ω(Σ( 1)) κ1(ω1) = κ1(A). The third equality holds because κ2 is normalized and the minimum is built over all possible worlds in Ω(Σ( 2)). As a consequence, one has (κ1 + κ2)(AB) = κ1(AB) < κ1(AB) = (κ1+κ2)(AB) for all conditionals (B|A) 1. The proof for conditionals in 2 is analogous. We eventually prove | = | . Proposition 2. Let be a consistent knowledge base. Then, | = | . In particular, | satisfies System P. Proof. From A | B it follows that A | (A,B) B holds. With (A, B) and Lemma 1, A | B follows. Now, let A | B. We define = \ (A, B) such that syntactically splits into { , (A, B)} (otherwise (A, B) would not be the limit of ( i(A, B))i N0). Let κ be a model of (A, B) and let κ be a model of . Lemma 2 states that κ + κ is a model of . Hence, A | B implies (κ + κ )(AB) < (κ + κ )(AB). Because of Σ(A | B) Σ( (A, B)), one has κ(AB) = (κ + κ )(AB) < (κ + κ )(AB) = κ(AB) (cf. the proof of Lemma 2), i.e., κ |= (B|A). As this result holds for arbitrary models κ of (A, B), both A | (A,B) B and A | B follow. Now, we investigate the inference relations | i with i < . Example 6 gives reason to expect that these inference relations do not satisfy System P. Actually, for all knowledge bases , there is a minimal i N0 such that | j satisfies System P for all j i, because there is k N0 with | k = | . However, this index i depends on the knowledge base . Nevertheless, some inference rules of System P hold in all foci. Proposition 3. Let be a consistent knowledge base and let i N0. The inference relation | i satisfies Reflexivity, Cautious Monotony, and Or. Proof. Reflexivity: If A , then all ranking functions κ satisfy κ |= (A|A) by definition and A | i A holds. If A , then κ(AA) = κ(A) < = κ( ) = κ(AA) for all ranking functions κ and, again, A | i A holds. Cautious Monotony (CM): A | i B (resp. A | i C) is equivalent to A | i(A,B) B (resp. A | i(A,C) C). With Lemma 1, A | i(A,B,C) B (resp. A | i(A,B,C) C) follows. Because | i(A,B,C) satisfies System P, in particular CM, AB | i(A,B,C) C and, hence, AB | i C hold. Or: A | i C (resp. B | i C) is equivalent to A | i(A,C) C (resp. B | i(B,C) C). With Lemma 1, A | i(A,B,C) C (resp. B | i(A,B,C) C) follows. Because | i(A,B,C) satisfies System P, in particular Or, A B | i(A,B,C) C and, hence, A B | i C hold. Proposition 4. There is no i N0 such that for all consistent knowledge bases , the inference relation | i satisfies Cut, Right Weakening, or Left Logical Equivalence. Proof. We give counterexamples for the case i = 0 first and generalize them to i > 0 afterwards. Cut: Consider = {(c|ab), (a| ), (d|a), (b|d)}. Then, ab | 0 c and a | 0 b hold, but a | 0 c does not hold. The inference a | 0 b holds because in all models of the most plausible worlds satisfy a (due to (a| ) ) and consequently d (due to (d|a) ) as well as b (due to (b|d) ). The inference a | 0 c does not hold because (b|d) / 0(a, c) implies that b cannot be inferred from a. For this reason, 0(a, c) {(c|a)} is consistent (consider any ranking function κ with κ 1(0) = {abcd} and κ 1(1) = {abcd}). This counterexample generalizes to arbitrary i N by separating the conclusion b from the premise a through a transitive chain of conditionals: For i = {(c|ab), (a| ), (d1|a), (d2|d1), . . . , (di+1|di), (b|di+1)}, (b|di+1) / i i(a, c) rules out the inference of b from a and, hence, of c from a. Right Weakening: Let = {(a| ), (b|a), (d|b), (bc|d)}. Then, a | 0 bc and bc |= c hold, but a | 0 c does not hold. In the most plausible worlds, a holds (due to (a| ) ) as well as b (due to (b|a) ) and d (due to (d|b) ). Consequently, c follows from bc |= c and (bc|d) . The inference a | 0 c does not hold because (d|b) / 0(a, c). Hence, c cannot be inferred from a. This counterexample generalizes to arbitrary i N: i = {(a| ), (b|a), (d1|b), (d2|d1), . . . , (d2i+1|d2i), (bc|d2i+1} proves that | i does not satisfy Right Weakening because (di+1|di) / i i(a, c). Left Logical Equivalence: Let = {(c|d), (d|a a)}. Then, a a | 0 c and a a hold, but | 0 c does not hold which is because of (d|a a) / 0(c) = {(c|d)}. This counterexample generalizes to arbitrary i N: i = {(c|d1), (d2|d1), . . . , (di+1|di), (di+1|a a)} proves that | i does not satisfy Left Logical Equivalence because (di+1|a a) / i i(c). The inference rules Cut, Right Weakening, and Left Logical Equivalence aim on inferring a proposition C from a proposition A by making use of a justification B. If this justification is out of the focus Fi(A, C), then the inference A | i C can (possibly) not be drawn. This is in compliance with human reasoning: The less present the justification for an inference is, the more likely it is to dismiss the inference. If the justification B is within the focus Fi(A, C), however, the inference A | i C should be drawn. In compliance with this consideration, the following weaker versions of Cut, Right Weakening, and Left Logical Equivalence apply. Proposition 5. Let be a consistent knowledge base, let i N0, and let A, B, C L. If Σ(B) Fi(A, C), then AB | i C, A | i B imply A | i C, (Focused Cut) A | i B, B |= C imply A | i C, (Focused RW) A B, B | i C imply A | i C. (Focused LLE) Proof. Focused Cut: From AB | i C and A | i B it follows that AB | i(A,B,C) C and A | i(A,B,C) B hold. Since | i(A,B,C) satisfies System P, A | i(A,B,C) C follows. Because of Σ(B) Fi(A, C) one has i(A, C) = i(A, B, C). Therefore, A | fi( ) C holds. The proofs of Focused RW and Focused LLE are analogous to the proof of Focused Cut: From A | i B and B |= C (resp. A B and B | i C), A | i(A,B,C) B (resp. B | i(A,B,C) C) follows. In both cases A | i(A,B,C) C follows with the same argument as in the proof of Focused Cut. Consequently, A | fi( ) C holds. Concerning Right Weakening we would like to point out that this inference rule is not entirely unquestioned (cf., e.g., (Casini, Meyer, and Varzinczak 2019)). Like Cut, it constitutes a weakened form of transitivity which is a typical property of monotonic reasoning. Focused RW and Focused LLE restrict transitivity more than Right Weakening and Left Logical Equivalence as they crop transitive chainings when they get out of focus (cf. the proof of Proposition 4). Left Logical Equivalence can also be guaranteed by restricting the language that is used to describe knowledge. The reason why Left Logical Equivalence is not satisfied by focused inference in general is that foci are defined on a syntactical level and it is possible that a formula A is within a focus F while an equivalent formula B is not. This, however, only happens when at least one of the formulas uses redundant variables. For instance, consider A = a and B = a(b b). Then, A B holds and B is considered in all foci F with a F or b F but A is considered only in foci F with a F. We avoid this problem by introducing a language L which is free of such syntactical sugar . Definition 5 (Propositional Language L ). The propositional language L L is defined by A L iff A L and B L : B A Σ(A) Σ(B). Formulas in L mention only those variables that are relevant for the evaluation of the formula. For instance, with respect to the abovementioned example, A = a is in L but B = a(b b) is not. Proposition 6. Let be a consistent knowledge base, and let i N0. If B L , then A B, B | i C imply A | i C. (Reduced LLE) Proof. B L and A B imply Σ(B) Σ(A) and, hence, Σ(B) Σ(C) Σ(A) Σ(C) holds. Consequently, i(B, C) i(A, C) holds, too. Because of A B and B | i C one has B | i(B,C) C and, as | i(B,C) satisfies System P and in particular Left Logical Equivalence, A | i(B,C) C. Finally, since | is semi-monotonous, A | i(A,C) C and A | i C follow. So far we have learned that for all knowledge bases there is a minimal index i N0 with i < min{|Σ|, | |} such that | i satisfies System P. Even if one does not want to miss any relevant knowledge for answering the query ?A | B, it is sufficient to focus on i(A, B) instead of considering because | = | i holds for this index i. The next proposition states that even if the focus Fj is too small to draw inferences compliant with System P, i.e., Fj Fi, the focused inference relation | j does not provide false positives . Proposition 7. Let be a knowledge base and let i, j N0. Then, j i implies | j | i . Input: Z-partition ( 1, . . . , m) of a consistent knowledge base ; knowledge base Output: Z-partition of = if is consistent; empty list otherwise 1 output [ ] 2 for i = 0, . . . , m 3 while i = 4 ; ; boolean false 5 for r 6 if Sm j=i j tolerates r 7 {r}; boolean true 8 for r i 9 if Sm j=i j tolerates r 10 {r}; boolean true 11 if boolean = false 12 output [ ] 13 break 14 output output.append( ) 15 i i \ ; \ 16 if = 17 output output.extend([ i+1, . . . , m]) 18 break 19 if = 20 output.extend(Algorithm 1( )) 21 return output Algorithm 2: Consistency test for a knowledge base which exploits the Z-partition of a consistent subset and returns the Z-partition of . Proof. This proposition directly follows from j(A, B) i(A, B) for j i and the semi-monotony of | . As a consequence of Proposition 7, the sequence ( | i )i N0 forms an ascending chain ( | 0 | 1 . . .) and converges to | . In the next section, we make use of this result and present an algorithm for drawing inferences in System P based on focused inference. For this, we test whether a query holds wrt. | 0 . If the answer is false, we iteratively enlarge the focus until we reach | . If the inference can still not be drawn wrt. | , then the query is false wrt. System P. In all other cases the query is true. An Algorithmic View on Focused Inference The fact that the focused inference relations | i for i N0 form an ascending chain which converges against the System-P-conform inference relation | makes it possible to iteratively approximate System P with increasing accuracy: In order to answer a query wrt. | one tests if this query holds wrt. | 0 . If this is the case, the query also holds wrt. | due to the semi-monotony of | . Otherwise, one tests the query wrt. | 1 and so on. For this procedure to be efficient, it is necessary to reuse the calculations for answering the query instance ?A | i B when ?A | i+1 B has to be tested. In other words, one has to take advantage of the consistency of i(A, B) {(B|A)} when deciding consistency of i+1(A, B) {(B|A)}. More general, an efficient algorithm is needed which decides consistency of a knowledge base provided that a subset of is already known to be consistent. We develop such an algorithm in this section step by step. For that purpose the Z-partition of is a useful auxiliary structure: The idea is to sort the conditionals from \ into the Z-partition ( 1, . . . , m) of . During this process it can happen that (a) conditionals from \ can simply be incorporated into a partition set i, (b) i has to be fanned out into several smaller subsets before applying (a), or (c) conditionals from \ constitute a completely novel partition set. What can not happen, however, is that two conditionals r1 and r2 from switch their order in the Z-partition, i.e., r1 occurs in a set with a lower index than r2 within the partition of but in a set with a higher index within the partition of (cf. the notion of tolerance). The whole procedure is implemented in Algorithm 2. Proposition 8. Algorithm 2 terminates and is correct. Its worst-case time-complexity is in m + | | | | + | |2 SAT(|Σ|) where SAT(|Σ|) is the worst-case time-complexity of testing satisfiability of a formula with |Σ|-many variables. Proof (Sketch). Termination: The for-loops in Algorithm 2 are obviously finite. In every pass of the while-loop, one out of these three events happens: (a) An element is removed from , (b) an element is removed from i, or (c) the loop aborts because the variable boolean is false. Since and i are finite sets, the termination condition i = eventuates after finitely many passes or the loop aborts due to case (c). Hence, the while-loop is finite, too. Correctness: Algorithm 2 sorts the conditionals from in the Z-partition ( 1, . . . , m) starting from 1 up to m while fanning out the partition sets i if necessary, such that each conditional in a new partition set i is tolerated by i, the remaining conditionals from i as well as the conditionals from j, j > i (the tolerance tests are performed in the lines 6 and 9). When all conditionals from are sorted in before the for-loop in line 2 ends, the partition sets from ( 1, . . . , m) which remained untouched are appended (line 17). When the for-loop ends before all conditionals from are sorted in instead, the Z-partition of the remaining conditionals from is appended (line 20). The outcome is a tolerance partition of . It remains to show that this tolerance partition has minimal rank. This holds because every conditional from is sorted in as early as possible and no conditional from j can be tolerated before a conditional from i when j > i as ( 1, . . . , m) forms a tolerance partition and, consequently, all conditionals from j have to appear in a higher partition of the Z-partition of than conditionals from i (if a conditional is not tolerated by a knowledge base , then it is also not tolerated by any superset of ). Input: Knowledge base ; query ?A | B Output: true if A | B holds; false otherwise 1 output false 2 i 0 3 T Algorithm 1( i(A, B) {(B|A)}) 4 if T = [ ] then output true 5 while i+1(A, B) = i(A, B) output = false 6 T Algorithm 2(T, i+1(A, B) \ i(A, B)) 7 if T = [ ] then output true 8 i i + 1 9 return output Algorithm 3: Iterative query answering in System P. Complexity: In the worst case, the algorithm takes O(Pm i=0(P| i| k=1(k + | |)) + | |2) = O(Pm i=0(| i|2 + | i| | |) + | |2) = O(Pm i=0( | |2 m | |) + | |2) m + | | | | + | |2) many SAT tests. For obtaining the last equality, the method of Lagrangian multipliers (Boyd and Vandenberghe 2014) with the side condition Pm i=0 | i| = | | is applied. The complexity of Algorithm 2 is the better the higher the rank m of the Z-partition of is. In the worst case, the Z-partition of is ( ) and does not provide any helpful information. In this case, the complexity of Algorithm 2 is the same as the complexity of a direct computation of the Z-partition of = with Algorithm 1. Eventually, Algorithm 3 recursively applies Algorithm 2 on i and the Z-partition of i 1 for increasing index i in order to answer the query instance ?A | B. Proposition 9. Algorithm 3 terminates and is correct. Its worst-case time-complexity is in | k(A, B)|2 SAT(|Σ( k(A, B))|) , where k is such that Fk(A, B) is the smallest focus in which ?A | B can be decided and mk is the rank of the Z-partition of k(A, B). Proof (Sketch). Termination: Algorithm 3 terminates because its only while-loop is finite; ( i)i N0 converges after at most min{|Σ|, | |}-many steps. Correctness: Algorithm 3 recursively tests whether A | i B holds for increasing i N0. If A | i B holds, then A | B holds, too, and the algorithm returns true. If A | i B does not hold, the index i is increased and the algorithm repeats. When ( | i )i N0 becomes stationary at index j and A | j B does not hold, then A | B does not hold either and the algorithm correctly returns false. Complexity: For i N0, we denote | i(A, B)| with di and the rank of the Z-partition of i(A, B) with mi. Then, Algorithm 3 takes O(d2 0 + Pk i=1( d2 i 1 mi 1 +(di 1 + di di 1) (di di 1))) = O(d2 0 + Pk i=1( d2 i 1 mi 1 + di (di di 1))) O(d2 0 + k mk 1 d2 k 1 + dk Pk i=1(di di 1)) = O(d2 0 + k mk 1 d2 k 1 + dk (dk d0)) = O((1 + k mk ) d2 k) many SAT tests. In the worst case, ?A | B can be answered with Algorithm 3 not before the first focus Fk with k(A, B) = is reached. Additionally, k = | | and mk = 1 could hold. In this case, the complexity of Algorithm 3 is in Θ(| (A, B)|3 SAT(|Σ|)) and worse than the complexity of a direct computation with Algorithm 1. In practical applications, however, k | | and mk > 1 can be expected. If A | B does not hold, then Algorithm 3 proceeds until the first focus Fk with k(A, B) = (A, B) is reached because focused inference is semi-decidable: If A | i B holds, then A | B holds as well, but if i < k and A | i B does not hold, nothing can be said about A | B. This weakness is attenuated by testing ?A | i B and ?A | i B in parallel and by aborting the procedure as soon as one of the query instances turns out to be true. In the best case, the inference A | B holds and can be drawn in the direct focus. Then, the complexity of Algorithm 3 is in O(| 0(A, B)|2 SAT(|Σ( 0(A, B)|). This result is promising not only because | 0(A, B)| | | holds in many cases and improves complexity directly but also because |Σ( 0(A, B)| |Σ| speeds up the SAT tests in Algorithm 3 in comparison to those in Algorithm 1. Conclusion and Future Work We analyzed the effect of focusing on knowledge when drawing inferences in System P. For this, we hierarchically organized the knowledge according to its syntactical distance to the query and defined focused inference relations which solely use the knowledge that is within reach of the query (within focus ) to draw the inference. All focused inferences are in compliance with System P but not all System P inferences are among the focused ones if the focus is not broad enough. Our focused inference approach benefits from the semi-monotony of System P but is not limited to System P. In future work, we want to extend our approach to more expressive background logics, formalize a semantical variant of focused inference, and we want to apply focused inference to other inference formalisms which satisfy semimonotony (e.g., Reiter s default logic for normal defaults (Reiter 1980)) and, more challenging, to formalisms which are not semi-monotonous (e.g., System Z (Pearl 1990) and c-representations (Kern-Isberner 2004)). We also see connections to other research topics such as forgetting (focused inference as a tunnel view) and paraconsistent logics (focus on a consistent part of the knowledge). References Adams, E. W. 1975. The Logic of Conditionals. Springer. Boyd, S. P.; and Vandenberghe, L. 2014. Convex Optimization. Cambridge University Press. Casini, G.; Meyer, T.; and Varzinczak, I. 2019. Simple Conditionals with Constrained Right Weakening. In Kraus, S., ed., Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, 1632 1638. ijcai.org. Chechetka, A.; and Guestrin, C. 2010. Focused Belief Propagation for Query-Specific Inference. In Teh, Y. W.; and Titterington, D. M., eds., Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13-15, 2010, volume 9 of JMLR Proceedings, 89 96. JMLR.org. Goldszmidt, M.; and Pearl, J. 1991. On the Consistency of Defeasible Databases. Artif. Intell. 52(2): 121 149. Kern-Isberner, G. 2004. A Thorough Axiomatization of a Principle of Conditional Preservation in Belief Revision. Ann. Math. Artif. Intell. 40(1-2): 127 164. Kern-Isberner, G.; and Brewka, G. 2017. Strong Syntax Splitting for Iterated Belief Revision. In Sierra, C., ed., Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, 1131 1137. ijcai.org. Kraus, S.; Lehmann, D.; and Magidor, M. 1990. Nonmonotonic Reasoning, Preferential Models and Cumulative Logics. Artif. Intell. 44(1-2): 167 207. Lakemeyer, G.; and Levesque, H. J. 2020. A First-Order Logic of Limited Belief Based on Possible Worlds. In Calvanese, D.; Erdem, E.; and Thielscher, M., eds., Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, Rhodes, Greece, September 12-18, 2020, 624 635. Parikh, R. 1999. Beliefs, Belief Revision, and Splitting Languages, 266 278. Center for the Study of Language and Information. Pearl, J. 1990. System Z: A Natural Ordering of Defaults with Tractable Applications to Nonmonotonic Reasoning. In Proceedings of the 3rd Conference on Theoretical Aspects of Reasoning about Knowledge, TARK 90, 121 135. Morgan Kaufmann Publishers Inc. Rajendra, A.; and Sajja, P. 2009. Knowledge-Based Systems. Jones and Bartlett Learning. Reiter, R. 1980. A Logic for Default Reasoning. Artif. Intell. 13(1): 81 132. Rosales, R.; and Jaakkola, T. S. 2005. Focused Inference. In Cowell, R. G.; and Ghahramani, Z., eds., Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, AISTATS 2005, Bridgetown, Barbados, January 6-8, 2005. Society for Artificial Intelligence and Statistics. Schwering, C. 2017. A Reasoning System for a First-Order Logic of Limited Belief. In Sierra, C., ed., Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 1925, 2017, 1247 1253. ijcai.org. Spohn, W. 2012. The Laws of Belief: Ranking Theory and Its Philosophical Applications. Oxford University Press.