A Declarative Approach for Computing Ordinal Conditional Functions Using Constraint Logic Programming

Abstract

In order to give appropriate semantics to qualitative conditionals of the form if A then normally B, ordinal conditional functions (OCFs) ranking the possible worlds according to their degree of plausibility can be used. An OCF accepting all conditionals of a knowledge base R can be characterized as the solution of a constraint satisfaction problem. We present a high-level, declarative approach using constraint logic programming (CLP) techniques for solving this constraint satisfaction problem. In particular, the approach developed here supports the generation of all minimal solutions; this also holds for different notions of minimality which we discuss and implement in CLP. Minimal solutions are of special interest as they provide a basis for model-based inference from R.

The research reported here was partially supported by the Deutsche Forschungsgemeinschaft – DFG (grants BE 1700/7-2 and KE 1413/2-2).

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In knowledge representation, rules play a prominent role. Default rules of the form If A then normally B are being investigated in nonmonotonic reasoning, and various semantical approaches have been proposed for such rules. Since it is not possible to assign a simple Boolean truth value to such default rules, a semantical approach is to define when a rational agent accepts such a rule. We could say that an agent accepts the rule Birds normally fly if she considers a world with a flying bird to be less surprising than a world with a nonflying bird. At the same time, the agent can also accept the rule Penguin birds normally do not fly; this is the case if she considers a world with a nonflying penguin bird to be less surprising than a world with a flying penguin bird.

The informal notions just used can be made precise by formalizing the underlying concepts like default rules, epistemic state of an agent, and the acceptance relation between epistemic states and default rules. In the following, we deal with qualitative default rules and a corresponding semantics modelling the epistemic state of an agent. While a full epistemic state could compare possible worlds according to their possibility, their probability, their degree of plausibility, etc. (cf. [9, 10, 18]), we will use ordinal conditional functions (OCFs), which are also called ranking functions [18]. To each possible world $\omega$, an OCF $\kappa$ assigns a natural number $\kappa (\omega )$ indicating its degree of surprise: The higher $\kappa (\omega )$, the greater is the surprise for observing $\omega$.

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. In [3] a system that computes a c-representation for any such $\mathcal {R}$ that is consistent is described, but this c-representation may not be minimal. An algorithm for computing a minimal ranking function is given in [5], but this algorithm fails to find all minimal ranking functions if there is more than one minimal one. In [15] an extension of that algorithm being able to compute all minimal c-representations for $\mathcal {R}$ is presented. The algorithm developed in [15] uses a non-declarative approach and is implemented in an imperative programming language. While the problem of specifying all c-representations for $\mathcal {R}$ is formalized as an abstract, problem-oriented constraint satisfaction problem $\textit{CR}(\mathcal {R})$ in [2], no solving method is given there.

In this paper, we present a high-level, declarative approach using constraint logic programming techniques for solving the constraint satisfaction problem $\textit{CR}(\mathcal {R})$ for any consistent $\mathcal {R}$. In particular, the approach developed here supports the generation of all minimal solutions; these minimal solutions are of special interest as they provide a preferred basis for model-based inference from $\mathcal {R}$. Moreover, we investigate different notions of minimality and demonstrate the flexibility of our approach by showing how alternative minimality concepts can be taken into account by slight modifications of the CLP implementation.

The rest of this paper is organized as follows: After recalling the formal background of conditional logics as it is given in [1] and as far as it is needed here (Sect. 2), we elaborate the birds-penguins scenario sketched above as an illustration for a conditional knowledge base and its semantics in Sect. 3. The definition of the constraint satisfaction problem $\textit{CR}(\mathcal {R})$ and its solution set denoting all c-representations for $\mathcal {R}$ is given in Sect. 4. In Sect. 5, a declarative, high-level CLP program GenOCF solving $\textit{CR}(\mathcal {R})$ is developed, observing the objective of being as close as possible to $\textit{CR}(\mathcal {R})$. Its realization in Prolog is described in detail, as well as the modifications needed for alternative notions of minimality. In Sect. 6, GenOCF is evaluated with respect to a series of some first example applications. Section 7 concludes the paper and points out further work.

2 Background

