Generalized Safe Conditional Syntax Splitting of Belief Bases

1 Introduction

For epistemic reasoning, both from a cognitive point of view and also from the point of view of effective implementations, it is often vital to focus on the relevant parts, and leaving aside facts and knowledge irrelevant for the question at hand, thus enabling local reasoning [Pearl, 1988]. This is the basic motivation underlying the concept of syntax splitting [Parikh, 1999; Peppas et al., 2015; Kern-Isberner and Brewka, 2017], and of the related idea of minimum irrelevance [Weydert, 1998]. Under the motto "syntax splitting = relevance + independence", respecting syntax splitting was formalized for inductive inference from conditional belief bases [Kern-Isberner et al., 2020], taking splittings over a belief base ∆ into account where the subbases ∆1, ∆2 are given over disjoint subsignatures of ∆. This condition is a severe restriction in practice because full disjointness is often not the case. The concept of conditional syntax splitting [Heyninck et al., 2023] is an approach to overcome this restriction by allowing ∆1 and ∆2 to overlap syntactically. A safety condition ensures that semantic (conditional) independence holds given the joint atoms, enabling local reasoning within the subbases. Furthermore, the postulate of conditional independence (CInd) for safe conditional splittings precisely characterizes avoiding the drowning effect [Pearl, 1990; Benferhat et al., 1993], yielding the first formal definition of the notorious drowning problem that had been described before only by specific examples [Heyninck et al., 2023]. However, it has been shown recently that the safety condition in [Heyninck et al., 2023] has the undesirable consequence that every conditional in the intersection of ∆1 and ∆2 is a trivial self-fulfilling conditional, meaning that it cannot be falsified [Beierle et al., 2024b], thus imposing a strong restriction on possible splitting benefits for inference. We develop a generalization of this safety condition, allowing the intersection of ∆1 and ∆2 to contain more meaningful conditionals. This greatly broadens the application possibilities of syntax splitting by increasing both the amount of splittings and the amount of belief bases where splittings can be exploited for inductive reasoning. The main contributions of this paper are:

• Generalization of safe conditional syntax splitting for belief bases;
• Identification of the subclass of genuine splittings, separating them from the large class of simple splittings that have no benefits for inductive inference because existing postulates cannot be meaningfully applied to them;
• Adapted postulates (CRel g ), (CInd g ), and (CSynSplit g ) for generalized safe conditional syntax splitting;
• Showing that (CSynSplit g ) implies (CSynSplit), but not the other way around;
• Evaluation of several inductive inference operators with respect to generalized safe conditional syntax splitting (CSynSplit g ).

After recalling the needed background in Sec. 2, we point out the limitations of safe conditional splittings (Sec. 3), introduce generalized and genuine splittings (Sec. 4), adapt the postulates for inference (Sec. 5), and evaluate inductive inference operators (Sec. 6) before concluding in Sec. 7.

2 Formal Basics

Let L be a finitely generated propositional language over a signature Σ with atoms a, b, c, . . . and with formulas A, B, C, . . . We may write AB instead of A ∧ B, and overline formulas to indicate negation, i.e., A means ¬A. Let Ω denote the set of possible worlds over L, taken here simply as the set of all propositional interpretations over L. ω |= A means that the propositional formula A ∈ L holds in ω ∈ Ω; in this case ω is called a model of A, and the set of all models of A is denoted by Mod (A). For propositions A, B ∈ L, A |= B holds iff Mod (A) ⊆ Mod (B), as usual. We will use ω both for the model and the corresponding complete conjunction of all positive or negated atoms, allowing us to use ω both as an interpretation and a proposition.

For Θ ⊆ Σ, let L(Θ) or short LΘ denote the propositional language defined by Θ, with associated set of interpretations Ω(Θ) or short ΩΘ. Note that while each formula of L(Θ) can also be considered as a formula of L, the interpretations ωΘ ∈ Ω(Θ) are not elements of Ω(Σ) if Θ ̸= Σ. But each interpretation ω ∈ Ω can be written uniquely in the form ω = ωΘωΘ with concatenated ωΘ ∈ Ω(Θ) and ωΘ ∈ Ω(Θ), where Θ = Σ\Θ. The world ωΘ is called the reduct of ω to Θ [Delgrande, 2017]. If Ω′ ⊆ Ω is a subset of models, then Ω′ |Θ = {ωΘ|ω ∈ Ω′ } ⊆ Ω(Θ) restricts Ω′ to a subset of Ω(Θ). In the following, we will often denote subsignatures of Σ by Σ1, Σ2, . . . and write ωi instead of ωΣi to ease notation.

