c-Core closure and syntax splitting for conditional belief bases

In logic-based knowledge representation, conditionals (B|A) are used to express defeasible statements of the form 'if A holds, then usually B follows'. The formal semantics of such conditionals is typically given by preference relations over possible worlds. A widely used semi-quantitative way of expressing such preferences is constituted by ranking functions^[1] which assign a degree of implausibility to possible worlds and based on that to formulas. A ranking function κ accepts a conditional if its verification is more plausible than its falsification, $ \kappa(A \land B) \lt \kappa(A \land \neg B) $, and models a finite set of conditionals $ \Delta $ (a belief base) if $ \kappa $ accepts all conditionals in $ \Delta $. A family of ranking models with particularly good inference properties are the so-called c-representations^[2]. c-Representations are characterized by penalizing possible worlds for falsifying conditionals from the belief base where, mathematically, the impact factors are solutions of a complex constraint satisfaction problem (CSP) which reflects the interactions among the conditionals. This CSP may involve cyclic dependencies among the impact factors. The research question of a 'best' c-representation is still unresolved because plainly applying ideas of (pareto-)minimality to the impact vectors does not yield unique solutions^[3].

In this paper, we identify a novel subclass of c-representations, the so-called core c-representations. Core c-representations are special because they rely on a simplified constraint satisfaction problem and, as a consequence, can be computed more easily. In fact, there is a stratification method for core c-representations which resolves the cyclic dependencies among the impact factors. Furthermore, core c-representations have a unique minimal representative which allows us to define an inductive inference operation, the so-called c-core closure, that selects for each consistent conditional belief base its minimal core c-representation to draw inferences from the belief base. Therewith, we bring together the goals of minimizing c-representations (cf.^[4]) and stratification for the first time. In our context, stratification was formerly known from the System Z-like Z-c-representation only^[2]. The Z-c-representation is another instance of the family of core c-representations which, however, usually computes impact factors that are far from being minimal.

This article is a revised and extended journal version of a previously published conference paper^[5]. In contrast to the previous research by Wilhelm et al.^[5], the present research provides proofs of all propositions, further explanations and intuitions, as well as an additional example which shows that generalized tolerance partitions are a proper superclass of tolerance partitions. Moreover, as a major novel contribution in this journal version, it is proven that c-core closure satisfies conditional syntax splitting, like skeptical c-inference over all c-representations^[6,7], which was not thematized in the study by Wilhelm et al.^[5]. This is particularly in contrast to p-entailment^[8,9] and System Z inference^[10], that both do not satisfy conditional syntax splitting. Here, it is shown that the latter inductive inference operators satisfy conditional relevance only. Altogether, the main contributions of this article are as follows:

● We define core c-representations as specific ranking models of consistent belief bases $ \Delta $, and show that they constitute a subclass of c-representations which is non-empty if and only if $ \Delta $ is consistent.

● We generalize the notion of tolerance partitions known from System Z and use them to show that core c-representations are stratified, and thus can be computed layer by layer.

● We prove that consistent belief bases have a unique (pareto-)minimal core c-representation.

● We introduce the inductive inference operator c-core closure which selects the minimal core c-representation of a belief base for drawing inferences.

● We show that c-core closure is based on an impact preserving selection strategy, satisfies conditional syntax splitting, and thus avoids the drowning problem.

The remainder of this article is organized as follows. In Section 2, we settle logical foundations on propositional and conditional logics in general and on c-representations in particular. In Section 3, we define core c-representations and present a constructive method for computing them that is based on a generalization of tolerance partitions of conditional belief bases. In Section 4, we show the existence of a unique minimal core c-representation. Based on this minimal core c-representation, we define the inductive inference operator c-core closure and analyze its properties in Section 5. Eventually, we discuss related work in Section 6 and conclude with an outlook in Section 7.

In this section, we settle the logical preliminaries of this work. We recall basics on propositional logics, introduce conditionals as representations of defeasible beliefs, interpret conditionals via ranking functions, and discuss with System P, System Z, lexicographic entailment, and c-representations, some well-established semantics of conditional belief bases.

2.1.   Propositional logics

As a background language for conditionals, we consider a propositional language $ {\cal{L}}(\Sigma) $ which is defined over a finite signature $ \Sigma $, and which provides the common connectives $ \land $ (conjunction), $ \lor $ (disjunction), and $ \neg $ (negation) to build formulas. For formulas $ A,B \in {\cal{L}}(\Sigma) $, we abbreviate conjunctions $ A \land B $ with $ AB $, negations $ \neg A $ with $ {\overline A } $, arbitrary tautologies $ A \lor {\overline A } $ with $ \top $, and arbitrary contradictions $ A{\overline A } $ with $ \bot $. Elements of $ \Sigma $ are called atoms, and both atoms and their negations are referred to as literals. Formulas in $ {\cal{L}}(\Sigma) $ are interpreted to $ 1 $ (true) or $ 0 $ (false) as usual. A propositional interpretation $ I $ is a model of a formula $ A $ if $ I(A)=1 $. With $ \models $ we denote the classical entailment relation between formulas, i.e., $ A \models B $ holds if and only if $ B $ is true in every model of $ A $. Two formulas $ A $ and $ B $ are (logically) equivalent, in symbols $ A \equiv B $, if both $ A \models B $ and $ B \models A $. The deductive closure of a formula $ A $ is defined by $ {\mathrm{Cn}}(A) = \{ B \in {\cal{L}}(\Sigma) \mid A \models B \} $. A possible world is a propositional interpretation over $ \Sigma $ represented as a complete conjunction of those literals which are true in the respective interpretation. The set of all possible worlds is denoted by $ \Omega(\Sigma) $. For example, if $ \Sigma = \{a,b\} $, then $ \Omega(\Sigma) = \{ ab, a{\overline b }, {\overline a b}, {\overline a \overline b }\} $. For subsignatures $ \Sigma' \subset \Sigma $ we denote with $ \Omega(\Sigma') $ the set of the partial possible worlds which make use of the atoms in $ \Sigma' $ only. Partial possible worlds particularly play a role in marginalization. The marginalization of a possible world $ \omega \in \Omega(\Sigma) $ on $ \Sigma' $ is the restriction of $ \omega $ on the atoms in $ \Sigma' $ and formally defined by $ \omega|_{\Sigma'} = \bigwedge_{a \in \Sigma' \colon \omega \models a} a \land \bigwedge_{a \in \Sigma' \colon \omega \models {\overline a }} {\overline a } $. Consequently, if $ \{\Sigma_1, \ldots, \Sigma_m\} $ is a partition of $ \Sigma $, then $ \omega = \bigwedge_{i \in [m]} \omega|_{\Sigma_i} $ (possibly up to a reordering of the conjuncts) where $ [m] $ abbreviates $ \{1, \ldots, m\} $.

2.2.   Conditionals and ranking functions

A conditional $ (B|A) $, where $ A $ and $ B $ are formulas from $ {\cal{L}}(\Sigma) $, is a formal representation of the defeasible belief 'if $ A $ holds, then usually $ B $ follows' where the formal meaning of 'usually' has to be clarified. A finite set of conditionals $ \Delta $ is called a belief base. In this article, we presuppose that belief bases do not contain duplicates of semantically equivalent conditionals where two conditionals $ (B|A) $ and $ (D|C) $ are semantically equivalent, in symbols $ (B|A) \equiv (D|C) $, if both $ A \equiv C $ and $ AB \equiv CD $^[11]. This ensures that the influence of a conditional on the models of the belief base cannot be amplified through duplication. With $ \Sigma(\Delta) $ we denote the signature of $ \Delta $, i.e., the set of atoms mentioned in $ \Delta $. Throughout the paper, we allocate $ n = |\Delta| $ and enumerate the conditionals in $ \Delta $ so that we can refer to the conditionals by their indices. Moreover, we identify $ \Delta = \{ \delta_1, \ldots, \delta_n \} $ with $ \delta_i = (B_i|A_i) $ for $ i \in [n] $.

The semantics of conditionals is given by ranking functions over possible worlds. A ranking function $ \kappa \colon \Omega(\Sigma) \to {\mathbb{N}}_0 \cup \{\infty\} $ is a mapping which assigns an (im)plausibility rank to each possible world in $ \Omega(\Sigma) $ while satisfying the normalization condition $ \kappa^{-1}(0) \neq \emptyset $^[1]. The higher the rank $ \kappa(\omega) $, the less plausible the possible world $ \omega $ is, so that $ \kappa^{-1}(0) $ is the set of the most plausible possible worlds. Accordingly,

is the belief set of a reasoner with belief state $ \kappa $, i.e., the consequences of the most plausible beliefs in $ \kappa $. A ranking function $ \kappa $ accepts a conditional $ (B|A) $ if $ \kappa(AB) \lt \kappa(A{\overline B }) $ where $ \kappa(A) = \min_{\omega \in \Omega(\Sigma) \colon \omega \models A} \kappa(\omega) $ for $ A \in {\cal{L}}(\Sigma) $. Hereby, the convention $ \min \emptyset = \infty $ applies. Further, $ \kappa $ is a ranking model of a belief base $ \Delta $ if $ \kappa $ accepts all conditionals in $ \Delta $. If $ \Delta $ has a ranking model, then $ \Delta $ is called consistent. Consistent belief bases have infinitely many ranking models. For instance, the plausibility ranks $ \kappa(\omega) $ of a ranking model $ \kappa $ can be multiplied by any fixed constant from $ {\mathbb{N}}_{>1} $ to obtain another model. Beyond that, ranking models can also differ more significantly, e.g., in terms of inference properties. To specify specific ranking models, we introduce further notations. We denote the sets of possible worlds which verify/falsify a conditional $ \delta = (B|A) $ with

and the sets of conditionals from $ \Delta $ which are verified/falsified in $ \omega \in \Omega(\Sigma) $ with

2.3.   System Z

For consistent belief bases $ \Delta $, a well-known ranking model is specified by System Z^[10] which classifies the conditionals in $ \Delta $ w.r.t. their 'normality' by making use of a specific tolerance partition of $ \Delta $. A conditional $ (B|A) $ is tolerated by $ \Delta $ if there is a possible world $ \omega $ such that both $ \omega \in {\mathrm{ver}}(\delta) $ ($ \omega $ verifies $ \delta $), and $ {\mathrm{fal}}_\Delta(\omega) = \emptyset $ ($ \omega $ does not falsify any conditional from $ \Delta $). Based on that, an ordered partition $ (\Delta_1, \ldots, \Delta_m) $ of $ \Delta $ is a tolerance partition of $ \Delta $ if, for $ i \in [m] $, every conditional in $ \Delta_i $ is tolerated by $ \bigcup_{j=i}^m \Delta_j $. The Z-partition $ Z(\Delta) $ is the unique tolerance partition of $ \Delta $ where the partitioning sets are chosen inclusion maximally, beginning with $ \Delta_1 $. The Z-partition of $ \Delta $ exists if and only if $ \Delta $ is consistent. Further, the Z-rank $ Z_\Delta(\delta) $ of a conditional $ \delta \in \Delta $ is the index $ i $ of the subbase $ \Delta_i \in Z(\Delta) $ with $ \delta \in \Delta_i $. The higher the System Z rank of a conditional $ \delta $, the more specific $ \delta $ is^[12]. The System Z ranking model of $ \Delta $ is given then by

The ranking model $ \kappa^Z_\Delta $ exists if and only if $ \Delta $ is consistent^[10].

Example 1. We consider the well-known Tweety example $ \Delta_{\mathrm{bfp}} = \{\delta_1, \delta_2, \delta_3\} $ with

stating that penguins (like Tweety) are usually birds ($ \delta_1 $), birds are usually able to fly ($ \delta_2 $), and penguins are usually not able to fly ($ \delta_3 $). The Z-partition of $ \Delta_{\mathrm{bfp}} $ is $ Z(\Delta_{\mathrm{bfp}}) = (\Delta_1, \Delta_2) $ with $ \Delta_1 = \{\delta_2\} $, and $ \Delta_2 = \{\delta_1, \delta_3\} $. The resulting System Z ranking model is

For instance, it states that, based on $ \Delta_{\mathrm{bfp}} $, non-flying penguin-birds are less plausible than birds that are able to fly:

For more technical details on this example, please see the extended version in Example 12.

Note that we start the indexing of the subbases in $ Z(\Delta) $ from $ i=1 $ because it makes the upcoming comparison with our new approach easier. In literature, you will often find $ i=0 $ as the lowest index which would imply a shift of the Z-ranks $ Z_\Delta(\delta) $ by $ -1 $. This shift is then compensated in the definition of the System Z ranking model by adding the term $ +1 $ to $ \kappa^Z_\Delta $ in case of $ {\mathrm{fal}}_\Delta(\omega) \neq \emptyset $ (cf. (1)). System Z coincides with rational closure^[13,14].

2.4.   c-Representations

c-Representations^[2] constitute another sophisticated class of ranking models. Let $ \Delta $ be a consistent belief base with $ |\Delta| = n $, and let $ \vec{\eta} = (\eta_1, \ldots, \eta_n) \in {\mathbb{N}}_0^n $. If the mapping

is a ranking model of $ \Delta $, then we call $ \kappa_\Delta^{\vec{\eta}} $ a c-representation of $ \Delta $. Note that c-representations are defined in a more general fashion in Kern-Isberner^[2] but (2) is a very common derivative. In particular, a belief base $ \Delta $ is consistent if and only if it has a c-representation of the form (2). We call the vector $ \vec{\eta} $ impact vector of $ \kappa_\Delta^{\vec{\eta}} $ and its entries impact factors. The impact factors can be understood as penalty points for falsifying the conditionals in $ \Delta $. With the positive ($ V_i $) and negative ($ F_i $) constraint inducing sets