We start with a propositional language $\mathcal L$, generated by a finite set $\varSigma$ 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 $\varOmega$ denote the set of possible worlds over $\mathcal L$; $\varOmega$ 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 $\varSigma$. For $\omega \in \varOmega$, $\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 “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 $\varOmega$ 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):

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

(1)

To give appropriate semantics to conditionals, they are usually considered within richer structures such as epistemic states. 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) [18], and possibility distributions [4], 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 [18]. An OCF is a function

$$\begin{aligned} \kappa :\, \varOmega \rightarrow {\mathbb {N}} \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; therefore, $\kappa (\omega ) = 0$ for at least one $\omega \in \varOmega$. Each such ranking function 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\} &{} {\text { if }}~ A ~{\text { is satisfiable}} \\ \infty &{} {\text { otherwise}} \end{array}\right. } \end{array} \end{aligned}$$

(2)

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

$$\begin{aligned} \kappa ((B|A)) = {\left\{ \begin{array}{ll} \kappa (AB) - \kappa (A) &{} {\text {if }}~ \kappa (A) \not = \infty \\ \infty &{} \text { otherwise} \end{array}\right. } \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) \text { iff } \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)$.

3 Example

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.

Suppose we have the propositional atoms

$f$ - flying, $b$ - birds, $p$ - penguins, $w$ - winged animals, $k$ - kiwis.

Let the set $\mathcal{R}$ consist of the following conditionals:                   

$\mathcal{R}$	$r_1$:	$(f|b)$	birds fly
	$r_2$:	$(b|p)$	penguins are birds
	$r_3$:	$(\overline{f}|p)$	penguins do not fly
	$r_4$:	$(w|b)$	birds have wings
	$r_5$:	$(b|k)$	kiwis are birds

Figure 1 shows a ranking function $\kappa$ that accepts all conditionals given in $\mathcal {R}$. Thus, for any $i \in \{1,2,3,4,5\}$ it holds that $\kappa \, {\models }_{\mathcal{O}} \, R_i$.

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

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

Fig. 1.

Ranking function $\kappa$ accepting the rule set $\mathcal{R}$ given in Example 1.

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

$$\begin{aligned} \kappa \, {\models }_{\mathcal{O}} \, (w|k) \end{aligned}$$

i.e., the conditional $(w|k)$ is accepted by $\kappa$. Thus, from their superclass birds, kiwis inherit the property of having wings.

4 Specification of Ranking Functions as Solutions of a Constraint Satisfaction Problem

Given a set $\mathcal {R}= \{R_1,\ldots ,R_n\}$ of conditionals, a ranking function $\kappa$ that accepts every $R_i$ represents an epistemic state of an agent accepting $\mathcal {R}$. If there is no $\kappa$ that accepts every $R_i$ then $\mathcal {R}$ is inconsistent. For the rest of this paper, we assume that $\mathcal {R}$ is consistent.

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)$. Thus, every such $\kappa$ inductively completes the knowledge given by $\mathcal {R}$, and it is a vital question whether some $\kappa '$ is to be preferred to some other $\kappa ''$, or whether there is a unique “best” $\kappa$. Different ways of determining a ranking function are given by system Z [9, 10] or its more sophisticated extension system $Z^{*}$ [9], see also [6]; for an approach using rational world rankings see [19]. For quantitative knowledge bases of the form $\mathcal {R}_x = \{(B_1|A_1)[x_1],\ldots ,(B_n|A_n)[x_n]\}$ with probability values $x_i$ and with models being probability distributions $P$ satisfying a probabilistic conditional $(B_i|A_i)[x_i]$ iff $P(B_i|A_i) = x_i$, a unique model can be choosen by employing the principle of maximum entropy [11, 16, 17]; the maximum entropy model is a best model in the sense that it is the most unbiased one among all models satisfying $\mathcal {R}_x$.

Using the maximum entropy idea, in [13] a generalization of system Z$^{*}$ is suggested. Based on an algebraic treatment of conditionals, the notion of conditional indifference 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 $\kappa _0, \kappa _{i}^+, \kappa _{i}^- \in \mathbb {Q}, \ 1 \leqslant i \leqslant n,$ such that for all $\omega \in \varOmega$,

$$\begin{aligned} \kappa (\omega ) = \kappa _0 + \sum _{1 \leqslant i \leqslant n \atop \omega \models A_i B_i} \kappa _{i}^+ + \sum _{1 \leqslant i \leqslant n \atop \omega \models A_i \overline{B_i}} \kappa _{i}^-. \end{aligned}$$