By making use of a conditional operator |, we introduce the language (L|L) = {(B|A) | A,B ∈ L} of conditionals over L. Conditionals (B|A) are meant to express plausible, defeasible rules "If A then plausibly (usually, possibly, probably, typically etc.) B". For a world ω a conditional (B|A) is either verified by ω if ω |= AB, falsified by ω if ω |= AB, or not applicable to ω if ω |= A. A conditional (F|E) is called self-fulfilling, or trivial, if E |= F, i.e., there is no world that can falsify it. A popular semantic framework for interpreting conditionals are ordinal conditional functions (OCFs) κ : Ω → N∪ {∞} with κ-1 (0) ̸= ∅. OCFs, also called ranking functions, introduced, in a more general form, by [Spohn, 1988]. Intuitively, less plausible worlds are assigned higher numbers. Formulas are assigned the rank of their most plausible models, i.e., κ(A) := min{κ(ω) | ω |= A}. The rank of (B|A) is κ(B|A) = κ(AB) - κ(A). A conditional (B|A) is accepted by κ, written as κ |= (B|A), iff κ(AB) < κ(AB), i.e., iff AB is more plausible than AB. This is lifted to belief bases via κ |= ∆ if κ |= (B|A) for all (B|A) ∈ ∆. Belief bases ∆ (over Σ) consist of finitely many conditionals from (L | L). Consistency of such a belief base ∆ can be defined in terms of OCFs [Pearl, 1990]: ∆ is (strongly) consistent iff there is an OCF κ such that κ |= ∆ and κ(ω) < ∞ for all ω ∈ Ω. We focus on (strongly) consistent belief bases in the sense of [Pearl, 1990; Goldszmidt and Pearl, 1996] in order to elaborate our approach without having to deal with distracting technical particularities. The nonmonotonic inference relation |∼κ induced by an OCF κ is [Spohn, 1988]

The marginal of κ on Θ ⊆ Σ, denoted by κ|Θ, is defined by

κ|Θ(ωΘ) = κ(ωΘ) for any ωΘ ∈ Ω(Θ). Here ωΘ is treated as a world in κ|Θ(ωΘ) but as a formula in κ(ωΘ). Note that this marginalization is a special case of the general forgetful functor Mod(σ) from Σ-models to Θ-models [Beierle and Kern-Isberner, 2012] where σ is the inclusion from Θ to Σ.

An inductive inference operator [Kern-Isberner et al., 2020] is a mapping C that assigns to each belief base ∆ ⊆ (L | L) an inference relation |∼∆ on L, i.e., C : ∆ ↦→ |∼∆, such that the following two properties hold:

Direct Inference (DI): If (B|A) ∈ ∆ then A |∼∆ B, and Trivial Vacuity (TV): A |∼∅ B implies A |= B.

Examples for inductive inference operators are:

p-entailment |∼p [Goldszmidt and Pearl, 1996]: Considers all ranking models of ∆; coincides with System P-inference [Lehmann and Magidor, 1992; Dubois and Prade, 1994].

SystemZ |∼z [Goldszmidt and Pearl, 1996]: Uses an OCF based on the tolerance partition of ∆; coincides with rational closure [Lehmann and Magidor, 1992].

c-inference |∼c [Beierle et al., 2018; Beierle et al., 2021]: Considers all c-representations of ∆ [Kern-Isberner, 2001; Kern-Isberner, 2004].

SystemW |∼w [Komo and Beierle, 2020; Komo and Beierle, 2022] Also considers the tolerance partition of ∆; extends both c-inference and system Z.

3 Limitations of Conditional Syntax Splitting

Syntax splittings describe that a belief base contains completely independent information about different parts of the signature. According to [Kern-Isberner et al., 2020], a belief base ∆ splits into subbases ∆1,∆2 if {Σ1, Σ2} is a partition of Σ such that ∆ = ∆1 ∪∆2, ∆i ⊂ (Li|Li), Li = L(Σi) for i ∈ {1, 2}, Σ1 ∩ Σ2 = ∅, and Σ1 ∪ Σ2 = Σ, denoted as

Syntax splittings are very useful for formalizing the idea that independent information about different topics should not affect each other in reasoning. Syntax splittings were generalized in [Heyninck et al., 2023] to conditional syntax splittings, which allow subbases to share some atoms in a given subsignature Σ3.

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

Unlike syntax splitting, conditional syntax splitting does not require the subbases ∆1 and ∆2 to be disjoint. For the remainder of this paper, we will use the notation introduced in the following straightforward proposition.

Proposition 2. Let ∆=∆1 ⋃Σ1,Σ2 ∆2 | Σ3 and let

Then ∆1\3, ∆2\3, ∆3 are pairwise disjoint and

Note that in Proposition 2, ∆3 = ∆ ∩ (L(Σ3)|L(Σ3)), implying that ∆3 ⊆ (L(Σ3)|L(Σ3)), and, for i ∈ {1, 2}, ∆i′ \3⊆ (L(Σi ∪ Σ3)|L(Σi ∪ Σ3)).

For ω ∈ Ω and A ∈ L(Σi) we have

Given some Σ3 ⊆ Σ, every belief base has at least one syntax splitting conditional on Σ3.

Proposition 3. Let ∆ be a belief base over a signature Σ. For every Σ3 ⊆ Σ, there exists the conditional syntax splitting ∆=∆1 ⋃Σ\Σ3,∅ ∆2 | Σ3.

