Descriptor Revision for Conditionals: Literal Descriptors and Conditional Preservation

Abstract

Descriptor revision by Hansson is a framework for addressing the problem of belief change. In descriptor revision, different kinds of change processes are dealt with in a joint framework. Individual change requirements are qualified by specific success conditions expressed by a belief descriptor, and belief descriptors can be combined by logical connectives. This is in contrast to the currently dominating AGM paradigm shaped by Alchourrón, Gärdenfors, and Makinson, where different kinds of changes, like a revision or a contraction, are dealt with separately. In this article, we investigate the realisation of descriptor revision for a conditional logic while restricting descriptors to the conjunction of literal descriptors. We apply the principle of conditional preservation developed by Kern-Isberner to descriptor revision for conditionals, show how descriptor revision for conditionals under these restrictions can be characterised by a constraint satisfaction problem, and implement it using constraint logic programming. Since our conditional logic subsumes propositional logic, our approach also realises descriptor revision for propositional logic.

1 Introduction

The work by Alchourrón, Gärdenfors, and Makinson [1] (AGM) and its successors have shaped the currently dominating paradigm for belief change. By AGM, mainly three main kinds of belief changes are subject of interest: revision (incorporating new beliefs into an agent’s belief state while maintaining consistency), contraction (removing beliefs from the agent’s belief state), and expansion (incorporating new beliefs into an agent’s belief state without maintaining consistency). The most prominent difference between these kinds of changes is their success condition. The approach to the problem of belief change by AGM is top-down, starting from the axiomatisation of each of the three kinds of changes and then investigating the representational issues through representation theorems.

In the last 20 years, the AGM theory has been extended into several directions and has been deeply investigated. This gives new insights on the requirements of representation and conceptual problems of (AGM) belief change. In particular, for Hansson [16], the requirement of epistemic states for iterative belief change [8], the central role of conditionals in belief change and non-monotonic logic [23, 24] and problems like the non-finite representability of the result of a contraction [14] or concerns about the “select-and-intersect” approach of AGM [16] were a motivation to design a new framework for belief change. Descriptor revision by Hansson [10] follows the top-down approach to belief change, but, in contrast to the AGM paradigm, in descriptor revision, different kinds of changes are expressible in one joint framework. For this, Hansson introduced a language for success conditions, called belief descriptors. Through belief descriptors, success conditions become an explicit part of the change process, instead of hiding them in distinct kinds of operations having different success conditions. This allows to express and analyse change processes that go beyond the classical AGM operations, e.g., a change process where a contraction of a belief $\alpha$ and a revision by $\beta$ appear at the same time. Descriptor revision has been broadly investigated by Hansson [11,12,13,14,15,16], but did not gain as much attention as AGM [26]. In particular, to the best of our knowledge, until now, no approach to the realisation of descriptor revision is available.

In this article, we investigate descriptor revision for a conditional logic while using ordinal conditional functions [25], also called ranking functions, as representation for epistemic states. We outline how to instantiate the framework of descriptor revision for this logic and design an approach for its realisation. Furthermore, for descriptor revision we use and adapt the sophisticated principle of conditional preservation by Kern-Isberner [18, 19] for ranking functions. In summary, the main contributions of this article are:

• Introduction of conditional descriptor revision, which introduces the principle of conditional preservation to the framework of descriptor revision.

• A sound and complete characterisation of conditional descriptor revision for elementary descriptors by a constraint satisfaction problem.

• Implementation of elementary descriptor revision using constraint logic programming and by employing the developed characterisation.

The article is organised as follows. In Sect. 2, we present logical preliminaries. We recall descriptors and descriptor revision in Sect. 3. Section 4 introduces our framework of conditional descriptor revision. Section 5 develops a characterisation of conditional descriptor revision for elementary descriptors by a constraint satisfaction problem. The implementation of this approach is sketched in Sect. 6. We conclude and point out future work in Sect. 7.

2 Logical Preliminaries

Let $\varSigma$ be a propositional signature (non-empty finite set of propositional variables) and $\mathcal {L}^\mathrm {prop}$ the propositional language over $\varSigma$. With upper case letters $A,B,C,\ldots$, we denote formulas in $\mathcal {L}^\mathrm {prop}$ and with lower case letters $a,b,c,\ldots$ propositional variables from $\varSigma$. We allow the typical abbreviation $A \rightarrow B$ for $\lnot A \vee B$, abbreviate $A \wedge B$ by AB and write $\overline{A}$ for $\lnot A$. With $\top$, we denote a propositional tautology and with $\bot$ a propositional falsum. The set of propositional interpretations $\varOmega =\mathcal {P}(\varSigma )$, also called set of worlds, is identified with the set of corresponding complete conjunctions over $\varSigma$, where $\mathcal {P}(\cdot )$ is the powerset operator. Propositional entailment is denoted by $~\models ~$, the set of models of A with $Mod (A)$, and $Cn(A)=\{ B \mid A~\models ~B \}$ is the deductive closure of A. For a set X, we define $Cn(X)=\{ B \mid X~\models ~B \}$ and say X is deductively closed if $X = Cn(X)$. In the context of belief change, a deductively closed set is also called a belief set.

A function $\kappa : \varOmega \rightarrow \mathbb {N}$ such that $\kappa ^{-1}(0) \ne \emptyset$ is a called a ordinal conditional function (OCF), also called a ranking function [25]. It expresses degrees of implausibility of interpretations. This is lifted to propositional formulas A by defining $\kappa (A) := \min \{\kappa (\omega ) \mid \omega ~\models ~A\}$, where $\min \emptyset =\infty$, yielding a function $\kappa : \mathcal {L} \rightarrow \mathbb {N}\cup \{\infty \}$ which specifies a degree of implausibility for each formula. With $Mod (\kappa ) =\{\omega \mid \kappa (\omega )=0\}$ we denote the minimal interpretations with respect to $\kappa$, and $Bel \left( \kappa \right)$ denotes the theory of propositional formulas that hold in all $\omega \in Mod (\kappa )$.

