Splitting Techniques for Conditional Belief Bases for Nonmonotonic Reasoning

Abstract

In nonmonotonic reasoning with belief bases, we often ask the question wether a formula entails a formula in the context of a belief base Δ. We want to investigate how to answer such a query in the most eficient way, that is which elements in the belief base are actually relevant to answering the query and which are not. The research question we want to investigate is therefore "Given a belief base Δ and two formulas and , find a suficiently small subbase Δ′ ⊆ Δ , such that entails in the context of Δ′ if and only if entails in the context of Δ".

1. Motivation

2. Formal Basics

We consider a finitely generated propositional language ℒ over a signature Σ with atoms , , , . . . and with formulas , , , . . . As models of formulas we will use the set Ω of possible worlds over ℒ. We will use both for the model and the corresponding conjunction of all positive or negated atoms. For subsets Σ of Σ, let ℒ(Σ ) denote the propositional language defined by Σ , with associated set of interpretations Ω(Σ ). With we denote the reduct of to Σ [ 7 ]. Conditionals (|) are meant to express plausible, yet defeasible rules “If then plausibly ”. (|) is verified by if |= and falsified by if |= . A conditional (|) is called self-fulfilling, or trivial, if |= , i.e., there is no world that falsifies it. A belief base ∆ is a finite set of conditionals, and we focus on (strongly) consistent belief bases in the sense of [ 8, 1 ]. A semantic framework for interpreting conditionals are ordinal conditional functions (OCFs) : Ω → N ∪ {∞} with −1 (0) ̸= ∅, also called ranking functions [ 9 ]. Intuitively, less plausible worlds are assigned higher numbers. Formulas are assigned the rank of their most plausible models, i.e. () := min{() | |= } . A conditional (|) is accepted by , written as |= (|) , if () < ( ). A belief base ∆ is accepted by , written |= ∆ , if accepts all its conditionals. The nonmonotonic inference relation |∼ induced by is |∼ if ≡ ⊥ or () < ( ).

(1) To formalize inductive inference from belief bases the notion of an inductive inference operator was introduced [ 10 ] which is a mapping C that assigns to each belief base ∆ ⊆ (ℒ | ℒ) an inference relation |∼ Δ on ℒ, i.e., C : ∆ ↦→ |∼ Δ, such that Direct Inference (DI): If (|) ∈ ∆ then |∼ Δ , and Trivial Vacuity (TV): |∼ ∅ implies |= are satisfied.

3. State of the Art and Related Work

Localized reasoning has been investigated in a variety of works. The mechanism of focused inference was introduced in [ 11 ]. The idea behind this approach is to gradually increase the amount of conditionals considered when answering a query by first taking only those closest to the query into account. Then the set of conditionals is gradually increased by a measure of syntactic distance until the query can be answered. Obtaining correct answers, however, crucially relies on the semi-monotonicity of the relevant inference operator, which, from those mentioned in this paper, only System P satisfies. This approach was generalized using an activation function [ 12 ] with the intent to model more closely human reasoning and their understanding of relevant knowledge.

A recent work on localized reasoning is due to [ 13 ] where a context-based refinement of the belief base was introduced utilizing a refiner function and a context. Utilizing the query as a context this approach is related to the research question posed here.

A substantial amount of work has been done on syntax splitting [ 14 ] which means that the signature splits into disjoint subsignatures. This approach has since been picked up in a variety of works (e.g. [ 15, 16, 17 ]). A related idea of minimum irrelevance was investigated in [ 18 ]. For inductive inference from belief bases, syntax splitting has been characterized as "syntax splitting = relevance + independence" [ 10 ]; this approach considers splittings over a belief bases ∆ into disjoint subbases ∆ 1 and ∆ 2 induced by a syntax splitting over the underlying signature. As a disjoint split of the signature is rare in real applications and thus poses a severe restriction, this notion was generalized to conditional syntax splitting [ 17 ], allowing the signatures to overlap on some elements.

Definition 1 ([ 17 ]). A belief base ∆ splits into subbases ∆ 1,∆ 2 conditional on Σ 3, if there are Σ 1, Σ 2 ⊆ Σ such that ∆ = ∆ ∩ (ℒ(Σ ∪ Σ 3) | ℒ(Σ ∪ Σ 3)) for = 1, 2, and {Σ 1, Σ 2, Σ 3} is a partition of Σ . This is denoted as ∆ = ∆ ∆ = ∆ 1 ⋃︁ ∆ 2 | Σ 3.