Note that for a splitting adhering to this form we have ∆1 = ∆ and ∆2 = ∆3 = ∆ ∩ (L(Σ3)|L(Σ3)).

Given a complete conjunction over Σ3, i.e., a formula uniquely describing a world in Ω(Σ3), conditional syntax splittings in general do not ensure complete independence of ∆1 and ∆2 (for details see [Heyninck et al., 2023], Ex. 6). To fix this, safe conditional syntax splittings were introduced.

Definition 4 ([Heyninck et al., 2023]). A belief base ∆ = ∆1 ⋃Σ1,Σ2 ∆2 | Σ3 can be safely split into subbases ∆1, ∆2 conditional on a subsignature Σ3, writing

if the following safety property holds for i, i′ ∈ {1, 2}, i ̸= i′ :

for every ωiω3 ∈ Ω(Σi ∪Σ3), there is ωi′ ∈ Ω(Σi′ )

The safety condition demands, in essence, that no complete conjunction over Σ3 may force the falsification of a conditional in ∆ when considering Σ as a whole.

Example 5 (∆sun ). Consider the belief base ∆sun = {(s|r), (r|s), (b|sr), (g|b), (o|sr), (o|r), (u|or)} describing the following: If it is (r)ainy, then usually it is not (s)unny and vice versa. If it is rainy and sunny at the same time, then we can usually observea rain(b)ow. Maybe superstitiously, we believe that there is usually some (g)old to be found at the end of the rainbow. Unrelated to this, we usually spend some time (o)utside if it is sunny and not rainy. If it is rainy, then we usually do not spend time outside. If, despite our normal habits, we do spend time outside and it is rainy, then we usually have an (u)mbrella. ∆sun has a safe conditional syntax splitting

where Σ1 = {g},Σ2 = {s, r, o, u},Σ3 = {b},∆sun 1 = {(g|b)}, ∆sun 2 = {(s|r), (r|s), (b|sr), (o|sr), (o|r), (u|or)}, and ∆sun 3 = ∅. This splitting is safe: We can extend any ω1 ∈ Ω(Σ1 ∪Σ3) by any ω′ ∈ Ω(Σ2) with ω′ |= s∧r∧o∧u without falsifying a conditional in ∆sun 2 . Similarly we can extend any ω2 ∈ Ω(Σ2 ∪Σ3) by any ω′′ ∈ Ω(Σ1) with ω′′ |= g without falsifying a conditional in ∆sun 1 .

Safe conditional syntax splitting provides similar benefits for inductive inference as syntax splitting. Reasoning in the language of ∆1 is independent of the conditionals in ∆2, and vice versa, given we have full knowledge over the atoms in Σ3. However, it has been shown recently that the safety property (10) imposes a strong, undesired restriction on ∆3.

Lemma 6 ([Beierle et al., 2024b]). Let ∆ = ∆1 ⋃sΣ1,Σ2 ∆2 | Σ3, then ∆3 = ∆1 ∩ ∆2 contains only self-fulfilling conditionals.

While it is true that ∆3 can not contain "meaningful" information, the elements in Σ3 are still relevant and can occur in conditionals of both ∆1 and ∆2.

A generalization of the safety property to avoid the effect described in Lemma 6 would be advantageous. Recall that Σ3 represents a sort of global knowledge, that should be considered in both subbases. However it is not always possible to find a safe splitting, given some intuitive or in practice desirable allocation of signature elements to Σ3.

Example 7 (∆sun cont.). Assume we want to reason based on ∆sun , under the assumption that we have full knowledge about s and r. A conditional syntax splitting reflecting our knowledge about the weather is

where Σ1 = {b, g},Σ2 = {o, u},Σ3 = {s, r},∆sun 1 = {(s|r), (r|s), (b|sr), (g|b)}, ∆sun 2 = {(s|r), (r|s), (o|sr), (o|r), (u|or)}, and ∆sun 3 = {(s|r), (r|s)}. Assume that we know that it is sunny and rainy at the same time, and we would like to know if there will usually be a rainbow, i.e., whether sr |∼∆sunb holds. Employing the splitting (12), it suffices to consider ∆sun 1 to answer this query because we have full knowledge about {s, r}. However, because the conditionals in ∆sun 3 are not self-fulfilling the splitting (12) is not safe.

Comparing the splittings (11) and (12), we can see that there are situations where (12) provides benefits not provided by (11). For instance, as it will be shown formally in the following sections, answering the query sr |∼∆sunb can be done using the subbase ∆sun 1 from (12) while the splitting (11) does not provide any advantage for answering this query.

Another limitation of safe conditional syntax splittings is that there exist belief bases where all safe conditional syntax splittings involve a subset relationship between the subbases.

Example 8 (∆rain ). Starting from ∆sun , we get rid of our superstitious beliefs by removing the signature element g and all associated conditionals, yielding ∆rain = {(s|r), (r|s), (b|sr), (o|sr), (o|r), (u|or)}. ∆rain has a splitting conditional on {s, r}