Over $\varSigma$ and $\mathcal {L}^\mathrm {prop}$, we define the set of conditionals $\mathcal {L}^\mathrm {cond}= \{ (B|A) \mid A,B \in \mathcal {L}\}$. A conditional (B|A) formalizes “if A then usually B” and establishes a plausible connection between the antecedent A and the consequent B. Conditionals with tautological antecedents are taken as plausible statements about the world. Because conditionals go well beyond classical logic, they require a richer setting for their semantics than classical logic. Following De Finetti [9], a conditional (B|A) can be verified (falsified) by a possible world $\omega$ iff $\omega ~\models ~AB$ ($\omega ~\models ~A \overline{B}$). If $\omega \not \models A$, then we say the conditional is not applicable to $\omega$.

Ranking functions serve here as interpretations in a model theory for a conditional logic. We say a conditional (B|A) is accepted in a ranking function $\kappa$, written as $\kappa ~\models ~(B|A)$, iff $\kappa (AB) < \kappa (A\overline{B}),$ i.e., iff the verification AB of the conditional is more plausible than its falsification $A\overline{B}$. For a propositional formula A, we define $\kappa ~\models ~A$ if $\kappa ~\models ~(A|\top )$, i.e., iff $\kappa (A) < \kappa (\overline{A})$ or equivalently iff $\kappa (\overline{A}) > 0$, since at least one of $\kappa (A), \kappa (\overline{A})$ must be 0 due to $\kappa ^{-1}(0) \ne \emptyset$. The models of a conditional $(B|A)$ are the set of all ranking functions accepting $(B|A)$, i.e. $Mod ((B_1|A_1)) = \{ \kappa \mid \kappa \models (B|A) \}$. A conditional $(B_1|A_1)$ entails $(B_2|A_2)$, written $(B_1|A_1)~\models ~(B_2|A_2)$, if $Mod ((B_1|A_1)) \subseteq Mod ((B_2|A_2))$ holds. Furthermore, we define the set of consequences for $X\subseteq \mathcal {L}^\mathrm {cond}$ by $Cn(X) = \{ (B|A) \mid X~\models ~(B|A) \}$. As usual, $X\subseteq \mathcal {L}^\mathrm {cond}$ is called deductively closed if $X = Cn(X)$. This ranking function based semantics can be mapped to, and can also be obtained from, other semantics of conditionals [4].

Example 1

(adapted [5]). Let $\varSigma =\{p,b,f\}$ with p meaning “penguin”, b “bird” and f “able to fly”. “Birds normally fly” is modelled with the conditional $r_1=(f|b)$, “penguins normally do not fly” with $r_2=(\overline{f}|p)$, and “penguins are normally birds” with $r_3=(b|p)$. Consider the ranking function $\kappa _ p$ from Table 1, which will act as our running example for the following sections (where we will also elaborate the other ranking function and conditionals shown in Table 1). Table 1 also contains the verifying and falsifying interpretations of the conditional $(\overline{f}|p)$. The ranking function $\kappa _ p$ accepts all conditionals in $\mathcal {R}_{ pen }= \{r_1, r_2, r_3 \}$, i.e. $\kappa _ p \models r_i$ for all $1\leqslant i\leqslant 3$. For example, $\kappa ~\models ~r_1$ because $\kappa (bf) = 0 < 1 = \kappa (b\overline{f})$ holds. For the rest of the article, we will assume that the ranking function $\kappa _ p$ is the initial belief state representing the beliefs about penguins, flying, and birds of our agent.

Table 1. Verifying (v) and falsifying (f) interpretations for the conditionals $(p|b)$, $(f|p)$, and $(\overline{f}|p)$, and the ranking functions for the running penguin example.

3 Descriptors and Descriptor Revision

The main building blocks of descriptor revision are belief descriptors, which provide a language for expressing membership constraints for a belief set.

Definition 1

(Descriptor [15]). Let $\mathcal {L}$ be a logical language. For any sentence $\varphi \in \mathcal {L}$ the expression $\mathfrak {B}{\varphi }$ is an atomic descriptor (over $\mathcal {L}$). Any connection of atomic descriptors with disjunction, conjunction and negation is called a molecular descriptor (over $\mathcal {L}$). A composite descriptor (over $\mathcal {L}$) is a set of molecular descriptors (over $\mathcal {L}$).

As stated by Hansson [15], composite descriptors are just denoted as descriptors. A molecular descriptor of the form $\mathfrak {B}{\varphi }$ or $\lnot \mathfrak {B}{\varphi }$ is called a literal descriptor. An elementary descriptor is a set of literal descriptors (and therefore a descriptor).

Definition 2

(Descriptor Semantics [15]). An atomic descriptor $\mathfrak {B}{\varphi }$ holds in a belief set X, written $X \Vdash \mathfrak {B}{\varphi }$, if $\varphi \in X$. This is lifted to molecular descriptors truth-functionally. A descriptor $\varPsi$ holds in X, likewise written $X \Vdash \varPsi$, if $X \Vdash \alpha$ holds for every molecular descriptor $\alpha \in \varPsi$.

For an example of descriptors, consider the following example.

Example 2

