A Practical Comparison of Qualitative Inferences with Preferred Ranking Models

Abstract

When reasoning qualitatively from a conditional knowledge base, two established approaches are system Z and p-entailment. The latter infers skeptically over all ranking models of the knowledge base, while system Z uses the unique pareto-minimal ranking model for the inference relations. Between these two extremes of using all or just one ranking model, the approach of c-representations generates a subset of all ranking models with certain constraints. Recent work shows that skeptical inference over all c-representations of a knowledge base includes and extends p-entailment. In this paper, we follow the idea of using preferred models of the knowledge base instead of the set of all models as a base for the inference relation. We employ different minimality constraints for c-representations and demonstrate inference relations from sets of preferred c-representations with respect to these constraints. We present a practical tool for automatic c-inference that is based on a high-level, declarative constraint-logic programming approach. Using our implementation, we illustrate that different minimality constraints lead to inference relations that differ mutually as well as from system Z and p-entailment.

1 Introduction

In the area of knowledge representation and reasoning, rules play a prominent role, especially default rules of the form “If A then usually/normally/preferably B”. Sets of such rules, so called knowledge bases, are used to represent the knowledge of a reasoning agent, and the inference relation of the agent depends on this knowledge. A knowledge base usually is incomplete to such an extent that it contains all conditional rules relevant to the agent, but it usually does not contain enough information to represent all preferences, beliefs, and assumptions of the agent, that is, an epistemic state in the sense of [11]. Here, inductive methods come into play that construct a model of the knowledge base. Such models can be representations from various formalisms, encoding, for instance, the probability [20], the (im-)possibility [8], or the (im-)plausibility [22, 23] of the possible worlds. Based on these models that inductively complete the knowledge given explicitly by the rules of a knowledge base, corresponding inductive inference relations can be constructed.

In this paper, we focus on models based on plausibility as defined by Ordinal Conditional Functions [22, 23] (OCF, also known as ranking functions). Established approaches of inductive inference using OCF include the skeptical inference over all ranking models of a knowledge base, known as p-entailment [9], and the inference with the unique, with respect to ranks of worlds, pareto-minimal OCF with this property, known as System Z [21].

In [12, 13] a criterion when a ranking function respects the conditional structure of a set ${\mathcal{R}}$ of conditionals is defined, leading to the notion of c-representation for ${\mathcal{R}}$, and it is argued that ranking functions defined by c-representations are of particular interest for model-based inference. It has been shown that reasoning inductively with a single c-representation yields an inference relation of high quality (cf., e.g., [14, 24]). Recent work also shows that the skeptical inference over all c-representations (called c-inference) includes and extends p-entailment [2]. To define the inference relation, in this paper, we follow the idea of [18] as well as [21] by using a set of preferred models of the knowledge base ${\mathcal{R}}$ instead of using of the set of all models. We employ different minimality constraints for c-representations and demonstrate inference relations from sets of preferred c-representations with respect to these constraints.

The main objective of this paper is to present and illustrate these inference relations and to provide a practical tool for automatic inference and for comparison of the inference results. For this tool, we employ the observation that the definition of c-representations as solutions of a constraint satisfaction problem $CR ({\mathcal{R}})$ (see [2, 4]) allows to implement c-representations in a high-level, declarative approach using constraint logic programming techniques. In particular, this approach also supports the generation of all minimal solutions, providing a preferred basis for model-based inference from ${\mathcal{R}}$; previously, no other implementation of minimal c-inference has been available.

This article is a revised and largely extended version of [4]. In particular, in this paper we add the comparison to system Z and to p-entailment, extend and refine the notions of minimality, introduce corresponding inferences relations, and present a newly developed implementation for computing and comparing different inference relations.

The rest of this paper is organized as follows: After recalling the formal background of conditional logics as far as it is needed here (Sect. 2), we elaborate an illustration for a conditional knowledge base and discuss resulting inference relations based on OCFs in Sect. 3. In Sect. 4, we recall the inductive approaches of System Z and c-representations and present the constraint satisfaction problem $CR ({\mathcal{R}})$ whose solutions are computed by the declarative, high-level CLP program GenOCF (Sect. 5). Section 6 introduces three different notions of minimality for c-representations, and, in Sect. 7, an implementation of the corresponding inference relations based on GenOCF is presented. Section 8 concludes the paper and points out further work.

2 Background

We start with a propositional language ${\mathcal{L}}$, generated by a finite set $\Sigma$ of atoms $a,b,c, \ldots$. The formulas of ${\mathcal{L}}$ will be denoted by uppercase Roman letters $A,B,C, \ldots$. For conciseness of notation, we will omit the logical and-connective, writing AB instead of $A \wedge B$, and overlining formulas will indicate negation, i.e. $\overline{A}$ means $\lnot A$. Let $\Omega$ denote the set of possible worlds over ${\mathcal{L}}$; $\Omega$ will be taken here simply as the set of all propositional interpretations over ${\mathcal{L}}$ and can be identified with the set of all complete conjunctions over $\Sigma$. For $\omega \in \Omega$, $\omega \models A$ means that the propositional formula $A \in {\mathcal{L}}$ holds in the possible world $\omega$.

By introducing a new binary operator |, we obtain the set ${({\mathcal{L}}\mid {\mathcal{L}})}= \{ (B|A) \mid A,B \in {\mathcal{L}}\}$ of conditionals over ${\mathcal{L}}$. $(B | A)$ formalizes the conditional rule “if A then (normally) B” and establishes a plausible, probable, possible etc. connection between the antecedent A and the consequence B. Here, conditionals are supposed not to be nested, that is, antecedent and consequent of a conditional will be propositional formulas.

A conditional $(B|A)$ is an object of a three-valued nature, partitioning the set of worlds $\Omega$ in three parts: those worlds satisfying AB, thus verifying the conditional, those worlds satisfying $A\overline{B}$, thus falsifying the conditional, and those worlds not fulfilling the premise A and so which the conditional may not be applied to at all. This allows us to represent $(B|A)$ as a generalized indicator function going back to [7] (where u stands for unknown or indeterminate):