which, however, is not safe. In fact, every safe splitting of ∆rain = ∆rain 1 ⋃sΣ1,Σ2 ∆rain 2 | Σ3 satisfies ∆rain 1 ⊆ ∆rain 2 or ∆rain 2 ⊆∆rain 1 .

Every conditional syntax splitting ∆ = ∆1 ⋃Σ1,Σ2 ∆2 | Σ3 with ∆1 ⊆ ∆2 or ∆2 ⊆ ∆1 is of little use for inductive inference. Suppose ∆1 ⊆ ∆2. Then answering any query over

Σ2 ∪Σ3 requires considering ∆ as a whole because ∆2 = ∆. Furthermore, any query over Σ1 ∪ Σ3 can also not benefit from the splitting. This is because atoms of Σ1 can not appear in ∆1, since all conditionals of ∆1 are defined over Σ3 as ∆1 = ∆1 ∩∆2 = ∆3 and full knowledge of Σ3 is required to make use of the splitting.

The observations above give rise to two points. First, we will extend the notion of safety to cover conditional splittings like (12) and (13). Second, we will identify splittings that are useful for inductive inference.

4 Generalized Safe Conditional Syntax Splitting

We first introduce generalized safe splittings as a generalization of safe splittings to cover cases where the subbases may share non-trivial conditionals, and we introduce genuine splittings, which identify splittings that provide benefits for inductive inference.

Definition 9. 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 i, i′ ∈ {1, 2}, i ̸= i′ :

The deciding difference in (15) compared to (10) is that only conditionals in ∆i′ \3 are considered for the generalized safety property as opposed to all conditionals in ∆i′ for the safety property.

Proposition 10. Let ∆ be a belief base over Σ with a conditional syntax splitting S : ∆ = ∆1 ⋃Σ1,Σ2 ∆2 | Σ3.

1. If S is safe, S is generalized safe.

Generalized safety allows for more splittings adhering to a notion of safety. For example, the conditional syntax splittings in Proposition 3 are always generalized safe. Thus, for every Σ3 ⊆ Σ, there always exists a generalized safe syntax splitting conditional on Σ3. Observe that generalized safe splittings allow for non-trivial conditionals in ∆3.

Example 11 (∆sun ,∆rain cont.). While not safe, the conditional syntax splittings in Examples 7 and 8 are generalized safe. For instance, in both examples, the conditional (r|s) can be falsified by rs ∈ Ω(Σi ∪ Σ3), thus making the splittings not safe, but since (r|s) ∈ ∆sun 3 and (r|s) ∈ ∆rain 3 , this fact does not lead to a violation of generalized safety.

With Example 11 and Proposition 10 we can see that there exists more generalized safe conditional syntax splittings than safe conditional syntax splittings. Thus, generalized safety properly extends the amount of belief bases that can be conditionally split while adhering to a notion of safety.

For governing inductive inference, we are only interested in (generalized) safe conditional syntax splittings. Example 8 shows that there exists belief bases that have safe conditional syntax splittings, but some ∆i is a subset of ∆j and therefore, even though the splitting is safe, it does not provide any meaningful information for inductive inference. We now identify splittings that are meaningful with respect to inductive inference as so-called genuine splittings.

Definition 12. 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

Note that genuine splittings can be equivalently characterized by ∆1\3 ̸= ∅ and ∆2\3 ̸= ∅. Intuitively, we call a splitting genuine if each subbase contains information that can not be found in the other subbase. Especially, the following types of splittings are not genuine.

While the 〈trivial〉 splitting (i) is safe, the splitting (ii) is not safe, unless ∆ contains self-fulfilling conditionals only. However, splitting (ii) is generalized safe. Furthermore, in the case that Σ contains no elements that do not appear in ∆, the not genuine splittings are exactly the 〈sig-empty〉 splittings. If ∆3 = ∅, then the not genuine splittings are exactly the 〈set-empty〉 splittings. We give an example to illustrate the importance of identifying genuine splittings.

Example 13 (∆rain cont.). We continue Example 8. The belief base ∆rain 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 36 splittings are genuine. For this belief base all genuine splittings are generalized safe, while no safe splitting is genuine.

While in Example 13 the set of genuine and generalized safe splittings coincide, this does not hold in general. Example 13 shows that there exist belief bases for which no genuine, safe conditional syntax splitting exists, but a genuine, generalized safe splitting exists. Indeed, conditional syntax splittings that are both genuine and generalized safe are those splittings, where the properties of conditional relevance and conditional independence for inductive inference may be meaningfully applied.

5 Inductive Inference Respecting Generalized Safe Conditional Syntax Splitting

We will now introduce postulates to evaluate inductive inference operators with respect to generalized safe conditional syntax splitting. For this, we adjust the notions of conditional relevance and conditional independence from [Heyninck et al., 2023] to include also generalized safe splittings. The idea of these postulates is that for a belief base with (generalized safe conditional) syntax splitting, inference over one subsignature should be independent from the information about the other subsignature (given that the valuation of the shared subsignature is fixed).