Assume that $\mathcal {L}_{ab}$ is the propositional language over $\varSigma =\{a,b\}$ and $X=Cn(a\,\vee \, b)$. Then, $\lnot \mathfrak {B}{a}$ expresses that a is not part of the belief set, whereas $\mathfrak {B}{\lnot a}$ states that the formula $\lnot a$ is part of the belief set, e.g. $X \Vdash \lnot \mathfrak {B}{a}$ and $X \not \Vdash \mathfrak {B}{\lnot a}$. Likewise, $\mathfrak {B}{a}\, \vee \, \mathfrak {B}{b}$ expresses that a or b is believed, whereas $\mathfrak {B}{(a\,\vee \, b)}$ states that the formula $a\vee b$ is believed, e.g. $X \Vdash \mathfrak {B}{(a\,\vee \, b)}$ and $X \not \Vdash \mathfrak {B}{a}\,\vee \,\mathfrak {B}{b}$.

For the setting of belief change, we assume that every agent is equipped with a belief state, also called epistemic state, which contains all information necessary for performing belief change operations. We denote belief states by $K,K_1,K_2,\ldots$ following the notion of Hansson [15]. General descriptor revision does not specify what a belief state is, but assumes that a belief set $Bel \left( K\right)$ is immanent for every epistemic state K. To make descriptors compatible with belief states, we naturally lift the semantics to belief states, i.e. $K \Vdash \varPsi$ if $Bel \left( K\right) \Vdash \varPsi$.

Example 3 (Continued)

Assume ranking functions as a representation of belief states. Let $\kappa _ p$ be the belief state from Table 1 and let $\varPsi = \{ \mathfrak {B}{\overline{p}},\,\mathfrak {B}{(b \rightarrow f)},\,\lnot \mathfrak {B}{b\overline{f}} \}$ be an elementary descriptor. The descriptor $\varPsi$ expresses belief in $\overline{p}$ (it is not a penguin) and $b \rightarrow f$ (a bird flies) and not believing $b\overline{f}$ (it is a non-flying bird). The immanent belief set of $\kappa _ p$ is $Bel \left( \kappa _ p \right) =Cn(\overline{p}\,\wedge \,(b\rightarrow f))$. The descriptor $\varPsi$ holds in $\kappa _ p$, i.e. $\kappa _ p \Vdash \varPsi$, since $\overline{p}\in Bel \left( \kappa _ p \right)$, $b\rightarrow f\in Bel \left( \kappa _ p \right)$ and $b\overline{f}\notin Bel \left( \kappa _ p \right)$.

AGM theory [1] focuses on properties of revision (or contraction) operations by examining the interconnection between prior belief state, new information and posterior belief state of a change. Descriptor revision examines the interconnection between prior belief state and posterior belief states that satisfy a particular descriptor. Let $\mathbb {K}_K$ denote the set of all reasonable conceivable successor belief states for a belief state K. A descriptor revision by a descriptor $\varPsi$ is the process of choosing a state $K'$ from $\mathbb {K}_K$ such that $K' \Vdash \varPsi$. We abstract from the internal process of how $\mathbb {K}_K$ is obtained and define descriptor revision¹ as follows.

Definition 3

(Descriptor Revision, Adapted [15]). Let K be a belief state, $\mathbb {K}_K$ a set of belief states and $C: \mathcal {P}(\mathbb {K}_K) \rightarrow \mathbb {K}_K$ be a choice function. Then the change from K to $K^\circ =K \circ \varPsi$ is called a descriptor revision by $\varPsi$ realised by C over $\mathbb {K}_K$ if the following holds:

$$\begin{aligned} K \circ \varPsi = C( \, \{ K' \in \mathbb {K}_K \mid K' \Vdash \varPsi \} \, ) \end{aligned}$$

(1)

We say that the change from K to $K^\circ$ is a descriptor revision (by $\varPsi$), if C and $\mathbb {K}_K$ (and $\varPsi$) exist such that the change from K to $K^\circ$ is realised by C over $\mathbb {K}_K$. We also say $K^\circ$ is the result of the descriptor revision of K (by $\varPsi$ under $\mathbb {K}_K$).

Descriptors allow to express a variety of different success conditions, e.g.

• $\{\mathfrak {B}{\varphi }\}$ Revision by $\varphi$

• $\{\lnot \mathfrak {B}{\varphi }\}$ Contraction by $\varphi$ (also called revocation [16])

• $\{ \lnot \mathfrak {B}{\varphi }, \lnot \mathfrak {B}{\lnot \varphi } \}$ Giving up the judgement on $\varphi$ (also called ignoration [5]).

Additionally, Hansson provides the following examples [16]:

• $\{ \mathfrak {B}{\varphi _1},\ldots ,\mathfrak {B}{\varphi _n} \}$ Package revision by $\{ \varphi _1,\ldots ,\varphi _n \}$

• $\{ \lnot \mathfrak {B}{\varphi },\mathfrak {B}{\psi } \}$ Replacement of $\varphi$ by $\psi$

• $\{ \mathfrak {B}{\varphi _1}\vee \ldots \vee \mathfrak {B}{\varphi _n} \}$ Choice revision by $\{ \varphi _1,\ldots ,\varphi _n \}$

• $\{\mathfrak {B}{\varphi }\vee \mathfrak {B}{\lnot \varphi }\}$ Making up one’s mind about $\varphi$.

Note that all given examples, except for choice revision and “making up one’s mind”, are elementary descriptors. In particular, elementary descriptor revision subsumes operations of AGM, and, furthermore, also allows to express changes which lead to a revision and a contraction at the same time. For a concrete example, we continue our running example.

Example 4 (Continued)