Σ1,Σ2

s 1 ⋃︁ ∆ 2 | Σ 3 Σ1,Σ2

We denote the intersection of the subbases ∆ 1 and ∆ 2 by ∆ 3 = ∆ 1 ∩ ∆ 2, containing all conditionals over the language of Σ 3. As it turns out however, a purely syntactic separation is not suficient to ensure independence between the subbases in general. Thus safe conditional syntax splittings were introduced.

Definition 2 ([ 17 ]). A belief base ∆ = ∆ conditional on a subsignature Σ 3, writing 1 ⋃︀Σ1,Σ2 ∆ 2 | Σ 3 can be safely split into subbases ∆ 1, ∆ 2 (2) (3) (4) if the following safety property holds for , ′ ∈ {1, 2}, ̸= ′: for every 3 ∈ Ω Σ∪Σ3 , there is ′ ∈ Ω Σ′ s.t. 3′ ̸|= ⋁︁ ( |)∈Δ′ ∧ ¬.

Safety, in essence, demands that no valuation of the signature elements of Σ 3 may force the falsification of a conditional in ∆ . The notion of conditional syntax splitting was then formalized analogously to postulates for syntax splitting [ 10 ] as a property for inductive inference operators via the following postulates.

Definition 3 ([ 17 ]). For any ∆ = ∆ 1 ⋃︀sΣ1,Σ2 ∆ 2 | Σ 3, for ∈ {1, 2}, and any , ∈ ℒ(Σ ), ∈ ℒ(Σ ) and a complete conjunction ∈ ℒ(Σ 3), such that ̸|∼ Δ ⊥, an inductive inference operator C satisfies (CRel) if |∼ Δ (CInd) if |∼ Δ (CSynSplit) if it satisfies (CRel) and (CInd).

4. Current Results

Lemma 6 ([ 19 ]). Let ∆ = ∆ conditionals.

Two major works have been published as part of this research [ 19, 20 ]. The paper [ 19 ] showed that two diferent kinds of reasoning with c-representations satisfy conditional syntax splitting.

A c-representation is a special kind of ranking function, that assigns penalty points to worlds based c-sk obtained by on the conditionals they falsify [ 21, 22 ]. c-Inference [ 3, 4 ] is the inductive inference |∼ Δ c-sk if |∼ for all c-representations of ∆. taking all c-representations into account, i.e. |∼ Δ Proposition 4 ([ 19 ]). c-Inference satisfies (CRel) and (CInd) and thus (CSynSplit).

A selection strategy assigns to each belief base a unique c-representation [ 23 ], thus yielding an inductive inference operator via Cc-rep : ∆ ↦→ (Δ) where |∼ (Δ) is obtained via Equation (1). In general Cc-rep does not satisfy (CSynSplit). But in [ 19 ] the postulate (IP-CSP) for selection strategies was introduced, demanding that, for any ∆ = ∆ 1 ⋃︀sΣ1,Σ2 ∆ 2 | Σ 3, the selection strategy assigns the same impact to the conditionals of ∆ in ∆ as in ∆ .

Δ .

With this the following proposition was shown. (IP-CSP) [ 19 ] A selection strategy is impact preserving w.r.t. safe conditional belief base splitting if, for every safe conditional belief base splitting ∆ = ∆ 1 ⋃︀sΣ1,Σ2 ∆ 2 | Σ 3, for ∈ {1, 2}, we have (∆ ) = (∆)| Proposition 5 ([ 19 ]). Let be a selection strategy that satisfies (IP-CSP). Then Cc-rep satisfies (CRel) and (CInd) and thus (CSynSplit).

Additionally in [19] the following result was also shown.

1 ⋃︀sΣ1,Σ2 ∆ 2 | Σ 3, then ∆ 3 = ∆ 1 ∩ ∆ 2 contains only self-fulfilling

Thus the safety condition as defined in [ 17 ] is quite restrictive; the intersection of the two belief bases of a safe splitting cannot contain any "meaningful" conditionals.