(CRel g ) (adapted from [Heyninck et al., 2023]) An inductive inference operator C satisfies (CRel g ) if for any ∆ = ∆1 ⋃gs Σ1,Σ2 ∆2 | Σ3, for i ∈ {1, 2} and any A, B ∈ L(Σi), and a complete conjunction E ∈ L(Σ3),

Thus, (CRel g ) restricts the scope of inference by requiring that inferences in the sub-language Σ1 ∪Σ3 can be made taking only ∆1 into account.

(CInd g ) (adapted from [Heyninck et al., 2023]) An inductive inference operator C satisfies (CInd g ) if for any ∆ = ∆1 ⋃gs Σ1,Σ2 ∆2 | Σ3, for i, j ∈ {1, 2}, j ̸= i, and any A,B ∈ L(Σi), D ∈ L(Σj), and a complete conjunction E ∈ L(Σ3), such that DE ̸|∼∆ ⊥ we have

Thus, an inductive inference operator satisfies (CInd g ) if, for any ∆ that safely splits into ∆1 and ∆2 conditional on Σ3, whenever we have all the necessary information about Σ3, inferences from one sub-language are independent from formulas over the other sub-language.

Syntax splitting (CSynSplit g ) is the combination of the two properties (CInd g ) and (CRel g ).

(CSynSplit g ) (adapted from [Heyninck et al., 2023]) An inductive inference operator C satisfies conditional syntax splitting (CSynSplit g ) if it satisfies (CRel g ) and (CInd g ).

The difference between (CSynSplit) and our new variant (CSynSplit g ) is that (CSynSplit) was defined regarding safe conditional syntax splittings only, while our adjusted variant (CSynSplit g ) takes into account all generalized safe conditional syntax splittings. Thus, an inductive inference operator satisfing (CSynSplit g ) respects an increased number of conditional splittings.

Example 14 (∆rain cont.). Recall the splitting (13) for ∆rain from Example 8. Let C : ∆ ↦→ |∼rain ∆ be an inductive inference operator that satisfies (CSynSplit g ). Applying (CRel g ), we obtain that the inference sr |∼rain ∆ b holds iff the inference sr |∼rain ∆1 b holds. Thus, if we want to know whether the inference holds in ∆, it is sufficient to consider only ∆1, reducing the amount of conditionals we need to take into account from 6 to 3. By applying (CInd g ), we additionally know that the inferences sro |∼rain ∆ b and sro |∼rain ∆ b hold if the inference sr |∼rain ∆ b holds. In this way, we can localize our reasoning tasks for the entire belief base to a smaller subbase, given that our reasoning mechanism satisfies (CSynSplit g ).

The postulate (CSynSplit g ) covers and indeed properly generalizes (CSynSplit):

Proposition 15. The following relationships hold:

1. (CSynSplit g ) implies (CSynSplit).
2. (CSynSplit) does not imply (CSynSplit g ).

While the first part of Proposition 15 holds trivially, the second part can be shown by constructing an inductive inference operator satisfying (CSynSplit) but violating (CSynSplit g ). Such an operator can be obtained by applying an inference operator satisfying (CSynSplit) if the input belief base ∆ has a genuine safe conditional syntax splitting, and an inference operator violating (CSynSplit g ) otherwise.

6 Evaluating Inductive Inference Operators with respect to (CSynSplit g )

In this section we consider several inductive inference operators and evaluate whether they satisfy (CSynSplit g ).

6.1 SystemZ and SystemW

System Z is an OCF-based inductive inference operator based on the ranking function κz [Pearl, 1990]. The definition of κz crucially relies on the notion of tolerance. A conditional (B|A) is tolerated by a set of conditionals ∆ = {(B1|A1), . . . , (Bn|An)} if there is a world ω ∈ Ω such that ω |= AB and ω |= ∧ni=1 (Ai ∨ Bi), i.e., iff ω verifies (B|A) and does not falsify any conditional in ∆. For every consistent knowledge base, the notion of tolerance yields a unique inclusion-maximal ordered partition, in the following denoted by OP(∆) = (∆0 , . . . , ∆k ), of ∆ where each ∆i is the (with respect to set inclusion) maximal subset of ⋃kj=i ∆j that is tolerated by ⋃kj=i ∆j. Intuitively, general conditionals of ∆ are placed in the first sets of OP(∆) while more specific conditionals are placed in later parts of the partition. The system Z ranking function κz (ω) is defined as follows. If ω does not falsify any conditional in ∆, then let κz (ω) = 0. Otherwise, let ∆j be the latest part in the tolerance partition containing a conditional falsified by ω, and let κz (ω) = j +1 [Goldszmidt and Pearl, 1996]. System Z yields the inference relation induced by κz , i.e., Cz : ∆ ↦→ |∼κz .

Just like safe splittings, generalized safe splittings are respected by the notion of tolerance.

Proposition 16. Let ∆=∆1 ⋃gs Σ1,Σ2 ∆2 | Σ3. Then, for any i ∈ {1, 2}, ∆i tolerates (B|A) ∈ ∆i iff ∆ tolerates (B|A).