Let $\kappa _ p$ and $\kappa ^\circ _ p$ be as in Table 1, let $\mathbb {K}_{\kappa _ p }$ be the set of all ranking functions, let C be a choice function such that $C(X)=\kappa ^\circ _ p$ if $\kappa ^\circ _ p \in X$, and let $\varPsi =\{ \mathfrak {B}{\overline{b}}\,\vee \,\mathfrak {B}{p},\,\lnot \mathfrak {B}{bf} \}$ be a descriptor. The descriptor $\varPsi$ expresses posterior belief in $\overline{b}$ or belief in p and disbelief in bf. In particular, $\lnot \mathfrak {B}{bf}$ expresses a contraction with bf (it is a flying bird), but for $\mathfrak {B}{\overline{b}}\,\vee \,\mathfrak {B}{p}$ (it is not a bird or it is a penguin), there is no straight counterpart in the AGM framework. Note that we have $Bel \left( \kappa ^\circ _ p \right) =Cn(\overline{b}\,\wedge \,\overline{p})$, and thus, it holds that $\overline{b}\in Bel \left( \kappa ^\circ _ p \right)$ and $bf \notin Bel \left( \kappa ^\circ _ p \right)$, and therefore, the descriptor $\varPsi$ holds in $\kappa ^\circ _ p$. Thus, the change from $\kappa _ p$ to $\kappa ^\circ _ p$ is a descriptor revision by $\varPsi$ realised by C over $\mathbb {K}_{\kappa _ p }$.

4 Conditional Descriptor Revision

We instantiate descriptor revision for the case in which the underlying logic is the conditional logic $\mathcal {L}^\mathrm {cond}$ and ranking functions serve as a representation for epistemic states. Furthermore, we adapt the principle of conditional preservation by Kern-Isberner [18] to the requirements of descriptor revision.

4.1 Adaptions for Conditionals in $\mathcal {L}^\mathrm {cond}$

In the formal framework of descriptor revision by Hansson, as recalled in Sect. 3, semantics of a descriptor refer to a belief set, containing formulas of the underlying logic. Thus, when using the logic $\mathcal {L}^\mathrm {cond}$, we need to refer to the set of conditionals accepted by a ranking function $\kappa$ when choosing ranking functions as representations for epistemic states. However, the belief set $Bel \left( \kappa \right)$ of a ranking function $\kappa$ is a set of propositional beliefs, i.e. $Bel \left( \kappa \right) \subseteq \mathcal {L}^\mathrm {prop}$. We define the set of conditional beliefs for a ranking function $\kappa$ as follows:

$$\begin{aligned} Bel ^ cond \left( \kappa \right) = \{\, (B|A) \mid \kappa ~\models ~(B|A) \,\} \end{aligned}$$

Clearly, the set $Bel ^ cond \left( \kappa \right)$ is a deductively closed set for every ranking function $\kappa$ and therefore a belief set. Descriptors and descriptor revision for $\mathcal {L}^\mathrm {cond}$ then refer to the set of conditional beliefs $Bel ^ cond \left( \kappa \right)$, and their formal definition can be easily obtained by correspondingly modifying Definitions 1, 2 and 3.

Note that the conditional logic $\mathcal {L}^\mathrm {cond}$ embeds the propositional logic $\mathcal {L}^\mathrm {prop}$, hence every proposition $A\in \mathcal {L}^\mathrm {prop}$ can be represented by $(A|\top )$. Moreover, the definition of $Bel ^ cond \left( \kappa \right)$ ensures compatibility of propositional beliefs with the conditional beliefs, i.e. $\{ (A|\top ) \mid A \in Bel \left( K\right) \} \subseteq Bel ^ cond \left( K\right)$. Thus, our approach to descriptor revision by conditionals, presented in the following, subsumes descriptor revision for propositions.

4.2 Conditional Preservation

When an agent performs a belief change, the change might not only affect explicit beliefs, but also implicit beliefs. Boutilier proposed that belief change should also minimize the effect on conditional beliefs [6]. Kern-Isberner introduced the principle of conditional preservation (PCP) and gave a thorough axiomatisation of PCP [17, 18] in a very general manner.

Note that the principle of conditional preservation is usually defined as a property of a change by a set of conditionals $\mathcal {R}$. However, when having a descriptor revision, the underlying change framework and its parameters and capabilities might be hidden. Thus, we abstract from the assumption that the change is done by a set of conditionals $\mathcal {R}$, and just state that a change satisfies PCP with respect to a set of conditionals $\mathcal {R}$. This allows us to say that a change satisfies the principle of conditional preservation without assuming the involvement of specific parameters in the underlying change framework. In the following, we present our relaxed variant of the principle of conditional preservation for the special case of ranking functions.

Definition 4

(PCP for OCF Changes, Adapted [20]). A change of a ranking function $\kappa$ to a ranking function $\kappa ^\circ$ fulfils the principle of conditional preservation with respect to the conditionals $\mathcal {R}=\{ (B_1|A_1),\ldots ,(B_n|A_n) \}$, if for every two multisets of propositional interpretations $\varOmega _1=\{\omega _1,\ldots ,\omega _m\}$ and $\varOmega _2=\{\omega '_1,\ldots ,\omega '_m\}$ with the same cardinality m such that the multisets $\varOmega _1$ and $\varOmega _2$ contain the same number of interpretations which verify, respectively falsify, each conditional $(B_i|A_i)$ in $\mathcal {R}$, the ranking functions $\kappa$ and $\kappa ^\circ$ are balanced in the following way:

$$\begin{aligned} \sum _{i=1}^{m} \kappa (\omega _i) - \sum _{i=1}^{m} \kappa (\omega '_i) = \sum _{i=1}^{m} \kappa ^\circ (\omega _i) - \sum _{i=1}^{m} \kappa ^\circ (\omega '_i) \end{aligned}$$

(2)

Example 5 (Continued)