the acceptance condition $ \kappa_\Delta^{\vec{\eta}}(A_i B_i) \lt \kappa_\Delta^{\vec{\eta}}(A_i {\overline{{{B}_{i}}}}) $ of the $ i $-th conditional in $ \Delta $ can be written as (cf.^[15]) ($ \kappa_\Delta^{\vec{\eta}}(A_i B_i) \lt \kappa_\Delta^{\vec{\eta}}(A_i {\overline{{{B}_{i}}}}) $ is equivalent to $ \min_{\omega \in {\mathrm{ver}}(\delta_i)} \sum\nolimits_{\delta_j \in {\mathrm{fal}}_\Delta(\omega)} \eta_j \lt \min_{\omega \in {\mathrm{fal}}(\delta_i)} \sum\nolimits_{\delta_j \in {\mathrm{fal}}_\Delta(\omega)} \eta_j $ by definition which can be rewritten to $ \min_{\omega \in {\mathrm{ver}}(\delta_i)} \sum\nolimits_{\delta_j \in {\mathrm{fal}}_{\Delta\setminus{\delta_i}}(\omega)} \eta_j \lt \eta_i + $ $ \min_{\omega \in {\mathrm{fal}}(\delta_i)} \sum\nolimits_{\delta_j \in {\mathrm{fal}}_{\Delta \setminus {\delta_i}}(\omega)} \eta_j $ from which (3) follows.

The set $ {\mathrm{CSP}}(\Delta) = \{C_1,\ldots,C_n\} $ constitutes a constraint satisfaction problem which has to be solved in order to calculate a c-representation of $ \Delta $. More precisely, every non-negative integer solution of $ {\mathrm{CSP}}(\Delta) $ induces a c-representation of $ \Delta $, and every c-representation of $ \Delta $ can be computed this way.

Example 2. As a running example, we consider the belief base $ \Delta_{\mathrm{ex}} = \{ \delta_1, \ldots, \delta_5 \} $ with

The sets $ {\mathrm{ver}}_{\Delta_{\mathrm{ex}}}(\omega) $ and $ {\mathrm{fal}}_{\Delta_{\mathrm{ex}}}(\omega) $ are shown in Table 1 and the resulting constraint inducing sets $ V_i $ and $ F_i $ in Table 2. The constraint satisfaction problem $ {\mathrm{CSP}}(\Delta_{\mathrm{ex}}) = \{ C_1, \ldots, C_5 \} $ is given by

$ {\mathrm{CSP}}(\Delta_{\mathrm{ex}}) $ has three pareto-minimal solutions: $ (1,1,1,3,1) $, $ (2,0,1,3,1) $, and $ (0,2,1,3,1) $, where pareto-minimal means that there is no further non-negative integer solution of $ {\mathrm{CSP}}(\Delta_{\mathrm{ex}}) $ with any entry less than the respective entries of the solutions above.

For comparing the solutions $ \vec{\eta} $ of $ {\mathrm{CSP}}(\Delta) $ w.r.t. their induced c-representation $ \kappa^{\vec{\eta}}_\Delta $, the relation $ \vec{\eta} \preccurlyeq_O \vec{\eta} {\, '} $ if and only if $ \kappa^{\vec{\eta}}_\Delta(\omega) \leq \kappa^{\vec{\eta} {\, '}}_\Delta(\omega) $ for all $ \omega \in \Omega(\Sigma) $ leads to a refined notion of minimality: $ \vec{\eta} $ is minimal w.r.t. $ \preccurlyeq_O $, called ind-minimal, if and only if there is no solution $ \vec{\eta} {\, '} $ of $ {\mathrm{CSP}}(\Delta) $ such that $ \vec{\eta} {\, '} \preccurlyeq_O \vec{\eta} $ and $ \vec{\eta} \not\preccurlyeq_O \vec{\eta} {\, '} $^[3]. For $ \Delta_{\mathrm{ex}} $ from Example 2, all three pareto-minimal solutions of $ {\mathrm{CSP}}(\Delta_{\mathrm{ex}}) $ induce the same c-representation and are thus ind-minimal. On the other hand, there are belief bases $ \Delta $ where only some of the pareto-minimal solutions of $ {\mathrm{CSP}}(\Delta) $ are also ind-minimal and the ind-minimal solutions induce different, inferentially non-equivalent ranking models of $ \Delta $.

2.5.   Constraint reductions for c-representations

When computing a c-representation of a consistent belief base $ \Delta $, it is useful to simplify $ {\mathrm{CSP}}(\Delta) $ before solving it. For instance, the constraint $ C_1 $ in Example 2 can be reduced to $ \eta_1 \gt \eta_3 - \eta_2 $. In studies by Beierie et al.^[15,16], Wilhelm et al.^[17], transformation rules are suggested which simplify $ {\mathrm{CSP}}(\Delta) $ by manipulating the constraint inducing sets $ V_i $ and $ F_i $, $ i \in [n] $, without changing the solution set of $ {\mathrm{CSP}}(\Delta) $. These rules are shown in Fig. 1, and read as follows:

Figure 1. 

Transformation rules for simplifying the constraint satisfaction problem $ {\mathrm{CSP}}(\Delta) $. A pair ${\langle { {\cal{V}}},\; { {\cal{F}}} \rangle_{{i}}} $ represents the sets of constraint variables in the minimum expressions associated to the verification and the falsification, respectively, of the $ i $-th conditional $ \delta_i \in \Delta $ in the constraint $ C_i \in {\mathrm{CSP}}(\Delta) $ modeling the acceptance condition of $ \delta_i $.

$ {\bf{R1}} $ If $ S,S' \in V_i $ with $ S \subsetneq S' $, then $ V_i \leftarrow V_i \setminus \{S'\} $.

$ {\bf{R2}} $ If $ S,S' \in F_i $ with $ S \subsetneq S' $, then $ F_i \leftarrow F_i \setminus \{S'\} $.

$ {\bf{R3}} $ If $ V_i \neq \{\emptyset\} $, $ F_i \neq \{\emptyset\} $, and $ \delta_j \in S $ for all $ S \in V_i \cup F_i $, then $ V_i \leftarrow \{ S \setminus \{\delta_j\} \mid S \in V_i\} $ and $ F_i \leftarrow \{ S \setminus \{\delta_j\} \mid S \in F_i\} $.

$ {\bf{R4}} $ If $ V_i = F_i $, then $ V_i \leftarrow \{\emptyset\} $ and $ F_i \leftarrow \{\emptyset\} $.

$ {\bf{R5}} $ If there are $ {\cal{D}} \subseteq 2^\Delta $ and $ T,T' \subseteq \Delta $ such that $ V_i = \{ S {\dot \cup} T \mid S \in {\cal{D}} \} $ and $ F_i = \{ S {\dot \cup} T' \mid S \in {\cal{D}} \} $, then $ V_i \leftarrow \{T\} $ and $ F_i \leftarrow \{T'\} $.

$ {\bf{R6}} $ If $ F_i = F_j = \{\emptyset\} $ for $ i \neq j $ and there is $ {\cal{D}} \subseteq 2^\Delta $ such that $ V_i = {\cal{D}} {\dot \cup} \{\{\delta_j\}\} $ and $ V_j = {\cal{D}} {\dot \cup} \{\{\delta_i\}\} $, then $ V_i \leftarrow {\cal{D}} $ and $ V_j \leftarrow {\cal{D}} $.

The transformation rules R1–R6 rely on basic laws of minimization and arithmetics. Note that some of them take both $ V_i $ and $ F_i $ into account. With $ \hat{V}_i $ and $ \hat{F}_i $, $ i \in [n] $, we denote the reduced constraint inducing sets, i.e., $ V_i $ and $ F_i $ after applying the transformation rules R1–R6 exhaustively. We will see in Proposition 1 that the reduced constraint inducing sets are independent of the order in which the rules are applied (cf.^[17]). Applying the transformation rules removes spurious dependencies between the conditionals in $ \Delta $ from the constraint satisfaction problem $ {\mathrm{CSP}}(\Delta) $. With $ {\mathrm{CSP}}^\wedge(\Delta) = \{ \hat{C}_1, \ldots, \hat{C}_n \} $ we denote the reduced constraint satisfaction problem where

Thus, $ \hat{C}_i $ is $ C_i $ in which $ V_i $ and $ F_i $ are replaced by $ \hat{V}_i $ and $ \hat{F}_i $.

Proposition 1. Let $ \Delta $ be a consistent belief base. Then $ {\mathrm{CSP}}^\wedge(\Delta) $ is uniquely defined and independent of the order in which the transformation rules R1-R6 are applied. Furthermore, the set of the non-negative integer solutions of $ {\mathrm{CSP}}(\Delta) $ equals the set of the non-negative integer solutions of $ {\mathrm{CSP}}^\wedge(\Delta) $.

Proof. First, we prove, rule by rule, that applying any transformation rule from R1–R6 preserves the solutions of $ {\mathrm{CSP}}(\Delta) $.

$ {\underline{{\rm{R1}}:}} $ Let $ S,S'\in V_i $ with $ S\subsetneq S' $, and let $ V_i'=V_i\setminus\{S'\} $. Then,

and, hence,

$ {\underline{{\rm{R2}}:}} $ The proof is analogous to the proof w.r.t. R1.

$ {\underline{{\rm{R3}}:}} $ Suppose $ \delta_j\in S $ for $ S\in V_i\cup F_i $, and let $ V_i'=\{S\setminus\{\delta_j\}\mid S\in V_i\} $ and $ F_i'=\{S\setminus\{\delta_j\}\mid S\in F_i\} $. Then,

$ {\underline{{\rm{R4}}:}} $ Let $ V_i=F_i $. Then,

$ {\underline{{\rm{R5}}:}} $ Let $ {\cal{D}}\subseteq 2^\Delta $ and $ T,T'\subseteq \Delta $ such that $ V_i=\{S{\dot \cup} T\mid S\in{\cal{D}} \} $ and $ F_i=\{S{\dot \cup} T'\mid S\in{\cal{D}} \} $. Then,

$ {\underline{{\rm{R6}}:}} $ Let $ F_i=F_j=\emptyset $ for $ i\neq j $, and let $ {\cal{D}}\subseteq 2^\Delta $ such that $ V_i={\cal{D}}{\dot \cup} \{\{\delta_j\}\} $ and $ V_j={\cal{D}}{\dot \cup} \{\{\delta_i\}\} $.

Then Eq. (3) becomes

Assume $ \eta_j=\min {\cal{H}}_i $ and $ \eta_i=\min {\cal{H}}_j $. Then (3) reduces to $ \eta_i \gt \eta_j $ and $ \eta_j>\eta_i $ which is a contradiction. Now, assume $ \eta_j =\min {\cal{H}}_i $ and $ H=\min {\cal{H}}_j $ for some $ H\in \{\sum\nolimits_{\delta_k\in S} \eta_k\mid S\in {\cal{D}}\} $ with $ H<\eta_i $. Then, (3) becomes $ \eta_j>H $ which contradicts the assumption that $ \eta_j $ minimizes $ {\cal{H}}_i $ (note that $ H\in{\cal{H}}_i $). Putting both cases together, we have that $ \eta_j $ cannot be minimal in $ {\cal{H}}_i $. Analogously, one can show that $ \eta_i $ is not minimal in $ {\cal{H}}_j $, and (3) simplifies to

which proves the statement.

For showing that $ {\mathrm{CSP}}^\wedge(\Delta) $ is uniquely defined, first observe that applying the transformation rules R1–R6 exhaustively in whatever order terminates because every rule strictly decreases the size of $ \langle {\cal{V}}, {\cal{F}}\rangle $. Now, we prove that $ {\mathrm{CSP}}^\wedge(\Delta) $ is independent of the order in which the rules R1–R6 are applied. The basic idea of our proof is to show that for each pair of rules (Ri, Rj) applying Ri before Rj leads to the same result as applying Rj before Ri. With $ \phi_j(V_i) $ and $ \phi_j(F_i) $, respectively, we denote the result of applying the transformation rule Rj to $ V_i $ ($ F_i $) once. For convenience, if the precondition of Rj is not satisfied in a concrete situation, then we assume that $ \phi_j $ is the identity mapping.

There are some pairs of transformation rules which trivially commute, for instance because they do not interfere. This holds, among others, for all pairs (Ri, Ri), the pair (R1, R2), or if transformation rules are applied to constraint inducing sets of different conditionals (as long as R6 is not involved). We omit these trivial cases and analyze the more interesting cases in detail.

$ {\underline{({\rm{R1}}, {\rm{R3}}):}} $ Let $ S,S'\in V_i $ with $ S\subsetneq S' $, and let $ \delta_j\in T $ for all $ T\in V_i\cup F_i $. Then,

because $ \delta_j\in T $ for all $ T \in \phi_1(V_i) $, which equals

The latter holds, because $ S\subsetneq S' $ implies $ S\setminus\{\delta_j\}\subsetneq S'\setminus\{\delta_j\} $. Further, because R1 does not affect $ F_i $, one obtains

$ {\underline{({\rm{R1}}, {\rm{R4}}):}} $ Let $ S,S'\in V_i $ with $ S\subsetneq S' $, and let $ V_i=F_i $. Then, both

Applying R1 to $ V_i $ first leads to $ \phi_1(V_i)\neq F_i $ and R4 is not applicable. But because $ S,S'\in V_i $ with $ S\subsetneq S' $ and $ V_i=F_i $ by assumption, R2 is applicable to $ F_i $ and yields $ \phi_2(F_i)=\phi_1(V_i) $. Thereafter, R4 can be applied and one obtains that $ V_i $ and $ F_i $ are reduced to $ \emptyset $ in both cases.

$ {\underline{({\rm{R1}}, {\rm{R5}}):}} $ Let $ S,S'\in V_i $ with $ S\subsetneq S' $, $ {\cal{D}}\subseteq 2^\Delta $, and $ T,T'\subseteq \Delta $ such that $ V_i=\{R{\dot \cup} T\mid R\in {\cal{D}}\} $ and $ F_i=\{R{\dot \cup} T'\mid R\in {\cal{D}}\} $. Then, $ S=R{\dot \cup} T $ and $ S'=R'{\dot \cup} T $ for some $ R,R'\in {\cal{D}} $. As a consequence, $ R\subsetneq R' $ and the sets $ \hat{S}=R{\dot \cup} T' $ as well as $ \hat{S'}=R'{\dot \cup} T' $ are in $ F_i $ and satisfy $ \hat{S}\subsetneq\hat{S}' $. Applying R1 to $ V_i $ leads to $ \phi_1(V_i) = \{R{\dot \cup} T\mid R\in{\cal{D}}\setminus\{R'\}\}. $ Because R5 is not applicable now, we apply R2 to $ F_i $ as an auxiliary reduction first and obtain $ \phi_2(F_i)=\{R{\dot \cup} T'\mid R\in{\cal{D}}\setminus\{R'\}\}. $ After that, R5 is applicable and we have

If one applies R5 first, one directly obtains

$ {\underline{({\rm{R1}}, {\rm{R6}}):}} $ Let $ S,S'\in V_i $ with $ S\subsetneq S' $, and let $ {\cal{D}}\subseteq 2^\Delta $ such that $ V_i={\cal{D}}{\dot \cup}\{\{\delta_j\}\} $ and $ V_j={\cal{D}}{\dot \cup}\{\{\delta_i\}\} $. First, we note that there is no $ T\in{\cal{D}} $ with $ \delta_i\in T $ because $ {\cal{D}}\subseteq V_i $ or with $ \delta_j\in T $ because $ {\cal{D}}\subseteq V_j $. If $ S'=\{\delta_j\} $, then $ S=\emptyset $ and applying R1 leads to $ \phi_1(V_i)=\phi_1({\cal{D}}) $. Because $ S\in {\cal{D}} $, we also have $ S\in V_j $. Further, we note that $ \{\delta_i\}\in V_j $ is a superset of $ S=\emptyset $. Consequently, R1 removes $ \{\delta_i\} $ from $ V_j $, too. That is, $ \phi_1(V_j)=\phi_1({\cal{D}}) $ as well. Applying R6 afterwards does not make any changes, i.e.,

If $ S'\neq \{\delta_j\} $ but applying R1 reduces $ {\cal{D}} $, the same reduction on $ {\cal{D}} $ can be performed by R2 on $ F_i $ to make R6 applicable again. On the other hand, we also have

$ {\underline{({\rm{R2}}, {\rm{R3}}), ({\rm{R2}}, {\rm{R4}}), ({\rm{R2}}, {\rm{R5}}):}} $ These cases can be proven analogously to the cases (R1, R3), (R1, R4), and (R1, R5).

$ {\underline{({\rm{R2}}, {\rm{R6}}), ({\rm{R3}}, {\rm{R6}}):}} $ Because R6 requires $ F_i=F_j=\emptyset $, R2 and R6 (resp. R3 and R6) cannot be applicable at the same time to $ F_i $ and $ F_j $, respectively.

$ {\underline{({\rm{R3}}, {\rm{R4}}):}} $ Let $ \delta_j\in S $ for all $ S\in V_i\cup F_i $, and let $ V_i=F_i $. Applying R3 yields

Because $ V_i=F_i $, we have $ \phi_3(V_i)=\phi_3(F_i) $, and R4 is still applicable. Hence,

Applying R4 first directly leads to $ \phi_4(V_i)=\emptyset=\phi_4(F_i) $ directly.

$ {\underline{({\rm{R3}}, {\rm{R5}}):}} $ Let $ \delta_j\in S $ for $ S\in V_i\cup F_i $, $ {\cal{D}}\subseteq 2^\Delta $, and $ T,T'\subseteq \Delta $ such that $ V_i=\{R{\dot \cup} T\mid R\in{\cal{D}}\} $ and $ F_i=\{R{\dot \cup} T'\mid R\in{\cal{D}}\} $. Applying R3 yields $ \phi_3(V_i)=\{R{\dot \cup} \hat{T}\mid R\in\hat{{\cal{D}}}\} $ and $ \phi_3(F_i)=\{R{\dot \cup} \hat{T}'\mid R\in\hat{{\cal{D}}}\} $ with $ \hat{{\cal{D}}}\subseteq 2^{\Delta\setminus\{\delta_j\}} $ and $ \hat{T},\hat{T}'\subseteq\Delta\setminus\{\delta_j\} $. Now, R5 is applicable and leads to

Applying R3 and R5 in reversed order leads to the same results:

$ {\underline{({\rm{R4}}, {\rm{R5}}):}} $ Let $ V_i=F_i $, let $ {\cal{D}}\subseteq 2^\Delta $, and let $ T,T'\subseteq \Delta $ such that $ V_i=\{S{\dot \cup} T\mid S\in {\cal{D}}\} $ and $ F_i=\{S{\dot \cup} T'\mid S\in {\cal{D}}\} $. It directly follows that $ T=T' $. Then,

On the other hand,