Proof. First, assume (B|A) is tolerated by ∆i. Then there must be some ωiω3 such that ωiω3 |= AB and there is no (D|C) ∈ ∆i such that ωiω3 |= CD. In particular, there is no such conditional in ∆3. Due to generalized safe ty there is an extension ωi′ such that there is no conditional (F |E) ∈ ∆i′ \3 with ωiω3ωi′ |= EF. Since ∆ = ∆i ∪ ∆i′ \3, (B|A) is tolerated by ∆. The other direction is immediate.

For System Z we can then show the following result.

Proposition 17. System Z satisfies (CRel g ), but does not satisfy (CInd g ) and thus does not satisfy (CSynSplit g ).

Crucial to showing that System Z satisfies (CRel g ) is Proposition 16 which can be used to show that the ordered partition of ∆i is respected by ∆ and vice versa. The fact that System Z does not satisfy (CInd g ) follows from the fact, that it does not satisfy (CInd) [Heyninck et al., 2023].

SystemW is an inference operator also using the tolerance partition OP(∆), but while System Z considers only which parts of OP(∆) contain falsified conditionals, system W also takes into account the structural information about which conditionals are falsified [Komo and Beierle, 2020; Komo and Beierle, 2022]. For this, System W uses the preferred structure on worlds <w∆ which compares worlds according to the set of conditionals in ∆ they falsify, giving preference to the more specific conditionals according to OP(∆). Using this ordering, B is a system W inference from A, denoted A|∼w∆B, if for every ω′ ∈ ModΣ(AB) there is an ω ∈ ModΣ(AB) with ω <w∆ ω′ . For details we refer to [Komo and Beierle, 2020; Komo and Beierle, 2022].

Proposition 18. SystemW satisfies (CRel g ) and (CInd g ) and thus (CSynSplit g ).

The proof of Proposition 18 is based on the observations that for ∆ = ∆1 ⋃gs Σ1,Σ2 ∆2 | Σ3 the order ω <w∆ ω′ of two worlds coinciding on Σ2 ∪ Σ3 depends only on ∆1 and that the order ω <w∆1 ω′ of worlds induced by ∆1 does not change if we change the valuation over Σ2 in the worlds.

6.2 Inference with Single c-Representations

Among the OCF models of ∆, c-representations are special ranking models obtained by assigning individual integer impacts to the conditionals in ∆ and generating the world ranks as the sum of impacts of falsified conditionals.

Definition 19 (c-representation [Kern-Isberner, 2001; Kern-Isberner, 2004]). A c-representation of ∆ = {(B1|A1), . . . , (Bn|An)} is an OCF κ constructed from non-negative impacts ηj ∈ N0 assigned to each (Bj|Aj) such that κ accepts ∆ and is given by:

c-Representations can conveniently be specified using a constraint satisfaction problem (for detailed explanations, see [Kern-Isberner, 2001; Kern-Isberner, 2004]):

Definition 20 (CR(∆), [Kern-Isberner, 2001; Beierle et al., 2018]). The constraint satisfaction problem CR(∆) for crepresentations of ∆ = {(B1|A1), . . . , (Bn|An)} is given by the conjunction of the constraints, for all j ∈ {1, . . . , n}:

Note that (17) expresses that falsification of conditionals should make worlds not more plausible, and (18) ensures that κ as specified by (16) accepts ∆. A solution of CR(∆) is a vector #» η = (η1, . . . , ηn) of natural numbers. Sol (CR(∆)) denotes the set of all solutions of CR(∆). For #» η ∈ Sol(CR(∆)) and κ as in Equation (16), κ is the OCF induced by #» η and is denoted by κ#» η . CR(∆) is sound and complete [Kern-Isberner, 2001; Beierle et al., 2018]: For every #» η ∈ Sol(CR(∆)), κ#» η is a c-representation with κ#» η |=∆, and for every c-representation κ with κ |=∆, there is #» η ∈ Sol(CR(∆)) such that κ = κ#» η . For #» η , we will simply write #» η 1 and #» η 2 for the corresponding projections #» η |∆1 and #» η |∆2 , and ( #» η 1 , #» η 2 ) for their composition.

A fundamental property of c-representations is that for any syntax splitting ∆ = ∆1 ⋃ Σ1,Σ2 ∆2 the composition of any

impact vectors for the subbases yields an impact vector for ∆, and vice versa [Kern-Isberner et al., 2020]. This property was also shown to extend to safe conditional syntax splittings [Beierle et al., 2024b]. However, a key part in showing this was Lemma 6 which no longer holds for generalized safe conditional syntax splittings. Indeed the composition property no longer holds, as the impacts assigned to the conditionals in ∆3 can be vastly different between the two subbases. Thus, we show a slightly weaker property here. While it still states that any impact vector for ∆ can be split into impact vectors for the subbases, impact vectors for the subbases may only yield an impact vector for ∆ if they match on the impacts assigned to the conditionals in ∆3.