Assume our agent lives in Antarctica and she starts to question her beliefs about penguins and birds. The only birds she sees in Antarctica are penguins, and moreover, she observes, through her window, a lot of penguins jumping off a cliff, and thus, flying for a moment. Her belief state is changing from $\kappa _ p$ to $\kappa ^\circ _ p$ from Table 1. Consider now the conditional $(p|b)$ expressing that birds are usually penguins, the conditional $(f|p)$ expressing that penguins usually fly, and the conditional $(\overline{f}|p)$ expressing that penguins usually don’t fly. The change from $\kappa _ p$ to $\kappa ^\circ _ p$ satisfies the principle of conditional preservation with respect to the conditionals in $\mathcal {R}=\{ (p|b), (f|p), (\overline{f}|p) \}$. For instance, the two multisets $\varOmega _1=\{ bfp, \overline{b}\,\overline{f}p \}$ and $\varOmega _2=\{ b\overline{f}p, \overline{b}fp \}$, containing for every conditional in $\mathcal {R}$ the same number of verifying and falsifying worlds, and their values under $\kappa _ p$ and $\kappa ^\circ _ p$ are balanced according to Eq. (2), i.e.

$$\begin{aligned}&\kappa _ p (bfp)+\kappa _ p (\overline{b}\,\overline{f}p)-\kappa _ p (b\overline{f}p)-\kappa _ p (\overline{b}fp) = 2+2-1-4 = -1\\&\qquad \qquad \qquad \quad \! =1+2-1-3 =\kappa ^\circ _ p (bfp)+\kappa ^\circ _ p (\overline{b}\,\overline{f}p)-\kappa ^\circ _ p (b\overline{f}p)-\kappa ^\circ _ p (\overline{b}fp). \end{aligned}$$

The definition of the principle of conditional preservation, as given in Definition 4, does not require information about the success condition of a change. Thus, the notion of the principle of conditional preservation is directly available for descriptor revision of conditionals when we provide a set of conditionals. A natural choice are the conditionals appearing in a descriptor $\varPsi$. For a descriptor $\varPsi$ over $\mathcal {L}^\mathrm {cond}$, we define the set of conditionals in $\varPsi$, denoted by $cond (\varPsi )$, as follows:

• for $\varPsi =\emptyset$ let $cond (\varPsi )=\emptyset$,

• for $\varPsi =\{ \mathfrak {B}{(B|A)} \}$ let $cond (\varPsi )=\{ (B|A) \}$,

• for $\varPsi =\{ \alpha ,\beta ,\ldots \}$ let $cond (\varPsi )= cond (\{\alpha \})\cup cond (\{\beta ,\ldots \})$,

• for $\varPsi =\{ \alpha \vee \beta \}$ let $cond (\varPsi )= cond (\{\alpha \})\cup cond (\{\beta \})$,

• for $\varPsi =\{ \alpha \wedge \beta \}$ let $cond (\varPsi )= cond (\{\alpha \})\cup cond (\{\beta \})$, and

• for $\varPsi =\{ \lnot \alpha \}$ let $cond (\varPsi )= cond (\{\alpha \})$.

In the following, we use a central characterisation [19, 20] of the principle of conditional preservation to obtain a characterisation of the principle of conditional preservation for descriptor revisions.

Proposition 1

(PCP for Descriptor Revision, Adapted [20]). Let $\varPsi$ be a descriptor over $\mathcal {L}^\mathrm {cond}$ and $cond (\varPsi ) = \{ \, (B_1|A_1),\, \ldots \,,\, (B_n|A_n) \, \}$ be the set of conditionals in $\varPsi$, and let $\kappa ^\circ$ be the result of the descriptor revision of $\kappa$ by $\varPsi$. Then this change satisfies the principle of conditional preservation with respect to the conditionals in $cond (\varPsi )$ if and only if there are integers² $\kappa _0, \gamma _i^+, \gamma _i^- \in \mathbb {Z}$, $1 \leqslant i \leqslant n$, such that:

(3)

The proof of Proposition 1 is directly obtainable from a proof given by Kern-Isberner [19, Theorem 4.6.1], since no specific information on the success condition for the conditionals in the descriptor was used in Proposition 1. The idea underlying Proposition 1 is that interpretations that are verifying and falsifying the same conditionals are treated in the same way. Thus, for every conditional $(B_i|A_i)\in cond (\varPsi )$, the two constants $\gamma _i^+$ and $\gamma _i^-$ handle how interpretations are shifted over the change process. The constant $\kappa _0$ acts as a normalizer, ensuring that $\kappa ^\circ$ is indeed a ranking function, i.e. there is at least one world $\omega$ such that $\kappa ^\circ (\omega )=0$.

Example 6 (Continued)

Consider the change from $\kappa _ p$ to $\kappa ^\circ _ p$, both given in Table 1. As shown in Example 5, this change satisfies the principle of conditional preservation with respect to the conditionals in $\mathcal {R}=\{ (p|b), (f|p), (\overline{f}|p) \}$. Indeed, as stated in Proposition 1, we can obtain $\kappa ^\circ _ p$ from $\kappa _ p$ via Eq. (3) by choosing $\kappa _0=0$, $\gamma _1^+=0$, $\gamma _1^-=-1$, $\gamma _2^+=0$, $\gamma _2^-=2$, $\gamma _3^+=0$, and $\gamma _3^-=0$.

4.3 Descriptor Revision with Conditional Preservation

The principle of conditional preservation is a powerful basic principle of belief change and it is natural to demand satisfaction of this principle. The principle demands a specific relation between the conditionals in the prior belief state K, the conditionals in the posterior state $K^\circ$ and the conditionals in the descriptor $\varPsi$. Remember that by Definition 3, a descriptor revision from K to $K^\circ$ is determined by a choice function C, the descriptor $\varPsi$ and the set $\mathbb {K}_K$ such that Eq. (1) holds, but none of these components allow to express a direct relation between K, $K^\circ$ and $\varPsi$. Thus, there is no possibility to express conditional preservation by the means of descriptor revision. The principle of conditional preservation is somewhat orthogonal to descriptor revision, which gives rationale to the following definition of conditional descriptor revision.

Definition 5 (Conditional Descriptor Revision)