$$ (B|A)(\omega) = \left\{ \begin{array}{lll} 1 &\quad \text{if} & {\omega \models AB} \\ 0 &\quad \text{if} & {\omega \models A \overline{B}} \\ u &\quad {\text{if}} & {\omega \models \overline{A}} \end{array} \right. $$

(1)

To give appropriate semantics to conditionals, they are usually considered within richer structures such as epistemic states [11]. Besides certain (logical) knowledge, epistemic states also allow the representation of preferences, beliefs, assumptions of an intelligent agent. Basically, an epistemic state allows one to compare formulas or worlds with respect to plausibility, possibility, necessity, probability, etc.

Well-known qualitative, ordinal approaches to represent epistemic states are Spohn’s ordinal conditional functions, OCFs, (also called ranking functions) [22], and possibility distributions [6], assigning degrees of plausibility, or of possibility, respectively, to formulas and possible worlds. In such qualitative frameworks, a conditional (B|A) is valid (or accepted), if its confirmation, AB, is more plausible, possible, etc. than its refutation, ${A\overline{B}}$; a suitable degree of acceptance is calculated from the degrees associated with AB and ${A\overline{B}}$.

In this paper, we consider Spohn’s OCFs [22]. An OCF is a function

$$\begin{aligned} \kappa :\Omega \rightarrow {\mathbb {N}_0} \end{aligned}$$

expressing degrees of plausibility of propositional formulas where a higher degree denotes “less plausible” or “more suprising”. At least one world must be regarded as being normal (or maximally plausible or unsurprising); therefore, $\kappa (\omega ) = 0$ for at least one $\omega \in \Omega$. Each OCF can be taken as the representation of a full epistemic state of an agent. Each such $\kappa$ uniquely extends to a function (also denoted by $\kappa$) mapping sentences and rules to $\mathbb {N} \cup \{\infty \}$ and being defined by

$$\begin{aligned} \begin{array}{lll} \kappa (A) & = & {\left\{ \begin{array}{ll} \min \{\kappa (\omega ) \mid \omega \models A\} &\quad {\text{if }} A {\text{ is satisfiable}} \\ \infty &\quad \text{otherwise}\\ \end{array}\right. } \end{array} \end{aligned}$$

(2)

for sentences $A \in {\mathcal{L}}$ and by

$$\begin{aligned} \begin{array}{lll} \kappa ((B|A)) & = & {\left\{ \begin{array}{ll} {\kappa (AB)} - {\kappa (A)} &\quad {\text{if }} \kappa (A) \not = \infty \\ \infty &\quad {\text{otherwise}}\\ \end{array}\right. } \end{array} \end{aligned}$$

(3)

for conditionals $(B|A) \in {({\mathcal{L}}\mid {\mathcal{L}})}$. Note that $\kappa ((B|A)) \geqslant 0$ since any $\omega$ satisfying AB also satisfies A and therefore $\kappa (AB) \geqslant \kappa (A)$.

The belief of an agent being in epistemic state $\kappa$ with respect to a default rule $(B|A)$ is determined by the satisfaction relation $\, {\models }_{\mathcal{O}} \,$ defined by:

$$\begin{aligned} \kappa \, {\models }_{\mathcal{O}} \, (B|A)\quad \text{ iff } \quad\kappa (AB) < \kappa (A\overline{B}) \end{aligned}$$

(4)

Thus, $(B|A)$ is believed in $\kappa$ iff the rank of AB (verifying the conditional) is strictly smaller than the rank of $A\overline{B}$ (falsifying the conditional). We say that $\kappa$ accepts the conditional $(B|A)$ iff $\kappa \, {\models }_{\mathcal{O}} \, (B|A)$.

We call a conditional $(B|A)$ with $A \models B$ self-fulfilling since it can not be falsified by any world. Obviously, such conditionals are meaningless from a modeling point of view, and we will not consider them in the following. A set ${\mathcal{R}}\subseteq ({\mathcal{L}}|{\mathcal{L}})$ of conditionals is called a knowledge base if it does not contain any self-fulfilling conditional. An OCF $\kappa$ accepts a knowledge base if and only if $\kappa$ accepts all conditionals in ${\mathcal{R}}$; such an OCF is called a (ranking) model of ${\mathcal{R}}$. A knowledge base ${\mathcal{R}}$ is consistent iff a ranking model of ${\mathcal{R}}$ exists [21].

3 Inference and the Drowning Problem

In order to illustrate the concepts presented in the previous section, we will use a scenario involving a set of some default rules representing common-sense knowledge.

Example 1

(${\mathcal{R}}_{ pen }$) Suppose we have the propositional atoms: f—flying, b—birds, p—penguins, w—winged animals, k—kea. Let the set ${\mathcal{R}}_{ pen }$ consist of the following conditionals:

$$\begin{array}{lll} r_1 : & (f|b) & \textit{birds \,fly}\\ r_2 : & (b|p) & \textit{penguins \,are \,birds}\\ r_3 : & (\overline{f}|p) & \textit{penguins \,do \,not \,fly}\\ r_4 : & (w|b) & \textit{birds \,have \,wings}\\ r_5 : & (b|k) & \textit{kea \,are \,birds}\\ \end{array}$$

Table 1 shows two ranking functions $\kappa$ and $\kappa _{{\mathcal{R}}_{ pen }}^Z$ that accept all conditionals given in ${\mathcal{R}}_{ pen }$. Thus, for any $i \in \{1,2,3,4,5\}$ it holds that $\kappa \, {\models }_{\mathcal{O}} \, r_i$ and $\kappa _{{\mathcal{R}}_{ pen }}^Z\, {\models }_{\mathcal{O}} \, r_i$.

Table 1 Two ranking functions $\kappa$ and $\kappa _{{\mathcal{R}}_{ pen }}^Z(\omega )$ accepting the rule set ${\mathcal{R}}_{ pen }$ given in Example 1

For the conditional $(f|p)$ (“Do penguins fly?”) that is not contained in ${\mathcal{R}}_{ pen }$, we get $\kappa (pf) = \kappa _{{\mathcal{R}}_{ pen }}^Z(pf) = 2$ and $\kappa (p\overline{f})= \kappa _{{\mathcal{R}}_{ pen }}^Z(p\overline{f}) = 1$ and therefore

$$\begin{aligned} \kappa \,\,\,{\models }_{\mathcal{O}}\!\!\!\!\!\!\!/ \,\;\; \, (f|p) \quad \text{and}\quad \kappa _{{\mathcal{R}}_{ pen }}^Z\,\,\,{\models }_{\mathcal{O}}\!\!\!\!\!\!\!/ \,\;\; \, (f|p) \end{aligned}$$

so that the conditional $(f|p)$ is neither accepted by $\kappa$ nor by $\kappa _{{\mathcal{R}}_{ pen }}^Z$. This is in accordance with the behavior of a rational agent believing ${\mathcal{R}}_{ pen }$ since the knowledge base ${\mathcal{R}}_{ pen }$ used for building up $\kappa$ explicitly contains the opposite rule $(\overline{f}|p)$.

On the other hand, for the conditional $(w|k)$ (“Do kea have wings?”) that is also not contained in ${\mathcal{R}}_{ pen }$, we get $\kappa (kw)= \kappa _{{\mathcal{R}}_{ pen }}^Z(kw) = 0$ and $\kappa (k\overline{w})= \kappa _{{\mathcal{R}}_{ pen }}^Z(k\overline{w}) = 1$ and therefore

$$\begin{aligned} \kappa \, {\models }_{\mathcal{O}} \, (w|k)\quad \text{and}\quad \kappa _{{\mathcal{R}}_{ pen }}^Z\, {\models }_{\mathcal{O}} \, (w|k) \end{aligned}$$

i.e., the conditional $(w|k)$ is accepted by $\kappa$ and by $\kappa _{{\mathcal{R}}_{ pen }}^Z$. Thus, from their superclass birds, kea inherit the property of having wings.

For these conditionals, both OCFs show identical behavior. But if we inspect the conditional $(w|p)$ (“Do penguins have wings?”) we obtain $\kappa (pw)=\kappa _{{\mathcal{R}}_{ pen }}^Z(pw)=\kappa _{{\mathcal{R}}_{ pen }}^Z(p\overline{w})=1$, $\kappa (p\overline{w})=2$, and therefore

$$\begin{aligned} \kappa \, {\models }_{\mathcal{O}} \, (w|p)\quad \text{but} \quad \kappa _{{\mathcal{R}}_{ pen }}^Z\,\,\,{\models }_{\mathcal{O}}\!\!\!\!\!\!\!/ \,\;\; \, (w|p). \end{aligned}$$

So reasoning with one model of ${\mathcal{R}}_{ pen }$ yields that penguins have wings, while reasoning with another does not (and neither the opposite, since also $\kappa _{{\mathcal{R}}_{ pen }}^Z\,\,\,{\models }_{\mathcal{O}}\!\!\!\!\!\!\!/ \,\;\; \, (\overline{w}|p)$). This particular case is known as the drowning problem [5]. The knowledge base contains information about penguins being special birds that differ from normal birds in their ability to fly, that is, penguins are exceptional birds with respect to the property of flying. The inference relation induced by $\kappa$ treats penguins as regular birds with respect to every property inherited from being birds, apart from their explicitly stated (exceptional) inability to fly. The inference relation induced by $\kappa _{{\mathcal{R}}_{ pen }}^Z$ treats penguins as exceptional with respect to every property of their superclass bird. So the property of having wings is drowned and not inherited from the superclass.

Any OCF $\kappa$ is a function that induces a total and transitive ordering $\leqslant _\kappa$ on $\Omega$ such that for each pair $\omega ,\omega '\in \Omega$ we have $\omega \leqslant _\kappa \omega '$ if and only if $\kappa (\omega )\leqslant \kappa (\omega ')$, with the strict ordering defined in the usual way, i.e., $\omega <_\kappa \omega '$ if and only if $\omega \leqslant _\kappa \omega '$ and $\omega '\not \leqslant _\kappa \omega$. The set of possible worlds $\Omega$ is finite, so with classical satisfaction $\models$ we hence can define a classical stoppered [18] (or smooth [15]) preferential model $\langle \Omega ,\models ,<_\kappa \rangle$ which, with [18], induces a preferential entailment $\,|\!\!{\sim} \,^\kappa$ as

$$\begin{aligned} A \,|\!\!{\sim} \,^\kappa B \quad \text{ iff }\quad \forall ~\omega ' \models A\overline{B}\quad \!\exists \,\,~\omega \models AB\quad \text{ s.t.}\quad \omega <_\kappa \omega '. \end{aligned}$$

(5)

This is equivalent [14] to defining the relation $\,|\!\!{\sim} \,^\kappa$ by the ranking entailment

$$\begin{aligned} A \,|\!\!{\sim} \,^\kappa B\quad \text{iff}\quad \kappa (AB)&<\kappa (A\overline{B})\quad \text{iff}\quad \kappa \, {\models }_{\mathcal{O}} \, (B|A). \end{aligned}$$

(6)

By definition, $\langle \Omega ,\models ,<_\kappa \rangle$ is a ranked model in the sense of [17], so overall we obtain that $\,|\!\!{\sim} \,^\kappa$ satisfies Adam’s System P [1] and Rational Monotony [17]; among others, [14] further investigates the formal properties of such a ranking entailment. Note that these properties are inherited by any ranking entailment induced by an OCF $\kappa$ via (6), so especially the ones obtained inductively from a conditional knowledge base by means of system Z and c-representations as presented in the following section.

4 Inductive Reasoning

In Sect. 2 we recalled that a knowledge base is consistent if and only if there is a ranking model $\kappa$ for the knowledge base, and Sect. 3 illustrated how to reason with such ranking models. This raises the question how to obtain such a ranking model, if it exists. Also, for any consistent ${\mathcal{R}}$ there may be many different $\kappa$ accepting ${\mathcal{R}}$, each representing a complete set of beliefs with respect to every possible formula A and every conditional $(B|A)$ which we also illustrated in Sect. 3. Thus, every such $\kappa$ inductively completes the knowledge given by ${\mathcal{R}}$. In this section we recall two established inductive approaches, System Z and c-representations.

4.1 System Z

The approach of System Z [21] sets up a ranking model of a knowledge base ${\mathcal{R}}$ by inclusion-maximal partitions of ${\mathcal{R}}$ with respect to the notion of tolerance:

A set of conditionals ${\mathcal{R}}'\subseteq ({\mathcal{L}}|{\mathcal{L}})$ tolerates a conditional $(D|C)$ if and only if there is a world $\omega \in \Omega$ that verifies $(D|C)$ and does not falsify any conditional $(B|A)\in {\mathcal{R}}'$, that is, there is a world $\omega \in \Omega$ such that

$$\begin{aligned} \omega \models {CD}\wedge \bigwedge \limits _{(B|A)\in {\mathcal{R}}'}(\overline{A}\vee B). \end{aligned}$$

For each knowledge base ${\mathcal{R}}$, Algorithm 1 [21] calculates the unique inclusion-maximal ordered list $\langle {\mathcal{R}}_0,{\mathcal{R}}_1,...{\mathcal{R}}_k\rangle$ of partitions ${\mathcal{R}}=\bigcup _{i=0}^k{\mathcal{R}}_i$, ${\mathcal{R}}_i\cap {\mathcal{R}}_j=\emptyset$ for each $0\leqslant i,j\leqslant k$, $i\ne j$, such that each conditional in a partition ${\mathcal{R}}_i$ is tolerated by the union $\bigcup _{j=i}^k{\mathcal{R}}_j$.

We define by $Z:({\mathcal{L}}|{\mathcal{L}})\rightarrow \mathbb {N}_0$ the function that assigns to each conditional $(B|A)\in {\mathcal{R}}$ the number i of the partition such that $(B|A)\in {\mathcal{R}}_i$. With this function the System Z ranking function $\kappa _{\mathcal{R}}^Z$ is defined as [21]

$$\begin{aligned} \kappa _{{\mathcal{R}}}^Z(\omega )&\!=\!\left\{ \begin{array}{ll} 0&\quad \text{iff}\quad \omega \text{~does not falsify any~} (B|A)\in {\mathcal{ R}}\\ \max \limits _{(B|A)\in {\mathcal{R}}}\{Z((B|A))|\omega \models A\overline{B}\}+1& \quad \text{otherwise.} \end{array} \right. \end{aligned}$$

(7)

It has been shown that $\kappa _{\mathcal{R}}^Z\, {\models }_{\mathcal{O}} \, {\mathcal{R}}$ and that $\kappa _{\mathcal{R}}^Z$ is the unique, with respect to ranks of worlds, pareto-minimal OCF with this property [21].

Example 2

Algorithm 1 partitions the knowledge base ${\mathcal{R}}_{ pen }$ given in Example 1 in the sets

$$\begin{aligned} {\mathcal{R}}_0&=\{r_1:~(f|b),\,\,\,\,r_4:~(w|b),\,\,\,\,r_5:~(b|k)\}\\ {\mathcal{R}}_1&=\{r_2:~(b|p),\,\,\,\,r_3:~(\overline{f}|p)\} \end{aligned}$$

and so (7) results in the OCF $\kappa _{{\mathcal{R}}_{ pen }}^Z$ given in Table 1.

4.2 C-Representations

Based on an algebraic treatment of conditionals and the idea of maximum entropy, the notion of conditional indifference [13] of $\kappa$ with respect to ${\mathcal{R}}$ is defined and the following criterion for conditional indifference is given: An OCF $\kappa$ is indifferent with respect to ${\mathcal{R}}= \{(B_1|A_1),\ldots ,(B_n|A_n)\}$ iff $\kappa (A_i) < \infty$ for all $i \in \{1,\ldots ,n\}$ and there are rational numbers $\eta _{0}, \eta _{i}^+, \eta _{i} \in \mathbb {Q}, \ 1 \leqslant i \leqslant n,$ such that for all $\omega \in \Omega$,

$$\begin{aligned} \kappa (\omega ) = \eta _{0}+ \sum _{\begin{subarray}{c} 1 \leqslant i \leqslant n \\ \omega \models A_i B_i \end{subarray}} \eta _{i}^+ + \sum _{\begin{subarray}{c} 1 \leqslant i \leqslant n \\ \omega \models A_i \overline{B_i} \end{subarray}} \eta _{i}. \end{aligned}$$

(8)

The idea of conditional indifference is that the antecedence $A_i$ of each conditional is at least somewhat plausible and that the plausibility of a world depends on impacts $\eta _{i}^+, \eta _{i}$ assigned to $(B_i|A_i)$ in the following way: When starting with an epistemic state of complete ignorance (i.e., each world $\omega$ has rank 0), for each rule $(B_i|A_i)$ the values $\eta _{i}^+, \eta _{i}$ determine how the rank of each satisfying world and of each falsifying world, respectively, should be changed:

• If the world $\omega$ verifies the conditional $(B_i|A_i)$,   –   i.e., $\omega \models A_i B_i$   –, then $\eta _{i}^+$ is used in the summation to obtain the value $\kappa (\omega )$.

• Likewise, if $\omega$ falsifies the conditional $(B_i|A_i)$,   –   i.e., $\omega \models A_i \overline{B_i}$   –, then $\eta _{i}$ is used in the summation instead.

• If the conditional $(B_i|A_i)$ is not applicable in $\omega$,   –   i.e., $\omega \models \overline{A_i}$   –, then this conditional does not influence the value $\kappa (\omega )$.

The normalization constant $\eta _{0}$ ensures that there is a smallest world rank 0. Employing the postulate that the ranks of a satisfying world should not be changed and requiring that changing the rank of a falsifying world may not result in an increase of the world’s plausibility leads to the concept of a c-representation [12, 13]:

Definition 1

Let ${\mathcal{R}}= \{(B_1|A_1),\ldots ,(B_n|A_n)\}$. Any ranking function $\kappa$ satisfying the conditional indifference condition (8) and $\eta _{i}^+ = 0$, $\eta _{i} \geqslant 0$ (and thus also $\eta _{0}= 0$ since ${\mathcal{R}}$ is assumed to be consistent) as well as

$$\begin{aligned} \kappa (A_iB_i) < \kappa (A_i\overline{B_i}) \end{aligned}$$

(9)

for all $i \in \{1,\ldots ,n\}$ is called a (special) c-representation of ${\mathcal{R}}$.

Note that for $i \in \{1,\ldots ,n\}$, condition (9) expresses that $\kappa$ accepts the conditional $R_i = (B_i|A_i) \in {\mathcal{R}}$ (cf. the definition of the satisfaction relation in (4)) and that this also implies $\kappa (A_i) < \infty$.

Thus, finding a c-representation for ${\mathcal{R}}$ amounts to choosing appropriate values $\eta _{1}$, ..., $\eta _{n}$. In [4] this situation is formulated as a constraint satisfaction problem $CR ({\mathcal{R}})$ whose solutions are vectors of the form $(\eta _{1}, \ldots , \eta _{n})$ determining c-representations of ${\mathcal{R}}$. The development of $CR ({\mathcal{R}})$ exploits (2) and (8) to reformulate (9) and requires that the $\eta _{i}$ are natural numbers (and not just rational numbers). In the following, we set $\min (\emptyset ) = \infty$.

Definition 2

($\varvec{ CR ({\mathcal{R}})}$ [4]) The constraint satisfaction problem for c-representations of a knowledge base ${\mathcal{R}}= \{(B_1|A_1),\ldots ,(B_n|A_n)\}$, denoted by $CR ({\mathcal{R}})$, is given by the conjunction of the constraints

$$\begin{aligned}&\eta _{i} \geqslant 0 \end{aligned}$$

(10)

$$\begin{aligned}&\eta _{i} > \min _{\omega \models A_i B_i} \sum _{\begin{subarray}{c} j \ne i \\ \omega \models A_j \overline{B_j} \end{subarray}} \eta _{j} - \min _{\omega \models A_i \overline{B}_i} \sum _{\begin{subarray}{c} j \ne i \\ \omega \models A_j \overline{B_j} \end{subarray}} \eta _{j} \end{aligned}$$

(11)

for all $i \in \{1,\ldots ,n\}$.

A solution of $CR ({\mathcal{R}})$ is an n-tuple $(\eta _{1}, \ldots , \eta _{n})$ of natural numbers, and with $Sol _ {CR} ({\mathcal{R}})$ we denote the set of all solutions of $CR ({\mathcal{R}})$.

Proposition 1

(Correctness of $\varvec{ CR ({\mathcal{R}})}$ [2]) For ${\mathcal{R}}= \{(B_1|A_1),\ldots ,(B_n|A_n)\}$ let $\vec {\eta }= (\eta _{1}, \ldots , \eta _{n}) \in Sol _ {CR} ({\mathcal{R}})$. Then the function $\kappa$ defined by

$$\begin{aligned} \kappa (\omega ) = \sum _{\begin{subarray}{c} 1 \leqslant i \leqslant n \\ \omega \models A_i \overline{B_i} \end{subarray}} \eta _{i} \end{aligned}$$

(12)

in the following denoted by $\kappa _{\vec {\eta }}$, is an OCF that accepts  ${\mathcal{R}}$.

Example 3

We illustrate c-representations using the alphabet $\Sigma =\{p,b,f\}$ and the knowledge base

$$\begin{aligned} {\mathcal{R}}'_{ pen }= \{r_1\!:\,(f|b),\;r_2\!:\,(b|p),\;r_3\!:\,(\overline{f}|p)\} \end{aligned}$$

which is a proper subset of ${\mathcal{R}}_{ pen }$ from Example 1. Using the verification/falsification behavior of the worlds over $\Sigma$ with respect to the conditionals in ${\mathcal{R}}'_{ pen }$ given in Table 2, the system of inequalities in $CR ({\mathcal{R}}'_{ pen })$ according to (11) is:

$$\begin{aligned} \eta _{1}>\min \{\eta _{3},0\}-\min \{0,0\}=0\\ \eta _{2}>\min \{\eta _{3},\eta _{1}\}- \min \{\eta _{3},0\}=\min \{\eta _{1},\eta _{3}\}\\ \eta _{3}&>\min \{\eta _{1},\eta _{2}\}- \min \{\eta _{2},0\}=\min \{\eta _{1},\eta _{2}\}. \end{aligned}$$

One solution for this system of inequalities and thus the constraint satisfaction problem $CR ({\mathcal{R}}'_{ pen })$ is the triple (1, 2, 2). The ranking function induced by this solution according to (12) is shown in Table 3.

Applying this method to the knowledge base ${\mathcal{R}}_{ pen }$ (Example 1), one solution of $CR ({\mathcal{R}}_{ pen })$ is the quintuple (1, 2, 2, 1, 1), and using this solution in (12) we obtain the OCF $\kappa$ given in Table 1.

Table 2 Verification/falsification behavior of the knowledge base ${\mathcal{R}}'_{ pen }$ and possible worlds used in Example 3

Table 3 Induced ranking function $\kappa _{(1,2,2)}$ by the solution (1, 2, 2) of the constraints in $CR ({\mathcal{R}}'_{ pen })$ from Example 3

Note that each $\eta _{i}$ of a solution $\vec {\eta }\in Sol _ {CR} ({\mathcal{R}})$ defines the impact of the conditional $(B_i|A_i)$, that is, how severe it is to falsify the conditional. A solution $\vec {\eta }$ partitions the conditionals in sets of conditionals of equal impact. There are knowledge bases where this partitioning does not coincide with the partitioning induced by system Z. The ranking function $\kappa _{\vec {\eta }}$ sums up the impacts of falsified conditionals for each world which results in a plausibility ranking between worlds s.t.

• 1. A world $\omega$ that, ceteris paribus, falsifies less conditionals of a partition than a world $\omega '$ is ranked to be more plausible, i.e., $\kappa _{\vec {\eta }}(\omega )<\kappa _{\vec {\eta }}(\omega ')$, and

• 2. A world $\omega$ that, ceteris paribus, falsifies a conditional of a partition with a lower impact than a world $\omega '$ is ranked to be more plausible, i.e., $\kappa _{\vec {\eta }}(\omega )<\kappa _{\vec {\eta }}(\omega ')$.

The following example illustrates the relationship of c-representations to system Z and to the lexicographic ordering of worlds as in [16].

Example 4

Let ${\mathcal{R}}_{ abcd }=\{(c|a),(c|b),(\overline{c}|d),(a|d)\}$. The vector $\vec {\eta }=(1,1,2,2)$ is a possible solution for the constraint satisfaction problem $CR ({\mathcal{R}}_{ abcd })$ (cf. Definition 2). Thus, the solution vector $\vec {\eta }$ partitions the conditionals into the sets ${\mathcal{R}}_0=\{(c|a),(c|b)\}$, each with an impact of 1, and ${\mathcal{R}}_1=\{(\overline{c}|d),(a|d)\}$, each with an impact of 2. Now lets consider the possible worlds, $\omega =ab\overline{c}\overline{d}$, $\omega '=a\overline{b}cd$ and $\omega ''=a\overline{b}\overline{c}\overline{d}$.

The world $\omega$ falsifies both conditionals in ${\mathcal{R}}_0$ and none in ${\mathcal{R}}_1$, and $\omega '$ falsifies only one conditional in ${\mathcal{R}}_1$ but no other conditionals. The rank of both worlds with respect to $\kappa _{\vec {\eta }}$ is 2, since $\kappa _{\vec {\eta }}(\omega )=1+1=2$ and $\kappa _{\vec {\eta }}(\omega ')=2$, so both worlds are considered equally (im)plausible with respect to this c-representation. Applying system Z yields the same partitions but ranks of $\kappa ^Z(\omega )=1$ and $\kappa _Z(\omega ')=2$, so under system Z, $\omega$ is considered more plausible than $\omega '$. This valuation coincides with the lexicographic ordering in the sense of [16], where $\omega '$ is considered less plausible than $\omega$ since $\omega '$ falsifies a conditional in set ${\mathcal{R}}_1$ and $\omega$ does not.

For the worlds $\omega$ and $\omega ''$ we obtain that they are equivalent with respect to their system Z rank, since they both falsify conditionals in ${\mathcal{R}}_0$ and we have $\kappa (\omega )=1=\kappa (\omega '')$, but for $\kappa _{\vec {\eta }}$ we have $\kappa _{\vec {\eta }}(\omega '')=1<2= \kappa _{\vec {\eta }}(\omega )$, so $\omega ''$ is considered more plausible than $\omega$. Also, since $\omega$ falsifies more conditionals in ${\mathcal{R}}_0$ than $\omega ''$ and no conditionals in a more severe partition, lexicographic ordering in the sense of [16] considers $\omega ''$ to be more plausible than $\omega$.

Thus, inference by c-representations is, in general, different to inference by system Z or lexicographic ordering of the worlds in the sense of [16]. It shares the central ideas of a ceteris paribus ordering with the latter, and shares the property of overcoming the Drowing Problem found for System Z. Since the individual impacts are nonnegative integers, an impact of a conditional can be 0. Since the rank of the worlds is computed by a summation of the impacts of falsified conditionals, falsifying or not falsifying a conditional with a zero impact does not change the rank of a world, which is in accordance with this conditional’s effect already being realised by other conditionals in the knowledge base.

5 A Declarative CLP Program for $CR ({\mathcal{R}})$

In this section, we will demonstrate that it is possible to obtain a declarative program, called GenOCF, that solves $CR ({\mathcal{R}})$ while exploiting the concepts of constraint logic programming in such a way that there is a direct correspondence between the abstract formulation of $CR ({\mathcal{R}})$ and the executable program code. We will employ finite domain constraints, and from (10) we immediately get 0 as a lower bound for $\eta _{i}$. Considering that we are interested mainly in minimal solutions, due to (10) we restrict ourselves to n as an upper bound for $\eta _{i}$, yielding $0 \leqslant \eta _{i} \leqslant n$ for all $i \in \{1,\ldots ,n\}$ with n being the number of conditionals in ${\mathcal{R}}$.

5.1 Input Format and Preliminaries

Since we want to focus on the constraint solving part, we do not consider reading and parsing a knowledge base ${\mathcal{R}}= \{(B_1|A_1),\ldots ,(B_n|A_n)\}$. Instead, we assume that ${\mathcal{R}}$ is already given as a Prolog code file providing the following predicates variables/1, conditional/3 and indices/1:

$$\begin{aligned} \begin{array}{llll} \texttt {variables}([a_1,\ldots ,a_m]) && \% &\text{list of atoms in} \,\, \Sigma \\ \texttt {conditional}(i,{\langle A_i \rangle },{\langle B_i \rangle }) && \%& \text{representation of} (B_i|A_i) \\ \texttt {indices}([1,...,n]) && \%& \text{list of indices}\{1,...,n\} \end{array} \end{aligned}$$

If $\Sigma = \{a_1,\ldots , a_m\}$ is the set of atoms, we assume a fixed ordering $a_1< a_2< \cdots < a_m$ on $\Sigma$ given by variables([$a_1$,...,$a_m$]). The fixed index ordering given by indices([1,...,n]) ensures that the i-th conditional can be accessed by conditional(i,A,B), and in a solution vector [$\text{K}_1$ ,..., $\text{K}_n$], the i-th component $\text{K}_i$ is the $\eta$-value for the i-th conditional.

In the representation of a conditional, a propositional formula A, constituting the antecedent or the consequence of the conditional, is represented by $\langle A \rangle$ where $\langle A \rangle$ is a Prolog list [$\langle D_1 \rangle$ ,..., $\langle D_l \rangle$]. Each $\langle D_i \rangle$ represents a conjunction of literals such that $D_1 \vee \cdots \vee D_l$ is a disjunctive normal form of A. Each $\langle D \rangle$, representing a conjunction of literals, is a Prolog list [$b_1$ ,..., $b_m$] of fixed length m where m is the number of atoms in $\Sigma$ and with $b_k \in \{{\hbox {\texttt {0, 1,}}}\, \_\}$. Such a list [$b_1$ ,..., $b_m$] represents the conjunctions of atoms obtained from $\dot{a}_1 \wedge \dot{a}_2 \wedge \cdots \wedge \dot{a}_m$ by eliminating all occurrences of $\top$, where:

$$\begin{aligned} \begin{array}{lll} \dot{a}_k & = & {\left\{ \begin{array}{ll} a_k & \quad \text{ if }\, b_k = 1 \\ \overline{a_k} &\quad \text{ if }\, b_k = 0 \\ \top & \quad \text{ if }\, b_k = \_\\ \end{array}\right. } \end{array} \end{aligned}$$

Example 5

The internal representation of the knowledge base ${\mathcal{R}}_{ pen }$ presented in Example 1 is:

As further preliminaries, using conditional/3 and indices/1, we have implemented the predicates worlds/1, verifying_worlds/2, falsifying_worlds/2, and falsify/2, realising the evaluation of the indicator function (1):

$$ \begin{array}{lll} {\texttt {worlds}}( Ws ) & \% \quad & Ws \,\, {\text{list of possible worlds}} \\ {\texttt {verifying\_worlds}}(i, Ws ) & \% \quad & {\text{worlds verifying}} \,\, i{\text{th conditional}}\\ {\texttt {falsifying\_worlds}}(i,{ Ws }) & \% \quad & {\text{worlds falsifying}} \,\, i{\text{th conditional}}\\ {\texttt {falsify}}(i,W) & \% \quad & {\text{world}}\quad W \quad {\text{falsifies}} \,\, i{\text{th conditional}} \end{array} $$

where worlds are represented as complete conjunctions of literals, using the representation described above.

5.2 Generation of Constraints and Solutions

The particular program code given here uses the SICStus Prolog system¹ and its clp(fd) library implementing constraint logic programming over finite domains [19]. The main predicate kappa/2 expecting a knowledge base KB of conditionals and yielding a vector K of $\eta _{i}$ values as specified by (11) is presented in Fig. 1.

Fig. 1

Main predicate kappa/2

After reading in the knowledge base, the constraints for K are generated. In constraints/1, after getting the list of indices, a list K of free constraint variables, one for each conditional, is generated; in the two subsequent subgoals, the constraints for the elements of K corresponding to the formulas $0 \leqslant \eta _{i} \leqslant n$ and (11) are generated. Finally, labeling([], K) yields a list of $\eta _{i}$ values. Upon backtracking, this will enumerate all possible solutions with an upper bound of n for each $\eta _{i}$.

Fig. 2

Constraining the vector K representing $\eta _{1},\ldots ,\eta _{n}$ as in (11)

Figure 2 shows how the goal constrain_K(Is, K) in kappa/2 generates a constraint for each index $i \in \{1,\ldots ,n\}$ according to (11). Given an index I, constrain_Ki(I,K) (cf. Fig. 2) determines all worlds verifying and falsifying the I-th conditional; over these two sets of worlds the two $\min$ expressions in (11) are defined. Two lists VS and FS of sums corresponding exactly to the first and the second sum, repectively, in (11) are generated (how this is done is defined in Fig. 3 and will be explained below). With the constraint variables Vmin and Fmin denoting the minimum of these two lists, the constraint

$$\tt{K}_{i}\;\# >{\tt{V}_{\tt{min}}}-{\tt{F}_{\tt{min}}}$$

given in the last line of Fig. 2 reflects precisely the restriction on $\eta _{i}$ given by (11).

For an index I, a kappa vector K, and a list of worlds Ws, the goal list_of_sums(I, K, Ws, Ss) (cf. Fig. 3) yields a list Ss of sums such that for each world W in Ws, there is a sum S in Ss that is generated by sum_kappa_j(Js, I, K, W, S) where Js is the list of indices $\{1,\ldots ,n\}$. In the goal sum_kappa_j(Js, I, K, W, S), S corresponds exactly to the respective sum expression in (11), i.e., it is the sum of all Kj such that J $\ne$ I and W falsifies the j-th conditional.

Fig. 3

Generating list of sums of $\eta _{i}$ as in (11)

After all constraints have been generated, the final subgoal of kappa/2 (Fig. 1) yields all solutions of $CR ({\mathcal{R}})$.

Example 6

If kb_penguins.pl is a file containing the conditionals of ${\mathcal{R}}_{ pen }$ given in Example 1, the first six solutions generated by kappa/2 are:

Note that the first solution vector induces the OCF $\kappa$ given in Table 1 (cf. Example 3).

Using the predicates described in Sect. 5.1, we have presented the complete source code of the constraint logic program GenOCF solving $CR ({\mathcal{R}})$. In Sect. 7, GenOCF extended to find minimal solutions of $CR ({\mathcal{R}})$ (cf. [4]) will be used for computing inference relations induced by minimal OCF models of ${\mathcal{R}}$.

6 Minimal C-Representations

All c-representations built from (10), (11), and (12) provide an excellent basis for model-based inference, for instance each c-representation satisfies System P and none suffers from the drowning problem [12–14]. However, from the point of view of minimal specificity (see e.g. [6]), those c-representations with minimal $\eta _{i}$ yielding minimal degrees of implausibility are most interesting. In [10], an OCF $\kappa$ accepting ${\mathcal{R}}$ is said to be minimal iff for every other $\kappa '$ accepting ${\mathcal{R}}$ there exists a world $\omega \in \Omega$ with $\kappa (\omega ) < \kappa '(\omega )$. Since in this paper, our focus is on c-representations, and since for any ${\mathcal{R}}$, the OCFs being c-representations and accepting ${\mathcal{R}}$ are induced by the solutions of $CR ({\mathcal{R}})$, we will consider different orderings on $Sol _ {CR} ({\mathcal{R}})$ proposed in [3, 4], leading to three different minimality notions: The minimal accumulated impact of the conditionals (sum-minimality), the pareto-minimal impact of the conditionals (cw-minimality), and the pareto-minimal ranking of the worlds in the induced ranking functions (ind-minimality).

Definition 3

(sum-minimal, $\varvec{\preccurlyeq _{+}}$) Let ${\mathcal{R}}$ be a knowledge base and $\vec {\eta }$, $\vec {\eta }'$ $\in$ $Sol _ {CR} ({\mathcal{R}})$. Then

$$\begin{aligned} (\eta _{1}, \ldots , \eta _{n}) \preccurlyeq _{+}({\eta '_{1}}, \ldots , {\eta '_{n}})\quad \text{ iff } \; \sum _{1 \leqslant i \leqslant n} \eta _{i} \leqslant \sum _{1 \leqslant i \leqslant n} {\eta '_{i}}. \end{aligned}$$

(13)

A vector $\vec {\eta }$ is sum-minimal iff $\vec {\eta }\,\preccurlyeq _{+}\,\vec {\eta }'$ for all $\vec {\eta }'\in Sol _ {CR} ({\mathcal{R}})$. We write $\vec {\eta }\prec _{+}\vec {\eta }'$ iff $\vec {\eta }\, \preccurlyeq _{+}\, \vec {\eta }'$ and $\vec {\eta }'\! \not \preccurlyeq _{+}\, \vec {\eta }$.

As we are interested in minimal $\eta _{i}$-vectors, an important question is whether there is always a unique minimal solution. This is not the case; the following example illustrates that $Sol _ {CR} ({\mathcal{R}})$ may have more than one sum-minimal element.

Example 7

Let ${{\mathcal{R}}_{ birds }}= \{r_1, \, r_2, \, r_3\}$ be the following set of conditionals:

$$ \begin{array}{lll} r_1: \,\,\,\, & (f|b) & \underline{b}irds\, \underline{f}ly \\ r_2: \ & (a|b) & \underline{b}irds\, are\, \underline{a}nimals\\ r_3: \ & (a|fb) & \underline{f}lying\,\underline{b}irds\, are\, \underline{a}nimals\\ \end{array} $$

From (11), we get

$$ \begin{aligned} & \eta _{1}> 0 \\ & \eta _{2}> 0 - min\{\eta _{1}, \, \eta _{3}\} \\ & \eta _{3} > 0 - \eta _{2} \end{aligned} $$

and since $\eta _{i} \geqslant 0$ according to (10), the two vectors

$$\begin{aligned} \begin{array}{l} \vec {\eta }^{(1)} = (\eta _{1}, \eta _{2}, \eta _{3}) = (1, 1, 0) \\ \vec {\eta }^{(2)} = (\eta _{1}, \eta _{2}, \eta _{3}) = (1, 0, 1)\\ \end{array} \end{aligned}$$

are two different solutions of $CR ({{\mathcal{R}}_{ birds }})$ with $\sum _{1 \leqslant i \leqslant n} \eta _{i} = 2$ that are both minimal in $Sol _ {CR} ({{\mathcal{R}}_{ birds }})$ with respect to $\preccurlyeq _{+}$.

Instead of taking the sum of the $\eta _{i}$, we can also consider the componentwise ordering $\preccurlyeq _{ cw }$.

Definition 4

(cw-minimal, $\varvec{\preccurlyeq _{ cw }}$) Let ${\mathcal{R}}$ be a knowledge base and $\vec {\eta }$, $\vec {\eta }'$ $\in$ $Sol _ {CR} ({\mathcal{R}})$. Then

$$\begin{aligned} &(\eta _{1}, \ldots , \eta _{n}) \preccurlyeq _{ cw }({\eta '_{1}}, \ldots , {\eta '_{n}})\\ &\text{ iff } \; \eta _{i} \leqslant {\eta '_{i}}\quad \text{ for all } i \in \left\{ 1, \ldots , n\right\} \end{aligned}$$

(14)

A vector $\vec {\eta }$ is cw-minimal iff there is no vector $\vec {\eta }'\in Sol _ {CR} ({\mathcal{R}})$ such that $\vec {\eta }'\preccurlyeq _{ cw } \, \vec {\eta }$ and $\vec {\eta }\not \preccurlyeq _{ cw } \, \vec {\eta }'$.

Example 8

The two sum-minimal solution vectors $\vec {\eta }^{(1)}$ and $\vec {\eta }^{(2)}$ for ${{\mathcal{R}}_{ birds }}$ from Example 7 are both also cw-minimal.

Instead of defining an ordering directly in terms of the solution vectors in $Sol _ {CR} ({\mathcal{R}})$ as done for $\preccurlyeq _{+}$ and $\preccurlyeq _{ cw }$, the following ordering on $Sol _ {CR} ({\mathcal{R}})$ takes the ordering of the induced ranking functions into account.

Definition 5

(ind-minimal, $\varvec{\preccurlyeq _{ O }}$) Let ${\mathcal{R}}$ be a knowledge base and $\vec {\eta }$, $\vec {\eta }'$ $\in$ $Sol _ {CR} ({\mathcal{R}})$. Then

$$\begin{aligned} (\eta _{1}, \ldots , \eta _{n}) \, \preccurlyeq _{ O } \, ({\eta '_{1}}, \ldots , {\eta '_{n}}) \;\text{ iff } \; \kappa _{\vec {\eta }}(\omega ) \leqslant \kappa _{\vec {\eta }'}(\omega ) \quad \text{ for all } \omega \in \Omega \end{aligned}$$

(15)

A vector $\vec {\eta }$ is ind-minimal iff there is no vector $\vec {\eta }'\in Sol _ {CR} ({\mathcal{R}})$ such that $\vec {\eta }'\preccurlyeq _{ O }\,\vec {\eta }$ and $\vec {\eta }\not \preccurlyeq _{ O }\,\vec {\eta }'$.

Example 9

Consider again the knowledge base ${{\mathcal{R}}_{ birds }}$ from Example 7 and the two solution vectors $\vec {\eta }^{(1)}$ and $\vec {\eta }^{(2)}$. Table 4 shows the ranking functions induced by $\vec {\eta }^{(1)}$ and $\vec {\eta }^{(2)}$. While both $\vec {\eta }^{(1)}$ and $\vec {\eta }^{(2)}$ are sum-minimal and also cw-minimal, only $\vec {\eta }^{(2)}$ is ind-minimal because $\kappa _{\vec {\eta }^{(2)}}(\overline{a}b\overline{f}) = 1 < 2 = \kappa _{\vec {\eta }^{(1)}}(\overline{a}b\overline{f})$ and $\kappa _{\vec {\eta }^{(2)}}(\omega ) = \kappa _{\vec {\eta }^{(1)}}(\omega )$ for all $\omega$ with $\omega \not = \overline{a}b\overline{f}$.

Table 4 Ranking functions induced by the solution vectors $\vec {\eta }^{(1)}$ and $\vec {\eta }^{(2)}$ from Example 7

Although for the knowledge base ${{\mathcal{R}}_{ birds }}$ there is a unique ind-minimal solution of $CR ({{\mathcal{R}}_{ birds }})$, there are knowledge bases ${\mathcal{R}}$ with multiple ind-minimal solutions of $CR ({\mathcal{R}})$ that induce different ranking functions accepting ${\mathcal{R}}$; examples of such knowledge bases are given in [3]. Note that this implies that an ind-minimal solution of $CR ({\mathcal{R}})$ does not necessarily induce the unique pareto-minimal model of ${\mathcal{R}}$ with respect to the ranking of worlds generated with System Z (see Sect. 4.1 and [21]), underpinning the observation that c-representations and System Z are different in general (see Example 4 and [14, 24]).

In order to define inference over the minimal models of a knowledge base ${\mathcal{R}}$, we consider subsets of $Sol _ {CR} ({\mathcal{R}})$ containing only the minimal c-representations with respect to one of the defined notions of minimality.

$$\begin{aligned} Sol _{\preccurlyeq _{+}}^{ min }( CR ({\mathcal{R}}))= \{\vec {\eta }\mid&\vec {\eta }\in Sol _ {CR} ({\mathcal{R}})\;\text{ and } \; \vec {\eta }\text{ is sum-minimal}\} \end{aligned}$$

(16)

$$\begin{aligned} Sol _{\preccurlyeq _{ cw }}^{ min }( CR ({\mathcal{R}}))= \{\vec {\eta }\mid&\vec {\eta }\in Sol _ {CR} ({\mathcal{R}})\; \text{ and } \; \vec {\eta }\text{ is cw-minimal}\} \end{aligned}$$

(17)

$$\begin{aligned} Sol _{\preccurlyeq _{ O }}^{ min }( CR ({\mathcal{R}}))= \{\vec {\eta }\mid&\vec {\eta }\in Sol _ {CR} ({\mathcal{R}})\;\text{ and } \; \vec {\eta }\text{ is ind-minimal}\} \end{aligned}$$

(18)

Proposition 2

Let ${\mathcal{R}}$ be a knowledge base. Then

$$\begin{aligned} Sol _{\preccurlyeq _{+}}^{ min }( CR ({\mathcal{R}}))&\subseteq Sol _{\preccurlyeq _{ cw }}^{ min }( CR ({\mathcal{R}}))\end{aligned}$$

(19)

$$\begin{aligned} Sol _{\preccurlyeq _{ O }}^{ min }( CR ({\mathcal{R}}))&\subseteq Sol _{\preccurlyeq _{ cw }}^{ min }( CR ({\mathcal{R}})) \end{aligned}$$

(20)

holds.

Proof

For proving (19), assume there is a $\vec {\eta }\in Sol _{\preccurlyeq _{+}}^{ min }( CR ({\mathcal{R}}))$ with $\vec {\eta }\not \in Sol _{\preccurlyeq _{ cw }}^{ min }( CR ({\mathcal{R}}))$. Then there is a $\vec {\eta }'\in Sol _{\preccurlyeq _{ cw }}^{ min }( CR ({\mathcal{R}}))$ with $\vec {\eta }'\preccurlyeq _{ cw }\vec {\eta }$ and $\vec {\eta }'\ne \vec {\eta }$. From (14) we get ${\eta '_{i}} \leqslant \eta _{i}$ for all $i \in \left\{ 1,\ldots ,n\right\}$ and ${\eta '_{s}} < \eta _{s}$ for some $s \in \left\{ 1,\ldots ,n\right\}$, and thus:

$$\begin{aligned} \sum _{i = 1}^{n} {\eta '_{i}} < \sum _{i = 1}^{n} \eta _{i} \end{aligned}$$

(21)

Therefore, $\vec {\eta }'$ $\prec _{+}$ $\vec {\eta }$ and hence $\vec {\eta }\not \in Sol _{\preccurlyeq _{+}}^{ min }( CR ({\mathcal{R}}))$, contradicting the assumption and thus implying (19).

For proving (20), assume there is a $\vec {\eta }\in Sol _{\preccurlyeq _{ O }}^{ min }( CR ({\mathcal{R}}))$ with $\vec {\eta }\not \in Sol _{\preccurlyeq _{ cw }}^{ min }( CR ({\mathcal{R}}))$. Then there is a $\vec {\eta }'\in Sol _{\preccurlyeq _{ cw }}^{ min }( CR ({\mathcal{R}}))$ with $\vec {\eta }'\preccurlyeq _{ cw }\vec {\eta }$ and $\vec {\eta }'\ne \vec {\eta }$. From (14) we get ${\eta '_{i}} \leqslant \eta _{i}$ for all $i \in \left\{ 1,\ldots ,n\right\}$ and ${\eta '_{s}} < \eta _{s}$ for some $s \in \left\{ 1,\ldots ,n\right\}$.

Since we excluded self-fulfilling conditionals $(B|A)$ with $A \models B$ from a knowledge base ${\mathcal{R}}$, there is at least one world $\omega _s \in \Omega$ with $\omega _s \models A_s\overline{B_s}$. From (12) we get:

$$\begin{aligned} \kappa _{\vec {\eta }'}(\omega )&\leqslant \kappa _{\vec {\eta }}(\omega ) \quad \text{for all} \, \omega \in \Omega \end{aligned}$$

(22)

$$\begin{aligned} \kappa _{\vec {\eta }'}(\omega _s)&< \kappa _{\vec {\eta }}(\omega _s) \end{aligned}$$

(23)

That means that $\vec {\eta }'\preccurlyeq _{ O } \, \vec {\eta }$ and $\vec {\eta }\not \preccurlyeq _{ O } \, \vec {\eta }'$; hence, $\vec {\eta }\not \in Sol _{\preccurlyeq _{ O }}^{ min }( CR ({\mathcal{R}}))$, contradicting the assumption and thus implying (20). $\square$

7 C-Inference Based on Preferred Models

Each of the ordering relations $\preccurlyeq _{\bullet }$ with $\bullet \in \{+, cw , O \}$ induces a set of solutions of $CR ({\mathcal{R}})$ that are minimal with respect to $\preccurlyeq _{\bullet }$, cf. (16)–(18). Using the OCFs induced by these $\preccurlyeq _{\bullet }$-minimal solutions

$$\begin{aligned} {\mathcal{O}}_{\preccurlyeq _{\bullet }}^{ min }( CR ({\mathcal{R}}))= \left\{ \kappa _{\vec {\eta }} \mid \vec {\eta }\in Sol _{\preccurlyeq _{\bullet }}^{ min }( CR ({\mathcal{R}}))\right\} \end{aligned}$$

(24)

as preferred models, we obtain three nonmonotonic inference relations. We say that a formula B is (skeptically) $\bullet$-entailed by a formula A (in the context of a knowledge base ${\mathcal{R}}$) iff every $\bullet$-minimal OCF accepting ${\mathcal{R}}$ also accepts the conditional $(B|A)$, i.e.:

$$\begin{aligned} A \,|\!\!{\sim} \,^{\!\!\bullet }B \text{ iff } \kappa \, {\models }_{\mathcal{O}} \, (B|A)\quad \text{ for all } \kappa \in {\mathcal{O}}_{\preccurlyeq _{\bullet }}^{ min }( CR ({\mathcal{R}}))\end{aligned}$$

(25)

We have developed the system InfOCF that implements these three inference relations $\,|\!\!{\sim} \,^{\!\!+}$, $\,|\!\!{\sim} \,^{\!\! cw }$, $\,|\!\!{\sim} \,^{\!\! O }$. Additionally, InfOCF also implements system Z inference and p-entailment and compares the inference results. The system uses an extension of GenOCF for computing all $\preccurlyeq _{\bullet }$-minimal ranking functions. For computing system Z inference and p-entailment, InfOCF employs a straight-forward Haskell implementation of the consistency test for a knowledge base (Listing 1). The user interface (UI) and the inference over a set of minimal C-Representations is implemented in Java using the library Log4KR.² For checking whether the inference $A \,|\!\!{\sim} \,^{\!\!\bullet }B$ holds, InfOCF determines the ranks $\kappa (AB)$ and $\kappa (A\overline{B})$ and checks $\kappa (AB) < \kappa (A\overline{B})$ for every computed $\bullet$-minimal ranking function $\kappa$.

Fig. 4

User interface InfOCF for nonmonotonic inference based on ranking functions

Figure 4 shows an example of InfOCF in use. The knowledge base ${\mathcal{R}}_{ pen }$ introduced in Example 1 has been loaded in the top left corner. The computed ranking functions are shown in the top right corner. The lower half of the UI is used for inference where the query is entered in two text fields for checking whether A entails B in the context of the given knowledge base; from these formulas the query conditional $(B|A)$ is constructed. In addition to (skeptical) c-inference $\,|\!\!{\sim} \,^{\!\!\bullet }$, InfOCF also implements credulous entailment where A credulously entails B (in the context of a knowledge base ${\mathcal{R}}$) iff there is a $\bullet$-minimal OCF accepting ${\mathcal{R}}$ that also accepts the conditional $(B|A)$.

The results of the last query as well as of the previous queries are listed in the bottom right. The particular queries shown in Fig. 4 are already discussed in Example 1 and demonstrate the drowning problem observable in system Z and the difference between inference over all ranking models (system p) and system Z as well as the different minimal c-representations.

Since the solutions for $CR ({\mathcal{R}}_{ pen })$ which are sum-, cw- or ind-minimal, respectively, coincide, there is no difference in c-inference for the three different notions of minimality. The following example demonstrates that this is not the case in general.

Example 10

Let ${\mathcal{R}}_{ strange }= \left\{ r_1, \, r_2, \, r_3, \, r_4, \, r_5 \right\}$ be the following set of conditionals:

$$\begin{array}{lll} r_1: \,\,\,\, & (b|p) & \underline{p}enguins\, are\, \underline{b}irds \\ r_2: & (b|\overline{p}) & non{\text{-}}\underline{p}enguins\, are\, \underline{b}irds \\ r_3: & (b|\overline{p}sf) \,\,\,\, & \underline{f}lying\, \underline{s}trange\, non{\text{-}}\underline{p}enguins\, are\, \underline{b}irds\\ r_4: & (s|\overline{b}f) & \underline{f}lying\, things\, that\, aren't\, \underline{b}irds\, are\, \underline{s}trange\\ r_5: & (p|\overline{f}) & things\, that\, don't\, \underline{f}ly\, are\, likely \, \underline{p}enguins\\ \end{array}$$

For $CR ({\mathcal{R}}_{ strange })$, the impact vector $\vec {\eta }^{(1)} = (1,0,1,2,1)$ is both cw- and ind-minimal while $\vec {\eta }^{(2)}= (1,1,0,1,1)$ is cw-, ind- and sum-minimal; there are no other minimal solutions. For the four worlds satisfying $\overline{p}\overline{f}$, their assigned ranks under both solutions and under system Z are given in Table 5.

For the conditional $(b|\overline{p}\overline{f})$ observe that $\kappa _{\vec {\eta }^{(1)}} \,\,\,{\models }_{\mathcal{O}}\!\!\!\!\!\!\!/ \,\;\; \, (b|\overline{p}\overline{f})$ since $\kappa _{\vec {\eta }^{(1)}}(\overline{p}b\overline{f}) = \kappa _{\vec {\eta }^{(1)}}(\overline{p}\overline{b}\overline{f})$, but $\kappa _{\vec {\eta }^{(2)}} \, {\models }_{\mathcal{O}} \, (b|\overline{p}\overline{f})$ since $\kappa _{\vec {\eta }^{(2)}}(\overline{p}b\overline{f}) = 1 < 2 = \kappa _{\vec {\eta }^{(2)}}(\overline{p}\overline{b}\overline{f})$. Thus, $\overline{p}\overline{f} \,\,\,/\!\!\!\!\!\,|\!\!{\sim} \,^{\!\! cw }b$ and $\overline{p}\overline{f} \,\,\,/\!\!\!\!\!\,|\!\!{\sim} \,^{\!\! O }b$ς, but $\overline{p}\overline{f} \,|\!\!{\sim} \,^{+} b$. This shows that skeptical inference over all c-representations induced by sum-minimal impact vectors differs both from inference over cw-minimal and over ind-minimal models in general.

Inference with a single c-representation and inference with system Z are different in general (see [14, 24]), and it also has been shown that skeptical inference over all c-representations of a given knowledge base (c-inference) differs from system Z inference (see [2]). The latter is also the case for skeptical inferences over a set of $\preccurlyeq _{\bullet }$-preferred c-representations, as these relations also do not suffer from the Drowning Problem, which does occur for system Z. Compared to skeptical c-inference, taking only minimal/preferred models into account relaxes the conditions for inference. Thus, minimal c-inference extends skeptical c-inference; the exact formal relationships among these different c-inference relations have still to be investigated in detail.

8 Conclusions and Further Work

In this paper we studied conditionals and conditional knowledge bases which can be used by an intelligent reasoning agent. For obtaining a complete epistemic state from the (usually incomplete) knowledge base, we recalled the established inductive inference approaches p-entailment, system Z, and c-representations. These approaches generate inference relations based on ranking models of the knowledge base. Here, system Z defines the inference relation based on the unique pareto minimal ranking model, whereas p-entailment is the skeptical inference over all ranking models of the knowledge base. We used this idea to contrast the skeptical inference over all c-representations of a knowledge base [2] with inference relations defined as skeptical inference over preferred ranking models of this knowledge base. These preference relations are defined over the c-representations of a knowledge base induced by three different notions of minimality. Using a high-level, declarative approach based on constraint-logic programming techniques, we developed a practical tool implementing the resulting three inference relations. Using our implementation, we demonstrated that these inference relations based on c-representations differ from the classical approaches of p-entailment and system Z and that in general they do not coincide.

Table 5 Assigned ranks for worlds in which $\overline{p}\overline{f}$ holds

Our current work includes the investigation of the formal properties of the inference relations induced by the different notions of minimality, as well as their exact relationship to the inference over all c-representations. While the focus of our implementation described here was to obtain a high-level, declarative program close to the abstract problem specification, in future work we will also study the complexity of the inference relations and investigate performance optimizations.