Proposition 21. Let ∆=∆1 ⋃gs Σ1,Σ2 ∆2 | Σ3. The following two properties hold for i, i′ ∈ {1, 2}, i ̸= i′ :

• For every #» η ∈ Sol(CR(∆)) there are #» η i ∈ Sol(CR(∆i)), #» η i′ ∈ Sol(CR(∆i′)) and #» η 3 ∈ Sol(CR(∆3)) with #» η i |∆3 = #» η i′ |∆3 = #» η 3 , such that #» η = ( #» η i |∆i\3 , #» η i′ |∆i′\3 , #» η 3 ).
• For every #» η i ∈ Sol(CR(∆i)), #» η i′ ∈ Sol(CR(∆i′)) and #» η 3 ∈ Sol(CR(∆3)) with #» η i |∆3 = #» η i′ |∆3 = #» η 3 there is #» η ∈ Sol(CR(∆)) such that #» η = ( #» η i |∆i\3 , #» η i′ |∆i′\3 , #» η 3 ).

Due to the condition that #» η i |∆3 = #» η i′ |∆3 = #» η 3 , we have that #» η i = ( #» η i |∆3 , #» η 3 ) and #» η i′ = ( #» η i′ |∆3 , #» η 3 ). And thus #» η = ( #» η i , #» η i′ |∆i′\3 ) for both points of Proposition 21.

Example 22. For the belief base ∆ = {(c|a), (b|a)}, a possible c-representation κ#» η is given by #» η 1 = (1, 1) ∈ Sol (CR(∆)), yielding the following OCF:

Because ∆ = {(b|a)} ⋃gs {b},{c} {(c|a)} | {a} and ∆3 = ∅ we can obtain #» η 1 by combining #» η 11 = (1) and #» η 21 = (1) and vice versa utilizing Proposition 21.

To show that nonmonotonic reasoning with crepresentations satisfies (CSynSplit g ) we employ the concept of conditional κ-independence.

Definition 23 ([Heyninck et al., 2023],[Spohn, 2012]). Let Σ1,Σ2,Σ3 ⊆ Σ where Σ1,Σ2 and Σ3 are pairwise disjoint and let κ be an OCF. Σ1,Σ2 are conditionally κindependent given Σ3, in symbols Σ1 ⊥⊥κ Σ2|Σ3, if for all ω1 ∈ Ω(Σ1), ω2 ∈ Ω(Σ2), and ω3 ∈ Ω(Σ3), it holds that κ(ω1 |ω2ω3 ) = κ(ω1 |ω3 ).

Proposition 24 (adapted from [Beierle et al., 2024b]). Let ∆ = ∆1 ⋃gs Σ1,Σ2 ∆2 | Σ3, and κ a c-representation with κ |= ∆. Then Σ1 ⊥⊥κ Σ2|Σ3.

Now we introduce an alternative characterization of (CInd) and (CRel) based on OCFs, adapted to our new notion of generalized safe splittings.

Proposition 25 (adapted from [Heyninck et al., 2023]). An inductive inference operator for OCFs Cocf : ∆ ↦→ κ∆ satisfies (CInd g ) iff for any ∆ = ∆1 ⋃gs Σ1,Σ2 ∆2 | Σ3 we have Σ1 ⊥⊥κ∆ Σ2|Σ3.

Proposition 26 (adapted from [Heyninck et al., 2023]). An inductive inference operator for OCFs Cocf : ∆ ↦→ κ∆ satisfies (CRel g ) iff for any ∆ = ∆1 ⋃gs Σ1,Σ2 ∆2 | Σ3 and i ∈ {1, 2} we have κ∆i = κ∆ |Σi∪Σ3 .

We will now define model-based inductive inference operators assigning a c-representation κ to each ∆, by employing the concept of selection strategies.

Definition 27 (selection strategy σ, [Beierle and Kern-Isberner, 2021]). A selection strategy (for c-representations) is a function σ : ∆ ↦→ #» η assigning to each conditional belief base ∆ an impact vector #» η ∈ Sol(CR(∆)).

Each selection strategy yields an inductive inference operator Cc-rep σ : ∆ ↦→ κσ(∆) where |∼κσ(∆) is obtained via Equation (1) fromκσ(∆). Note that each |∼κσ(∆) satisfies both (Direct Inference) and (Trivial Vacuity). A recent example for a specific selection strategy are minimal core c-representations [Wilhelm et al., 2024].

In principle, for every ∆, a selection strategy may choose some impact vector independently from the choices for all other belief bases. The following property characterizes selection strategies that preserve the impacts chosen for subbases if ∆ splits into these subbases.

(IP-CSP g ) (adapted from [Beierle et al., 2024b]) A selection strategy σ is impact preserving w.r.t. conditional belief base splitting if, for every generalized safe conditional belief base splitting ∆ = ∆1 ⋃gs Σ1,Σ2 ∆2 | Σ3, for i ∈ {1, 2}, we have σ(∆i) = σ(∆)|∆i .