Thus, because $ \phi_4(\phi_5(V_i))=\phi_4(\phi_5(F_i)), $ we have $ \phi_4(\phi_5(V_i))=\phi_4(\phi_5(F_i))=\emptyset $ again.

$ {\underline{({\rm{R4}}, {\rm{R6}}):}} $ From $ V_i=F_i $ and the precondition $ F_i=F_j=\emptyset $ of R6 it would follow that $ V_i=\emptyset $ holds which contradicts $ \{\delta_j\}\in V_i $. Hence, R4 and R6 cannot be applicable at the same time.

$ {\underline{({\rm{R5}}, {\rm{R6}}):}} $ From $ F_i=F_j=\emptyset $ and the construction of the sets $ V_i $ and $ F_i $ according to the preconditions of R5 it would follow that $ V_i=\emptyset $ holds which contradicts $ \{\delta_j\}\in V_i $. Hence, R5 and R6 cannot be applicable at the same time. □

We give an example of applying the transformation rules R1–R6.

Example 3. We recall $ \Delta_{\mathrm{ex}} $ from Example 2. The reduced constraint inducing sets $ \hat{V}_i $ and $ \hat{F}_i $ are shown in Table 2, and $ {\mathrm{CSP}}^\wedge(\Delta_{\mathrm{ex}}) $ is given by

Note that because a belief base $ \Delta $ is consistent if and only if a c-representation of $ \Delta $ exists, the belief base $ \Delta $ is consistent if and only if $ {\mathrm{CSP}}^\wedge(\Delta) $ has a non-negative integer solution.

2.6.   Inductive inference

Once a ranking model $ \kappa $ of a belief base $ \Delta $ is determined, this model leads to a nonmonotonic inference relation $ |\!\!\!\sim_\kappa $ between formulas, telling which formulas $ B $ a reasoner with belief state $ \kappa $ should infer from $ A $:

Compared with this, inductive inference is the task of drawing inferences right from the belief base $ \Delta $. Inductive inference can be realized by selecting a model $ \kappa $ of $ \Delta $ and then applying $ |\!\!\!\sim_\kappa $.

Definition 1 (Inductive Inference Operator^[18]). An inductive inference operator is a mapping $ {\cal{I}} \colon \Delta \mapsto |\!\!\!\sim ^{\cal{I}}_\Delta $ which assigns to every consistent belief base $ \Delta $ a binary relation $ |\!\!\!\sim ^{\cal{I}}_\Delta $ on $ {\cal{L}}(\Sigma) $ such that the properties direct inference (DI) ^[19] and trivial vacuity (TV) ^[18] are satisfied:

$ {\bf{(DI)}} $ $ (B|A) \in \Delta $ implies $ A |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $.

$ {\bf{(TV)}} $ If $ \Delta = \emptyset $, then $ A |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $ only if $ A \models \!\! B $.

This leads to the definition $ \Delta |\!\!\!\sim ^{\cal{I}} (B|A) $ if and only if $ A |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $. We give examples of important inductive inference operators (cf.^[18]): (we write $ |\!\!\!\sim ^X_\Delta $ instead of $ |\!\!\!\sim ^{{\cal{I}}^X}_\Delta $ to avoid double superscripts).

● p-Entailment $ {\cal{I}}^P \colon \Delta \mapsto |\!\!\!\sim ^P_\Delta $ is defined by $ A |\!\!\!\sim ^P_\Delta \!\! B $ if $ A |\!\!\!\sim _\kappa \!\! B $ for all ranking models $ \kappa $ of $ \Delta $^[8,9].

● The System Z inference operator $ {\cal{I}}^Z \colon \Delta \mapsto |\!\!\!\sim ^Z_\Delta $ is defined by $ A |\!\!\!\sim ^Z_\Delta \!\! B $ if $ A |\!\!\!\sim _{\kappa^Z_\Delta} \!\! B $ where $ \kappa^Z_\Delta $ is the System Z ranking model of $ \Delta $^[10].

● The skeptical c-inference operator $ {\cal{I}}^c \colon \Delta \mapsto |\!\!\!\sim ^c_\Delta $ is defined by $ A |\!\!\!\sim ^c_\Delta \!\! B $ if $ A |\!\!\!\sim _{\kappa^{\vec{\eta}}_\Delta} \!\! B $ for all c-representations $ \kappa^{\vec{\eta}}_\Delta $ of $ \Delta $^[6,7].

It is a well-known result that p-entailment is characterized by an axiomatic collection of inference rules called System P^[20] which is why we call $ {\cal{I}}^P $ the System P inference operator here.

Definition 2 (System P^[20]).Let $ \Delta $ be a consistent belief base, and let $ A, B, C \in {\cal{L}}(\Sigma) $ be formulas. Then System P is the collection of the inference rules reflexivity (REF), Cut (CUT), cautious monotony (CM), right weakening (RW), or (OR), and left logical equivalence (LLE):

$ {\bf{(REF) }}$ $ A|\!\!\!\sim ^{\cal{I}}_\Delta A $,

$ {\bf{(CUT)}} $ $ AB|\!\!\!\sim ^{\cal{I}}_\Delta C $ and $ A|\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $ implies $ A|\!\!\!\sim ^{\cal{I}}_\Delta C $,

$ {\bf{(CM)}} $ $ A|\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $ and $ A|\!\!\!\sim ^{\cal{I}}_\Delta C $ implies $ AB |\!\!\!\sim ^{\cal{I}}_\Delta C $,

$ {\bf{(RW)}} $ $ A|\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $ and $ B\models C $ implies $ A|\!\!\!\sim ^{\cal{I}}_\Delta C $,

$ {\bf{(OR)}} $ $ A |\!\!\!\sim ^{\cal{I}}_\Delta C $ and $ B|\!\!\!\sim ^{\cal{I}}_\Delta C $ implies $ A\lor B |\!\!\!\sim ^{\cal{I}}_\Delta C $,

$ {\bf{(LLE)}} $ $ A\equiv B $ and $ B|\!\!\!\sim ^{\cal{I}}_\Delta C $ implies $ A|\!\!\!\sim ^{\cal{I}}_\Delta C $.

Further, System P inference satisfies semi-monotony (SM)^[21,22], and classic preservation (CP)^[23], among others:

$ {\bf{(SM)}} $ $ A |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $ and $ \Delta \subseteq \Delta' $ implies $ A |\!\!\!\sim ^{\cal{I}}_{\Delta'} \!\! B $,

$ {\bf{(CP)}} $ $ A |\!\!\!\sim ^{\cal{I}}_\Delta \bot $ if and only if $ A |\!\!\!\sim ^P_\Delta \bot $.

System P is considered to be the "conservative core" of nonmonotonic reasoning systems^[20]. System Z extends System P, most notably, by satisfying rational monotony (RM)^[14,24]:

$ {\bf{(RM)}} $ $ A |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $ and implies $ AC |\!\!\!\sim ^{\cal{I}}_{\Delta} \!\! B $.

Both System P and System Z do not satisfy syntax splitting^[18,25], though, and suffer from the drowning problem^[10,26]. Syntax splitting (SynSplit) requires that inferences depend on relevant parts of the belief base only, known as the property relevance (Rel), and that strengthening antecedents by irrelevant information has no influence on the inferences, called independence (Ind).

Definition 3 (Syntax Splitting^[18]). Let $ \Delta $ be a consistent belief base, let $ \{\Sigma_1,\Sigma_2\} $ be a partition of $ \Sigma $, and let $ \{\Delta_1,\Delta_2\} $ be a partition of $ \Delta $ such that, for $ i=1,2 $, the subbase $ \Delta_i $ makes use of atoms from $ \Sigma_i $ only, i.e., $ \Sigma(\Delta_i) \subseteq \Sigma_i $. Then,

$ {\bf{(Rel) }}$ For $ i \in \{1,2\} $, $ A, B \in {\cal{L}}(\Sigma_i) $ implies $ A |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $ iff $ A |\!\!\!\sim ^{\cal{I}}_{\Delta_i} \!\! B $.

$ {\bf{(Ind)}} $ For $ i,j \in \{1,2\} $ with $ i \neq j $, $ A, B \in {\cal{L}}(\Sigma_i) $ and $ C \in {\cal{L}}(\Sigma_j) $ implies $ A |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $ iff $ AC |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $.

$ {\bf{(SynSplit)}} $ = (Rel) + (Ind).

The drowning problem describes the circumstance when exceptional subclasses do not inherit properties from their superclass although these properties are unrelated to the reason for the exceptionality. For instance, if the belief base $ \Delta_{\mathrm{bfp}} $ in Example 1 would mention the additional conditional $ (e|b) $ stating that birds usually have beaks, then with System P and System Z it would not be possible to infer from $ \Delta_{\mathrm{bfp}} $ that penguins usually have beaks, $ (e|p) $, because penguins constitute an exceptional subclass of birds (cf. Example 12). A formalization of the drowning problem is given in Heyninck et al.^[27] based on conditional syntax splitting. According to that, an inductive inference operator suffers from the drowning problem if the operator violates a conditional version (CInd) of the independence property. Its definition is based on safe splittings.

Definition 4 (Safe Splitting^[27]). Let $ \Delta $ be a consistent belief base, let $ \Delta_1, \Delta_2 \subseteq \Delta $ be subbases of $ \Delta $ with $ \Delta_1 \cup \Delta_2 = \Delta $, and let $ \Sigma_3 \subseteq \Sigma $. Then, $ \{\Delta_1,\Delta_2\} $ is a safe splitting of $ \Delta $ w.r.t. $ \Sigma_3 $ if and only if there are $ \Sigma_1, \Sigma_2 \subseteq \Sigma $ such that

● $ \Sigma_1, \Sigma_2, \Sigma_3 $ are pairwise disjoint and cover $ \Sigma $, i.e., $ \Sigma = \Sigma_1 \cup \Sigma_2 \cup \Sigma_3 $,

● for $ i \in \{1,2\} $ it holds that $ \Sigma(\Delta_i) \subseteq \Sigma_i \cup \Sigma_3 $,

● (Safeness) for $ i,j \in \{1,2\} $ with $ i \neq j $, for all $ \omega_i \in \Omega(\Sigma_i) $ and $ \omega_3 \in \Omega(\Sigma_3) $, there is $ \omega_j \in \Omega(\Sigma_j) $ such that

We denote such a safe splitting of $ \Delta $ by $ \Delta_1 \bigcup_{\Sigma_1,\Sigma_2}^s \Delta_2 \mid \Sigma_3 $.

The safeness property (6) guarantees that partial possible worlds which are defined over the atoms from one subbase $ \Delta_i $ of the splitting of $ \Delta $ can be extended to (complete) possible worlds over $ \Sigma $ in such a way that no conditionals from the other subbase $ \Delta_j $, $ j\neq i $, are falsified.

Definition 5 (Conditional Syntax Splitting^[27]).An inductive inference operator $ {\cal{I}} \colon \Delta \mapsto |\!\!\!\sim ^{\cal{I}}_\Delta $ satisfies conditional relevance, conditional independence, and conditional syntax splitting, respectively, if for every safe splitting $ \Delta_1 \bigcup_{\Sigma_1,\Sigma_2}^s \Delta_2 \mid \Sigma_3 $ of $ \Delta $, for $ i,j \in \{1,2\} $ with $ i \neq j $ it holds that

$ {\bf{(CRel)}} $ $ A, B \in {\cal{L}}(\Sigma_i) $, $ \omega \in \Omega(\Sigma_3) $ implies ($ A\omega |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $ iff $ A\omega |\!\!\!\sim ^{\cal{I}}_{\Delta_i} \!\! B $),

$ {\bf{(CInd) }}$ $ A, B \in {\cal{L}}(\Sigma_i) $, $ C \in {\cal{L}}(\Sigma_j) $, $ \omega \in \Omega(\Sigma_3) $ with implies ($ A\omega |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $ iff $ AC\omega |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $).

$ {\bf{(CSynSplit)}} $ = (CRel) + (CInd).

In contrast to System P and System Z, skeptical c-inference does not suffer from the drowning problem but satisfies syntax splitting^[18], and also conditional syntax splitting^[28]. Hence, c-representations constitute a powerful basis for defining inductive inference operators. However, skeptical c-inference does not satisfy rational monotony (RM) but only the weaker version weak rational monotony (wRM)^[29,30]:

$ {\bf{(wRM)}} $ $ \top |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $ and implies $ A |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $.

Inference operators which are defined w.r.t. a single c-representation, similar to the System Z inference operator that is defined w.r.t. the unique System Z ranking model, satisfy (RM), instead^[29]. An axiomatic scheme for inductive inference operators selecting a single c-representation per belief base and ensuring satisfaction of conditional syntax splitting is given in the study by Beierle et al.^[28], but without presenting a concrete instance. In this paper, we will develop such an inductive inference operator which selects a unique 'best' model per belief base.

A straightforward strategy for selecting a unique c-representation $ \kappa^{\vec{\eta}}_\Delta $ would be to minimize the impact factors in $ \vec{\eta} $. However, Example 2 demonstrates that this does not lead to unique results in general. The same applies to other notions of minimality for c-representations (cf.^[3]). With core c-representations we establish a subclass of c-representation for which a unique minimal, thus, outstanding c-representation exists that qualifies for the model selection task. In the remainder of this paper, we define (minimal) core c-representations and c-core closure, an inference operator based on the minimal core c-representations, and we investigate their properties.

In this section, we define core c-representations as a subclass of c-representations and discuss their connection to tolerance partitions. Therewith, we intertwine the inference strength of c-representations with the layer-wise structure of System Z. The main features of core c-representations are:

● For every consistent belief base $ \Delta $, each core c-representation of $ \Delta $ is also a c-representation of $ \Delta $, and $ \Delta $ is consistent if and only if a core c-representation of $ \Delta $ exists.

● Core c-representations are easier to compute than general c-representations. While the computation of c-representations requires to solve the constraint satisfaction problem $ {\mathrm{CSP}}(\Delta) $ (cf. (3)) which possibly involves cyclic dependencies among the impact factors, the constraint satisfaction problems of core c-representations are stratified, hence, can be solved successively, allowing for deciding on each impact factor successively.

● Core c-representations provide a unique minimal ranking model while belief bases have several pareto-minimal c-representations in general, depending on the notion of minimality. Therewith, we obtain a natural model selection strategy for inductive reasoning based on minimal core c-representations.

● As being c-representations, core c-representations inherit many beneficial properties from c-representations including the satisfaction of syntax splitting, and the solution of the drowning problem. Moreover, the inductive inference operator based on minimal core c-representations fully complies with conditional syntax splitting.

The definition of core c-representations is based on a simplification of the constraint satisfaction problem $ {\mathrm{CSP}}(\Delta) $.

Definition 6 (Core c-Representation). Let $ \Delta $ be a consistent belief base, let $ n = |\Delta| $, and let $ {\mathrm{CSP}}^+(\Delta) = \{\hat{C}_1^+, \ldots, \hat{C}_n^+ \} $ where

If $ \vec{\eta} \in {\mathbb{N}}_0^n $ is a solution of $ {\mathrm{CSP}}^+(\Delta) $, then we call $ \kappa^{\vec{\eta},{c}}_{\Delta}(\omega) = \sum\nolimits_{\delta_i \in {\mathrm{fal}}_\Delta(\omega)} \eta_i $, $ \omega \in \Omega(\Sigma), $ a core c-representation of $ \Delta $.

The constraint (7) corresponds to (4) without the negative part on the right-hand side. That is, like general c-representations, core c-representations penalize possible worlds for falsifying conditionals but put usually 'higher' constraints on the impact vector $ \vec{\eta} $. We have the following first result.

Proposition 2. Let $ \Delta $ be a consistent belief base, and let $ \kappa^{\vec{\eta},c}_\Delta $ be a core c-representation of $ \Delta $. Then $ \kappa^{\vec{\eta},c}_\Delta $ is also a c-representation of $ \Delta $.

Proof. By definition, $ \vec{\eta} = (\eta_1, \ldots, \eta_n) $ satisfies (7) for $ i \in [n] $. Consequently, for $ s_i \in {\mathbb{N}}_0 $,

holds, too. With $ s_i = \min \{ \sum\nolimits_{\delta_j \in S} \eta_j \mid S \in F_i \} $, it follows that $ \vec{\eta} $ satisfies (3) and, hence, $ \kappa^{\vec{\eta},c}_\Delta $ is a c-representation of $ \Delta $.□