Let $\kappa$ be a ranking function. A descriptor revision of $\kappa$ to $\kappa ^\circ$ by a descriptor $\varPsi$ over $\mathcal {L}^\mathrm {cond}$ (realised by C over $\mathbb {K}_\kappa$) is called a conditional descriptor revision of $\kappa$ to $\kappa ^\circ$ by $\varPsi$ (realised by C over $\mathbb {K}_\kappa$) if the change from $\kappa$ to $\kappa ^\circ$ satisfies the principle of conditional preservation with respect to $cond (\varPsi )$.

In Definition 5, we choose ranking functions as representations for belief states, but note that the principle of conditional preservation also applies to other representations [19]. Thus, for other kinds of representations of belief states one might give a definition of conditional descriptor revision similar to the one given here. However, for the rest of the article, we focus on ranking functions. Moreover, we assume $\mathbb {K}_\kappa$ to be the set of all ranking functions, i.e. when revising by a descriptor over $\varPsi$, we choose over the set of all ranking functions.

Example 7 (Continued)

Consider $\kappa _ p$ to $\kappa ^\circ _\varPsi$ given in Table 1. The change from $\kappa _ p$ to $\kappa ^\circ _\varPsi$ is a conditional descriptor revision by $\varPsi =\{ \mathfrak {B}{(p|b)}, \lnot \mathfrak {B}{(f|p)}, \lnot \mathfrak {B}{(\overline{f}|p)} \}$. Note that $cond (\varPsi )=\{ (p|b), (f|p), (\overline{f}|p) \}$, and therefore, as stated in Example 5, the change from $\kappa _ p$ to $\kappa ^\circ _\varPsi$ satisfies the principle of conditional preservation with respect to $cond (\varPsi )$. Note that $\varPsi$ holds in $\kappa ^\circ _ p$, i.e. $\kappa ^\circ _ p \Vdash \varPsi$. In particular, it is the case that $\kappa ^\circ _ p \Vdash \lnot \mathfrak {B}{(\overline{f}|p)}$, which is equivalent to $\kappa ^\circ _ p \not \models (\overline{f}|p)$, i.e. $\kappa ^\circ _ p (\overline{f}p) \not < \kappa ^\circ _ p (fp)$.

5 Characterisation of Conditional Descriptor Revision with Elementary Descriptors by CSPs

The arithmetic nature of ranking functions and the characterisation of the principle of conditional preservation by Proposition 1 allow us to give a constraint, expressing the success condition of a literal descriptor.

Definition 6

(Constraint for Literal Descriptors, $CR _{\! D }(\kappa ,\alpha ,\varPsi )$). Let $\kappa$ be a ranking function, let $\varPsi =\{\alpha _1,\ldots ,\alpha _m\}$ be an elementary descriptor over $\mathcal {L}^\mathrm {cond}$ with $cond (\varPsi )=\{ (B_1|A_1),\ldots , (B_n|A_n) \}$, and let $\alpha$ be a literal descriptor in $\varPsi$. The constraint for $\alpha$ in $\kappa$ under $\varPsi$, denoted by $CR _{\! D }(\kappa ,\alpha ,\varPsi )$, on the constraint variables $\gamma _1^+,\gamma _1^-,\ldots ,\gamma _n^+,\gamma _n^-$ ranging over $\mathbb {Z}$, is given for a positive literal $\alpha =\mathfrak {B}{(B_i|A_i)}$ descriptor by

$$\begin{aligned} \begin{aligned} \gamma _i^- - \gamma _i^+ >&\, (\min _{\omega \vDash A_i B_i} \kappa (\omega ) + \sum _{\begin{array}{c} j \ne i \\ \omega \vDash A_j B_j \end{array}} \gamma _j^+ + \sum _{\begin{array}{c} j \ne i \\ \omega \vDash A_j \bar{B}_j \end{array}} \gamma _j^-) \\ - \,&(\min _{\omega \vDash A_i \bar{B}_i} \kappa (\omega ) + \sum _{\begin{array}{c} j \ne i \\ \omega \vDash A_j B_j \end{array}} \gamma _j^+ + \sum _{\begin{array}{c} j \ne i \\ \omega \vDash A_j \bar{B}_j \end{array}} \gamma _j^-) \quad \text { for } i = 1, \dots , n \end{aligned} \end{aligned}$$

(4)

and for a negative literal descriptor $\alpha =\lnot \mathfrak {B}{(B_i|A_i)}$ by

$$\begin{aligned} \begin{aligned} \gamma _i^- - \gamma _i^+ \leqslant&\, (\min _{\omega \vDash A_i B_i} \kappa (\omega ) + \sum _{\begin{array}{c} j \ne i \\ \omega \vDash A_j B_j \end{array}} \gamma _j^+ + \sum _{\begin{array}{c} j \ne i \\ \omega \vDash A_j \bar{B}_j \end{array}} \gamma _j^-) \\ - \,&(\min _{\omega \vDash A_i \bar{B}_i} \kappa (\omega ) + \sum _{\begin{array}{c} j \ne i \\ \omega \vDash A_j B_j \end{array}} \gamma _j^+ + \sum _{\begin{array}{c} j \ne i \\ \omega \vDash A_j \bar{B}_j \end{array}} \gamma _j^-) \quad \text { for } i = 1, \dots , n. \end{aligned} \end{aligned}$$

(5)

The rationale for Definition 6 is that a positive literal descriptor $\{ \mathfrak {B}{(B|A)} \}$ holds in the posterior state $\kappa ^\circ$ if $(B|A)$ is accepted by $\kappa ^\circ$, more formally $\kappa ^\circ ~\models ~(B|A)$, i.e. $\kappa ^\circ (AB) < \kappa ^\circ (A\overline{B})$. Likewise, a negative literal descriptor $\{\lnot \mathfrak {B}{(B|A)}\}$ corresponds to $\kappa ^\circ \not \models (B|A)$, i.e. $\kappa ^\circ (AB) \geqslant \kappa ^\circ (A\overline{B})$. Combining all the constraints obtained for each literal descriptor in $\varPsi$ yields a constraint satisfaction problem.