(5)

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 $\kappa _{i}^+, \kappa _{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 $\kappa _{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 $\kappa _{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 )$.

$\kappa _0$ is a normalization constant ensuring 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 (5) and $\kappa _{i}^+ = 0$, $\kappa _{i}^- \geqslant 0$ (and thus also $\kappa _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}$$

(6)

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 (6) 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 $\kappa _{1}^-$, ..., $\kappa _{n}^-$. In [2] this situation is formulated as a constraint satisfaction problem $\textit{CR}(\mathcal {R})$ whose solutions are vectors of the form $(\kappa _{1}^-, \ldots , \kappa _{n}^-)$ determining c-representations of $\mathcal {R}$. The development of $\textit{CR}(\mathcal {R})$ exploits (2) and (5) to reformulate (6) and requires that the $\kappa _{i}^-$ are natural numbers (and not just rational numbers). In the following, we set $\min (\emptyset ) = \infty$.

Definition 2.

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

$$\begin{aligned}&\kappa _{i}^- \geqslant 0 \end{aligned}$$

(7)

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

(8)

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

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

Proposition 1.

For $\mathcal {R}= \{(B_1|A_1),\ldots ,(B_n|A_n)\}$ let $\vec {\kappa }= (\kappa _{1}^-, \ldots , \kappa _{n}^-) \in Sol _{ CR }(\mathcal {R})$. Then the function $\kappa$ defined by

$$\begin{aligned} \kappa (\omega ) = \sum _{1 \leqslant i \leqslant n \atop \omega \models A_i \overline{B_i}} \kappa _{i}^- \end{aligned}$$

(9)

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

All c-representations built from (7), (8), and (9) provide an excellent basis for model-based inference [12, 13]. However, from the point of view of minimal specificity (see e.g. [4]), those c-representations with minimal $\kappa _{i}^-$ yielding minimal degrees of implausibility are most interesting.

While different orderings on $Sol _{ CR }(\mathcal {R})$ can be defined, leading to different minimality notions, in the following we will first focus on the ordering on $Sol _{ CR }(\mathcal {R})$ induced by taking the sum of the $\kappa _{i}^-$, i.e.

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

(10)

A vector $\vec {\kappa }$ is sum-minimal (just called minimal in the following) iff there is no vector $\vec {\kappa }'$ such that $\vec {\kappa }'\prec _{+}\vec {\kappa }$ where $\prec _{+}$ is the irreflexive subrelation of $\preccurlyeq _{+}$. As we are interested in minimal $\kappa _{i}^-$-vectors, an important question is whether there is always a unique minimal solution. This is not the case; the following example that is also discussed in [15] illustrates that $Sol _{ CR }(\mathcal {R})$ may have more than one minimal element.

Example 2.

Let $\mathcal {R}_{ birds } = \{R_1, \, R_2, \, R_3\}$ be the following set of conditionals:

$$\begin{aligned} \begin{array}{lll} R_1: &{} (f|b) &{}\qquad {{{\underline{b}}}irds~ {{\underline{f}}}ly}\\ R_2: &{} (a|b) &{} \qquad {{{\underline{b}}}irds~ are~ {{\underline{a}}}nimals}\\ R_3: &{} (a|fb) &{} \qquad {{{\underline{f}}}lying ~{{\underline{b}}}irds~ are~ {{\underline{a}}}nimals} \end{array} \end{aligned}$$

From (8) we get

$$\begin{aligned} \begin{array}{l} \kappa _{1}^- > 0\\ \kappa _{2}^- > 0 - min\{\kappa _{1}^-, \, \kappa _{3}^-\}\\ \kappa _{3}^- > 0 - \kappa _{2}^- \end{array} \end{aligned}$$

and since $\kappa _{i}^- \geqslant 0$ according to (7), the two vectors

$$\begin{aligned} \begin{array}{l} sol _1 = (\kappa _{1}^-, \kappa _{2}^-, \kappa _{3}^-) = (1, 1, 0) \\ sol _2 = (\kappa _{1}^-, \kappa _{2}^-, \kappa _{3}^-) = (1, 0, 1) \end{array} \end{aligned}$$

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

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

In this section, we will develop a CLP program GenOCF solving $\textit{CR}(\mathcal {R})$. Our main objective is to obtain a declarative program that is as close as possible to the abstract formulation of $\textit{CR}(\mathcal {R})$ while exploiting the concepts of constraint logic programming. We will employ finite domain constraints, and from (7) we immediately get a lower bound for $\kappa _{i}^-$. Considering that we are interested mainly in minimal solutions, due to (8) we can safely restrict ourselves to $n$ as an upper bound for $\kappa _{i}^-$, yielding

$$\begin{aligned} 0 \leqslant \kappa _{i}^- \leqslant n \end{aligned}$$

(11)

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}{ll} {{\mathtt{{variables([a_1, \ldots , a}}}}_m]) &{} \mathtt{{\%}} ~{\text {list of atoms in}}~ \varSigma \\ {{\mathtt{{conditional}}}(i,{\langle A_i \rangle },{\langle B_i \rangle })} &{} \mathtt{{\%}}~{\text {representation of ith conditional}}~ (B_i|A_i) \\ {{\mathtt{{indices([1,...,}}}}n]) &{}\mathtt{{\%}}~{\text {list of indices}}~ \{1,\ldots ,n\}\\ \end{array} \end{aligned}$$

If $\varSigma = \{a_1,\ldots , a_m\}$ is the set of atoms, we assume a fixed ordering $a_1 < a_2 < \ldots < a_m$ on $\varSigma$ given by the predicate variables([${a_1}$,...,${a_m}$]). The fixed index ordering gven by indices([1,...,${n}$]) ensures that the conditionals are ordered consecutively from 1 to $n$. Thus, the i-th conditional can be accessed by conditional(${i}$, A,B), and in a solution vector [K $_1$,...,K $_{n}$], the i-th component K $_{\mathtt{{i}}}$ is the $\kappa ^-$-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 \ldots \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 \{{\mathtt{{0, 1, {\_}}}}\}$. Such a list [${b}_1$,...,${b_m}$] represents the conjunctions of atoms obtained from $\dot{a}_1 \wedge \dot{a}_2 \wedge \ldots \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 &{} \text { if }~ b_k = 1 \\ \overline{a_k} &{} \text { if }~ b_k = 0 \\ \top &{} \text { if }~ b_k = \_ \end{array}\right. } \end{array} \end{aligned}$$