In the work [ 20 ] the safety condition was therefore generalized, allowing more meaningful conditionals in the intersection and thus broadening the applicability of conditional syntax splitting postulates to more splittings and more belief bases.

Definition 7 ([ 20 ]). A belief base ∆ = ∆ 1 ⋃︀Σ1,Σ2 ∆ 2 | Σ 3 can be generalized safely split into subbases ∆ 1, ∆ 2 conditional on a subsignature Σ 3, writing if the following generalized safety property holds for , ′ ∈ {1, 2}, ̸= ′: for every 3 ∈ Ω Σ∪Σ3 , there is ′ ∈ Ω Σ′ s.t. 3′ ̸|= ⋁︁ ( |)∈Δ′ ∖Δ3

The deciding diference in (6) compared to (4) is that only conditionals in ∆ ′ ∖ ∆ 3 are considered for the generalized safety property as opposed to all conditionals in ∆ ′ for the safety property. Following this generalization of the safety property, the postulates (CRel), (CInd) and (CSynSplit) were generalized accordingly.

Definition 8 ([ 20 ]). For any ∆ = ∆ 1 ⋃︀gΣs1,Σ2 ∆ 2 | Σ 3, for ∈ {1, 2}, and any , ∈ ℒ(Σ ), ∈ ℒ(Σ ) and a complete conjunction ∈ ℒ(Σ 3), such that ̸|∼ Δ ⊥, an inductive inference operator C satisfies (CRelg) if |∼ Δ (CIndg) if |∼ Δ (CSynSplitg) if it satisfies (CRel g) and (CIndg).

The postulate (CSynSplitg) properly generalizes (CSynSplit) as stated in the following proposition. Proposition 9 ([ 20 ]). (CSynSplitg) implies (CSynSplit) but not vice versa.

In [ 20 ] it was then shown that skeptical c-inference also satisfies this generalized version of conditional syntax splitting.

Proposition 10 ([ 20 ]). c-Inference satisfies (CRel g) and (CIndg) and thus (CSynSplitg).

With regard to reasoning with single c-representations the postulate (IP-CSP) for selection strategies was also adapted for generalized safe splittings into the postulate (IP-CSPg). (IP-CSPg) [ 20 ] A selection strategy is impact preserving w.r.t. generalized safe conditional belief base splitting if, for every generalized safe conditional belief base splitting ∆ = ∆ 1 ⋃︀gΣs1,Σ2 ∆ 2 | Σ 3, for ∈ {1, 2}, we have (∆ ) = (∆)| Δ .

Accordingly, inference with c-representations based on a selection strategy satisfying this postulate have been shown to satisfy (CSynSplitg).

Proposition 11 ([ 20 ]). Let be a selection strategy that satisfies (IP-CSP and (CIndg) and thus (CSynSplitg). g). Then Cc-rep satisfies (CRel g)

Additionally, in [ 20 ] another subclass of conditional syntax splittings, called genuine splittings was identified.

Definition 12 ([ 20 ]). Let ∆ be a belief base over a signature Σ . A conditional syntax splitting ∆ = ∆ 1 ⋃︀Σ1,Σ2 ∆ 2 | Σ 3 of ∆ is called genuine, if ∆ 1 ̸⊆ ∆ 2 and ∆ 2 ̸⊆ ∆ 1.

Intuitively, we call a splitting genuine if each subbase contains information that can not be found in the other subbase. This means that non-genuine splittings cannot be exploited for inductive inference, and the postulates (CRelg) and (CIndg) describe only trivial cases. We illustrate the importance of identifying genuine splittings and our generalization of the safety property with an example. Example 13 (∆ , [ 20 ]). {(|), (|), (|), (|), (|), (|)}. ∆ is

We

consider the belief base ∆ =

One of the possible conditionals syntax splittings of ∆ = {(|), (|), (|)} {(|), (|), (|), (|), (|)} | {, } (7) which, however, is not safe. ∆ has a total of 37 conditional syntax splittings, out of which 32 are generalized safe splittings, but only 16 are safe splittings. Only 5 of the 37 splittings are genuine. The splitting (7) is both generalized safe and genuine. For the belief base ∆ all genuine splittings are generalized safe, while no safe splitting is genuine.