Beyond a numerical simplification of $ \hat{C}_i $, (7) also strengthens the impact of each conditional in $ \Delta $. For instance, in Example 3, $ \hat{C}_1 $ yields $ \eta_1 \gt \eta_3 - \eta_2 $, i.e., $ \eta_1 + \eta_2 \gt \eta_3 $. This means that $ \hat{C}_1 $ actually reflects the joint impact of $ \delta_1 $ and $ \delta_2 $, while $ \hat{C}^+_1 $ postulates $ \eta_1 \gt \eta_3 $. Hence, core c-representations isolate the impact of each conditional better. In particular, each conditional definitely has a significant impact, as the following proposition shows.

Proposition 3. Let $ \Delta $ be a consistent belief base, let $ n = |\Delta| $, and let $ \kappa^{\vec{\eta},c}_\Delta $ be a core c-representation of $ \Delta $. Then $ \vec{\eta} $ is positive, i.e., for $ i \in [n] $, $ \eta_i \geq 1 $ holds.

Proof. Because $ \kappa^{\vec{\eta},c}_\Delta $ is a core c-representation of $ \Delta $, $ \vec{\eta} $ satisfies $ \eta_i \gt \min \{ \sum\nolimits_{\delta_j \in S} \eta_j \mid S \in \hat{V}_i \} $ for $ i \in [n] $. From $ \vec{\eta} \in {\mathbb{N}}^n_0 $ it follows that $ \sum\nolimits_{\delta_j \in S} \eta_j \geq 0 $ for all $ S \in \hat{V}_i $ and $ i \in [n] $ so that $ \min \{ \sum\nolimits_{\delta_j \in S} \eta_j \mid S \in \hat{V}_i\} \geq 0 $ holds. Therewith, we have $ \eta_i \gt 0 $, $ i \in [n] $. □

Because of Proposition 3, core c-representations satisfy the property inductive enforcement (Ind-Enf), while general c-representations violate it (cf.^[31]):