Example 3.

The internal representation of the knowledge base presented in Example 1. is shown in Fig. 2.

Fig. 2.

Internal representation of the knowledge base from Example 1.

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) given in Sect. 2:

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

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

Using these predicates, in the following subsections we will present the complete source code of the constraint logic program GenOCF solving $\textit{CR}(\mathcal {R})$.

5.2 Generation of Constraints

The particular program code given here uses the SICStus Prolog system¹ and its clp(fd) library implementing constraint logic programming over finite domains [14].

The main predicate kappa/2 expecting a knowledge base KB of conditionals and yielding a vector K of $\kappa _{i}^-$ values as specified by (8) is presented in Fig. 3.

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 corresponding to the formulas (11) and (8) are generated, constraining the elements of K accordingly. Finally, labeling([], K) yields a list of $\kappa _{i}^-$ values. Upon backtracking, this will enumerate all possible solutions with an upper bound of $n$ as in (11) for each $\kappa _{i}^-$. Later on, we will demonstrate how to modify kappa/2 in order to take minimality into account (Sect. 5.3).

Fig. 3.

Main predicate kappa/2

How the subgoal constrain_K(Is, K) in kappa/2 generates a constraint for each index $i \in \{1,\ldots ,n\}$ according to (8) is defined in Fig. 4.

Fig. 4.

Constraining the vector K representing $\kappa _{1}^-,\ldots ,\kappa _{n}^-$ as in (8)

Given an index I, constrain_Ki(I,K) (cf. Fig. 4) determines all worlds verifying and falsifying the I-th conditional; over these two sets of worlds the two $\min$ expressions in (8) are defined. Two lists VS and FS of sums corresponding exactly to the first and the second sum, repectively, in (8) are generated (how this is done is defined in Fig. 5 and will be explained below). With the constraint variables Vmin and Fmin denoting the minimum of these two lists, the constraint