gs ⋃︁ {},{,}

5. Future Work

The next step in this line of research is to investigate how a fitting conditional syntax splitting for a given query and belief base might be found. That is, given a belief base ∆ and two formulas and , ifnd a conditional syntax splitting ∆ = ∆ 1 ⋃︀gΣs1,Σ2 ∆ 2 | Σ 3, such that entails in the context of ∆ if and only if entails in the context of ∆ 1 and such that ∆ is minimal with this property. An obvious problem is that this computation might be even more expensive than simply working out the query directly, thus it seems reasonable to develop heuristics such that ∆ 1 might not be minimal but "suficiently small" instead. For this we plan to develop algorithms and implement them to evaluate their benefits for implementations of inductive inference operators. Another possible direction is the integration of conditional syntax splitting with focused inference [ 11 ] as an approximation from "both directions": While conditional syntax splitting chiefly concerns itself with which conditionals are not relevant, focused inference instead governs which conditionals are necessarily relevant for a query. Integrating these frameworks could therefore lead to the construction of a sort of upper and lower bound of conditionals relevant for a given query. Additionally, we plan to investigate the case where both a conditional syntax splitting and a query are given. Not all queries can benefit from a given conditional syntax splitting as the requirement is that a full conjunction over Σ 3 is part of the antecedent of the query. Therefore, we plan to investigate how queries might be transformed or optimized to take advantage of a given syntax splitting. Furthermore, the concept of case splittings [ 24 ] has been investigated where the antecedents of the conditionals are required to split into exclusive and exhaustive sets partitioning the belief base. We intend to investigate expanding this approach to also consider splittings into non-exclusive cases that may share some atoms in an analogous way to conditional syntax splitting. Of all these avenues, we intend to prioritize the development of an algorithm for ifnding appropriate conditional syntax splittings and then further refine this by investigating the other mentioned research directions.

Acknowledgments

This work was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - 512363537, grant BE 1700/12-1 awarded to Christoph Beierle. Lars-Phillip Spiegel was supported by this grant.

Declaration on Generative AI

The author has not employed any Generative AI tools.

References

[1] M. Goldszmidt , J. Pearl , Qualitative probabilities for default reasoning, belief revision, and causal modeling , Artif. Intell . 84 ( 1996 ) 57 - 112 .

[2] D. Lehmann , Another perspective on default reasoning , Annals of Mathematics and Artificial Intelligence 15 ( 1995 ) 61 - 82 .

[3] C. Beierle , C. Eichhorn , G. Kern-Isberner , S. Kutsch , Properties of skeptical c-inference for conditional knowledge bases and its realization as a constraint satisfaction problem , Annals of Mathematics and Artificial Intelligence 83 ( 2018 ) 247 - 275 .

[4] C. Beierle , C. Eichhorn , G. Kern-Isberner , S. Kutsch , Properties and interrelationships of skeptical, weakly skeptical, and credulous inference induced by classes of minimal models , Artificial Intelligence 297 ( 2021 ) 103489 . doi: 10 .1016/j.artint. 2021 . 103489 .

[5] C. Komo , C. Beierle , Nonmonotonic inferences with qualitative conditionals based on preferred structures on worlds , in: KI 2020 , volume 12325 of LNCS , Springer, 2020 , pp. 102 - 115 . doi: 10 . 1007/978-3- 030 -58285-2\_8.

[6] C. Komo , C. Beierle , Nonmonotonic reasoning from conditional knowledge bases with system W, Ann . Math. Artif. Intell. 90 ( 2022 ) 107 - 144 . doi: 10 .1007/s10472-021-09777-9.

[7] J. P. Delgrande , A knowledge level account of forgetting , J. Artif. Intell. Res . 60 ( 2017 ) 1165 - 1213 . URL: https://doi.org/10.1613/jair.5530. doi: 10 .1613/jair.5530.

[8] J. Pearl , System Z : A natural ordering of defaults with tractable applications to nonmonotonic reasoning , in: Proc. TARK' 1990 , Morgan Kaufmann, 1990 , pp. 121 - 135 .

[9] W. Spohn , Ordinal conditional functions: a dynamic theory of epistemic states, in: Causation in Decision, Belief Change , and Statistics, II , Kluwer Academic Publishers, 1988 , pp. 105 - 134 .