Definition 7

(CSP for Elementary Descriptors, $CR _{\! D }(\kappa ,\varPsi )$). Let $\kappa$ be a ranking function and $\varPsi$ be an elementary belief descriptor with $cond (\varPsi )=\{ (A_1|B_1),\ldots , (A_n|B_n) \}$. The constraint satisfaction problem for $\kappa$ and $\varPsi$, on the constraint variables $\gamma _1^+,\gamma _1^-,\ldots ,\gamma _n^+,\gamma _n^-$ ranging over $\mathbb {Z}$, denoted by $CR _{\! D }(\kappa ,\varPsi )$, is given by the conjunction of the constraints $CR _{\! D }(\kappa ,\alpha ,\varPsi )$ for each $\alpha \in \varPsi$.

With $Sol ( CR _{\! D }(\kappa ,\varPsi ))$, we denote the solutions of the constraint satisfaction problem $CR _{\! D }(\kappa ,\varPsi )$. Each solution $\vec {\gamma } = \langle {\gamma _1^+,\gamma _1^-,\ldots ,\gamma _n^+,\gamma _n^-}\rangle \in Sol ( CR _{\! D }(\kappa ,\varPsi ))$ induces a unique ranking function $\kappa _{\vec {\gamma }}$ obtained from Eq. (3) in Theorem 1 by choosing $\kappa _0$ as the smallest integer such that the equation yields a ranking function, i.e., there is a propositional interpretation $\omega \in \varOmega$ such that $\kappa _{\vec {\gamma }}(\omega )=0$ and for all $\omega \in \varOmega$ the value $\kappa _{\vec {\gamma }}(\omega )$ is a non-negative integer.

Example 8 (Continued)

Consider $\kappa _ p$ from Table 1 and the elementary descriptor $\varPsi =\{ \mathfrak {B}{(p|b)}, \lnot \mathfrak {B}{(f|p)}, \lnot \mathfrak {B}{(\overline{f}|p)} \}$. The CSP $CR _{\! D }(\kappa ,\varPsi )$ is given by:

The vector $\vec {\gamma }=\langle {\gamma _1^+,\gamma _1^-,\gamma _2^+,\gamma _2^-,\gamma _3^+,\gamma _3^-}\rangle$ with $\gamma _1^+=0$, $\gamma _1^-=-1$, $\gamma _2^+=0$, $\gamma _2^-=2$, $\gamma _3^+=0$, and $\gamma _3^-=0$ is a solution of $Sol ( CR _{\! D }(\kappa _ p ,\varPsi ))$, i.e. $\vec {\gamma } \in Sol ( CR _{\! D }(\kappa _ p ,\varPsi ))$. We obtain the ranking function $\kappa ^\circ _ p =\kappa _{\vec {\gamma }}$ given in Table 1.

We examine whether our approach is sound and complete with respect to conditional descriptor revision.

Theorem 1

(Soundness of $CR _{\! D }(\kappa ,\varPsi )$). Let $\kappa$ be an ordinal conditional ranking function, $\varPsi$ be an elementary belief descriptor, and let $\vec {\gamma } \in Sol ( CR _{\! D }(\kappa ,\varPsi ))$. Then, the change from $\kappa$ to $\kappa _{\vec {\gamma }}$ is a conditional descriptor revision by $\varPsi$ (over all ranking functions).

Note that a ranking function $\kappa ^\circ$ is a c-representation [19] for a set of conditionals $\mathcal {R}$ if and only if $\kappa ^\circ$ is the result of a conditional descriptor revision starting form a ranking function $\kappa$ such that $\kappa (\omega )=0$ for every $\omega \in \varOmega$ with a descriptor $\varPsi =\{ \mathfrak {B}{(B|A)} \mid (B|A) \in \mathcal {R} \}$. The construction of a c-representation can be characterised by a constraint-satisfaction problem similar to the one given in Definition 7 [3, 19]. The soundness proof transfers to a proof of Theorem 1.

Theorem 2

(Completeness of $CR _{\! D }(\kappa ,\varPsi )$). Let $\varPsi$ be an elementary belief descriptor and $\kappa ,\kappa ^\circ$ be ordinal conditional functions. If the change from $\kappa$ to $\kappa ^\circ$ is a conditional descriptor revision by $\varPsi$ (over all ranking functions), then there exists a vector $\vec {\gamma }\in Sol ( CR _{\! D }(\kappa ,\varPsi ))$ such that $\kappa ^\circ =\kappa _{\vec {\gamma }}$.

Proof (Sketch)

Because of Proposition 1, there exists $\kappa _0$ and $\vec {\gamma }=\langle {\gamma _1^+,\gamma _1^-,\ldots }\rangle$ such that the ranking function $\kappa ^\circ$ is representable as stated in Eq. (3). Therefore, we have $\kappa ^\circ =\kappa _{\vec {\gamma }}$. It remains to show that $\vec {\gamma }\in Sol ( CR _{\! D }(\kappa ,\varPsi ))$. Note that by our assumptions $\kappa ^\circ \Vdash \alpha$ holds for each $\alpha \in \varPsi$. Suppose that $\alpha$ is a positive literal descriptor, i.e. $\alpha =\mathfrak {B}{(B|A)}$, and thus, $\kappa ^\circ (AB) < \kappa ^\circ (A\overline{B})$. By employing Eq. (3), we obtain Eq. (4) from $\kappa ^\circ (AB) < \kappa ^\circ (A\overline{B})$ by algebraic transformations [19]. In an analogue way, one can obtain Eq. (5) from a negative literal descriptor. Note that these are exactly the inequalities in $CR _{\! D }(\kappa ,\varPsi )$. Therefore, the vector $\vec {\gamma }$ is a solution for $Sol ( CR _{\! D }(\kappa ,\varPsi ))$.