$$\begin{aligned} {\mathtt {Ki}} ~\mathtt{\#> } ~{\mathtt { Vmin - Fmin} } \end{aligned}$$

given in the last line of Fig. 4 reflects precisely the restriction on $\kappa _{i}^-$ given by (8).

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. 5) 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 (8), i.e., it is the sum of all Kj such that J $\ne$ I and W falsifies the j-th conditional.

Fig. 5.

Generating list of sums of $\kappa _{i}^-$ as in (8)

Example 4.

Suppose that kb_birds.pl is a file containing the conditionals of the knowledge base $\mathcal {R}_{ birds }$ given in Example 2.. Then the first five solutions generated by the program given in Figs. 3, 4, 5 are:

Note that the first and the fourth solution are the minimal solutions.

Example 5.

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

5.3 Generation of Minimal Solutions

The enumeration predicate labeling/2 of SICStus Prolog allows for an option that minimizes the value of a cost variable. Since we are aiming at minimizing the sum of all $\kappa _{i}^-$, the constraint sum(K, #=, S) introduces such a cost variable S. Thus, exploiting the SICStus Prolog minimization feature, we can easily modify kappa/2 to generate a minimal solution: We just have to replace the last subgoal labeling([], K) in Fig. 3 by the two subgoals given in Fig. 6.

Fig. 6.

Predicate kappa_min_sum/2 generating a minimal solution

With this modification, the obtained predicate kappa_min_sum/2 returns a single minimal solution (and fails on backtracking). Hence calling ?- kappa_min_sum(’kb_birds.pl’, K). similar as in Example 4. yields the minimal solution K = [0,1,1].

However, as pointed out in Sect. 4, there are good reasons for considering not just a single minimal solution, but all minimal solutions. We can achieve the computation of all minimal solutions by another slight modification of kappa/2. This time, the enumeration subgoal labeling([], K) in Fig. 3 is preceded by two new subgoals as in kappa_min_sum_all/2 in Fig. 7.

Fig. 7.

Predicate kappa_min_all/2 generating exactly all minimal solutions

The first new subgoal sum(K, #=, S) introduces a constraint variable S just as in kappa_min_sum/2. In the subgoal min_sum_kappas(K, S), this variable S is constrained to the sum of a minimal solution as determined by min_sum_kappas(K, Min). These two new subgoals ensure that in the generation caused by the final subgoal labeling([], K), exactly all minimal solutions are enumerated.

Example 6.

Continuing Example 4., calling

yields the two minimal solutions for $\mathcal {R}_{ birds }$.

Example 7.

For the situation in Example 5., kappa_min_sum_all/2 reveals that there is a unique minimal solution:

The predicate rank/3 given in Fig. 8 can be used for determining the OCF $\kappa _{\vec {\kappa }}$ induced by the vector $\vec {\kappa }= (\kappa _{1}^-, \kappa _{2}^-, \kappa _{3}^-, \kappa _{4}^-, \kappa _{5}^-) = (1, 2, 2, 1, 1)$ according to (9), yielding the ranking function given in Fig. 1.

Fig. 8.

Predicate rank/3 determining the rank of a world for given

5.4 Alternative Notions of Minimality

In general, it is still an open problem how to strengthen the requirements defining a c-representation so that a unique minimal solution is guaranteed to exist. Such a strengthening could use alternative minimality criteria. In this subsection, we illustrate the realization of an alternative minimality criterion in our constraint logic programming approach.

Instead of ordering the vectors $\vec {\kappa }$ by the sum of their components as done by $\preccurlyeq _{+}$ in (10), we could consider a componentwise ordering $\preccurlyeq _{ cw }$

$$\begin{aligned} (\kappa _{1}^-, \ldots , \kappa _{n}^-) \preccurlyeq _{ cw }({\kappa '}_{1}^{-}, \ldots , {\kappa '}_{n}^{-}) \quad \text{ iff } \quad \kappa _{i}^- \leqslant {\kappa '}_{i}^{-} \text { for all }~ i \in \{1,\ldots ,n\} \end{aligned}$$

(12)

yielding a partial order $\preccurlyeq _{ cw }$ on $Sol _{ CR }(\mathcal {R})$.

Let $\prec _{ cw }$ denote the irreflexive subrelations of $\preccurlyeq _{ cw }$ , respectively. A vector $\vec {\kappa }$ is componentwise minimal (or cw-minimal) iff there is no vector $\vec {\kappa }'$ with $\vec {\kappa }'\prec _{ cw }\vec {\kappa }$. In order to demonstrate the flexibility of the high-level CLP implementation realized in GenOCF, we will show how slight modifications of the program realize these alternative notions of minimality.

Fig. 9.

Predicate kappa_min_cw_all computing all componentwise minimal solutions

The predicate kappa_min_cw_all/2 as given in Fig. 9 computes all componentwise minimal solution for a knowledge base. After consulting the knowledge base KB, the subgoal kappa(KB, K) says that K is a solution for KB, while minimal_cw(K) ensures that K is cw-minimal. The predicate minimal_cw/1 enforces that there is no solution vector K2 for the given knowledge base that is strictly less than K: If constraints(K2) succeeds where constraints/1 is given as in Fig. 3, then there is no labeling for K2 under the constraint lt_cw(K2,K). The predicate lt_cw/2 takes two vectors of the same length and succeeds if there is at least one position where the component at that position in the first vector is strictly less than the corresponding component in the second vector (ensured by the constraint with $\mathtt \#<$ in lt_cw/2 in Fig. 9), and all other corresponding vector components are less or equal (ensured by the constraints with #= in lt_cw/2 and with $\mathtt \#=<$ in leq_cw/2).

Example 8.

Continuing Example 6., calling

reveals that in this simple example the set of sum-minimal solutions coincides with the set of cw-minimal solutions.

In our further invstigations, we will extend GenOCF to be able to take into account more alternative minimality criteria. For instance, as illustrated in the previous example, GenOCF determines that both $\kappa _1 = {\mathtt{{[1,0,1]}}}$ and $\kappa _2 = {\mathtt{{[1,1,0]}}}$ are minimal with respect to $\preccurlyeq _{+}$ and also with respect to $\preccurlyeq _{ cw }$ for $\mathcal {R}_{ birds }$. However, we could also compare the full OCFs induced by $\kappa _1$ and $\kappa _2$ according to (9). These induced OCFs are given by the following table:

Note that under $\kappa _1$, the world $\overline{f}b\overline{a}$ has a smaller rank than under $\kappa _2$, while all other worlds have the same rank under both OCFs. Further theoretical and experimental studies are needed for this and still other minimality criteria.

6 Example Applications and First Evaluation

Although the objective in developing GenOCF was on being as close as possible to the abstract formulation of the constraint satisfaction problem $\textit{CR}(\mathcal {R})$, we will present the results of some first example applications we have carried out.

For $n \geqslant 1$, we generated synthetic knowledge bases kb_synth $\mathtt{< }$ ${ {n}}$ $\mathtt{> }$_c $\mathtt{< }$ $\mathtt{2n }-1$ $\mathtt{> }$.pl according to the following schema: Using the variables $\{f\} \cup \{a_1, \ldots , a_n\}$, kb_synth $\mathtt{< }$ ${ {n}}$ $\mathtt{> }$_c $\mathtt{< }$ $\mathtt{2n }-1$ $\mathtt{> }$.pl contains the $2*n -1$ conditionals given by::

$$\begin{aligned} \begin{array}{lll} (f|a_i) &{} \text { if }~i~\text { is odd, } i \in \{1,\ldots ,n\} \\ (\overline{f}|a_i) &{} \text { if }~i~\text { is even, } i \in \{1,\ldots ,n\} \\ (a_i|a_{i+1}) &{} \text { if }~i~\in \{1,\ldots ,n-1\} \end{array} \end{aligned}$$

For instance, kb_synth4_c7.pl uses the five variables $\{f, a_1, a_2, a_3, a_4\}$ and contains the seven conditionals:

$$\begin{aligned} \begin{array}{l} (f|a_1) \\ (\overline{f}|a_2)\\ (f|a_3)\\ (\overline{f}|a_4)\\ (a_1|a_2)\\ (a_2|a_3)\\ (a_3|a_4)\\ \end{array} \end{aligned}$$

The basic idea underlying the construction of these synthetic knowledge bases kb_synth $\mathtt{< }$ ${ {n}}$ $\mathtt{> }$_c $\mathtt{< }$ $\mathtt{2n }-1$ $\mathtt{> }$.pl is to establish a kind of subclass relationship between $a_{i+1}$ and $a_i$ for each $i \in \{1,\ldots ,n-1\}$ on the one hand, and to state that every $a_{i+1}$ is exceptional to $a_i$ with respect to its behaviour regarding $f$, again for each $i \in \{1,\ldots ,n-1\}$. This sequence of pairwise exceptional elements will force any minimal solution of $CR$(kb_synth $\mathtt{< }$ ${ {n}}$ $\mathtt{> }$_c $\mathtt{< }$ $\mathtt{2n }-1$ $\mathtt{> }$.pl) to have at least one $\kappa _{i}^-$ value of size greater or equal to $n$.

From kb_synth $\mathtt{< }$ $n$ $\mathtt{> }$_c$\mathtt{< }$ $m$ $\mathtt{> }$.pl, the knowledge bases kb_synth $\mathtt{< }$ $n$ $\mathtt{> }$_c$\mathtt{< }$ $m\!\!-\!\!j$ $\mathtt{> }$.pl are generated for $j \in \{1,\ldots , m-1\}$ by removing the last $j$ conditionals. For instance, kb_synth4_c5.pl is obtained from kb_synth4_c7.pl by removing the two conditionals $\{(a_2|a_3)$, $(a_3|a_4)\}$.

Fig. 10.

Execution times (given in seconds) of GenOCF under SICStus Prolog for computing all sum-minimal solutions for various synthesized knowledge bases

Figure 10 shows the time needed by GenOCF for computing all sum-minimal solutions for some of these synthesized knowledge bases with different numbers of variables and conditionals. Execution times are given in seconds for measurements taken in the following environment: SICStus 4.0.8 (x86-linux-glibc2.3), Intel Core 2 Duo E6850 3.00GHz.

Of course, these knowledge bases are by no means representative, and further evaluation is needed. In particular, investigating the complexity depending on the number of variables and conditionals and determining an upper bound for worst-case complexity has still to be done; the graphical illustration in Fig. 10 clearly indicates an exponential increase. However, it should be noted that the high-level, declarative approach taken here provides many opportunities for improving run-time efficiency. For instance, it suffices to compute the verifying and the falsifying worlds for each conditional only once instead of multiple times when generating the constraints for a solution vector K as done in Fig. 4. Furthermore, while the code for GenOCF given above uses SICStus Prolog, we also have a variant of GenOCF for the SWI Prolog system² [20]. In our further investigations, we want to evaluate GenOCF also using SWI Prolog, to elaborate the changes required and the options provided when moving between SICStus and SWI Prolog, and to study whether there are any significant differences in execution that might depend on the two different Prolog systems and their options.

7 Conclusions and Further Work

While for a set of probabilistic conditionals $(B_i|A_i)[x_i]$ the principle of maximum entropy yields a unique model, for a set $\mathcal {R}$ of qualitative default rules $(B_i|A_i)$ there may be several minimal ranking functions. In this paper, we developed a CLP approach for solving $\textit{CR}(\mathcal {R})$, realized in the Prolog program GenOCF. The solutions of the constraint satisfaction problem $\textit{CR}(\mathcal {R})$ are vectors of natural numbers $\vec {\kappa }= (\kappa _{1}^-, \ldots , \kappa _{n}^-)$ that uniquely determine an OCF $\kappa _{\vec {\kappa }}$ accepting all conditionals in $\mathcal {R}$. GenOCF is also able to generate exactly all minimal solutions of $\textit{CR}(\mathcal {R})$ for different notions of minimality. Minimal solutions of $\textit{CR}(\mathcal {R})$ are of special interest for model-based inference.

In general, it is an open problem how to strengthen the requirements defining a c-representation so that a unique solution is guaranteed to exist. The declarative nature of constraint logic programming supports easy constraint modification, enabling the experimentation and practical evaluation of different notions of minimality for $Sol _{ CR }(\mathcal {R})$ and of additional requirements that might be imposed on a ranking function. Furthermore, in [8] the framework of default rules concidered here is extended by allowing not only default rules in the knowledge base $\mathcal {R}$, but also strict knowledge, rendering some worlds completely impossibe. This can yield a reduction of the problem’s complexity, and it will be interesting to see which effects the incorporation of strict knowledge will have on the CLP approach presented here.