[10] G. Kern-Isberner , C. Beierle , G. Brewka, Syntax splitting = relevance + independence: New postulates for nonmonotonic reasoning from conditional belief bases , in: KR-2020 , 2020 , pp. 560 - 571 . doi: 10 .24963/kr.2020/56.

[11] M. Wilhelm , G. Kern-Isberner , Focused inference and system P, in: Thirty- Fifth AAAI Conference on Artificial Intelligence , AAAI 2021 , Virtual Event , February 2-9 , 2021 , 2021 , pp. 6522 - 6529 .

[12] M. Wilhelm , D. Howey , G. Kern-Isberner , K. Sauerwald , C. Beierle , Activation-based conditional inference , FLAP 10 ( 2023 ) 221 - 247 . URL: https://collegepublications.co.uk/downloads/ifcolog00058. pdf.

[13] F. D. de Saint-Cyr , P. Bisquert , The form and the content: Non-monotonic reasoning with syntactic contextual filtering , in: ECAI 2024 - 27th European Conference on Artificial Intelligence , volume 392 of Frontiers in Artificial Intelligence and Applications , 2024 , pp. 1309 - 1316 .

[14] R. Parikh , Beliefs, belief revision, and splitting languages, Logic, Language, and Computation 2 ( 1999 ) 266 - 278 .

[15] P. Peppas , M.- A. Williams , S. Chopra , N. Y. Foo , Relevance in belief revision, Artificial Intelligence 229 ( 2015 ) 126 - 138 .

[16] G. Kern-Isberner , G. Brewka, Strong syntax splitting for iterated belief revision , in: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017 , Melbourne, Australia, August 19-25 , 2017 , 2017 , pp. 1131 - 1137 .

[17] J. Heyninck , G. Kern-Isberner , T. Meyer, J. P. Haldimann , C. Beierle , Conditional syntax splitting for non-monotonic inference operators , in: AAAI-2023 , volume 37 , 2023 , pp. 6416 - 6424 . doi: 10 . 1609/aaai.v37i5. 25789 .

[18] E. Weydert , System JZ - How to build a canonical ranking model of a default knowledge base , in: A. Cohn , L. Schubert , S. Shapiro (Eds.), Proc. of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98) , Morgan Kaufmann, 1998 , pp. 190 - 201 .

[19] C. Beierle , L.-P. Spiegel , J. Haldimann , M. Wilhelm , J. Heyninck , G. Kern-Isberner , Conditional splittings of belief bases and nonmonotonic inference with c-representations , in: Principles of Knowledge Representation and Reasoning: Proceedings of the 21st International Conference, KR 2024 , 2024 , pp. 106 - 116 .

[20] L. Spiegel , J. Haldimann , J. Heyninck , G. Kern-Isberner , C. Beierle , Generalized safe conditional syntax splitting of belief bases , in: Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025 , Montreal, Canada, August 16-22 , 2025 , ijcai.org, 2025 , pp. 4678 - 4686 . URL: https://doi.org/10.24963/ijcai. 2025 /521. doi: 10 .24963/IJCAI. 2025 /521.

[21] G. Kern-Isberner , Conditionals in Nonmonotonic Reasoning and Belief Revision - Considering Conditionals as Agents , number 2087 in Lecture Notes in Computer Science , Springer Science+Business Media, Berlin, DE, 2001 .

[22] G. Kern-Isberner , A thorough axiomatization of a principle of conditional preservation in belief revision , Ann. Math. Artif. Intell. 40 ( 1-2 ) ( 2004 ) 127 - 164 .

[23] C. Beierle , G. Kern-Isberner , Selection strategies for inductive reasoning from conditional belief bases and for belief change respecting the principle of conditional preservation , in: E. Bell , F. Keshtkar (Eds.), Proceedings of the 34th International Florida Artificial Intelligence Research Society Conference (FLAIRS-34) , 2021 . doi: 10 .32473/flairs.v34i1. 128459 .

[24] G. Kern-Isberner , M. Sezgin , C. Beierle , A kinematics principle for iterated revision , Artif. Intell . 314 ( 2023 ) 103827 . doi: 10 .1016/j.artint. 2022 . 103827 .