In [Beierle et al., 2024b] it is shown that any inductive inference operator based on an impact preserving selection strategy satisfies (CSynSplit); we extend this result to (CSynSplit g ).

Proposition 28. Let σ be a selection strategy satisfying (IPCSP g ). Then Cc-rep σ satisfies (CRel g ) and (CInd g ) and thus (CSynSplit g ).

After showing that inference based on a single crepresentation satisfies (CSynSplit g ) if the underlying selection strategy satisfies (IP-CSP g ), we next consider inference with respect to all c-representations of a belief base.

6.3 c-Inference

c-Inference was introduced in [Beierle et al., 2016; Beierle et al., 2018] as the skeptical inference relation obtained by taking all c-representations of a belief base ∆ into account.

Definition 29 (c-inference, |∼ c-sk ∆ , [Beierle et al., 2016]). Let ∆ be a belief base and let A, B be formulas. B is a (skeptical) c-inference from A in the context of ∆, denoted by A |∼c-sk ∆ B, iff A |∼ κB holds for all c-representations κ of ∆, yielding the inductive inference operator

Before proving that c-inference satisfies conditional syntax splitting, we show a lemma stating the following observations. Consider a generalized safe conditional syntax splitting of ∆ into ∆1 and ∆2, and a c-representation κ#» η determined by a solution vector #» η ∈ Sol(CR(∆)) together with its projections κ#» η 1 and κ#» η 2 to ∆1 and ∆2, respectively. Then the rank of any formula Fi over the language L(Σi ∪ Σ3) of ∆i under the projection κ#» η i coincides with the rank of the formula rank determined by κ#» η .

Proposition 30 (adapted from [Beierle et al., 2024b]). For any ∆ = ∆1 ⋃gs Σ1,Σ2 ∆2 | Σ3, for all #» η ∈ Sol(CR(∆)), and for i ∈ {1, 2}, Fi ∈ L(Σi ∪Σ3), we have κ#» η (Fi) = κ#» η i (Fi).

The related proposition in [Beierle et al., 2024b] additionally states that the rank of the formulas Fi is zero in the OCF κ#» η j . This no longer holds for generalized safe splittings because conditionals in ∆3 can be falsified by Fi.

Next we can show that for every generalized safe conditional syntax splitting and every solution vector for ∆i, we can actually find matching solution vectors for ∆i′ and ∆3.

Proposition 31. Let ∆ be a belief base with ∆ = ∆1 ⋃gs Σ1,Σ2 ∆2 | Σ3. Then for i ∈ {1, 2}, and for every #» η i ∈ Sol(CR(∆i)) there are #» η i′ ∈ Sol(CR(∆i′)) and #» η 3 ∈ Sol(CR(∆3)), such that #» η i |∆3 = #» η i′ |∆3 = #» η 3 .

With Propositions 21, 30, and 31 we can show:

Proposition 32. c-Inference satisfies (CRel g ) and (CInd g ) and thus (CSynSplit g ).

Thus also the inference taking all c-representations into account fully complies with (CSynSplit g ).

7 Conclusions and FutureWork

In this paper, we generalized the notion of safety for conditional syntax splittings, allowing the subbases to share nontrivial conditionals, and thus broadened the application scope of the beneficial splitting techniques. Moreover, we identified genuine splittings as the subclass of meaningfull conditional syntax splittings. We showed that this notion of safety properly generalizes the previous notion of safety and and gave illustrative examples of belief bases that have no safe conditional syntax splitting, but a generalized safe conditional syntax splitting. We adjusted postulates for conditional syntax splitting based on the generalized notion and showed that System W and inductive inference with a single c-representation based on a selection strategy, as well as inference with all c-representations fully comply with this new property. While System Z fails to satisfy syntax splittings, we showed that it fulfills (CRel g ). Furthermore, we showed that, while (CSynSplit g ) implies (CSynSplit), the other direction does not hold.

In future work, we will investigate further inference operators like lexicographic inference [Lehmann, 1995] with respect to (CSynSplit g ), and we will study the exact relationship of our approach to syntactic contextual filtering [Dupin de Saint-Cyr and Bisquert, 2024] and to propositional forgetting [Lang et al., 2003; Sauerwald et al., 2022; Sauerwald et al., 2024]. We will exploit the beneficial properties of splitting techniques for implementations of inductive inference [Beierle et al., 2024a] and we will adapt the concepts shown here to include also belief bases that satisfy a weaker notion of consistency (cf. [Haldimann et al., 2023; Haldimann et al., 2024]).

Acknowledgments

We would like to thank all reviewers for their valuable comments and hints which helped us to improve the paper.

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.

This work was supported by the Austrian Science Fund (FWF) projects P30873, PIN8884924, and the FWF and netidee SCIENCE project T1349-N. Jonas Haldimann was supported by these grants.

Jesse Heyninck was partially supported by the project NGF.1609.241.010 of the research programme NGF AiNed XS Europa 2024-1 which is (partly) financed by the Dutch Research Council (NWO).