${\bf{(Ind-Enf)}} $ For $ \omega, \omega' \in \Omega(\Sigma) $, $ {\mathrm{fal}}_\Delta(\omega) \subsetneq {\mathrm{fal}}_\Delta(\omega') $ implies $ \kappa(\omega) \lt \kappa(\omega') $.

Note that we use the reduced constraint inducing sets $ \hat{V}_i $ in (7). While the application of the transformation rules R1–R6 does not affect the solution set of $ {\mathrm{CSP}}(\Delta) $, applying the rules R1–R6 makes a difference here, as the transformation rules remove spurious dependencies between $ \eta_i $ and the set $ V_i $ which can no longer be resolved after cropping of the negative part of (4) as the next example illustrates. Apart from that, the application of constraint reductions to $ V_i $, $ i\in[n] $, is not necessary for the definition of core c-representations, i.e., core c-representations could also be defined from (3) which would generally lead to higher impact factors, though.

Example 4. We continue Example 3. The constraint satisfaction problem $ {\mathrm{CSP}}^+(\Delta_{\mathrm{ex}}) $ consists of the constraints

and has the unique component-wise minimal solution $ (2,1,1,3,1) $. Note that if we had not applied the transformation rules R1−R6, the constraint w.r.t. $ \delta_5 $ would be $ \eta_5 \gt \min\{\eta_3\} $ which takes no account of the fact that the positive and the negative part in $ C_5 $ (cf. Example 2) cancel each other out and, actually, $ \eta_5 $ does not depend on $ \eta_3 $.

Core c-representations are closely related to System Z which becomes clear when characterizing tolerance in terms of the constraint inducing sets $ V_i $.

Proposition 4. Let $ \Delta $ be a consistent belief base, and let $ {\cal{T}}(\Delta) = (\Delta_1, \ldots, \Delta_m) $ be an ordered partition of $ \Delta $. Then $ {\cal{T}}(\Delta) $ is a tolerance partition of $ \Delta $ if and only if for all $ k \in [m] $ and all conditionals $ \delta_i \in \Delta_k $ there is a set $ S \in V_i $ with $ S \subseteq \bigcup_{j=1}^{k-1} \Delta_j $. In particular, $ \delta_i $ is tolerated by $ \Delta $ if and only if $ \emptyset \in V_i $.

Proof. Let $ {\cal{T}}(\Delta) = (\Delta_1,\ldots, \Delta_k) $ be a tolerance partition. Then by definition, for $ k \in [m] $ and every conditional $ \delta_i \in \Delta_k $, there is a possible world $ \omega $ which verifies $ \delta_i $ and does not falsify any conditional from $ \bigcup_{j=k}^m \Delta_j $. Thus, $ \omega $ falsifies at most conditionals from $ \bigcup_{j=1}^{k-1} \Delta_j $ which means that there is a corresponding set $ S \in V_i $ with $ S \subseteq \bigcup_{j=1}^{k-1} \Delta_j $.

The other way round, the existence of $ S \in V_i $ with $ S \subseteq \bigcup_{j=1}^{k-1} \Delta_j $ proves the existence of a possible world $ \omega $ which verifies $ \delta_i $ but does not falsify any conditional from $ \bigcup_{j=k}^{m} \Delta_j $. As this holds for all $ k \in [m] $ and $ \delta_i \in \Delta_k $, $ {\cal{T}}(\Delta) $ is a tolerance partition of $ \Delta $.

In the special case where $ \delta_i $ is tolerated by the whole belief set $ \Delta $, the existence of a possible world which verifies $ \delta_i $ and falsifies no conditional from $ \Delta $ is equivalent to the condition $ \emptyset \in V_i $ as we are seeking for a set $ S \subseteq \bigcup_{j=1}^{0} \Delta_j = \emptyset $ in this case which implies $ S = \emptyset $. □

Analog to the constellation in Proposition 4, we can define generalized tolerance partitions by replacing $ V_i $ by $ \hat{V}_i $.

Definition 7 (Generalized Tolerance Partition). Let $ \Delta $ be a consistent belief base. We call an ordered partition $ (\Delta_1, \ldots, \Delta_m) $ of $ \Delta $ a generalized tolerance partition of $ \Delta $ if for all $ k \in [m] $ and all conditionals $ \delta_i \in \Delta_k $ there is $ S \in \hat{V}_i $ with $ S \subseteq \bigcup_{j=1}^{k-1} \Delta_j $. If $ \hat{V}_i = \{\emptyset\} $, then we say that $ \delta_i $ is weakly tolerated by $ \Delta $.

Tolerance partitions constitute a proper subclass of generalized tolerance partitions, as the next proposition shows. As a consequence, generalized tolerance partitions of consistent belief bases always exist.

Proposition 5. Let $ \Delta $ be a consistent belief base. If $ {\cal{T}}(\Delta) $ is a tolerance partition of $ \Delta $, then $ {\cal{T}}(\Delta) $ is a generalized tolerance partition of $ \Delta $. The other way around, there are generalized tolerance partitions which are not tolerance partitions.

Proof. Let $ {\cal{T}}(\Delta) = (\Delta_1, \ldots, \Delta_m) $ be a tolerance partition of $ \Delta $. In order to prove that $ {\cal{T}}(\Delta) $ is also a generalized tolerance partition of $ \Delta $, we have to show that for $ k \in [m] $ and every conditional $ \delta_i \in \Delta_k $ it follows from the existence of $ S \in V_i $ with $ S \subseteq \bigcup_{j=1}^{k-1} \Delta_j $ that there is $ S' \in \hat{V}_i $ with $ S' \subseteq \bigcup_{j=1}^{k-1} \Delta_j $. We do this by reconsidering the effects of applying the transformation rules R1-R6 on $ V_i $.

If R1 removes $ S $ with $ S \subseteq \bigcup_{j=1}^{k-1} \Delta_j $ from $ V_i $, then only because there is a proper subset $ S' $ of $ S $ in $ V_i $. This subset $ S' $ satisfies $ S' \subseteq \bigcup_{j=1}^{k-1} \Delta_j $ as well. The rule R2 does not affect $ V_i $ at all. The rules R3 and R5, at most, replace $ S $ by a subset of $ S $ such that an argumentation analog to R1 applies. R4 possibly removes $ S $ from $ V_i $ but inserts $ \emptyset $ in this case for which $ \emptyset \subseteq \bigcup_{j=1}^{k-1} \Delta_j $ trivially holds. The only critical case is when R6 applies, i.e., there are $ i,l \in [n] $ with $ i \neq l $, $ F_i = F_l = {\emptyset} $, and $ {\cal{D}} \subseteq 2^\Delta $ with $ V_i = {\cal{D}} {\dot \cup} \{\{\delta_l\}\} $ and $ V_l = {\cal{D}} {\dot \cup} \{\{\delta_i\}\} $ as well as $ S = \{\delta_l\} $. In this case, $ S $ would be removed from $ V_i $ without adding a subset of $ S $ to $ V_i $. However, there has to be $ S' \in {\cal{D}} $ with $ S' \subseteq \bigcup_{j=1}^{k-1} \Delta_j $ anyway. Assume that this is not the case. This means that either $ \delta_i \in \bigcup_{j=1}^{k-1} \Delta_j $, which is a contradiction to $ \delta_i \in \Delta_k $, or $ \delta_l \in \Delta_j $ with $ j \gt k $. The latter contradicts $ \{\delta_l\} = S \subseteq \bigcup_{j=1}^{k-1} \Delta_j $ which finishes the proof.

The fact that there is a generalized tolerance partition which is not a tolerance partition is proven by the following Example 5.□

Example 5. We continue Example 4. The ordered partition $ {\cal{T}}(\Delta_{\mathrm{ex}}) = (\Delta_1,\Delta_2) $ of $ \Delta_{\mathrm{ex}} $ with $ \Delta_1 = \{\delta_2, \delta_3, \delta_5\} $ and $ \Delta_2 = \{\delta_1, \delta_4\} $ is a generalized tolerance partition of $ \Delta_{\mathrm{ex}} $ because $ \hat{V}_i = \{\emptyset\} $ for $ i \in \{2,3,5\} $ and $ \{\delta_3\} \in \hat{V}_1 \cap 2^{\Delta_1} $ as well as $ \{\delta_3, \delta_5\} \in \hat{V}_4 \cap 2^{\Delta_1} $. However, $ {\cal{T}}(\Delta_{\mathrm{ex}}) $ is not a tolerance partition of $ \Delta $ because $ \delta_5 $ is not tolerated by $ \Delta $. In every possible world which verifies $ \delta_5 = ({\overline c }|ab) $, the conditional $ \delta_3 = ({\overline a }|b \lor c) $ is falsified. Thus, $ \delta_5 $ is only weakly tolerated by $ \Delta $. This example shows that there are generalized tolerance partitions which are not tolerance partitions.

Generalized tolerance partitions help focus on relevant dependencies among the conditionals in $ \Delta $. For instance, in Example 5 it turns out that in the end $ \delta_3 $ is not relevant for $ \delta_5 $ because it is falsified by both the verifying and falsifying component of $ \delta_5 $ (see Table 2). In contrast to System Z and the original definition of tolerance, this can be taken into account by c-representations and is dealt with by reduction rule R4 which eliminates this dependency. Hence, it is no longer relevant for the generalized tolerance partition of $ \Delta $.

Based on the notion of generalized tolerance partitions and the next lemma, we can formulate a construction method for core c-representations.

Lemma 1. Let $ \Delta $ be a non-empty consistent belief base, and let $ n = |\Delta| $. Then there is $ i \in [n] $ with $ \hat{V}_i = \{\emptyset\} $.

Proof. Because $ \Delta $ is consistent and non-empty, there is a conditional $ \delta_i \in \Delta $ which is tolerated by $ \Delta $. Otherwise, there would be no tolerance partition of $ \Delta $ because its existence is equivalent to the consistency of $ \Delta $. From Proposition 4 we know that $ \emptyset \in V_i $ holds then. With transformation rule R1, $ \hat{V}_i = \{\emptyset\} $ follows.□

The crucial point of the construction method for core c-representations is that the impact factors of conditionals in the $ i $-th partitioning set of any generalized tolerance partition of $ \Delta $ may be specified solely based on the impact factors of conditionals in lower partitioning sets as captured in the concept of base functions which is the crucial concept behind the stratification of core c-representations.

Definition 8 (Base Function). Let $ {\cal{T}}(\Delta) = (\Delta_1, \ldots, \Delta_m) $ be a generalized tolerance partition of a consistent belief base $ \Delta $, let $ n = |\Delta| $, and let $ \vec{\eta} \in {\mathbb{N}}^n $. We define the base function $ \phi^{\vec{\eta}}_{{\cal{T}}(\Delta)} \colon \Delta \to {\mathbb{N}}_0 $ w.r.t. $ \vec{\eta} $ and $ {\cal{T}}(\Delta) $ by

where, $ k $ is the index of the partitioning set $ \Delta_k \in {\cal{T}}(\Delta) $ with $ \delta_i \in \Delta_k $.

Base functions transfer the idea of Z-ranks from System Z to c-representations and arbitrary generalized tolerance partitions. The expression in (8) is the right-hand side of (7) where the sums in the min-term are restricted to cover conditionals from $ \bigcup_{j=1}^{k-1} \Delta_j $ instead of the whole set $ \Delta $.

Proposition 6. Let $ \Delta $ be a consistent belief base, let $ n = |\Delta| $, and let $ {\cal{T}} (\Delta) = (\Delta_1, \ldots, \Delta_m) $ be a generalized tolerance partition of $ \Delta $. Further, suppose $ \vec{\eta} \in {\mathbb{N}}^n $ satisfies

Then, $ \kappa(\omega) = \sum\nolimits_{\delta_i \in {\mathrm{fal}}_\Delta(\omega)} \eta_i $, $ \omega \in \Omega(\Sigma) $, is a core c-representation of $ \Delta $. In particular, this holds for $ \eta_i = \phi_{{\cal{T}}(\Delta)}^{\vec{\eta}}(\delta_i) + 1 $, $ i \in [n] $.

Proof. Because of $ \{ S \in \hat{V}_i \mid S \subseteq \bigcup_{j=1}^{k-1} \Delta_j \} \subseteq \hat{V}_i $ and $ \min N \leq \min N' $ for $ N' \subseteq N \subseteq {\mathbb{N}} $, we have

which shows that $ \kappa^{\vec{\eta},c}_\Delta $ is a core c-representation of $ \Delta $.□

In Proposition 9 we will show that for every core c-representation $ \kappa^{\vec{\eta},c}_\Delta $ of $ \Delta $ there is a generalized tolerance partition $ {\cal{T}}(\Delta) $, such that $ \vec{\eta} $ satisfies (9), which proves that core c-representations are stratified, i.e., the impact factors of core c-representations can be calculated layer by layer. This becomes clear when realizing that $ \phi^{\vec{\eta}}_{{\cal{T}}(\Delta)}(\delta_i) $ does actually not depend on the whole vector $ \vec{\eta} $ but only on its entries referring to the conditionals which occur in $ {\cal{T}}(\Delta) $ before $ \delta_i $.

Example 6. We continue Example 5 and recall that $ {\cal{T}}(\Delta_{\mathrm{ex}}) = (\Delta_1,\Delta_2) $ with $ \Delta_1 = \{\delta_2, \delta_3, \delta_5\} $ and $ \Delta_2 = \{\delta_1, \delta_4\} $ is a generalized tolerance partition of $ \Delta_{\mathrm{ex}} $. According to Proposition 6, an impact vector which leads to a core c-representation of $ \Delta_{\mathrm{ex}} $ is $ \vec{\eta} = (2,1,1,3,1) $. This impact vector can be obtained as follows: First, for the conditionals in $ \Delta_1 $, we set $ \eta_2 = \eta_3 = \eta_5 = 1 \gt 0 $. Then, based on these assignments, for the conditionals in $ \Delta_2 $, we set $ \eta_1 = 2 \gt 1 = \eta_3 $ and $ \eta_4 = 3 \gt 1 + 1 = \eta_3 + \eta_5 $.

We remark that the so-called Z-c-representation from Kern-Isberner^[2] fits into the concept of core c-representations.

Definition 9 (Z-c-representation^[2]). Let $ \Delta $ be consistent belief base, let $ n = |\Delta| $, and let $ \vec{\eta}^{Z,c}_\Delta = (\eta_1, \ldots, \eta_n) \in {\mathbb{N}}^n $ be the impact vector with

where, $ Z(\Delta) = (\Delta_1, \ldots, \Delta_m) $ is the Z-partition of $ \Delta $. Then, $ \kappa^{Z,c}_\Delta(\omega) = \sum\nolimits_{\delta_i \in {\mathrm{fal}}_\Delta(\omega)} \eta_i $, $ \omega \in \Omega(\Sigma) $, is called the Z-c-representation of $ \Delta $.

Note that the base function $ \phi^{\vec{\eta}^{Z,c}_\Delta}_{Z(\Delta)} $ makes use of the reduced constraint inducing sets $ \hat{V}_i $, $ i \in [n] $, which is different from the original definition of the Z-c-representation. Apart from this, the two definitions are the same which is why we stick to the name Z-c-representation here.

Proposition 7. For every consistent belief base $ \Delta $, the Z-c-representation $ \kappa^{Z,c}_\Delta $ of $ \Delta $ exists and is unique. Further, $ \kappa^{Z,c}_\Delta $ is a core c-representation of $ \Delta $.

Proof. According to Proposition 5, the Z-partition $ Z(\Delta) $ is a generalized tolerance partition of $ \Delta $, and with Proposition 6 it follows that each vector $ \vec{\eta} \in {\mathbb{N}}^n $ with

leads to a core c-representation of $ \Delta $. This particularly holds for $ \vec{\eta}^{Z,c}_\Delta \in {\mathbb{N}}^n $ defined by

which is a unique assignment because $ Z(\Delta) $ is unique.□

The Z-c-representation $ \kappa^{Z,c}_\Delta $ illustrates the connection between the System Z ranking model and core c-representations well. Both $ \kappa^Z_\Delta $ and $ \kappa^{Z,c}_\Delta $ exploit the Z-partition of $ \Delta $, but while $ \kappa^Z_\Delta $ is defined via a maximum of Z-ranks, $ \kappa^{Z,c}_\Delta $ makes use of a summation and, therefore, inherits the inferential strength of c-representations.

According to Proposition 2, core c-representations of a belief base $ \Delta $ constitute a subclass of the c-representations of $ \Delta $ and, thus, are ranking models of $ \Delta $. It follows that $ \Delta $ is consistent if and only if $ \Delta $ has a core c-representation which is due to the fact that the consistency of $ \Delta $ concurs with the existence of a tolerance partition of $ \Delta $.

Proposition 8. Let $ \Delta $ be a belief base. Then, $ \Delta $ is consistent if and only if there is a core c-representation of $ \Delta $.

Proof. From Proposition 2 we know that core c-representations are c-representations. Because c-representations of $ \Delta $ only exist if $ \Delta $ is consistent, it follows that $ \Delta $ must be consistent if it has a core c-representation. The other way round, if $ \Delta $ is consistent, then the existence of the Z-c-representation $ \kappa^{Z,c}_\Delta $ proves the existence of a core c-representation of $ \Delta $.□

Next, we show that consistent belief bases have a unique minimal core c-representation and discuss this specific core c-representation in more detail.

The Z-c-representation $ \kappa^{Z,c}_\Delta $ is a pragmatic way of defining a unique core c-representation of a consistent belief base $ \Delta $. However, $ \kappa^{Z,c}_\Delta $ does not specify the impact factors in a minimal way. Nevertheless, consistent belief bases have a unique minimal core c-representation where we call a core c-representation $ \kappa^{\vec{\eta},c}_\Delta $ of $ \Delta $ minimal if there is no other core c-representation $ \kappa^{\vec{\eta} {\, '} ,c}_\Delta $ of $ \Delta $ with $ \eta'_i \lt \eta_i $ for some $ i \in [n] $. In other words, for the minimal core c-representation $ \kappa^{\vec{\eta},c}_\Delta $ we have $ \eta_i \leq \eta'_i $ for all $ i \in [n] $, and all core c-representations $ \kappa^{\vec{\eta} {\, '} ,c}_\Delta $ of $ \Delta $. Note that this component-wise concept of minimality necessitates a unique pareto-minimal solution $ \vec{\eta} $ of $ {\mathrm{CSP}}^+(\Delta) $ in general, and implies $ \kappa^{\vec{\eta},c}_\Delta(\omega) \leq \kappa^{\vec{\eta} {\, '} ,c}_\Delta(\omega) $ for all other solutions $ \vec{\eta} {\, '} $, and all $ \omega \in \Omega(\Sigma) $. That is, among all core c-representations, the minimal core c-representation assigns minimal ranks to possible worlds. As the investigations by Beierle et al.^[3] show, there is no unique minimal c-representation in general. Hence, the existence of such a unique minimal element in the subclass of core c-representations has to be proven explicitly. We choose a constructive approach here.

The construction of the minimal core c-representation is based on a specific generalized tolerance partition which we call canonical generalized tolerance partition.

Definition 10 (Canonical Generalized Tolerance Partition w.r.t. $ \vec{\eta} $). Let $ \Delta $ be a consistent belief base, and let $ \kappa^{\vec{\eta},c}_\Delta $ be a core c-representation of $ \Delta $. Then, the canonical generalized tolerance partition $ {\cal{Q}}_{\vec{\eta}}(\Delta) = (\Delta_1, \ldots, \Delta_m) $ of $ \Delta $ w.r.t. $ \vec{\eta} $ is defined as follows. For $ k \in [m] $ and $ \delta_i \in \Delta $$ \delta_i \in \Delta $, we have $ \delta_i \in \Delta_k $ if and only if

$ {\cal{Q}}_{\vec{\eta}}(\Delta) $ is a generalized tolerance partition of $ \Delta $ because it includes $ \delta_i $ into $ \Delta_k $ only if there is $ S \in \hat{V}_i $ with $ S \subseteq \bigcup_{j=1}^{k-1} \Delta_j $, and its existence follows from the consistency of $ \Delta $. In contrast to the Z-partition from System Z, $ {\cal{Q}}_{\vec{\eta}}(\Delta) $ does not include all conditionals in the next partitioning set $ \Delta_k $ which are (weakly) tolerated by $ \bigcup_{j=k}^m \Delta_j $ but only those which contribute to a minimal rank, i.e., a minimal sum of impact factors. In case of $ \Delta_1 $, this still coincides with adding all weakly tolerated conditionals from $ \Delta $, i.e.,

Then, if we assign the minimal impact value $ \eta_i = 1 $ to all weakly tolerated conditionals $ \delta_i \in \Delta_1 $, in $ \Delta_2 $ we find all remaining conditionals which falsify a minimal number of conditionals from $ \Delta_1 $. More precisely,

Since conditionals in $ \Delta_3 $ and upwards can falsify conditionals from lower partitioning sets with different impact factors assigned, deciding whether a conditional is in the next partitioning set or not is no longer just a counting problem but requires taking the impact factors into account. Note that this also holds for $ \Delta_2 $ already if the impact factors of the conditionals in $ \Delta_1 $ are not assigned minimally.

Example 7. We recall the belief base $ \Delta_{\mathrm{ex}} = \{ \delta_1, \ldots, \delta_5 \} $ with

from Example 2 and the fact that $ \vec{\eta} = (2,1,1,3,1) $ is the impact vector of a core c-representation of $ \Delta_{\mathrm{ex}} $ (cf. Example 6). Because $ \delta_2 $, $ \delta_3 $, and $ \delta_5 $ are all the weakly tolerated conditionals in $ \Delta_{\mathrm{ex}} $, one has $ \phi^{\vec{\eta}}_{{\cal{Q}}_{\vec{\eta}}(\Delta_{\mathrm{ex}})}(\delta_i) = 0 $ for $ i = 2, 3, 5 $, and the first partitioning set in $ {\cal{Q}}_{\vec{\eta}}(\Delta_{\mathrm{ex}}) $ is $ \Delta_1 = \{ \delta_2, \delta_3, \delta_5 \} $. Now, both remaining conditionals $ \delta_2 $ and $ \delta_4 $ are weakly tolerated and could principally be included in $ \Delta_2 $ to obtain a generalized tolerance partition of $ \Delta_{\mathrm{ex}} $ as it is done in $ {\cal{T}}(\Delta_{\mathrm{ex}}) $ in Example 6. However, this would not lead to the canonical generalized tolerance partition because only $ \delta_1 $ satisfies the minimization criterion in (11):

Thus, $ \Delta_2 = \{ \delta_1 \} $ and eventually $ \Delta_3 = \{ \delta_4 \} $ are the remaining partitioning sets in $ {\cal{Q}}_{\vec{\eta}}(\Delta_{\mathrm{ex}}) $ which distinguishes $ {\cal{Q}}_{\vec{\eta}}(\Delta_{\mathrm{ex}}) $ from $ {\cal{T}}(\Delta_{\mathrm{ex}}) $.

Note that while a canonical generalized tolerance partition is based on an impact vector $ \vec{\eta} $, we can use Definition 10 in a constructive way to build up core c-representations layer by layer, basically because $ \Delta_1 $ is independent of $ \vec{\eta} $, as we will see next.

By using $ {\cal{Q}}_{\vec{\eta}}(\Delta) $, we can show the reverse direction of Proposition 6, i.e., we can show that for every core c-representation $ \kappa^{\vec{\eta},c}_\Delta $ of $ \Delta $ there is a generalized tolerance partition $ {\cal{T}}(\Delta) $ of $ \Delta $ such that $ \eta_i \gt \phi^{\vec{\eta}}_{{\cal{T}}(\Delta)}(\delta_i) $ for $ i \in [n] $ holds, which is a consequence of the next proposition.

Proposition 9. Let $ \Delta $ be a consistent belief base, let $ n = |\Delta| $, let $ \kappa^{\vec{\eta},c}_\Delta $ be a core c-representation of $ \Delta $, and let $ {\cal{Q}}_{\vec{\eta}}(\Delta) $ be the canonical generalized tolerance partition of $ \Delta $ w.r.t. $ \vec{\eta} $. Then,

i.e., the canonical generalized tolerance partition is able to capture all relevant information for computing $ \eta_i $ according to (7) from previous layers.

Proof. The essence of the proof is to show for $ i \in [n] $ that there is no $ S' \in \hat{V}_i $ with $ S' \not\subseteq \bigcup_{j=1}^{k_i-1} \Delta_j $ such that

holds, where $ k_i $ is the index of the partitioning set $ \Delta_{k_i} \in {\cal{Q}}_{\vec{\eta}}(\Delta) $ with $ \delta_i \in \Delta_{k_i} $. Then,

immediately follows. Hence, we assume that there is $ i \in [n] $ with $ S' \in \hat{V}_i $ and $ S' \not\subseteq \bigcup_{j=1}^{k_i-1} \Delta_j $ such that (12) applies and bring it to a contradiction. W.l.o.g., we assume that $ S' $ is a set from $ \{ S \in \hat{V}_i \mid S \not\subseteq \bigcup_{j=1}^{k_i-1} \Delta_j\} $ with minimal sum $ \sum\nolimits_{\delta_j \in S'} \eta_j $ among them. Note that, in particular, for all $ \delta_l \in S' $,

holds then. Further, there is $ \delta_l \in S' $ with $ \delta_l \notin \bigcup_{j=1}^{k_i-1} \Delta_j $ by definition of $ S' $. Consequently, one of the following two cases must apply because $ \delta_l $ does not occur in a partitioning set with lower index than $ k_i $ (cf. (11)):

$ {\underline{{\text{Case 1}}:}} $ There is $ S \in \hat{V}_l $ with $ S \subseteq \bigcup_{j=1}^{k_i-1} \Delta_j $. Then,

must hold, too, in order that $ \delta_i $ is in $ \Delta_{k_i} $. Otherwise, $ \delta_i $ would not be in the set described by the arguments of the minima in (11).

$ {\underline{{\text{Case 2}}:}} $ There is no $ S \in \hat{V}_l $ with $ S \subseteq \bigcup_{j=1}^{k_i-1} \Delta_j $.

In Case 1, because of (13), (12), and (14) (in this order), we have

and, hence, there must be $ S'' \in \hat{V}_l $ with $ S'' \not\subseteq \bigcup_{j=1}^{k_i-1} \Delta_j $ such that

holds. Otherwise, condition (7) would not hold for $ \delta_l $ and $ \kappa^{\vec{\eta},c}_\Delta $ would not be a core c-representation of $ \Delta $. In Case 2, the existence of such a set $ S'' \in \hat{V}_l $ with $ S'' \not\subseteq \bigcup_{j=1}^{k_i-1} \Delta_j $ follows directly (note that $ \hat{V}_l $ is non-empty when $ \Delta $ is consistent).

Now, by combining (15) and (16), we obtain the same situation for $ \delta_l $ as for $ \delta_i $, namely that there must be $ S'' \in \hat{V}_l $ with $ S'' \not\subseteq \bigcup_{j=1}^{k_i-1} \Delta_j $, such that

holds. With the same argumentation as for $ \eta_i $, we can find $ \eta_k $ with $ \eta_l \gt \eta_k $ (like $ \eta_i \gt \eta_l $ holds), and so on. This defines a descending chain of impact factors which has to become cyclic because $ \Delta $ is finite. Consequently, we have $ \eta_i \gt \eta_l \gt \eta_k \gt \ldots \gt \eta_i $ which is a contradiction. □

Corollary 1. Let $ \Delta $ be a consistent belief base, let $ n = |\Delta| $, let $ \kappa^{\vec{\eta},c}_\Delta $ be a core c-representation of $ \Delta $, and let $ {\cal{Q}}_{\vec{\eta}}(\Delta) $ be the canonical generalized tolerance partition of $ \Delta $ w.r.t. $ \vec{\eta} $. Then,

Proof. According to (7) and Proposition 9, we have

for $ i \in [n] $. □

With regard to Proposition 8, also the following proposition holds.

Proposition 10. Let $ \Delta $ be a belief base. Then, $ \Delta $ is consistent if and only if there is a generalized tolerance partition of $ \Delta $.

Proof. Let $ \Delta $ be consistent. According to Proposition 8, there is a core c-representation $ \kappa^{\vec{\eta},c}_\Delta $ of $ \Delta $ and, thus, the canonical generalized tolerance partition $ {\cal{Q}}_{\vec{\eta}}(\Delta) $ exists. The other way round, if there is a generalized tolerance partition of $ \Delta $, then with Proposition 6 there is a core c-representation of $ \Delta $ and with Proposition 8 the consistency of $ \Delta $ follows. □

An important consequence of Proposition 9 is that the computation of an impact factor $ \eta_i $ depends on the impact factors $ \eta_j $ w.r.t. conditionals in previous layers of $ {\cal{Q}}_{\vec{\eta}}(\Delta) $ only. Note that this holds for all core c-representations and, thus, allows for simplification and minimization in a natural way, so that we are now ready to define the minimal core c-representation of $ \Delta $.

Definition 11 (Minimal Core c-Representation). Let $ \Delta $ be a consistent belief base, and let $ n = |\Delta| $. We call $ \kappa^{mc}_\Delta(\omega) = \sum\nolimits_{\delta_i \in {\mathrm{fal}}_\Delta(\omega)} \eta_i $, $ \omega \in \Omega(\Sigma) $, where $ \vec{\eta}^{\,mc}_\Delta = (\eta_1,\ldots, \eta_n) $ is defined w.r.t. the canonical generalized tolerance partition $ {\cal{Q}}^{mc}(\Delta) = {\cal{Q}}_{\vec{\eta}^{\,mc}_\Delta}(\Delta) $ by

the minimal core c-representation of $ \Delta $. We abbreviate $ \phi^{mc}_\Delta = \phi_{{\cal{Q}}^{mc}(\Delta)}^{\vec{\eta}^{\,mc}_\Delta} $.

The canonical generalized tolerance partition $ {\cal{Q}}^{mc}(\Delta) $ and the impact vector $ \vec{\eta}^{\,mc}_\Delta $ in Definition 11 can be determined in alternation, beginning with the lowest partitioning set in $ {\cal{Q}}^{mc}(\Delta) $. For $ k=1 $, (11) reduces to the claim that $ \delta_i $ is weakly tolerated by $ \Delta $, thus $ \eta_i = 1 $ follows. Note that this can be done independently of evaluating $ \phi_{{\cal{Q}}^{mc}(\Delta)}^{\vec{\eta}^{\,mc}_\Delta} $ because $ \cup_{j=1}^0 \Delta_j = \emptyset $ in any case, yielding a proper starting point for the construction. Afterwards, the conditionals $ \delta_i $ in the second lowest partitioning set (k = 2) can be determined because $ \phi^{mc}_\Delta(\delta_i) $ solely depends on the impact factors assigned to the conditionals in $ \Delta_1 $, and so on. The basic idea is to include into the next partitioning set those of the remaining conditionals which are weakly tolerated by the others and for which the base function makes the weakest possible restriction. Then, the impact factors of the included conditionals are specified in a minimal way among all core c-representations. The whole procedure is formalized in pseudocode in Algorithm 1.

Example 8. We recall $ \Delta_{\mathrm{ex}} $ from Example 2. The minimal core c-representation $ \kappa^{mc}_{\Delta_{\mathrm{ex}}} $ of $ \Delta_{\mathrm{ex}} $ can be computed as follows: First, the weakly tolerated conditionals in $ \Delta_{\mathrm{ex}} $ are determined which are $ \delta_2 $, $ \delta_3 $, and $ \delta_5 $. Hence, $ \Delta_1 = \{ \delta_2, \delta_3, \delta_5 \} $ is the first partitioning set in $ {\cal{Q}}^{mc}(\Delta_{\mathrm{ex}}) $. The impact values of the conditionals in $ \Delta_1 $ are minimally chosen to $ \eta_2 = \eta_3 = \eta_5 = 1 $ by default. Now, both $ \delta_1 $ and $ \delta_4 $ are weakly tolerated in $ \Delta_{\mathrm{ex}} \setminus \Delta_1 $ but with $ \phi^{mc}_{\Delta_{\mathrm{ex}}} $ provoking a weaker constraint on the impact value of $ \delta_1 $ ($ \eta_1 \gt \eta_3 = 1 $) than on $ \delta_4 $ ($ \eta_4 \gt \eta_3 + \eta_5 = 2 $). This can be decided at this point without knowing the complete impact vector $ \vec{\eta}^{\, mc}_{\Delta_{\mathrm{ex}}} $ because only impact values of conditionals from $ \Delta_1 $ are relevant. Hence, $ \Delta_2 = \{ \delta_1 \} $ and the impact value of $ \delta_1 $ is minimally chosen to $ \eta_1 = 2 $. Eventually, we obtain $ \Delta_3 = \{ \delta_4 \} $, and $ \eta_4 = 3 $. Thus, the complete impact vector of the minimal core c-representation of $ \Delta_{\mathrm{ex}} $ is $ \vec{\eta}^{\, mc}_{\Delta_{\mathrm{ex}}} = (2, 1, 1, 3, 1) $ (cf. Example 6). Although the merging of $ \Delta_2 $ and $ \Delta_3 $, which distinguishes the canonical generalized tolerance partition $ {\cal{Q}}^{mc}(\Delta_{\mathrm{ex}}) $ from the generalized tolerance partition $ {\cal{T}}(\Delta_{\mathrm{ex}}) $ in Example 6, would not make a difference to the impact factor assignments here, there are examples in which it is necessary to take the minimization in (11), which characterizes canonical generalized tolerance partitions, into account (cf. Example 9).

The core c-representation $ \kappa^{mc}_\Delta $ as given in Definition 11 is indeed the unique minimal core c-representation of $ \Delta $.

Proposition 11. Let $ \Delta $ be a consistent belief base, and let $ n = |\Delta| $. Then the core c-representation $ \kappa^{mc}_\Delta $ induced by the impact vector $ \vec{\eta}^{\,mc}_\Delta = (\eta_1, \ldots, \eta_n) $ from Definition 11 is the unique minimal core c-representation of $ \Delta $. That is, for all core c-representations $ \kappa^{\vec{\eta} {\, '} ,c}_\Delta $ of $ \Delta $, we have $ \eta_i \leq \eta'_i $ for $ i \in [n] $.

Proof. Let $ \kappa^{\vec{\eta} {\, '} ,c}_\Delta $ be a core c-representation of $ \Delta $. Then, there is a pareto-minimal solution $ \vec{\eta}{\,''} \in {\mathbb{N}}^n $ of $ {\mathrm{CSP}}^+(\Delta) $ such that $ \eta_i'' \leq \eta_i' $ for $ i \in [n] $ holds according to the definition of pareto-minimality. Hence, it suffices to show that for all pareto-minimal solutions $ \vec{\eta}{\,''} $ of $ {\mathrm{CSP}}^+(\Delta) $, $ \eta_i \leq \eta_i'' $ for $ i \in [n] $ holds. Because of Proposition 9, the canonical generalized tolerance partition $ {\cal{Q}}_{\vec{\eta}{\,''}}(\Delta) $ of $ \Delta $ w.r.t. $ \vec{\eta}{\,''} $ exists and it is $ \eta''_i \gt \phi^{\vec{\eta}{\,''}}_{{\cal{Q}}_{\vec{\eta}{\,''}}(\Delta)}(\delta_i) $ for $ i \in [n] $. According to Proposition 6,

follows. Otherwise, $ \vec{\eta}{\,''} $ would not be pareto-minimal.

Now, we prove by induction over the index $ k $ of the partitioning sets in $ {\cal{Q}}_{\vec{\eta}{\,''}}(\Delta) $ that $ {\cal{Q}}_{\vec{\eta}{\,''}}(\Delta) = {\cal{Q}}^{mc}(\Delta) $ holds. Then, by the definition of $ \vec{\eta}^{\,mc}_\Delta $ and because of (17), $ \eta_i = \eta''_i $ for $ i \in [n] $ follows. As this holds for all pareto-minimal solutions $ \vec{\eta}{\,''} $ of $ {\mathrm{CSP}}^+(\Delta) $, all these solutions coincide and $ \vec{\eta}^{\,mc}_\Delta $ is the unique pareto-minimal solution of $ {\mathrm{CSP}}^+(\Delta) $. Consequently, $ \kappa^{mc}_\Delta $ is the unique minimal core c-representation of $ \Delta $.

For the induction, we denote the canonical generalized tolerance partition of $ \Delta $ w.r.t. $ \vec{\eta}{\,''} $ by $ {\cal{Q}}_{\vec{\eta}{\,''}}(\Delta) = (\Delta''_1, \ldots, \Delta''_l) $ and w.r.t. $ \vec{\eta}^{\,mc}_\Delta $ by $ {\cal{Q}}^{mc}(\Delta) = (\Delta_1, \ldots, \Delta_m) $. Let $ k = 1 $. By definition,

As a consequence, $ \eta''_i = 1 = \eta_i $ for $ \delta_i \in \Delta''_1 $ holds (cf., in particular, (17)). Now, we assume that $ \Delta''_i = \Delta_i $ for $ i \in [k-1] $ and $ \eta''_i = \eta_i $ for $ \delta_i \in \bigcup_{j = 1}^{k - 1} \Delta_j $ hold. Therewith, we have (cf. (11)),

Hence, $ \Delta''_k = \Delta_k $ which finishes the proof. □

From the uniqueness of the minimal core c-representation it follows that essentially the same belief bases have the same minimal core c-representation. With 'essentially the same', we mean that the belief bases are pairwise equivalent.

Definition 12 (Pairwise Equivalent Belief Bases). Two belief bases $ \Delta $ and $ \Delta' $ are pairwise equivalent if there is a bijection $ \beta \colon \Delta \to \Delta' $ such that $ \beta(\delta) \equiv \delta $ for all $ \delta \in \Delta $.

Recall that in this article we assume that a belief base does not contain equivalent duplicates of conditionals, avoiding that $ \Delta $ contains, e.g., both $ (B|A) $, and also $ (B|A \lor A) $ or $ (AB|A) $.

Proposition 12. Let $ \Delta $ and $ \Delta' $ be pairwise equivalent consistent belief bases. Then,

for all $ \omega \in \Omega(\Sigma) $.

Proof. Because $ \Delta $ and $ \Delta' $ are pairwise equivalent, there is a bijection $ \beta \colon \Delta \to \Delta' $ such that $ \beta(\delta) \equiv \delta $ for all $ \delta \in \Delta $. As a direct consequence, $ {\mathrm{ver}}(\beta(\delta)) = {\mathrm{ver}}(\delta) $ for all $ \delta \in \Delta $ and also $ {\mathrm{fal}}(\beta(\delta)) = {\mathrm{fal}}(\delta) $. The latter holds because $ (B|A) \equiv (D|C) $, and therewith $ A \equiv C $ and $ AB \equiv CD $, also implies $ A{\overline B } \equiv C{\overline D } $. Then, $ {\mathrm{CSP}}(\Delta) = {\mathrm{CSP}}(\Delta') $ (up to a reindexing of the conditionals) from which the validity of the proposition follows because of the uniqueness of the minimal core c-representation. □

The next example shows that the minimal core c-representation is different from the Z-c-representation in general.

Example 9. We consider the belief base $ \Delta_{{\mathrm{ex}}2} = \{ \delta_1, \ldots, \delta_5 \} $ with

The sets $ {\mathrm{ver}}_{\Delta_{{\mathrm{ex}}2}}(\omega) $ and $ {\mathrm{fal}}_{\Delta_{{\mathrm{ex}}2}}(\omega) $ are shown in Table 3. $ {\mathrm{CSP}}^+(\Delta_{{\mathrm{ex}}2}) $ consists of the constraints

While the Z-partition of $ \Delta_{{\mathrm{ex}}2} $ is

and, hence, the impact vector of the Z-c-representation of $ \Delta_{{\mathrm{ex}}2} $ is$ \vec{\eta}^{\,Z,c}_{\Delta_{{\mathrm{ex}}2}} = (1,2,2,3,5) $, we have

and the minimal core c-representation $ \kappa^{mc}_{\Delta_{{\mathrm{ex}}2}} $ of $ \Delta_{{\mathrm{ex}}2} $ is given by $ \vec{\eta}^{\,mc}_{\Delta_{{\mathrm{ex}}2}} = (1,2,2,3,4) $. The difference here is that the Z-c-representation assigns the impact factors to $ \delta_4 $ and $ \delta_5 $ in the same step because they occur in the same partitioning set in $ Z(\Delta_{{\mathrm{ex}}2}) $. This means that we have to specify $ \eta_5 $ in a way that $ \eta_5 \gt \eta_2 + \eta_3 $ holds in order to satisfy the constraint $ \eta_5 \gt \min \{\eta_2 + \eta_3, \eta_4\} $ because $ \eta_4 $ is not known when $ \eta_5 $ is specified. The minimal core c-representation assigns an impact factor to $ \delta_4 $ before $ \delta_5 $ instead, because $ \eta_4 $ is (potentially) smaller than $ \eta_5 $, so that it suffices for $ \eta_5 $ to satisfy $ \eta_5 \gt \eta_4 $ which leads to a smaller value of $ \eta_5 $ in this case. For comparison, the System Z ranking model of $ \Delta_{{\mathrm{ex}}2} $ is given by $ (Z(\delta_1), \ldots, Z(\delta_5)) = (1,2,2,3,3) $ and assigns even lower ranks than $ \kappa^{mc}_{\Delta_{{\mathrm{ex}}2}} $ but it is not a c-representation.

Eventually, we note that $ {\cal{Q}}^{mc}(\Delta) $ orders the conditionals from $ \Delta $ w.r.t. their impact factors that refer to the minimal core c-representation of $ \Delta $.

Proposition 13. Let $ \Delta $ be a consistent belief base, let $ n = |\Delta| $, and let $ \kappa^{mc}_\Delta $ be the minimal core c-representation of $ \Delta $ with $ \vec{\eta}^{\,mc}_\Delta = (\eta_1, \ldots, \eta_n) $. Further, suppose $ {\cal{Q}}^{mc}(\Delta) = (\Delta_1, \ldots, \Delta_m) $, and let $ \delta_i \in \Delta_k $ and $ \delta_j \in \Delta_l $ where $ k,l \in [m] $. If $ k=l $, then $ \eta_i = \eta_j $, and if $ k \lt l $, then $ \eta_i \lt \eta_j $.

Proof. Let $ k=l $. Then, $ \eta_i = \eta_j $ follows directly from the definition of minimal core c-representations, and because of (11). Now, let $ l = k + 1 $. Because $ \eta_j \in \Delta_{k+1} $ in this case, there is $ S' \in \hat{V}_j $ with $ S' \subseteq \bigcup_{h=1}^{k} \Delta_h $ such that (cf. Proposition 9)

If $ S' \subseteq \bigcup_{h=1}^{k-1} \Delta_h $, then $ \phi^{mc}_\Delta(\delta_i) \lt \sum\nolimits_{\delta_h \in S'} \eta_h $ must hold. Otherwise, $ \delta_j $ would be in $ \Delta_k $. Consequently,

in this case. If $ S' \not\subseteq \bigcup_{h=1}^{k-1} \Delta_h $, then there is $ \delta_g \in S' \cap \Delta_k $ and

Hence, in both cases $ \eta_i \lt \eta_j $. Finally, let $ k \lt l $. Then, there is $ s \in {\mathbb{N}} $ with $ l = k + s $ and for all $ p \in \{0, 1, \ldots, s\} $ we can find $ \delta_{l_{k+p}} \in \Delta_{k+p} $. With the arguments above,

follows.□

In the next section we use the minimal core c-representation to define a novel inductive inference operation which we call c-core closure.

We define an inference operator which selects for each consistent belief base $ \Delta $ its unique minimal core c-representation $ \kappa^{mc}_\Delta $.

Definition 13 (c-Core Closure). Let $ \Delta $ be a consistent belief base, and let $ A, B \in {\cal{L}}(\Sigma) $ be formulas. We define the c-core closure inference operator $ {\cal{I}}^{mc} \colon \Delta \mapsto |\!\!\!\sim ^{mc}_\Delta $ by $ A |\!\!\!\sim ^{mc}_\Delta \!\! B $ if $ A |\!\!\!\sim _{\kappa^{mc}_\Delta} \!\! B $ (cf. (5)) where $ \kappa^{mc}_\Delta $ is the minimal core c-representation of $ \Delta $.

c-Core closure inherits several inference properties that hold for arbitrary ranking models, such as the satisfaction of System P and (RM). Moreover, like skeptical c-inference, c-core closure fully complies with syntax splitting^[18], and also with conditional syntax splitting^[28], and thus does not suffer from the drowning problem^[27]. We prove this by showing that selecting minimal core c-representations for drawing inferences yields a so-called impact preserving selection strategy.

Definition 14 (Selection Strategy for c-Representations^[18]). A selection strategy is a mapping $ \sigma \colon \Delta \mapsto \vec{\eta} $ which assigns a vector $ \vec{\eta} \in {\mathbb{N}}_0^n $ to each consistent belief base $ \Delta $ such that $ \vec{\eta} $ is a non-negative integer solution of $ {\mathrm{CSP}}(\Delta) $.

In general, selection strategies can assign impact vectors $ \vec{\eta} $ to different belief bases independently. The impact preserving property realizes the idea that these assignments should follow an overarching strategy. This ensures that impact vectors of (specific) subbases can be reused when computing the impact vector of the whole belief base $ \Delta $.

Definition 15 (Impact Preserving Selection Strategy^[28]). A selection strategy $ \sigma $ is impact preserving w.r.t. safe splittings if and only if for every consistent belief base $ \Delta $, and for every safe splitting $ \Delta_1 \bigcup_{\Sigma_1,\Sigma_2}^s \Delta_2 \mid \Sigma_3 $ of $ \Delta $ it holds that $ \sigma(\Delta_i) = \sigma(\Delta)|_{\Delta_i} $ for $ i \in \{1,2\} $.

We say that an inductive inference operator $ {\cal{I}} \colon \Delta \mapsto |\!\!\!\sim ^{\cal{I}}_\Delta $ is impact preserving w.r.t. safe splittings if there is a selection strategy $ \sigma $ that is impact preserving w.r.t. safe splittings such that $ |\!\!\!\sim ^{\cal{I}}_\Delta = |\!\!\!\sim _{\kappa^{\sigma(\Delta)}_\Delta} $ for all consistent belief bases $ \Delta $, where $ \kappa^{\sigma(\Delta)}_\Delta $ is the c-representation of $ \Delta $ induced by $ \sigma(\Delta) $. According to Beierle et al.^[28], every selection strategy that is impact preserving w.r.t. safe splittings satisfies (CSynSplit) and, therewith, also (SynSplit).

Proposition 14. The inductive inference operator $ {\cal{I}}^{mc} $ is impact preserving w.r.t. safe splittings, thus, satisfies (CSynSplit) and therewith also (SynSplit).

Proof. Let $ \Delta $ be a consistent belief base, and let $ \Delta_1 \bigcup_{\Sigma_1,\Sigma_2}^s \Delta_2 \mid \Sigma_3 $ be a safe splitting of $ \Delta $. First, we prove $ \sigma(\Delta_1) = \sigma(\Delta)|_{\Delta_1} $ where $ \sigma $ is the selection strategy which selects for every consistent belief base $ \Delta' $ the impact vector $ \vec{\eta}^{\,mc}_{\Delta'} $ of the minimal core c-representation of $ \Delta' $.

For conditionals $ \delta_i \in \Delta_1 $, let $ V_i $ and $ F_i $ denote the constraint inducing sets of $ \delta_i $ w.r.t. $ \Delta $, and let $ \tilde{V}_i $ and $ \tilde{F}_i $ denote the constraint inducing sets of $ \delta_i $ w.r.t. $ \Delta_1 $. In a first step, we show $ \hat{V}_i = \hat{\tilde{V}}_i $. Because of the safeness property (6), for every $ S \in V_i $ there is $ S' \in V_i $ with $ S' \subseteq S $ and $ S' \cap \Delta_2 = \emptyset $. This holds because for every $ S \in V_i $ there is $ \omega \in \Omega(\Sigma) $ with $ \omega \in {\mathrm{ver}}(\delta_i) $ and $ {\mathrm{fal}}_\Delta(\omega)=S $. The marginalization

of $ \omega $ on $ \Sigma_1 \cap \Sigma_3 $ also verifies $ \delta_i $ because this can be decided based on the evaluation of the atoms in $ \Sigma_1 \cap \Sigma_3 $ and, according to the safeness property, $ \omega|_{\Sigma_1\cap\Sigma_3} $ ca be extended to $ \omega' \in \Omega(\Sigma) $ with $ \omega' \models \omega|_{\Sigma_1 \cap \Sigma_3} $ such that $ {\mathrm{fal}}_{\Delta_2}(\omega') = \emptyset $. Hence, there is $ \omega' \in \Omega(\Sigma) $ with $ \omega' \in {\mathrm{ver}}(\delta_i) $ and $ {\mathrm{fal}}_\Delta(\omega') \subseteq \Delta_1 $ which implies the existence of $ S' $.

Analogously, for every $ S \in F_i $ there is $ S' \in F_i $ with $ S' \subseteq S $ and $ S' \cap \Delta_2 = \emptyset $. Hence, we can apply the transformation rules R1 and R2 to $ V_i $ and $ F_i $, respectively, in order to remove all sets $ S \in V_i $ (resp. $ S \in F_i $) from $ V_i $ (resp. $ F_i $) with $ S \cap \Delta_2 \neq \emptyset $. By doing so, we obtain

Because the result of the exhaustive application of R1–R6 to the sets $ V_i $ and $ F_i $ for all $ \delta_i \in \Delta $ results in $ \hat{V}_i $ and $ \hat{F}_i $ independently of the order in which the rules are applied, we have

for all $ \delta_i \in \Delta_1 $. Now, showing $ V'_i = \tilde{V}_i $ and $ F'_i = \tilde{F}_i $ will finish the proof of $ \hat{V}_i = \hat{\tilde{V}}_i $ because the transformation rules R1–R6 are applied to the same constrained inducing sets then. The identities $ V'_i = \tilde{V}_i $ and $ F'_i = \tilde{F}_i $ are direct consequences of the safeness property (6), though. This is because every possible world $ \omega \in \Omega(\Sigma) $ which leads to a set $ S \in \tilde{V}_i $ can be marginalized to $ \Sigma_1 \cap \Sigma_3 $, while maintaining the verification of $ \delta_i $, and extended to a possible world that does not falsify a conditional from $ \Delta_2 $ such that $ \tilde{V}_i \subseteq V'_i $. And $ V'_i \subseteq \tilde{V}_i $ holds by construction of $ V'_i $. Analogous arguments apply to $ F'_i = \tilde{F}_i $.

If we denote the constraint inducing sets of $ \delta_i \in \Delta_2 $ with $ \tilde{V_i} $ and $ \tilde{F_i} $ and apply the same techniques to $ \delta_i $ as well, we obtain $ \hat{V}_i = \hat{\tilde{V}}_i $ for all $ \delta_i \in \Delta $, too. As a side note,

follows, where the constraints from $ {\mathrm{CSP}}^+(\Delta_1) $ do not mention impact factors of conditionals from $ \Delta_2 $ and vice versa.

Now, for $ \delta_i \in \Delta $, let $ \eta_i $ be the impact factor of the minimal core c-representation of $ \Delta $ and, for $ \delta_i \in \Delta_1 $, let $ \tilde{\eta}_i $ be the impact factor of the minimal core c-representation of $ \Delta_1 $. It remains to show $ \eta_i = \tilde{\eta}_i $. According to Definition 11 and Proposition 9, we have

Thus, $ \sigma(\Delta)|_{\Delta_1} = \sigma(\Delta_1) $ holds. For reasons of symmetry, the derivations above also hold when replacing $ \Delta_1 $ with $ \Delta_2 $, implying $ \sigma(\Delta_2) = \sigma(\Delta)|_{\Delta_2} $ and thus completing the proof. □

In contrast to c-core closure and skeptical c-inference, System P and System Z inference do not satisfy (CSynSplit) but only (CRel).

Proposition 15. The inductive inference operators $ {\cal{I}}^P $ and $ {\cal{I}}^Z $ satisfy (CRel) but not (CInd), and therefore not (CSynSplit).

Proof. Because $ {\cal{I}}^P $ and $ {\cal{I}}^Z $ do not satisfy (Ind), they neither satisfy (CInd) nor (CsynSplit).

The proof that $ {\cal{I}}^P $ satisfies (CRel) is analogous to the proof that $ {\cal{I}}^P $ satisfies (Rel) in Kern-Isberner et al.^[18]. Suppose $ \Delta_1 \bigcup^s_{\Sigma_1, \Sigma_2} \Delta_2 \mid \Sigma_3 $ is a safe splitting of $ \Delta $. First, we show that $ \Delta $ is consistent if and only if $ \Delta_1 $ and $ \Delta_2 $ are consistent. The only if-direction is clear because $ \Delta $ would be inconsistent if $ \Delta_1 $ or $ \Delta_2 $ is inconsistent as supersets of inconsistent belief bases are inconsistent. Now, assume that $ \Delta_1 $ and $ \Delta_2 $ are consistent. Then, $ \Delta'_1 = \Delta_1 \setminus \Delta_2 $, $ \Delta'_2 = \Delta_2 \setminus \Delta_1 $, and $ \Delta'_3 = \Delta_1 \cap \Delta_2 $ are consistent as well, and, according to Proposition 20 in the study by Beierle et al.^[28], if $ \kappa^{\vec{\eta}_1}_{\Delta'_1} $, $ \kappa^{\vec{\eta}_2}_{\Delta'_2} $, and $ \kappa^{\vec{\eta}_3}_{\Delta'_3} $ are c-representations of $ \Delta'_1 $, $ \Delta'_2 $, and $ \Delta'_3 $, respectively, then $ \kappa^{(\vec{\eta}_1, \vec{\eta}_2, \vec{\eta}_3)}_{\Delta} $ (up to a reindexing of conditionals) is a c-representation of $ \Delta $. Now, let $ i \in \{1,2\} $, let $ A,B \in {\cal{L}}(\Sigma_i) $, and let $ \omega \in \Omega(\Sigma_3) $. Then $ A \omega |\!\!\!\sim ^P_\Delta \!\! B $ is equivalent to $ \Delta \cup \{({\overline B }|A\omega)\} $ being inconsistent (cf.^[13]), which again is equivalent to $ \Delta_i \cup \{({\overline B }|A\omega)\} $ being inconsistent because $ ({\overline B }|A\omega) $ cannot be inconsistent with $ \Delta_j $, $ j \in \{1,2\} $, $ j \neq i $, due to the safeness property (6). Thus, $ A\omega |\!\!\!\sim ^P_\Delta \!\! B $ is equivalent to $ A\omega |\!\!\!\sim ^P_{\Delta_i} \!\! B $.

Also the proof that $ {\cal{I}}^Z $ satisfies (CRel) is analogous to the proof that $ {\cal{I}}^Z $ satisfies (Rel) reported in the study by Kern-Isberner et al.^[18]. The crucial point is that a conditional $ \delta \in \Delta_i $, $ i \in \{1,2\} $, is tolerated by a subbase $ \Delta' $ of $ \Delta $ if and only if it is tolerated by the intersection $ \Delta' \cap \Delta_i $ because each possible world $ \omega_i \in \Omega(\Sigma(\Delta_i)) $ can be extended to a possible world $ \omega \in \Omega(\Sigma) $ such that no conditional from $ \Delta' \setminus \Delta_i $ is falsified which is due to the safeness property (6). This implies that the partitioning sets of the Z-partition of $ \Delta $ are unions of the partitioning sets of the Z-partitions of the subbases $ \Delta_1 $ and $ \Delta_2 $ (note that due to the safeness property (6) all conditionals $ \delta \in \Delta_1\cap\Delta_2 $ are tolerated by $ \Delta $ and, hence, are tolerated in the lowest partitioning set of both the Z-partition of $ \Delta_1 $ as well as the Z-partition of $ \Delta_2 $). Therefore, for $ \delta \in \Delta_i $, we have $ Z_\Delta(\delta) = Z_{\Delta_i}(\delta) $, $ i \in \{1,2\} $, and it is straightforward to check that $ \kappa^Z_{\Delta_i} = \kappa^Z_\Delta|\Sigma_i $. □

Like System Z and skeptical c-inference, c-core closure violates (SM) (cf. Example 10). With weak semi-monotony (wSM), we propose a novel variant of (SM) which coincides with (SM) for the special case $ A = \top $ and which is satisfied by c-core closure:

$ {\bf{(wSM)}} $ $ \top |\!\!\!\sim ^{\cal{I}}_\Delta \!\! B $ and $ \Delta \subseteq \Delta' $ implies $ \top |\!\!\!\sim ^{\cal{I}}_{\Delta'} \!\! B $.

Proposition 16. Like System P, System Z, and skeptical c-inference, c-core closure satisfies both (CP) (cf. Section 2), and (wSM).

Proof. $ \underline{({\rm{CP}}):}$ In case of System P, the proposition becomes trivial. Now, let $ {\cal{I}} $ be either $ {\cal{I}}^Z $, $ {\cal{I}}^c $, or $ {\cal{I}}^{mc} $. For a ranking model $ \kappa $ of $ \Delta $, we have $ A |\!\!\!\sim _\kappa \bot $ if and only if $ \kappa(\bot) \lt \kappa(A) $ or $ \kappa(A) = \infty $ by definition. Because $ \infty = \kappa(\bot) \lt \kappa(A) $ is always false, $ A |\!\!\!\sim _\kappa \bot $ if and only if $ \kappa(A) = \infty $ follows. Further, because c-representations as well as the System Z ranking model assign finite ranks to formulas $ A $ that are satisfiable, $ A \equiv \bot $ must hold. Hence, if $ A |\!\!\!\sim _\Delta^X \bot $ for $ X \in \{ Z, c, mc\} $, then $ A \equiv \bot $. Because $ \bot |\!\!\!\sim _\kappa \bot $ for all ranking models $ \kappa $ of $ \Delta $ due to $ \kappa(\bot) = \infty $, $ \bot |\!\!\!\sim _\Delta^P \bot $ (resp. $ A |\!\!\!\sim _\Delta^P \bot $) follows. The other way around, from $ A |\!\!\!\sim _\Delta^P \bot $ it follows that $ \bot |\!\!\!\sim _\kappa A $ for all ranking models $ \kappa $ of $ \Delta $ and, thus, also for all c-representations and the System Z ranking model of $ \Delta $ from which $ A |\!\!\!\sim _\Delta^X $ for $ X \in \{ Z, c, mc\} $ follows.

$ \underline{({\rm{wSM}}):}$ In case of System P, (wSM) directly follows from the fact that System P satisfies the stronger postulate (SM). Now, let $ {\cal{I}} $ be either $ {\cal{I}}^Z $, $ {\cal{I}}^c $, or $ {\cal{I}}^{mc} $. For a ranking model $ \kappa $ of $ \Delta $, we have $ \top |\!\!\!\sim _\kappa \!\! B $ if and only if $ \kappa(B) \lt \kappa({\overline B }) $ which implies $ 0 \lt \kappa({\overline B }) $. That is, all models $ \omega $ of $ {\overline B } $ falsify at least one conditional in $ \Delta $, say $ \delta_{i_\omega} $. This remains true if $ \Delta $ is enlarged to $ \Delta' $. Then in case of System Z,

and in case of c-core closure,

Hence, in both cases $ \kappa^X_{\Delta'}({\overline B }) \gt 0 $ ($ X \in \{Z, mc\} $) and, necessarily, $ \kappa^X_{\Delta'}(B) = 0 $ so that $ \top |\!\!\!\sim _{\Delta'}^X \!\! B $ follows. The argumentation for skeptical c-inference is a bit more sophisticated because we have to show that for general c-representations $ \eta_{i_\omega} \gt 0 $ holds. Assume that for all $ \omega \in \Omega(\Sigma) $ with $ \omega \models {\overline B } $ and for all $ \delta_i \in {\mathrm{fal}}_{\Delta'}(\omega) $, $ \eta_i = 0 $ would be true. Then, because of (3), necessarily

However, there is $ S = {\mathrm{fal}}_{\Delta'}(\omega) \setminus \{\delta_i\} $ in $ F_i $ for which $ \sum\nolimits_{\delta_j \in S} \eta_j = 0 $ holds by assumption. Therewith, $ \min\{\sum\nolimits_{\delta_j \in S} \eta_j \mid S \in F_i\} = 0 $ follows. Consequently,

which is a contradiction. Thus, $ \top |\!\!\!\sim ^c_{\Delta'} \!\! B $ also holds. □

Proposition 16 states, among others, that the System Z ranking model and c-representations maintain most plausible beliefs when $ \Delta $ is extended. That is, in terms of the minimal core c-representation, if $ \Delta \subseteq \Delta' $, then $ {\mathrm{Bel}}(\kappa^{mc}_{\Delta}) \subseteq {\mathrm{Bel}}(\kappa^{mc}_{\Delta'}) $.

Example 10. We consider the belief bases $ \Delta_{{\mathrm{ex}}3} = \{ \delta_1, \delta_2 \} $ and $ \Delta'_{{\mathrm{ex}}3} = \Delta_{{\mathrm{ex}}3} \cup \{ \delta_3 \} $ with

Then (cf. Table 4),

so that the minimal core c-representations are given by the impact vectors $ \vec{\eta}^{\,mc}_{\Delta_{{\mathrm{ex}}3}} = (1,1) $ and $ \vec{\eta}^{\,mc}_{\Delta'_{{\mathrm{ex}}3}} = (2,1,2) $, respectively. The c-representations themselves are shown in Table 4. While $ a |\!\!\!\sim ^{mc}_{\Delta_{{\mathrm{ex}}3}} c $ holds because of $ \kappa^{mc}_{\Delta_{{\mathrm{ex}}3}}(ac) = 0 \lt 1 = \kappa^{mc}_{\Delta_{{\mathrm{ex}}3}}(a{\overline c }) $, we have because of $ \kappa^{mc}_{\Delta'_{{\mathrm{ex}}3}}(ac) = 2 \gt 1 = \kappa^{mc}_{\Delta_{{\mathrm{ex}}3}}(a{\overline c }) $ (even $ a |\!\!\!\sim ^{mc}_{\Delta'_{{\mathrm{ex}}3}} {\overline c } $ holds) which proves that $ {\cal{I}}^{mc} $ does not satisfy (SM) in general. However, for the most plausible beliefs, we have

where, $ {\mathrm{Cn}}(A) $ is the deductive closure of $ A \in {\cal{L}}(\Sigma) $, which is in compliance with (wSM).

Eventually, we note that c-core closure satisfies weak rational monotony (wRM), and also rational monotony (RM) (cf.^[29]). This is worth mentioning because it distinguishes c-core closure from skeptical c-inference which satisfies (wRM) but violates (RM).

Proposition 17. c-Core closure satisfies rational monotony (RM) and, therewith, also weak rational monotony (wRM).

Proof. Because each ranking model satisfies (RM)^[14], this also holds for $ \kappa^{mc}_\Delta $ from which the satisfaction of (RM) and also of (wRM) for $ {\cal{I}}^{mc} $ follows. □

Note that System P inference does not satisfy (wRM) as the next example shows.

Example 11. Let $ \Delta_{{\mathrm{ex}}4} = \{(b|\top)\} $. Then, $ \top |\!\!\!\sim ^P_{\Delta_{{\mathrm{ex}}4}} b $ holds due to (DI), and the ranking model $ \kappa $ of $ \Delta_{{\mathrm{ex}}4} $ with

proves that holds, too. However, holds because of the model $ \kappa' $ of $ \Delta_{{\mathrm{ex}}4} $ with

for instance.

Table 5 gives an overview of the inference properties which are satisfied or violated by the inference formalisms mentioned in this article. It shows that c-core closure differs from all the other inference formalisms w.r.t. its properties. We demonstrate this by revisiting the Tweety example from the beginning.

Example 12. We extend the Tweety example from Example 1 by the conditional $ \delta_4 = (e|b) $ ('birds usually have beaks'), and consider the belief base $ \Delta_{\mathrm{bfpe}} = \{ \delta_1, \ldots, \delta_4 \} $ with

over the signature $ \Sigma = \{ b, f, p, e\} $. Table 6 shows which conditionals are verified and falsified in the possible worlds in $ \Omega(\Sigma) $ from which the (reduced) constraint inducing sets of $ \Delta_{\mathrm{bfpe}} $ are derived (Table 7). The Z-partition of $ \Delta_{\mathrm{bfpe}} $ is $ Z(\Delta_{\mathrm{bfpe}}) = (\Delta_1, \Delta_2) $ with $ \Delta_1 = \{ \delta_2, \delta_4 \} $ (mentioning the general beliefs about birds) and $ \Delta_2 = \{ \delta_1, \delta_3 \} $ (mentioning the more specific beliefs about penguins). Hence, according to our definition, the Z-ranks of the conditionals in $ \Delta_{\mathrm{bfpe}} $ are $ (Z(\delta_1), \ldots, Z(\delta_4)) = (2, 1, 2, 1) $, and the corresponding System Z ranking model $ \kappa^Z_{\Delta_{\mathrm{bfpe}}} $ of $ \Delta_{\mathrm{bfpe}} $ is shown in Table 6. Further, in this example, the canonical generalized tolerance partition of $ \Delta_{\mathrm{bfpe}} $ coincides with the Z-partition and the impact vector of the minimal core c-representation is also $ \vec{\eta}^{\, mc}_{\Delta_{\mathrm{bfpe}}} = (2, 1, 2, 1) $. (The constraint satisfaction problem $ {\mathrm{CSP}}(\Delta_{\mathrm{bfpe}}) $ equals $ {\mathrm{CSP}}^\wedge(\Delta_{\mathrm{bfpe}}) $ and is given by $ \eta_1 \gt \min\{ \eta_2, \eta_3\} $ and $ \eta_2 \gt 0 $ and $ \eta_3 \gt \min\{\eta_1, \eta_2\} $ and $ \eta_4 \gt 0 $.) However, the minimal core c-representation $ \kappa^{mc}_{\Delta_{\mathrm{bfpe}}} $ of $ \Delta_{\mathrm{bfpe}} $ differs from the System Z ranking model as the impact values are processed differently from the Z-ranks (they are summed up instead of maximized; cf. Table 6). Table 6 further shows another c-representation $ \kappa^{\vec{\eta}}_{\Delta_{\mathrm{bfpe}}} $ of $ \Delta_{\mathrm{bfpe}} $ which is induced by $ \vec{\eta} = (2,1,2,4) $.

Because $ \kappa^Z_{\Delta_{\mathrm{bfpe}}}(pe) = 1 \not< 1 = \kappa^Z_{\Delta_{\mathrm{bfpe}}}(p{\overline e }) $, one has which proves that System Z suffers from the drowning problem (birds do not inherit having beaks to penguins because penguins are exceptional birds). An immediate consequence is that also in System P the conditional $ (e|p) $ cannot be inferred from $ \Delta_{\mathrm{bfpe}} $ and the drowning problem is present there, too. In contrast, $ \kappa^{mc}(pe) = 1 \lt 2 = \kappa^{mc}(p{\overline e }) $ and $ \Delta_{\mathrm{bfpe}} |\!\!\!\sim ^{mc} (e|p) $. illustrating that c-core closure does not suffer from the drowning problem. The same can be shown for skeptical c-inference. Nevertheless, c-core closure differs also from skeptical c-inference. For instance, $ \Delta_{\mathrm{bfpe}} |\!\!\!\sim ^{mc} (b|(b \lor p)f{\overline e }) $ ('if an individual is a bird or a penguin, can fly, and has no beak, then it is usually a bird') because $ \kappa^{mc}(bf{\overline e }) = 1 \lt 4 = \kappa^{mc}({\overline b }fp{\overline e }) $, but because $ \kappa^{\vec{\eta}}(bf{\overline e }) = 4 \not< 4 = \kappa^{\vec{\eta}}({\overline b }fp{\overline e }) $ w.r.t. $ \vec{\eta} = (2,1,2,4) $, and the inference has to hold for all c-representations to ensure skeptical c-inference.

At this point, it is worth noting that the satisfaction of inference properties is not inherently desirable; rather, their value depends on the application. For example, semi-monotony can be seen as a very strong property of a nonmonotonic inference operator that may be advantageous in some contexts, but undesirable in others.

In the study by Casini et al.^[23], inference relations which satisfy System P, (RM), and (CP) are called basic defeasible entailment relations. Therefore, c-core closure can be classified as a basic defeasible entailment operator. In summary, c-core closure benefits from the simple structure of the minimal core c-representations which are stratified like System Z while it inherits beneficial properties from the more complex framework of general c-reasoning.

In the light of minimal core c-representations, the transformation rules R1–R6, which help simplify the constraint satisfaction problems induced by c-representations, appear to be relevant even from a structural point of view. First, rules R3–R5 remove irrelevant dependencies among the conditionals before pruning the $ F_i $-part of the constraints for defining core c-representations (see Example 5 and the remarks afterwards). Note that R2 is also indirectly relevant here because it may remove irrelevant information from the $ F_i $-part of the constraint satisfaction problems before applying the other rules. Second, rules R1 and R6 anticipate the aim of minimizing $ \phi_{{\cal{Q}}_{\vec{\eta}}(\Delta)}^{\vec{\eta}}(\delta_l) $ in (11) when constructing the canonical generalized tolerance partition. This means that the minimization process in (11) can be considered as a general extension of R1 and R6 that is able to take also numerical (not only structural, like R1 and R6) peculiarities of the minimization process into account. In summary, after applying R1–R6 exhaustively, the information contained in the reduced constraint inducing sets $ \hat{V}_i $ and $ \hat{F}_i $ can be considered to be particularly relevant for constructing (core) c-representations.

Core c-representations $ \kappa^{\vec{\eta},c}_\Delta $ are positive in the sense that $ \eta_i \gt 0 $ for $ i \in [n] $ holds (cf. Proposition 3). This means that every conditional in $ \Delta $ has a significant impact on $ \kappa^{\vec{\eta},c}_\Delta $. However, there might be cases in which impact factors $ \eta_i = 0 $ are reasonable. This is the case when there are 'redundant' conditionals in $ \Delta $ where it appears to be debatable if they should increase implausibility ranks additionally, like in the next example.

Example 13. We consider the belief base $ \Delta_{{\mathrm{ex}}5} = \{ (c|a), (c|ab), (c|a{\overline b }) \} $. Then, $ {\mathrm{CSP}}(\Delta_{{\mathrm{ex}}5}) $ consists of the constraints

and has the pareto-minimal solutions $ (1,0,0) $ and $ (0,1,1) $ (cf. Table 8), yielding the same c-representation $ \kappa_{\Delta_{{\mathrm{ex}}5}} $. If we look at Table 8, then we see that only the possible worlds $ ab{\overline c } $ and $ a{\overline b }{\overline c } $ are penalized, either by $ \eta_1 + \eta_2 $ or by $ \eta_1 + \eta_3 $. This and the fact that $ (0,1,1) $ is a non-negative integer solution of $ {\mathrm{CSP}}(\Delta_{{\mathrm{ex}}5}) $ can be interpreted as $ \delta_1 $ being redundant because the penalization by $ \eta_1 $ can be mimicked by the impact factors $ \eta_2 $ and $ \eta_3 $, so that $ \delta_1 $ could be removed from $ \Delta_{{\mathrm{ex}}5} $ without altering the set of c-representations. The minimal core c-representation of $ \Delta_{{\mathrm{ex}}5} $ is characterized by $ \vec{\eta}^{\,mc}_{\Delta_{{\mathrm{ex}}5}} = (1,1,1) $ which penalizes $ ab{\overline c } $ and $ a{\overline b }{\overline c } $ seemingly unnecessarily twice, though.

Example 13 suggests to remove redundant conditionals from belief bases before performing core c-reasoning. However, clarifying what 'redundant' means, besides the semantical equivalent conditionals which we already excluded in this paper, is a hard problem in general. For instance, in Example 13, it is not easy to decide which of the conditionals are in fact redundant. For building up the c-representation $ \kappa_{\Delta_{{\mathrm{ex}}5}} $, both $ \{(c|a)\} $ and $ \{(c|ab), (c|a{\overline b })\} $ would be enough. $ \{(c|a)\} $ could be preferred if one is interested primarily in general, abstract beliefs, while $ \{(c|ab), (c|a{\overline b })\} $ expresses more detailed beliefs. If beliefs have to be changed, differences become even more apparent. Assume that in Example 13, the agent wants to change her beliefs by adopting the conditional $ ({\overline c }|ab) $. For the belief base $ \{(c|a)\} $, integrating this exception is easily done, a classical case of nonmonotonic reasoning. However, the belief base $ \{(c|ab), (c|a{\overline b }\} $ faces a plain contradiction between $ (c|ab) $ and $ ({\overline c }|ab) $ if explicit beliefs are considered. This might require deeper contemplations how exactly this revision should be done. For more intense discussions and technical approaches for handling such cases, cf.^[32].

As an alternative, in the study by Goldszmidt et al.^[33] the authors define a subclass of belief bases, the so-called minimal core sets, which exclude belief bases $ \Delta $ where $ \eta_i=0 $ for conditionals $ \delta_i \in \Delta $ is possible.

Definition 16 (Minimal Core Set^[33]). A consistent belief base $ \Delta $ is a minimal core set if for every conditional $ (B|A) \in \Delta $ its negation $ ({\overline B }|A) $ is tolerated by $ \Delta \setminus \{(B|A)\} $ or, equivalently, if for every $ (B|A) \in \Delta $ there is a possible world which falsifies $ (B|A) $ but no other conditional from $ \Delta $.

In other words, $ \Delta $ is a minimal core set if and only if $ \emptyset \in F_i $ for $ i \in [n] $. An example of a minimal core set is the belief base $ \Delta_{\mathrm{bfpe}} $ in Example 12. For minimal core sets, (4) coincides with (7) and we have the following proposition.

Proposition 18. Let $ \Delta $ be a minimal core set. Then $ \kappa^{\vec{\eta}}_\Delta $ is a c-representation of $ \Delta $ if and only if it is a core c-representation of $ \Delta $. Consequently, $ \Delta $ has a unique minimal c-representation, namely the minimal core c-representation $ \kappa^{mc}_\Delta $.

Proof. Because for minimal core sets $ \Delta $ (4) coincides with (7), a ranking model of $ \Delta $ is a c-representation of $ \Delta $ if and only if it is a core c-representation of $ \Delta $. As $ \kappa^{mc}_\Delta $ is minimal among all core c-representations of $ \Delta $ it directly follows that $ \kappa^{mc}_\Delta $ is also minimal among all c-representations of $ \Delta $ in this case. □

Minimal core sets do not precisely characterize the belief bases which enforce the impact factors to be positive, though, and, conversely, not all belief bases which allow for non-positive impact factors automatically involve 'redundant' conditionals (cf. Example 5 in the study by Goldszmidt et al.^[33]). Thus, a thorough investigation of this issue remains for future work.

The main topic of the study by Goldszmidt et al.^[33] is the derivation of a ranking model $ \kappa^\ast $ of a consistent belief base $ \Delta $ from the $ \epsilon $-semantics^[34] of conditionals, and the principle of maximum entropy^[35] from probability theory. The basic idea is to consider a set of parameterized probability distributions $ \{{\cal{P}}^\ast_\epsilon \} $ over $ \Omega(\Sigma) $ with parameter $ \epsilon \gt 0 $ where each distribution $ {\cal{P}}^\ast_\epsilon $ is an $ \epsilon $-model of $ \Delta $, i.e., it satisfies $ {\cal{P}}^\ast_\epsilon(B_i|A_i) \geq 1 - \epsilon $ for $ i \in [n] $, and maximizes the entropy $ {\cal{H}}({\cal{P}}_\epsilon) = - \sum\nolimits_{\omega\in\Omega(\Sigma)} {\cal{P}}_\epsilon(\omega) \cdot \log {\cal{P}}_\epsilon(\omega) $ among all $ \epsilon $-models $ {\cal{P}}_\epsilon $ of $ \Delta $. Then, $ \kappa^* $ is the ranking model of $ \Delta $ which satisfies $ A |\!\!\!\sim _{\kappa^*} \!\! B $ if and only if $ \lim_{\epsilon \to 0} {\cal{P}}^\ast_\epsilon(B|A) = 1 $. Goldszmidt et al.^[33] study this ranking model, especially for minimal core sets $ \Delta $, and it turns out that $ \kappa^\ast $ is given by $ \kappa^\ast(\omega) = \sum\nolimits_{\delta_i \in {\mathrm{fal}}_\Delta(\omega)} Z^\ast(\delta_i) $, where $ Z^\ast(\delta_i) = \min_{\omega \in {\mathrm{ver}}(\delta_i)} \kappa^\ast(\omega) + 1 $ in this case (cf. (18) and (19) in Goldszmidt et al.^[33]). This coincides with the definition of minimal core c-representations provided that no constraint reduction is applied (cf. Definition 11). This is not by coincidence. Actually, both maximum entropy distributions and c-representations rely crucially on the principle of conditional preservation^[2] that determines their structure. While $ \kappa^\ast $ in the study by Goldszmidt et al.^[33] originates from considering limits in probability theory, c-representations make a shortcut here by building upon the principle of conditional preservation for ranking functions directly. Hence, c-representations in general and minimal core c-representations in particular generalize the ranking model $ \kappa^\ast $ from the study by Goldszmidt et al.^[33] to arbitrary consistent belief bases and fully embed it into the theory of c-representations so that we provide a more convenient access to $ \kappa^\ast $ without the need to consider its probabilistic background.

With core c-representations we identified a subclass of c-representations which constitute a family of ranking models of symbolic conditional belief bases with particularly good inference behavior. Core c-representations are easier to compute than general c-representations as the underlying constraint satisfaction problem is stratified while the constraint satisfaction problems of general c-representations may involve cyclic dependencies. As a consequence, core c-representations provide a unique minimal ranking model of a conditional belief base, which makes it possible to define a novel, model-based inference operator that selects for each consistent belief base its minimal core c-representation. We prove that this c-core closure inference operation constitutes a basic defeasible entailment operator according to the study by Casini et al.^[23], and differs from System P inference, System Z inference, as well as skeptical c-inference. c-Core closure inference synergizes all good properties of c-representations, complies with conditional syntax splitting, and avoids the drowning problem, while also satisfying rational monotony (RM) and implementing the idea of minimality, i.e., maximal plausibility, in a unique way, for the first time.

In future work, we want to investigate to what extent ideas from the construction of the minimal core c-representation can be transferred to the computation of general c-representations. We would also like to investigate complexity issues, and the question whether there is an axiomatization of c-core closure. A further research direction is to analyze how core c-representations behave under belief change, especially (iterated) belief revision, and we are also interested in a comparison of c-core closure with other inference formalisms that have proven to be inferentially strong such as lexicographic entailment^[36,37], and System W^[38,39].