6 Implementation by ChangeOCF

We implemented descriptor revision for conditionals and elementary descriptors under the principle of conditional preservation. Given a ranking function $\kappa$ and an elementary descriptor $\varPsi$, our system, called ChangeOCF, calculates a list of possible outcomes of a revision of $\kappa$ with $\varPsi$. To calculate the possible outcomes of the revision, ChangeOCF uses a constraint system based on $CR _{\! D }(\kappa ,\varPsi )$ introduced in Sect. 5. Following the Propositions 1 and 2, the solutions of this constraint system correspond to the outcomes of a conditional descriptor revision. A straightforward approach would be to solve $CR _{\! D }(\kappa ,\varPsi )$ for the given $\kappa$ and $\varPsi$. Then, for each $\vec {\gamma } \in Sol ( CR _{\! D }(\varPsi ))$ the corresponding ranking function $\kappa _{\vec {\gamma }}$ is calculated.

In general, $Sol ( CR _{\! D }(\varPsi ))$ may contain infinite elements, but there is only a finite number of equivalence classes with respect to the acceptance of conditionals. Therefore, it is possible to restrict the set of solutions to finitely many without losing interesting results. To do this, we used an approach inspired by maximal impacts for c-representations [3] that addresses a similar problem for the enumeration of c-representations. The idea of maximal impacts is to add explicit bounds for the value of each $\gamma _i^+, \gamma _i^-$. This reduces the set of possible solutions to a finite set, without losing equivalent solutions when choosing the bounds appropriately. ChangeOCF limits the value of $\gamma _1^+, \gamma _1^-, \dots , \gamma _n^+, \gamma _n^-$ to an individual finite domain by extending the constraint system $CR _{\! D }(\kappa ,\varPsi )$ with constraints $u_i^{\min -} \leqslant \gamma _i^- \leqslant u_i^{\max -}$ and $u_i^{\min +} \leqslant \gamma _i^+ \leqslant u_i^{\max +}$ for $1\leqslant i \leqslant n$. We denote this extended constraint system by $CR ^{\vec {u}}_{\! D }(\kappa ,\varPsi )$ with $\vec {u} = \langle u_1^{\min -},u_1^{\max -},u_1^{\min +},u_1^{\max +},\dots , u_n^{\max +} \rangle$. Like for c-representations [21], it is an open problem which values for $\vec {u}$ guarantee that a representative for each equivalence class of solutions with respect to the acceptance of conditionals is found for a given $\kappa$ and $\varPsi$.

The implementation of ChangeOCF is build upon by InfOCF-Lib [22], a Java library for reasoning with conditionals and ranking functions. InfOCF-Lib calculates the c-representations of a conditional knowledge base by solving a constraint system similar to $CR ^{\vec {u}}_{\! D }(\kappa ,\varPsi )$. The interface of ChangeOCF is implemented in Java. To solve $CR ^{\vec {u}}_{\! D }(\kappa ,\varPsi )$, we use SICStus Prolog and its constraint logic programming library for finite domains [7]. The Prolog implementation is an adaption of the implementation of InfOCF [2] to the more general case of belief change.

Example 9 (Continued)

Consider again the descriptor revision of $\kappa _ p$ from Table 1 with the elementary descriptor $\varPsi =\{ \mathfrak {B}{(p|b)}, \lnot \mathfrak {B}{(f|p)}, \lnot \mathfrak {B}{(\overline{f}|p)} \}$. The corresponding constraint satisfaction problem $CR ^{\vec {u}}_{\! D }(\kappa ,\varPsi )$ is given by the conjunction of $CR _{\! D }(\kappa ,\varPsi )$ from Example 8 with the following constraints:

$$\begin{aligned} u_1^{\min -}&\leqslant \gamma _1^- \leqslant u_1^{\max -}&u_2^{\min -}&\leqslant \gamma _2^- \leqslant u_1^{\max -}&u_3^{\min -}&\leqslant \gamma _3^- \leqslant u_3^{\max -}\\ u_1^{\min +}&\leqslant \gamma _1^+ \leqslant u_1^{\max +}&u_2^{\min +}&\leqslant \gamma _2^+ \leqslant u_1^{\max +}&u_3^{\min +}&\leqslant \gamma _3^+ \leqslant u_3^{\max +} \end{aligned}$$

If we choose for example $\vec {u} = \langle -2, 0, 0, 2, -1, 1, -1, 1, 0, 0, 0, 0\rangle$, there are nine solutions to $CR ^{\vec {u}}_{\! D }(\kappa ,\varPsi )$. One of the solutions is $\vec {\gamma } = \langle 0, 2, -1, 0, 0, 0 \rangle$, which corresponds to $\kappa _{\!\vec {\gamma }} = \kappa ^\circ _ p$ from Table 1.

7 Summary and Future Work

In this article, we investigated descriptor revision for a conditional logic and its realisation. We defined elementary descriptors, a large fragment of the full descriptor language, allowing to express a multitude of different kinds of change processes. In particular, elementary descriptors cover the success conditions of AGM revision and AGM contraction. We introduced conditional descriptor revision, which is an extension of descriptor revision for conditionals obeying the principle of conditional preservation by Kern-Isberner. We gave a characterisation by a constraint satisfaction problem and an implementation of conditional descriptor revision with elementary descriptors was presented.

For future work, we plan to give a characterisation of conditional descriptor revision with descriptors with disjunction. This requires a more fine-grained handling of the interaction of the constraints, and might require transformations of a descriptor into a normal form. Another open problem is the determination of maximal impacts for the constraint problem such that all solutions up to equivalence with respect to acceptance of conditionals are captured.