2. Preliminaries

Before describing our framework of belief revision under restrictions, we first introduce some background knowledge, concepts, and notations.

We restrict our discussion to a finite propositional language $\mathcal{L}$ and assume basic knowledge of logic, such as the meaning of $\equiv, \vdash$ , and $\models$ (Hamilton, Reference Hamilton1988). Note that as propositional logic is sound and complete, ‘a formula $\varphi$ syntactically proves a formula $\psi$ ’ ( $\varphi \vdash \psi$ ) and ‘ $\varphi$ semantically entails $\psi$ ’ ( $\varphi \models \psi$ ) are equivalent, where $\varphi \vdash \psi$ means that from $\varphi$ , by using axioms and deduction rules of $\mathcal{L}$ , we can derive $\psi$ , and $\varphi \models \psi$ means that if $\varphi$ is true for given truth values of the variables, then $\psi$ is also true. A theory $\mathcal{K}$ of $\mathcal{L}$ is a set of formulas that is deductively closed, that is, $\varphi\in \mathcal{K}$ iff $\mathcal{K}\vdash\varphi$ ( $\varphi$ can be derived by using the formulas in $\mathcal{K}$ ). We say a theory $\mathcal{K}$ is complete iff for all $\varphi\in \mathcal{L}$ either $\varphi\in \mathcal{K}$ or $\neg\varphi\in \mathcal{K}$ . We say a theory $\mathcal{K}$ is consistent if there is no formula $\varphi$ s.t. $\varphi \in \mathcal{K}$ and $\neg\varphi \in \mathcal{K}$ . A world is a consistent complete theory of $\mathcal{L}$ . Semantically, we can also consider a world as an interpretation that maps each propositional variable to $\mathsf{True}$ or $\mathsf{False}$ . Here, we will use an equivalent formula of conjunctions of literals (variables or negation of variables) to represent a world. For example, if $\mathcal{L}$ is a propositional language generated by $\{p, q\}$ , then the formula $\neg p \wedge q$ represents the world that maps the variables p to $\mathsf{False}$ and q to $\mathsf{True}$ . We denote by W the set of all the worlds in $\mathcal{L}$ .

For each formula $\varphi\in \mathcal{L}$ , we denote by $[\varphi]$ the set of all the worlds that semantically entail $\varphi$ , that is $[\varphi]=\{\omega \in W\mid \omega \models \varphi\}$ , and call $[\varphi]$ the set of worlds of $\varphi$ . If a world $\omega$ is in $[\varphi]$ , then we say $\omega$ satisfies $\varphi$ . Similarly, for each set of formulas $\Gamma$ , we denote by $[\Gamma]=\{\omega\in W\mid \forall\varphi\in\Gamma$ , $ \omega\models\varphi\}$ the set of common worlds of the formulas in $\Gamma$ , and $\operatorname{Cn}\!({\Gamma})=\{\varphi\mid [\Gamma] \subseteq [\varphi]\}$ the set of formulas that $\Gamma$ logically implies. When $\Gamma=\{ \varphi \}$ , for ease of representation, we will write $[\{\varphi\}]$ as $[\varphi]$ and $\operatorname{Cn}\!({\{\varphi\}})$ as $\operatorname{Cn}\!({\varphi})$ by abuse of the notation. We say a set of formulas $\Gamma$ (a formula $\varphi$ , respectively) is consistent in $\mathcal{L}$ if $[\Gamma]\neq\varnothing$ ( $[\varphi]\neq\varnothing$ , respectively).

The most famous belief revision framework is the AGM, which contains eight postulates. In the AGM theory, the beliefs of an agent are represented by a theory that is called a belief set. A revision operator $\circ$ is a function that maps a belief set and a formula to a new belief set. There are two important principles in the AGM theory. One is the success principle: new evidence should be put into the revision result. The other one is the minimal change principle, which requires the agent to maintain the belief information from $\mathcal{K}$ to $\mathcal{K}\circ\varphi$ as much as possible. The following postulates from Alchourron et al. (Reference Alchourron, Gärdenfors and Makinson1985) respect these two principles.

• ( $K\ast 1$ ) $\mathcal{K}\circ\varphi$ is a theory of $\mathcal{L}$ .

• ( $K\ast 2$ ) $\varphi\in \mathcal{K}\circ\varphi$ .

• ( $K\ast 3$ ) $\mathcal{K}\circ\varphi\subseteq \operatorname{Cn}\!({\mathcal{K}\cup\{\varphi\}})$ .

• ( $K\ast 4$ ) If $\mathcal{K}\cup\{\varphi\}$ is consistent then $\operatorname{Cn}\!({\mathcal{K}\cup\{\varphi\}}) \subseteq \mathcal{K}\circ\varphi$ .

• ( $K\ast 5$ ) If $\varphi$ is consistent then $\mathcal{K}\circ\varphi$ is consistent.

• ( $K\ast 6$ ) If $\varphi\equiv\psi$ then $\mathcal{K}\circ\varphi=\mathcal{K}\circ\psi$ .

• ( $K\ast 7$ ) $\mathcal{K}\circ(\varphi\wedge\psi)\subseteq \operatorname{Cn}\!({(\mathcal{K}\circ\varphi)\cup \{\psi\}})$ .

• ( $K\ast 8$ ) If $\operatorname{Cn}\!({(\mathcal{K}\circ\varphi)\cup \{\psi\}})$ is consistent then $\operatorname{Cn}\!({(\mathcal{K}\circ\varphi)\cup\{\psi\}}) \subseteq \mathcal{K}\circ(\varphi\wedge\psi)$ .

A revision operator $\circ$ that satisfies ( $K\ast 1$ )-( $K\ast 8$ ) is called an AGM revision operator. It should be noted that, in propositional logic, Katsuno and Mendelzon (Reference Katsuno and Mendelzon1991) proposed another framework (KM) of revision and showed that the above eight postulates are equivalent to their proposed framework. In this article, we develop our extension of revision following AGM notations, whereas our work can also naturally extend to the KM framework.

Note that if a belief set $\mathcal{K}$ is inconsistent, then we have $\mathcal{K}=\mathcal{L}$ . In this case we shall have $\mathcal{K}\circ\varphi=\operatorname{Cn}\!({\varphi})$ .

The concept of preorder plays an important role in belief revision. A preorder $\preceq$ on a non-empty set E is a binary relation on E that is reflexive and transitive. A preorder $\preceq$ is called total if any two elements in E are comparable under $\preceq$ , that is, for any $x,y\in E$ , we have $x\preceq y$ or $y\preceq x$ . We write $x\sim y$ if $x\preceq y$ and $y\preceq x$ , and $x\prec y$ if $x\preceq y$ but $y\not\preceq x$ .

Katsuno and Mendelzon (Reference Katsuno and Mendelzon1991) gave a representation theorem with the notion of faithful assignment.

Suppose $\preceq$ is a total preorder. Let $\operatorname{min}\!({A,\preceq})$ denote the set $\{a \in A \mid \forall b \in A, a \preceq b\}$ . When A is a set of worlds, $\operatorname{min}\!({A,\preceq})$ is called the minimal worlds of A. We have the following representation theorem.

Theorem 1 (From Katsuno & Mendelzon, Reference Katsuno and Mendelzon1991). A revision operator $\circ$ satisfies ( $K\ast1$ )-( $K\ast8$ ) precisely when there exists a faithful assignment such that

\begin{align*} [\mathcal{K}\circ\varphi]=\operatorname{min}\!({[\varphi],\preceq_{\mathcal{K}}}). \end{align*}

In other words, an AGM revision operator is equivalent to selecting minimal worlds based on some total preorder, and a total preorder on W determines an AGM revision operator.

3. Belief revision under restrictions

Given a logic language $\mathcal{L}$ , traditional belief revision operates on W, viz., the set of all the worlds of $\mathcal{L}$ . However, as illustrated in Example 1, some worlds might not be acceptable in some circumstances. By restricting the set of acceptable worlds, a consistent formula in $\mathcal{L}$ might not be consistent anymore and thus cannot be considered as an acceptable belief in traditional belief revision. In the following, we discuss how to deal with belief revision when the set of worlds is restricted. The first task is to determine what is an acceptable belief in the new case.

For example, for the second case in Example 1 where it is impossible to satisfy both p and q at the same time due to limited resources, the restriction C is $\{p \wedge \neg q, \neg p \wedge q, \neg p \wedge \neg q\}$ , saying that any world with p and q both true is not acceptable, and p is consistent under C while $p \wedge q$ is inconsistent under C. Note that when $C=W$ , then a formula is consistent under C iff it is consistent in $\mathcal{L}$ and we fall back to traditional belief revision. A (potential) belief under the restriction of C is defined as follows.

Here, the word ‘potential’ means that a formula consistent under C is a candidate of beliefs, and it can be a belief of some specific agent. If $C=\varnothing$ , then $\mathcal{L}^C=\varnothing$ , that is there are no beliefs under C, which would be trivial for discussion. Therefore, we assume in this article that a restriction C is always non-empty. As an example, the formula p is a belief under the restriction of $C=\{p \wedge \neg q, \neg p \wedge q, \neg p \wedge \neg q\}$ . In the context of Example 1, p means manufacturing product A and the restriction means that A and B cannot be manufactured at the same time.

For $\mathcal{L}^C$ , it is possible that $\varphi\in\mathcal{L}^C$ but $\neg\varphi\not\in\mathcal{L}^C$ , and $\varphi,\psi\in\mathcal{L}^C$ but $\varphi\wedge\psi\not\in\mathcal{L}^C$ . However, it is easy to verify the following properties:

• $C \subset \mathcal{L}^C$ (when we consider a world as a conjunction formula of literals);

• if $\exists \varphi \in \mathcal{L}^C$ s.t. $\varphi \models \psi$ , then $\psi \in \mathcal{L}^C$ ;

• if $\varphi, \psi \in \mathcal{L}^C$ , then $\varphi \vee \psi \in \mathcal{L}^C$ .

Similar to the notation $[\varphi]$ , ${[{\varphi}]^C}$ is used to denote the set of worlds of $\varphi$ under the restriction of C, that is $[\varphi]^C=\{\omega\in C \mid\omega\models\varphi\} = [\varphi] \cap C$ , and for all $\Gamma\subseteq \mathcal{L}^C$ , we denote by $[\Gamma]^C=\{\omega\in C\mid\forall\varphi\in\Gamma,\omega\models\varphi\}$ the set of common worlds of the formulas in $\Gamma$ under that same restriction of C. For $\Gamma_1,\Gamma_2 \subseteq \mathcal{L}^C$ , we denote by $\Gamma_1\equiv^C \Gamma_2$ iff ${[{\Gamma_1}]^C}={[{\Gamma_2}]^C}$ . For example, ${[{p}]^C}=\{p \wedge \neg q\}$ , for $C= \{p \wedge \neg q, \neg p \wedge q, \neg p \wedge \neg q\}$ and $\{p\} \equiv^C \{p \wedge \neg q\}$ .

We can also define a consequence operator $\operatorname{Cn}^{C}\!({\cdot})$ on $\mathcal{L}^C$ by $\operatorname{Cn}^{C}\!({\Gamma})=\{\varphi\in\mathcal{L}^C\mid [\Gamma]^C\subseteq[\varphi]^C\}$ , where $\Gamma \subseteq \mathcal{L}^C$ . In particular, if ${[{\Gamma}]^C}=\varnothing$ then $\operatorname{Cn}^{C}\!({\Gamma})=\mathcal{L}^C$ which is similar to $\operatorname{Cn}\!({\mathsf{False}})=\mathcal{L}$ in traditional setting. This operator constructs the deductively closed set of formulas for $\Gamma$ under C. For example, for $\Gamma=\{p\}$ and $C = \{p \wedge \neg q, \neg p \wedge q, \neg p \wedge \neg q\}$ , $\operatorname{Cn}^{C}\!({\Gamma})$ will contain formulas like $p, p \vee q, p \wedge \neg q$ . Note that $p \wedge \neg q \in \operatorname{Cn}^{C}\!({\Gamma})$ while $p\wedge \neg q \not\in \operatorname{Cn}\!({\Gamma})$ , which is because under the specific C, saying p is the same as saying $p \wedge \neg q$ .

With the operator $\operatorname{Cn}^{C}\!({\cdot})$ , we can now formally define a belief set under the restriction of C.

For instance, for $C = \{p \wedge \neg q, \neg p \wedge q, \neg p \wedge \neg q\}$ , $\operatorname{Cn}^{C}\!({\{p\}}) = \{p, p \vee q, p \wedge \neg q, \ldots\}$ is a belief set under the restriction of C. In the following discussion, we always assume that a belief set under a restriction is consistent under that restriction, as an agent should be rational. Also, we should assume that a new evidence $\varphi$ is always consistent under C, that is a belief under C. If $\varphi$ is not consistent under C, we could of course define the revision result to be $\mathcal{L}^C$ , following the convention in the AGM framework, which however is trivial for discussion.

Furthermore, it is easy to verify the following lemma by use of Definition 5.

Belief revision under restrictions is about the revision of a belief set $\mathcal{K}$ under C with a new belief $\varphi$ . In the context of Example 1, the second case involves the restriction $C = \{p \wedge \neg q, \neg p \wedge q, \neg p \wedge \neg q\}$ , a belief set $\mathcal{K}=\operatorname{Cn}^{C}\!({\{p\}}) =\{p, p \vee q, p \wedge \neg q, \ldots\}$ , and a new belief q. The major problem is how the revision under restrictions should behave. Note that the original AGM revision postulates are not appropriate to characterize revision under restrictions, because the background language has changed, and some beliefs in the AGM framework will not be beliefs any more under certain restrictions. In what follows, we will first discuss the case of belief revision under a fixed restriction, and then the case of belief revision under a dynamic restriction.

3.1. Revision under a fixed restriction

Let $\mathcal{L}$ be a propositional logic language and C be a subset of worlds of $\mathcal{L}$ . In this subsection, we will discuss belief revision under the restriction of C.

Let $\star$ specifically denote a revision operator under the restriction of C. It is important to determine the postulates that $\star$ should satisfy, in order to see how belief revision under the restriction of C should behave. For example, following the idea of the ‘success principle’ and the ‘minimal change principle’ in traditional belief revision, if $\varphi$ is consistent under C and $[\mathcal{K}]^C\cap[\varphi]^C\neq\varnothing$ , it will be natural to define $[\mathcal{K} \star \varphi]^C=[\mathcal{K}]^{C}\cap[\varphi]^C$ , that is $\mathcal{K} \star \varphi = \operatorname{Cn}^{C}\!({\mathcal{K} \cup\{\varphi\}})$ . Then how about the case when $[\mathcal{K}]^C\cap[\varphi]^C=\varnothing$ , and exactly what postulates will such a revision operator satisfy? To answer these questions, we propose a natural generalization of the AGM postulates for belief revision under the restriction of C as follows. It should be noted that here $\mathcal{K} = \operatorname{Cn}^{C}\!({\mathcal{K}})$ , that is, $\mathcal{K}$ can only contain worlds from C.

• ( $C\ast 1$ ) $\mathcal{K}\star\varphi$ is a belief set under C.

• ( $C\ast 2$ ) If $\varphi$ is a belief under C, then $\varphi\in \mathcal{K}\star\varphi$ .

• ( $C\ast 3$ ) $\mathcal{K}\star\varphi\subseteq \operatorname{Cn}^{C}\!({\mathcal{K}\cup\{\varphi\}})$ .

• ( $C\ast 4$ ) If $\mathcal{K}\cup\{\varphi\}$ is consistent under C, then $\operatorname{Cn}^{C}\!({\mathcal{K}\cup\{\varphi\}})\subseteq \mathcal{K}\star\varphi$ .

• ( $C\ast 5$ ) If $\varphi$ is a belief under C, then $\mathcal{K}\star\varphi$ is consistent under C.

• ( $C\ast 6$ ) If $\varphi$ and $\psi$ are beliefs under C, and $\{\varphi\}\equiv^C\{\psi\}$ , then $\mathcal{K}\star\varphi=\mathcal{K}\star\psi$ .

• ( $C\ast 7$ ) If $\varphi$ and $\psi$ are beliefs under C, then $\mathcal{K}\star(\varphi\wedge\psi)\subseteq \operatorname{Cn}^{C}\!({(\mathcal{K}\star\varphi)\cup\{\psi\}})$ .

• ( $C\ast 8$ ) If $\varphi$ and $\psi$ are beliefs under C, and $\operatorname{Cn}^{C}\!({(\mathcal{K}\star\varphi)\cup\{\psi\}})$ is consistent under C, then $\operatorname{Cn}^{C}\!({(\mathcal{K}\star\varphi)\cup\{\psi\}}) \subseteq \mathcal{K}\star(\varphi\wedge\psi)$ .

Note that when $C=W$ , the above postulates would be exactly the AGM ones. ( $C \ast 1$ ) says that the result of revision should be a deductively closed set of formulas under C. ( $C \ast 2$ ) means that when the new information $\varphi$ is consistent under C, then it should be included in the result of revision. ( $C \ast 3$ ) and ( $C \ast 4$ ) together mean that whenever the new information is consistent with the current belief set, under the restriction C, the revision result should contain exactly all the beliefs that are consistent with the current belief set and the new information, under C. This is essentially the minimal change principle in that specific case. ( $C \ast 5$ ) says that the revision result should be consistent under C if the new information is consistent under C. ( $C \ast 6$ ) corresponds to the irrelevance of syntax postulate in AGM theory, saying that two sources of new information that are equivalent under C should result in the same revision result. ( $C \ast 7$ ) and ( $C \ast 8$ ) together say that if $\mathcal{K} \star \varphi$ is consistent with $\psi$ under C, then the revision result of $\mathcal{K} \star (\varphi \wedge \psi)$ is exactly the expansion of the result $\mathcal{K} \star \varphi$ to include $\psi$ .

Sometimes, we need to use a set of worlds as a formula, and for convenience, we define Form $(S)$ to be a formula whose worlds are exactly those in S, that is, [Form $(S)] = S$ .

Remark 1. Consider a subset C of W and let $\gamma =$ Form $(C)$ . One might wonder if revision under restrictions can be characterized by AGM postulates. Naturally, there are two possibilities to incorporate restrictions using AGM operator: $\mathcal{K} \diamond_1 \varphi \equiv \mathcal{K} \circ (\varphi \wedge \gamma)$ and $\mathcal{K} \diamond_2 \varphi \equiv \operatorname{Cn}^{C}\!({\mathcal{K} \cup \{\gamma\}}) \circ (\varphi \wedge \gamma)$ . The first operator $\diamond_1$ was considered in Katsuno and Mendelzon (1991) and is actually not an operator under restriction, which will be discussed later in the related work section. The second one $\diamond_2$ has the same result as an operator under restriction for some cases. Neither of these two operators is an AGM operator, as they contradict against the original AGM postulates. This can be seen from the following example. Let $C \subset W$ , that is some of the worlds are not in the restriction, $\mathcal{K} = \operatorname{Cn}\!($ Form $(\{\omega_1,\omega_3\}))$ , and $\varphi =$ Form $(\{\omega_2,\omega_3\})$ , where $\omega_1,\omega_2 \in C$ and $\omega_3 \in W \setminus C$ . Assume on the contrary that $\diamond_1$ and $\diamond_2$ are AGM operators. Then $\diamond_1$ and $\diamond_2$ should satisfy ( $K \ast 3$ ) and ( $K \ast 4$ ), and we have $[\mathcal{K \diamond_1 \varphi}] = [\mathcal{K\diamond_2 \varphi}] = \{\omega_3\}$ . However, as $[\varphi \wedge \gamma] = \{\omega_2\}$ and $\circ$ is an AGM operator, which should satisfy ( $K \ast 2$ ) and ( $K \ast 5$ ), then $[\mathcal{K}\circ (\varphi \wedge \gamma) ] =[\operatorname{Cn^{C}({\mathcal{K} \cup \{\gamma\}}) \circ (\varphi \wedge \gamma)}] = \{\omega_2\}$ . Therefore, $\mathcal{K} \diamond_1 \varphi \not\equiv \mathcal{K} \circ (\varphi \wedge \gamma)$ , $\mathcal{K} \diamond_2 \varphi \not\equiv \operatorname{Cn}^{C}\!({\mathcal{K} \cup \{\gamma\}}) \circ (\varphi \wedge \gamma)$ , that is, the two operators do not satisfy AGM postulates. This illustrates that revision under restriction cannot be fully characterized by the original AGM postulates.

For illustration of how a revision operator satisfying ( $C \ast 1$ )-( $C \ast 8$ ) works, consider again the context of Example 1. The restriction C is $\{p \wedge \neg q, \neg p \wedge q, \neg p \wedge \neg q\}$ saying that A and B cannot be manufactured at the same time. In one case, the current belief is $\neg p$ , corresponding to the belief set $\operatorname{Cn}^{C}\!({\{\neg p\}})$ , and the new information is $\neg p \wedge \neg q$ , that is ‘A and B will not be manufactured’. Then, since $\neg p$ and $\neg p \wedge \neg q$ are consistent under C, according to ( $C \ast 3$ ) and ( $C \ast 4$ ), the revision result would be $\operatorname{Cn}^{C}\!({\{\neg p,\neg p \wedge \neg q\}}) = \operatorname{Cn}^{C}\!({\{\neg p \wedge \neg q\}})$ , meaning ’to manufacture neither A nor B’. Another case is that the current belief is p, corresponding to the belief set $\operatorname{Cn}^{C}\!({\{p\}})$ . The new information is q. Note that q is inconsistent with p under C. In this case, what we know from the postulates ( $C \ast 2$ ) and ( $C \ast 5$ ) is that q will be in the result of revision and p will not, meaning ‘to manufacture B but not A’. This is different from revising p by q with an AGM revision operator, which will result in $\operatorname{Cn}\!({\{p \wedge q\}})$ , meaning ‘to manufacture both A and B’.

Since all the worlds that are not in C are considered impossible, a faithful assignment on $\mathcal{L}^C$ can be defined as follows.

Definition 6 (Faithful assignment on $\mathcal{L}^C$ ). A $\textrm{faithful assignment on}$ $\mathcal{L}^C$ is a function that maps each belief set $\mathcal{K}$ under C to a total preorder $\preceq_{\mathcal{K}}$ , such that $\preceq_{\mathcal{K}}$ is faithful at ${[{\mathcal{K}}]^C}$ (cf. Definition 1) and

• if $\mathcal{J}\equiv^C \mathcal{K}$ then $\preceq_\mathcal{J}$ and $\preceq_\mathcal{K}$ are equal on C; and

• if $\omega\not\in C$ then for all $\omega' \in C$ , $\omega'\prec_\mathcal{K}\omega$ .

Naturally, the original representation theorem (Theorem 1) can also be generalized to $\mathcal{L}^C$ .

Theorem 2 (Representation Theorem I). A revision operator $\star$ satisfies ( $C\ast1$ )-( $C\ast8$ ) if and only if there exists a faithful assignment on $\mathcal{L}^C$ that maps each $\mathcal{K}$ to a total preorder $\preceq_{\mathcal{K}}$ such that

(1) \begin{align} [\mathcal{K}\star\varphi]^C=\operatorname{min}\!({[\varphi]^C,\preceq_{\mathcal{K}}}). \end{align}

Proof. The proof idea would be similar to the one in Katsuno and Mendelzon (Reference Katsuno and Mendelzon1991) for Theorem 1 and thus we only show a sketch here.

For the if part, suppose there is a faithful assignment on $\mathcal{L}^C$ that maps each $\mathcal{K}$ to a total preorder $\preceq_\mathcal{K}$ . Then Equation (1) induces a revision operator that $\mathcal{K}\star\varphi=\operatorname{Cn}^{C}\!({\operatorname{min}\!({[\varphi]^C,\preceq_\mathcal{K}})})$ . Now we need to show $\star$ satisfies ( $C\ast1$ )-( $C\ast8$ ). ( $C\ast1$ )-( $C\ast3$ ) follows straightforwardly from the definition of $\star$ . Here we take( $C\ast7$ ) as an example, as the others are similar or simpler.

Assume $\varphi$ and $\psi$ are beliefs under C. If $\varphi\wedge\psi$ is inconsistent under C, that is, $[\varphi]^{C}\cap[\psi]^{C}=\varnothing$ , then $\mathcal{K}\star(\varphi\wedge\psi)=\mathcal{L}^C$ . Since $[\mathcal{K}\star\varphi]^C=\operatorname{min}\!({[\varphi]^C,\preceq_\mathcal{K}})\subseteq[\varphi]^C$ , we have $[\mathcal{K}\star\varphi]^C\cap[\psi]^C=\varnothing$ and $\operatorname{Cn}^{C}\!({(\mathcal{K}\star\varphi)\cup\{\psi\}})=\mathcal{L}^C$ . Then $\mathcal{K}\star(\varphi\wedge\psi)\subseteq \operatorname{Cn}^{C}\!({(K\star\varphi)\cup\{\psi\}})$ . If $\varphi\wedge\psi$ is consistent under C, then $[\mathcal{K}\star(\varphi\wedge\psi)]^C=\operatorname{min}\!({[\varphi\wedge\psi]^C,\preceq_\mathcal{K}})$ and $[\mathcal{K}\star\varphi]^C=\operatorname{min}\!({[\varphi]^C,\preceq_\mathcal{K}})$ , where $\operatorname{min}\!({[\varphi\wedge\psi]^C,\preceq_\mathcal{K}})$ is non-empty because $\preceq_\mathcal{K}$ is a total preorder. If $\operatorname{min}\!({[\varphi]^C,\preceq_\mathcal{K}})\cap [\psi]^C=\varnothing$ , that is, $[\mathcal{K}\star\varphi]^C \cap [\psi]^C = \varnothing$ , then $\mathcal{K}\star(\varphi\wedge\psi)\subseteq\operatorname{Cn}^{C}\!({(K\star\varphi)\cup\{\psi\}})=\operatorname{Cn}^{C}\!({\varnothing})=\mathcal{L}^C$ . If $\operatorname{min}\!({[\varphi]^C,\preceq_\mathcal{K}})\cap [\psi]^C\neq\varnothing$ then $\operatorname{min}\!({[\varphi]^C,\preceq_\mathcal{K}})\cap[\psi]^C=\operatorname{min}\!({[\varphi]^C\cap[\psi]^C,\preceq_\mathcal{K}})=\operatorname{min}\!({[\varphi\wedge\psi]^C,\preceq_\mathcal{K}})$ , that is, $\operatorname{Cn}^{C}\!({(\mathcal{K}\star\varphi)\cup\{\psi\}}) = \mathcal{K}\star(\varphi\wedge\psi)$ . Therefore, $\mathcal{K}\star(\varphi\wedge\psi)\subseteq\operatorname{Cn}^{C}\!({(\mathcal{K}\star\varphi)\cup\{\psi\}})$ .

For the only if part, we need to show that for each revision operator $\star$ satisfying ( $C\ast1$ )-( $C\ast8$ ) there is a faithful assignment on $\mathcal{L}^C$ such that $[\mathcal{K}\star\varphi]^C=min([\varphi]^C,\preceq_\mathcal{K})$ . Here we only show how to construct the total preorder $\preceq_{\mathcal{K}}$ given $\star$ and $\mathcal{K}$ . Suppose $\omega_1,\omega_2\in W$ . Then

• If $\omega_1,\omega_2\in C$ and $[\mathcal{K}\,\star$ Form $(\{\omega_1,\omega_2\})]^C=\{\omega_1\}$ then we define $\omega_1\prec_\mathcal{K}\omega_2$ .

• If $\omega_1,\omega_2\in C$ and $[\mathcal{K} \, \star$ Form $(\{\omega_1,\omega_2\})]^C=\{\omega_1,\omega_2\}$ then $\omega_1\sim_\mathcal{K}\omega_2$ .

• If $\omega_1\in C$ and $\omega_2\not\in C$ , then $[\mathcal{K}\star$ Form $(\{\omega_1,\omega_2\})]^C=\{\omega_1\}$ by ( $C\ast1$ )-( $C\ast2$ ).In this case we define $\omega_1\prec_\mathcal{K}\omega_2$ .

• If both $\omega_1$ and $\omega_2$ are not in C, then the ordering of $\omega_1$ and $\omega_2$ does not matter and can be any fixed one such as $\omega_1\sim_\mathcal{K}\omega_2$ .

It is not difficult to verify that $\preceq_{\mathcal{K}} $ is a faithful total preorder at C and the map from $\mathcal{K}$ to $\preceq_\mathcal{K}$ is a faithful assignment on $\mathcal{L}^C$ , as well as that $[\mathcal{K}\star\varphi]^C=\min\!([\varphi]^C,\preceq_\mathcal{K})$ is satisfied.

With the above representation theorem, we know that a revision operator for belief revision under the restriction of C is equivalent to selecting minimal worlds based on some total preorder on the worlds; conversely, by specifying a total preorder on the worlds, we can define a revision operator for revision under the restriction of C.

There are several possible candidates of the revision operator $\star$ . For belief merging and revision for qualitative constraints, we have already seen some researchers (Condotta et al., Reference Condotta, Kaci and Schwind2008; Hue & Westphal Reference Hue and Westphal2012; Dufour-Lussier et al., Reference Dufour-Lussier, Hermann, Ber and Lieber2014) using operators induced by pseudo-distances. Here, we show that a revision operator $\star$ based on some pseudo-distance satisfies the postulates ( $C\ast 1$ )-( $C\ast 8$ ) we proposed.

Definition 7. A mapping d from $W \times W$ to $\mathbb{R}$ is a $\textrm{pseudo-distance}$ if we have that

1. 1. for $\omega,\omega' \in W$ , $d(\omega,\omega')\ge 0$ , and $d(\omega,\omega')=0$ iff $\omega=\omega'$ ; and

2. 2. $\forall \omega, \omega' \in W$ , $d(\omega,\omega')=d(\omega',\omega)$ .

Definition 8. A $\textrm{revision operator}$ $\star_d$ $\textrm{based on the pseudo-distance}$ d can be defined as

(2) \begin{align} [\mathcal{K \star_d \varphi}]^C = \{\omega \in [\varphi]^C \mid \forall \omega' \in [\varphi]^C, d(\omega,{[{\mathcal{K}}]^C}) \le d(\omega',{[{\mathcal{K}}]^C})\},\end{align}

where

(3) \begin{equation} d(\omega,{[{\mathcal{K}}]^C}) = \left\{ \begin{array}{c@{\quad \mbox{if} \quad}l} 0 & \omega \in [\mathcal{K}]^C;\\[5pt] \sum_{\omega_i \in [\mathcal{K}]^C} d(\omega,\omega_i) & \omega \not\in [\mathcal{K}]^C. \end{array} \right.\end{equation}

Note that when defining $d(\omega,[\mathcal{K}]^C)$ in Definition 8, we used the aggregation operator $\sum$ (Lin, Reference Lin1996) for illustration of defining the distance, while other aggregation operators can also be used, for example, the $\min$ (Condotta et al. Reference Condotta, Kaci, Marquis and Schwind2009b) or $\max$ (Revesz, Reference Revesz1997) operators.

Example 2. Consider Example 1. There are three worlds in C, say $\omega_1, \omega_2, \omega_3$ corresponding to $p \wedge \neg q$ , $\neg p \wedge q$ , $\neg p \wedge \neg q$ respectively. The pseudo-distance d between the worlds is defined as $d(\omega_1,\omega_2) = 2$ , $d(\omega_1,\omega_3) = 1$ , $d(\omega_2,\omega_3) = 1$ (Hamming’s distance of the corresponding formulas). The current belief is ‘to manufacture A’, corresponding to the belief set $\mathcal{K}=\operatorname{Cn}^{C}\!($ Form $(\{\omega_1\}))$ , and the new information is ‘to manufacture B or to manufacture neither’, corresponding to the belief $\varphi = q \vee \neg (p \vee q)$ . As ${[{\mathcal{K}}]^C} = \{\omega_1\}$ and ${[{\varphi}]^C} = \{\omega_2,\omega_3\}$ (note that $\{q\} \equiv^C \{\neg p \wedge q\}$ ), we have ${[{\mathcal{K} \star_d \varphi}]^C} = \{\omega \in {[{\varphi}]^C} \mid \forall\omega' \in {[{\varphi}]^C}, d(\omega,{[{\mathcal{K}}]^C}) \le d(\omega',{[{\mathcal{K}}]^C})\} =\{\omega_3\}$ . The revision result means ‘to manufacture neither’, as $\omega_3$ is more close to ${[{\mathcal{K}}]^C}$ under the defined distance. This is expected, because the current restriction C means that ‘A and B cannot be manufactured simultaneously’ (probably due to resource limitation). Under such restriction, the current belief is actually ‘to manufacture A but not B’ and the new information is ‘to manufacture B but not A, or to manufacture neither’. Without such restriction, the revision result would then be ‘to manufacture both’.

The following proposition confirms that $\star_d$ satisfies ( $C\ast1$ )-( $C\ast8$ ).

Proposition 1. Suppose d is any pseudo-distance on W and $\star_d$ is a belief revision operator defined as in Definition 8. Then $\star_d$ satisfies ( $C\ast1$ )-( $C\ast8$ ).

Proof. According to the definition of $d(\omega,{[{\mathcal{K}}]^C})$ given in Equation (3), for each $\mathcal{K}$ , the distance $d(\omega,{[{\mathcal{K}}]^C})$ between any world $\omega$ and $\mathcal{K}$ actually induces a total preorder $\preceq_{\mathcal{K}}$ defined as follows:

• $\omega_1 \preceq_{\mathcal{K}} \omega_2$ if $\omega_1,\omega_2\in C$ and $d(\omega_1,{[{\mathcal{K}}]^C}) \le d(\omega_2,{[{\mathcal{K}}]^C}).$

• $\omega_1\prec_{\mathcal{K}}\omega_2$ if $\omega_1\in C$ and $\omega_2\not\in C$ .

• $\omega_1\sim_{\mathcal{K}}\omega_2$ if $\omega_1,\omega_2\not\in C$ .

Next we show that $\preceq_{\mathcal{K}}$ is faithful at ${[{\mathcal{K}}]^C}$ . Suppose $\omega_1,\omega_2\in C$ and $\omega_1\in {[{\mathcal{K}}]^C}$ . If $\omega_2\in {[{\mathcal{K}}]^C}$ then $\omega_1\sim_{\mathcal{K}}\omega_2$ by $d(\omega_1,{[{\mathcal{K}}]^C})=d(\omega_2,{[{\mathcal{K}}]^C})=0$ . If $\omega_2\not\in{[{\mathcal{K}}]^C}$ then $\omega_1\prec_{\mathcal{K}}\omega_2$ by $d(\omega_2,{[{\mathcal{K}}]^C})>0$ . Hence $\preceq_{\mathcal{K}}$ is faithful at ${[{\mathcal{K}}]^C}$ .

Then we verify that the function $f\,:\, \mathcal{K} \mapsto \preceq_{\mathcal{K}}$ is a faithful assignment on $\mathcal{L}^C$ (cf. Definition 6). If two belief sets $\mathcal{J}$ and $\mathcal{K}$ are equivalent under C, that is $\mathcal{J} \equiv^C \mathcal{K}$ , then ${[{\mathcal{J}}]^C} = {[{\mathcal{K}}]^C}$ . According to the above definition of the total preorder, it is easy to see that $\preceq_{\mathcal{J}}$ and $\preceq_{\mathcal{K}}$ are equal on C, and if $\omega \not\in C$ then for all $\omega' \in C, \omega' \prec_{\mathcal{K}} \omega$ .

Finally, we show that $[\mathcal{K}\star_d\varphi]^C=\operatorname{min}\!({[\varphi]^C,\preceq_{\mathcal{K}}})$ . Since $[\mathcal{K \star_d \varphi}] ^C = \{\omega \in [\varphi]^C\mid \forall \omega' \in [\varphi]^C, d(\omega,{[{\mathcal{K}}]^C}) \le d(\omega',{[{\mathcal{K}}]^C})\}$ , we have $\omega_1\in [\mathcal{K\star_d \varphi}] ^C$ iff $\omega_1\preceq_{\mathcal{K}}\omega_2$ for all $\omega_2\in[\varphi]^C$ . That is to say, $[\mathcal{K}\star_d\varphi]^C=\operatorname{min}\!({[\varphi]^C,\preceq_{\mathcal{K}}})$ . Therefore, by the Representation Theorem I, the revision operator $\star_d$ satisfies ( $C\ast1$ )-( $C\ast8$ ).

Note that $\star_d$ does not satisfy all the AGM postulates. Take ( $K \ast 3$ ) and ( $K \ast 4$ ) as an example. Consider $W=\{\omega_1,\omega_2,\omega_3,\omega_4\}$ , $C=\{\omega_1,\omega_4\}$ , $[\mathcal{K}]=\{\omega_1,\omega_2\}$ , and $[\psi]=\{\omega_2,\omega_4\}.$ ( $K \ast 3$ ) and ( $K \ast 4$ ) say that $\mathcal{K} \star_d \psi$ should be $\operatorname{Cn}\!({\mathcal{K} \cup \{\psi\}})$ , because $\mathcal{K} \cup \{\psi\}$ has a world $\omega_2$ and is thus consistent in $\mathcal{L}$ . However, ${[{\mathcal{K} \star_d \psi}]^C}$ is $\{\omega_4\}$ . Therefore, $\mathcal{K} \star_d \psi = \operatorname{Cn}^{C}\!($ Form $(\{\omega_4\})) \ne \mathcal{K} \cup \{\psi\}$ , violating ( $K \ast 3$ ) and ( $K \ast 4$ ).

Remark 2. Apart from using a distance to define a revision operator under restriction, we can also make use of some faithful assignment on $\mathcal{L}^C$ that defines a total preorder $\preceq_{\mathcal{K}}$ on the worlds in C. Such an ordering could reflect certain preference of the agent. For example, Spohn (1988) introduced a function that associates each world with a natural number, and thus a total preorder on the worlds is established that can be used to define a revision operator.

3.2. Revision under a dynamic restriction

In the previous subsection, we discussed how an agent changes her beliefs under some fixed restriction when new evidence emerges. However, in many real-world applications, an agent may also receive new restrictions and needs to adjust beliefs accordingly. For instance, consider the following example.

Example 3. Following Example 1, let p represent ‘product A is going to be manufactured’, and q represent ‘product B is going to be manufactured’. The current restriction is $C=\{p \wedge \neg q, \neg p\wedge\neg q\}$ , that may be described as ‘product B cannot be manufactured because of machinery maintenance’. The current belief is ‘Some products are going to be manufactured, but without the knowledge of which one’. Then under the restriction C, the current belief set can be represented as $\mathcal{K}=\operatorname{Cn}^{C}\!({\{p \wedge \neg q\}})$ , meaning ‘product A is going to be manufactured but not B’. Then suppose the maintenance of machinery for product B has already finished, but maintenance of machinery for product A has started. So actually product B can be manufactured but not A. The restriction C is thus changed to $C' = \{\neg p \wedge q, \neg p\wedge\neg q\}$ . Since the current belief set is $\operatorname{Cn}^{C}\!({\{p \wedge \neg q\}})$ , which is not appropriate under the new restriction C^′, the belief set needs to be revised accordingly. If we consider using the new restriction as a new belief $(\neg p \wedge q) \vee (\neg p \wedge \neg q)$ to revise $\mathcal{K}$ , then the new belief set will be $\operatorname{Cn}^{C}\!({\{\neg p \wedge \neg q\}})$ by ( $C \ast 2$ ) and ( $C \ast 5$ ). However, this should not be the only possible result. For example, as the previous belief set indicates that some products are manufactured, then $\neg p \wedge q$ , which means ‘product B is going to be manufactured but not A’, might be more appropriate to be included into the new belief set.

In fact, the result after changing the restriction would depend on the preferences of the newly allowed worlds, and the behaviour of a chosen operator might not conform to ( $C \ast 1$ )-( $C \ast 8$ ), such as an operator giving the result with the world $\neg p \wedge q$ in the above example. Therefore, in what follows we will discuss some postulates to characterize how an agent should change her beliefs when the restriction changes.

Recall that, in this article, a restriction is a subset of worlds. Let the current restriction be C and the current belief set under C be $\mathcal{K}_C$ . When the restriction changes to C ^′, $\mathcal{K}_C$ will change to a new set $\mathcal{K}_C \triangleright C'$ , where the mapping $\triangleright $ takes $(C,\mathcal{K}_C,C')$ as input. Similar to the previous discussion, we propose some postulates that a rational mapping $\triangleright $ should satisfy. The following postulates ( $R\ast 1$ )-( $R\ast 4$ ) characterize several very basic conditions for a mapping $\triangleright $ to be rational.

• ( $R\ast 1$ ) $\mathcal{K}_{C}\triangleright {C'}$ is a belief set under C ^′.

• ( $R\ast 2$ ) If $\mathcal{K}_C$ is consistent under C, then $\mathcal{K}_{C}\triangleright {C'}$ is consistent under C ^′.

• ( $R\ast 3$ ) $\mathcal{K}_{C}\triangleright {C'}\subseteq \operatorname{Cn}^{C'}(\mathcal{K}_C\cup \{$ Form $(C')\} )$ , where Form $(C')$ is a formula whose worlds are exactly those in C ^′.

• ( $R\ast 4$ ) If $\mathcal{K}_C$ is consistent under C ^′, then $\operatorname{Cn}^{C'}(\mathcal{K}_C\cup \{$ Form $ (C')\})\subseteq \mathcal{K}_{C}\triangleright {C'}$ .

( $R\ast 1$ ) means that the resulting set $\mathcal{K}_{C}\triangleright {C'}$ after changing the restriction is deductively closed under the new restriction. ( $R\ast 2$ ) says that if the original belief set is consistent under the original restriction, then the result is also a consistent belief set under the new restriction. ( $R\ast 3$ ) and ( $R\ast 4$ ) state that if ${[{\mathcal{K}_C}]^C}\cap C'$ is a non-empty set then the result is exactly the deductive closure of $\mathcal{K}_C\cup \{$ Form $ (C')\}$ in $\mathcal{L}^{C'}$ , that is $\mathcal{K}_{C}\triangleright {C'} =\operatorname{Cn}^{C'}(\mathcal{K}_C\cup \{$ Form $ (C')\}) =\operatorname{Cn}^{C'}({\mathcal{K}_C\cap \mathcal{L}^C})$ .

Note that in the case of belief revision under a fixed restriction C, the revision operator is determined by preferences of the worlds in C. For the case where C becomes C ^′, we would also like to have a total preorder of worlds so that we can choose the worlds that are preferred. The following postulate, when taken together with the above postulates, actually ensures a total preorder on the worlds, for each given C, $\mathcal{K}_C$ , and mapping $\triangleright $ .

• ( $R \ast 5$ ) If $\mathcal{K}_{C}\triangleright (C_1\cup C_2)\subseteq \mathcal{K}_{C}\triangleright {C_1}$ and $\mathcal{K}_{C}\triangleright (C_2\cup C_3)\subseteq \mathcal{K}_{C}\triangleright {C_2}$ , then $\mathcal{K}_{C}\triangleright (C_1\cup C_3)\subseteq \mathcal{K}_{C}\triangleright {C_1}$ .

Intuitively, ( $R \ast 5$ ) considers the transitivity of the ordering, that is if the worlds in $C_1$ are preferred over those in $C_2$ , and the worlds in $C_2$ are preferred over those in $C_3$ , then the worlds in $C_1$ are preferred over those in $C_3$ .

Moreover, in order to characterize ‘minimal change’ when revising the belief set, we propose the following additional postulates for the preferences of worlds on different restrictions.

• ( $R \ast 6$ ) Suppose $C_1,C_2,C_3$ are pairwise disjoint restrictions, that is, $C_1 \cap C_2 = \emptyset$ , $C_1 \cap C_3=\emptyset$ , and $C_2 \cap C_3 = \emptyset$ . Then $\mathcal{K}_{C}\triangleright (C_1\cup C_2\cup C_3) = \mathcal{K}_{C}\triangleright (C_1\cup C_2)$ iff $\mathcal{K}_{C}\triangleright (C_1\cup C_3)= \mathcal{K}_{C}\triangleright {C_1}$ or $\mathcal{K}_{C}\triangleright (C_2\cup C_3) = \mathcal{K}_{C}\triangleright {C_2}$ .

• ( $R \ast 7$ ) If $\mathcal{K}_{C}\triangleright (C_1\cup C_2)= \mathcal{K}_{C}\triangleright {C_1}$ and $C_3\subseteq C_2$ , then $\mathcal{K}_{C}\triangleright (C_1\cup C_3) = \mathcal{K}_{C}\triangleright {C_1}$ .

Intuitively, ( $R \ast 6$ ) means that for pairwise disjoint restrictions $C_1,C_2,C_3$ , if the union of $C_1$ and $C_2$ is preferred over $C_3$ , then at least one of $C_1$ and $C_2$ is preferred over $C_3$ ; ( $R \ast 7$ ) says that if $C_1$ is preferred over $C_2$ and $C_3$ is contained in $C_2$ , then $C_1$ is preferred over $C_3$ .

The above postulates ( $R \ast 1$ )-( $R \ast 7$ ) were inspired by revision rules given in Katsuno and Mendelzon (Reference Katsuno and Mendelzon1991). For these postulates, we have the following representation theorem.

Theorem 3 (Representation Theorem II). The mapping $\triangleright $ satisfies ( $R \ast 1$ )-( $R \ast 7$ ) iff for each restriction C and a consistent belief set $\mathcal{K}_{C}$ under C, there is a total preorder $\preceq_{C,\mathcal{K}}$ on W that is faithful at $[\mathcal{K_{C}}]^C$ such that for each restriction C^′, $[\mathcal{K_{C}\triangleright {C'}}]^{C'}=\operatorname{min}\!({C',\preceq_{C,\mathcal{K}}})$ .

Proof. Sufficiency is not difficult to verify. We take ( $R \ast 5$ ) as an example and the others are similar. Suppose there is a total preorder $\preceq_{C,\mathcal{K}}$ of worlds, faithful at $[\mathcal{K}_{\mathcal{C}}]^C$ , such that for each restriction C ^′, $[\mathcal{K_{C}\triangleright {C'}}]^{C'}=\operatorname{min}\!({C',\preceq_{C,\mathcal{K}}})$ . From $\mathcal{K}_{C}\triangleright (C_1\cup C_2)\subseteq \mathcal{K}_{C}\triangleright {C_1}$ , we know $[\mathcal{K}_{\mathcal{C}}\triangleright (\mathcal{C}_1\cup \mathcal{C}_2)]^{\mathcal{C}_1\cup \mathcal{C}_2}\subseteq [\mathcal{K}_{\mathcal{C}}\triangleright {\mathcal{C}_1}]^{C_1}$ . This means $\operatorname{min}\!({C_1\cup C_2,\preceq_{C,\mathcal{K}}})\subseteq \operatorname{min}\!({C_1,\preceq_{C,\mathcal{K}}})$ . Then $\forall \omega_2 \in C_2$ , there exists some $\omega_1 \in C_1$ s.t. $\omega_1 \prec_{C,\mathcal{K}} \omega_2$ . Similarly, from $\mathcal{K}_{C}\triangleright (C_2\cup C_3)\subseteq \mathcal{K}_{C}\triangleright C_2$ we know that $\forall \omega_3 \in C_3$ , there exists some $\omega_2 \in C_2$ s.t. $\omega_2 \prec_{C,\mathcal{K}} \omega_3$ . Therefore, $\forall \omega_3 \in C_3$ , there exists some $\omega_1$ s.t. $\omega_1 \prec_{C,\mathcal{K}} \omega_3$ . This exactly means that $\operatorname{min}\!({C_1\cup C_3,\preceq_{C,\mathcal{K}}}) \subseteq \operatorname{min}\!({C_1,\preceq_{C,\mathcal{K}}})$ , and hence $\mathcal{K}_{C}\triangleright (C_1\cup C_3)\subseteq \mathcal{K}_{C}\triangleright {C_1}$ and ( $R \ast 5$ ) is satisfied.

Next, we show the necessity. Suppose $\triangleright $ satisfies ( $R\ast 1$ )-( $R \ast 7$ ). In the following, we will show how to construct a total preorder $\preceq_{C,\mathcal{K}}$ that is faithful at ${[{\mathcal{K}_C}]^C}$ . For any $\omega,\omega'\in W$ , let $C'=\{\omega,\omega'\}$ . Following ( $R \ast 2$ ) we have $\varnothing\ne [\mathcal{K_{C}\triangleright {C'}}]^{C'}\subseteq\{\omega,\omega'\}$ . Then we can define a binary relation $\preceq_{C,\mathcal{K}}$ on C ^′ as follows: $\omega\preceq_{C,\mathcal{K}}\omega'$ iff $\omega\in [\mathcal{K_{C}\triangleright C'}]^{C'}$ . Therefore, from the definition of $\preceq_{C,\mathcal{K}}$ , we have the following properties:

• If $[\mathcal{K_{C}\triangleright {C'}}]^{C'}=\{\omega\}$ , then $\omega\preceq_{C,\mathcal{K}}\omega'$ , but $\omega'\not\preceq_{C,\mathcal{K}}\omega$ .

• If $[\mathcal{K_{C}\triangleright {C'}}]^{C'}=\{\omega'\}$ , then $\omega'\preceq_{C,\mathcal{K}}\omega$ , but $\omega\not\preceq_{C,\mathcal{K}}\omega'$ .

• If $[\mathcal{K_{C}\triangleright {C'}}]^{C'}=\{\omega,\omega'\}$ , then $\omega\preceq_{C,\mathcal{K}}\omega'$ and $\omega'\preceq_{C,\mathcal{K}}\omega$ .

It is not difficult to verify that when $\triangleright $ is given, $\preceq_{C,\mathcal{K}}$ is a total preorder on W. In fact, from the above we can see that ( $R \ast 2$ ) induces $\preceq_{C,\mathcal{K}}$ is reflexive and total. In addition, ( $R \ast 5$ ) shows that $\preceq_{C,\mathcal{K}}$ is transitive, which can be seen by setting $C_1=\{\omega_1\}$ , $C_2=\{\omega_2\}$ , and $C_3=\{\omega_3\}$ . Moreover, according to ( $R \ast 3$ ) and ( $R \ast 4$ ), by setting $C'=\{\omega,\omega'\}$ , if $\omega \in [\mathcal{K_{C}}]^C$ then we actually have $[\mathcal{K_{C}\triangleright {C'}}]^{C'} = [\mathcal{K_{C}}]^C \cap C'$ . Thus if $\omega' \in [\mathcal{K_{C}}]^C$ , then $\omega \sim \omega'$ ; if $\omega' \notin [\mathcal{K}]^C$ , then $\omega \prec \omega'$ . Hence $\preceq_{C,\mathcal{K}}$ is faithful at $[\mathcal{K_{C}}]^C$ .

Then, we only need to show that $[\mathcal{K_{C}\triangleright {C'}}]^{C'}$ is exactly the set of minimal worlds of C ^′ w.r.t. $\preceq_{C,\mathcal{K}}$ . It is clear that when C ^′ only contains one or two worlds, the revision result is exactly the minimal worlds of C ^′. This is because, the revision result should be consistent under C ^′ by ( $R \ast 2$ ), and thus the set of worlds of the result is contained in C ^′: if C ^′ only consists of one world, then the set consists of this single world, which is of course minimal under $\preceq_{C,\mathcal{K}}$ ; if C ^′ consists of two worlds, then by the above definition of $\preceq_{C,\mathcal{K}}$ , the set still consists of the minimal worlds under $\preceq_{C,\mathcal{K}}$ .

Next we show that this is also true for C ^′ consisting of more than two worlds by induction. We use $\|C'\|$ to represent the number of elements in C ^′. Suppose $[\mathcal{K_{C}\triangleright C'}]^{C'}=\operatorname{min}\!({C',\preceq_{C,\mathcal{K}}})$ is satisfied when $\|C'\|\leq k$ , where $k\in N$ and $k\geq 2$ . We need to show that the equation is also satisfied when $\|C'\|= k+1$ . Suppose $C'=\{\omega_1,\omega_2,\cdots,\omega_{k+1}\}$ . We finish the proof by considering the following two cases.

1. Case 1. If there are $\omega_i,\omega_j\in C'$ such that $\omega_i\prec_{C,\mathcal{K}}\omega_j$ , then let $C_2=\{\omega_i\},C_3=\{\omega_j\}$ and we have $\mathcal{K}_{C}\triangleright (C_2\cup C_3)= \mathcal{K}_{C}\triangleright {C_2}$ . Let $C_1=C'\setminus(C_2\cup C_3)$ , then we have $\mathcal{K}_{C}\triangleright {C'}=\mathcal{K}_{C}\triangleright (C_1\cup C_2\cup C_3)=\mathcal{K}_{C}\triangleright (C_1\cup C_2)$ by ( $R \ast 6$ ). Since $\|C_1\cup C_2\|= k$ , we have $[\mathcal{K_{C}\triangleright (C_1\cup C_2)}]^{C_1\cup C_2}=\operatorname{min}\!({C_1\cup C_2, \preceq_{C,\mathcal{K}}})$ . From $\omega_i\prec_{C,\mathcal{K}}\omega_j$ , we have $\operatorname{min}\!({C',\preceq_{C,\mathcal{K}}})=\operatorname{min}\!({C_1\cup C_2,\preceq_{C,\mathcal{K}}})$ . Therefore, $[\mathcal{K_{C}\triangleright {C'}}]^{C'}=\operatorname{min}\!({C',\preceq_{C,\mathcal{K}}})$ .

2. Case 2. If for all $\omega_i,\omega_j\in C'$ , we have $\omega_i\sim_{C,\mathcal{K}}\omega_j$ , then $\operatorname{min}\!({C',\preceq_{C,\mathcal{K}}})=C'$ , that is, every world in C ^′ is minimal. We need to show $[\mathcal{K_{C}\triangleright {C'}}^{C'}]=C'$ . Suppose by contradiction $[\mathcal{K_{C}\triangleright {C'}}]^{C'}\ne C'$ . Denote by $U=[\mathcal{K_{C}\triangleright {C'}}]^{C'}$ . Then $U\subset C'$ and hence $\|U\|\leq k$ .

• If $\|U\|< k$ , then let $C_1=U$ and $C_2=\{\omega_j\}$ where $\omega_j$ is randomly selected from $C'\setminus U$ . Therefore we have $\mathcal{K}_{C}\triangleright (C_1\cup C_2)=\mathcal{K}_{C}\triangleright {C_1}$ by ( $R \ast 7$ ). Since $\|C_1\|< k$ , we have $[\mathcal{K_{C}\triangleright {C_1}}]^{C_1}=C_1$ . Hence, $[\mathcal{K_{C}\triangleright (C_1\cup C_2)}]^{C_1\cup C_2}=C_1$ . However, by $\|C_1\cup C_2\|\leq k$ , we have $[\mathcal{K_{C}\triangleright (C_1\cup C_2)}]^{C_1\cup C_2}=\operatorname{min}\!({C_1\cup C_2,\preceq_{C,\mathcal{K}}})=C_1\cup C_2$ . This is a contradiction.

• If $\|U\|=k$ , then we can randomly select some $\omega_i\in U$ and let $C_1=U\setminus\{\omega_i\}$ , $C_2=\{\omega_i\}$ , and $C_3=C'\setminus U$ . Noticing that $k\geq 2$ , we know $C_1\neq\varnothing$ . We always have $\mathcal{K}_{C}\triangleright (C_1\cup C_2\cup C_3)= \mathcal{K}_{C}\triangleright (C_1\cup C_2)$ . However, by induction hypothesis, $\mathcal{K}_{C}\triangleright (C_1\cup C_3)=\operatorname{min}\!({C_1\cup C_3,\preceq_{C,\mathcal{K}}})=C_1\cup C_3$ , and $\mathcal{K}_{C}\triangleright {C_1}=\operatorname{min}\!({C_1, \preceq_{C,\mathcal{K}}})=C_1$ . Thus $\mathcal{K}_{C}\triangleright (C_1\cup C_3)\neq \mathcal{K}_{C}\triangleright {C_1}$ . Similarly, we have $\mathcal{K}_{C}\triangleright (C_2\cup C_3)\neq \mathcal{K}_{C}\triangleright {C_2}$ . This is a contradiction to ( $R \ast 6$ ) by $\mathcal{K}_{C}\triangleright (C_1\cup C_2\cup C_3)=\mathcal{K}_{C}\triangleright (C_1\cup C_2)$ .

Therefore, we also have $[\mathcal{K_{C}\triangleright {C'}}]^{C'}=\operatorname{min}\!({C',\preceq_{C,\mathcal{K}}})$ in this case.

Example 4. For the case considered in Example 3, where $\mathcal{K}_C=\operatorname{Cn}^{C}\!({\{p \wedge \neg q\}})$ , $C=\{p \wedge \neg q, \neg p\wedge\neg q\}$ , and $C' = \{\neg p \wedge q, \neg p\wedge\neg q\}$ , to define an operator $\triangleright $ satisfying ( $R \ast 1$ )-( $R \ast 7$ ) and giving the result with the world $\neg p \wedge q$ , we can construct a mapping $f: (C, \mathcal{K}_C) \mapsto \preceq_{C, \mathcal{K}}$ that is faithful at ${[{\mathcal{K}_C}]^C}$ , and for $\mathcal{K}_C = \operatorname{Cn}^{C}\!({\{p\wedge \neg q\}})$ , $\preceq_{C,\mathcal{K}}$ is that $p \wedge \neg q \prec_{C,\mathcal{K}} \neg p \wedge q \prec_{C,\mathcal{K}} \neg p \wedge \neg q \prec_{C,\mathcal{K}} p \wedge q$ . The revision result is actually $[\mathcal{K_{C}\triangleright {C'}}]^{C'}=\operatorname{min}\!({C',\preceq_{C,\mathcal{K}}}) = \{\neg p \wedge q\}$ .

Example 5. An instance of $\triangleright $ can also be induced by some pseudo-distance. We can define $\triangleright_d$ by using the pseudo-distance d defined in Equation (3) as follows:

(4) \begin{align} {[{\mathcal{K}_{C}\triangleright_d {C'}}]^{C'}} = \{&\omega \in C' \mid \forall \omega' \in C', d(\omega, {[{\mathcal{K}_{C}}]^C}) \leq d(\omega', {[{\mathcal{K}_{C}}]^C})\}. \end{align}

Consider the situation in Example 3. The current restriction is $C = \{p \wedge \neg q, \neg p\wedge\neg q\}$ , the current belief set is $\mathcal{K}_C = \operatorname{Cn}^{C}\!({\{p\wedge \neg q\}})$ , and the new restriction is $C'= \{\neg p \wedge q, \neg p\wedge\neg q\}$ . Let $\omega_1$ , $\omega_2$ , $\omega_3$ , $\omega_4$ correspond to $p \wedge q$ , $p \wedge \neg q$ , $\neg p \wedge q$ , $\neg p \wedge \neg q$ respectively. If the pseudo-distance d is defined as the Hamming’s distance between the formulas, for example, $d(\omega_1,\omega_2)= 1$ and $d(\omega_1,\omega_4)= 2$ , then as ${[{\mathcal{K}_C}]^C}=\{p\wedge \neg q\} = \{\omega_2\}$ , ${[{\mathcal{K}_C \triangleright_d C'}]^{C'}} = \{\omega \in C'\mid \forall \omega' \in C', d(\omega, {[{\mathcal{K}_{C}}]^C}) \leq d(\omega', {[{\mathcal{K}_{C}}]^C})\} =\{\neg p \wedge \neg q\}$ . If the pseudo-distance d is defined in another way s.t. $d(\omega_3,\omega_2) = 1$ and $d(\omega_4,\omega_2)=2$ , then ${[{\mathcal{K}_C \triangleright_d C'}]^{C'}} =\{\neg p \wedge q\}$ .

Proposition 2. For any pseudo-distance d on W, the mapping $\triangleright_d$ given in Equation (4) satisfies ( $R \ast 1$ )-( $R \ast 7$ ).

Proof. Given a belief set $\mathcal{K}_{C}$ under C, for each $\omega,\omega'\in W$ , we define $\omega\preceq\omega'$ if $d(\omega, [\mathcal{K_{C}}]^C)\leq d(\omega', [\mathcal{K_{C}}]^C)$ . Then it is clear that $\preceq$ is a total preorder. For each $\omega\in[\mathcal{K_{C}}]^C$ , we have $d(\omega, [\mathcal{K_{C}}]^C)=0$ . Also note that $\forall \omega' \ne \omega$ , $d(\omega,\omega') >0$ . Therefore $\preceq$ is faithful at $[\mathcal{K_{C}}]^C$ . Moreover, by the definition of $\mathcal{K}_{C}\triangleright_d {C'}$ in (4), we have $\mathcal{K}_{C}\triangleright_d {C'}=\operatorname{min}\!({C',\preceq})$ . By Theorem 3, $\triangleright_d$ satisfies ( $R \ast 1$ )-( $R \ast 7$ ).

Remark 3. Revising beliefs when the restriction changes is essentially different from revising beliefs under a fixed restriction, because the latter only needs to determine the preference of worlds on C, while the former needs to determine the preference of worlds in W.

In summary, we have proposed a generic framework for belief revision under either fixed or dynamic restrictions. Particularly, this framework characterizes how to revise the current belief set of an agent with new evidence, under a fixed restriction; it also considers how the current belief set should be adapted accordingly in the case when the restriction changes.

In the following, we discuss an application of this framework to belief revision of qualitative spatio-temporal information.

4. Belief revision of qualitative constraints

Beliefs in terms of qualitative spatio-temporal information have been observed in various areas, such as planning (e.g. Liu & Daneshmend, Reference Liu and Daneshmend2004), geographical information science (e.g. Egenhofer & Mark, Reference Egenhofer and Mark1995), and computer vision (e.g. Fernyhough et al., Reference Fernyhough, Cohn and Hogg2000), as well as our daily life. For example, an agent might have the belief ‘cinema A is to the south of parking lot B ^′. Several works have considered merging or revision of qualitative spatio-temporal information, for example Condotta et al. (Reference Condotta, Kaci and Schwind2008, 2009b,a), Wallgrün and Dylla (Reference Wallgrün and Dylla2010), Hue and Westphal (Reference Hue and Westphal2012), Dufour-Lussier et al., (2012, Reference Dufour-Lussier, Hermann, Ber and Lieber2014). However, none of them formally recognized the effects of restrictions. Therefore, in the sequel, we consider the application of the proposed framework of belief revision under restrictions to qualitative spatio-temporal information.

Qualitative spatio-temporal information is usually represented as a qualitative constraint network (QCN), defined as follows:

Intuitively, a QCN can be seen as a set of constraints, where each constraint is in the form of $(v_i R_{ij} v_j)$ , and $R_{ij}$ is called a qualitative relation between $v_j$ and $v_j$ . There are many choices of qualitative calculi and, by extension, qualitative relations. As illustration, Point Algebra (Vilain & Kautz, Reference Vilain and Kautz1986) provides qualitative relations $R_{ij} \subseteq \{{{precedes}}~(<), {{equals}}~(=), {{follows}}~(>)\}$ on the domain of rational numbers. In particular, considering the points on the line of rational numbers and the usual ordering relation $<$ , the three atomic relations of Point Algebra are defined in the following manner: precedes ( $<$ ) $=$ $\{(x,y) \in \mathbb{Q}\times\mathbb{Q}~|~x<y\}$ , follows ( $>$ ) $=$ $\{(x,y) \in \mathbb{Q}\times\mathbb{Q}~|~y<x\}$ , and equals ( $=$ ) $=$ $\{(x,y) \in \mathbb{Q}\times\mathbb{Q}~|~x=y\}$ . These atomic relations comprise the set R for Point Algebra, and based on that set we can define eight qualitative relations of Point Algebra in total that correspond to the set $2^R$ $=$ $\{+\{<,=,>\}$ , $\{<,>\}$ , $\{<,=\}$ , $\{=,>\}$ , $\{<\}$ , $\{>\}$ , $\{=\}$ , $\emptyset+\}$ . As an example, relation $\{<,>\}$ allows us to represent the knowledge that an event occurs before or after another event, but not at the same time. Further, two events $x,y \in \mathbb{Q}$ satisfy relation $\{<,>\}$ if and only if $x \neq y$ . As another example, $\mathcal{N}=\{(v_1 \le v_2), (v_2 < v_3), (v_1 = v_3)\}$ is a QCN over Point Algebra on the variables $V=\{v_1,v_2,v_3\}$ , where $\le$ is short for the relation $\{<,=\}$ . For a constraint $(v_i R_{ij} v_j)$ , following Pham et al., (Reference Pham, Thornton and Sattar2006), one can encode it as a logic formula $\bigvee_{r \in R_{ij}} r_{ij}$ , for example, $(v_1 \le v_2)$ can be encoded as $<_{12} \vee =_{12}$ . A world in this language corresponds to a qualitative scenario, which is a QCN where each pair of variables are related by an atomic relation (e.g. the relations $\{<\}$ , $\{=\}$ , and $\{>\}$ ). Note that not all qualitative scenarios are satisfiable. For example, the QCN $\{(v_1 < v_2), (v_2 < v_3), (v_1 = v_3)\}$ is a qualitative scenario but it is not satisfiable, as, based on $(v_1 < v_2)$ and $(v_2 < v_3)$ for example, the value of $v_1$ should always be smaller than the value of $v_3$ . Therefore, a natural restriction for belief revision of qualitative spatio-temporal information is the set of worlds that correspond to satisfiable qualitative scenarios. A belief set under such restriction then corresponds to a set of satisfiable qualitative scenarios.

In fact, the above settings have been adopted in Dufour-Lussier et al., (Reference Dufour-Lussier, Le Ber, Lieber and Martin2012), Hue and Westphal (Reference Hue and Westphal2012) for belief revision of qualitative spatio-temporal information. They performed belief revision implicitly under the natural restriction corresponding to satisfiable scenarios, by using an instance of the general revision operator $\star_d$ defined in Equation (2) as $ [\mathcal{K \star_d \varphi}]^C = \{\omega \in [\varphi]^C \mid \forall \omega' \in [\varphi]^C, d(\omega,{[{\mathcal{K}}]^C}) \le d(\omega',{[{\mathcal{K}}]^C})\}$ . The framework proposed here is more general as one can choose restrictions other than the natural one. Let us illustrate this on QCNs over Point Algebra for three variables.

Figure 1.

Revision of $\mathcal{N}_1$ by $\mathcal{N}_2$ under C, resulting in $\mathcal{N}^\star_{12}$

Example 6. Consider the QCN $\mathcal{N}_1=\{(v_1 \le v_2), (v_2 \le v_3), (v_1 \le v_3)\}$ (see Figure 1(a)). In the situation of manufacturing, this could mean the product $A_1$ shouldn’t be manufactured after the product $A_2$ ( $v_1 \le v_2$ ), the product $A_2$ shouldn’t be manufactured after the product $A_3$ ( $v_2 \le v_3$ ) and the product $A_1$ shouldn’t be manufactured after the product $A_3$ ( $v_1 \le v_3$ ). Suppose the restriction says that ‘not all variables are equal’ (and the qualitative scenarios should be satisfiable). For manufacturing, this could correspond to the restriction that ‘not all the products can be manufactured at the same time’ (probably because of limit of resources). Then the restriction C is the set of worlds corresponding to the satisfiable scenarios over Point Algebra except the one $\{=_{12}\wedge=_{23}\wedge=_{13}\}$ . Let $\mathcal{K}$ be the belief set representing the QCN $\mathcal{N}_1$ , that is, ${[{\mathcal{K}}]^C}$ is

\begin{align*} \{ &<_{12}\wedge<_{23}\wedge<_{13}, <_{12}\wedge=_{23}\wedge<_{13}, =_{12}\wedge<_{23}\wedge<_{13}\}. \end{align*}

Suppose we have a new evidence $\varphi_2\doteq\ge_{12}\wedge(<_{23} \vee =_{23} \vee >_{23})\wedge\ge_{13}$ , that is we now have $(v_1 \ge v_2)$ and $(v_1 \ge v_3)$ . For manufacturing, this could be a suggestion from some expert saying that ‘product $A_1$ should not be manufactured before $A_2$ or $A_3$ ’. Figure 1(b) illustrates the corresponding QCN $\mathcal{N}_2$ of $\varphi_2$ . Then ${[{\varphi_2}]^C}$ is

\begin{align*} \{>_{12}\wedge<_{23}\wedge>_{13},&>_{12}\wedge<_{23}\wedge=_{13}, >_{12}\wedge=_{23}\wedge>_{13},\\ &>_{12}\wedge>_{23}\wedge>_{13},=_{12}\wedge>_{23}\wedge>_{13}\}. \end{align*}

In order to revise $\mathcal{K}$ by $\varphi_2$ , we exploit the operator $\star_d$ defined in Definition 8 which satisfies the postulates for revision under restriction ( $C \ast 1$ )-( $C \ast 8$ ). Following Condotta et al. (Reference Condotta, Kaci, Marquis and Schwind2009b), the distance between worlds is defined as the conceptual neighbourhood distance between corresponding scenarios. The conceptual neighbourhood distance between relations characterizes ‘conceptual similarities’ of relations. For example, $<$ is a conceptual neighbour of $=$ , because for two variables representing numbers, by continuously changing the values of them can lead the relation between them to change from $<$ to $=$ or vice versa, without becoming any other relations during the process. Then the conceptual neighbourhood distance between two scenarios can be defined as $d(\omega_1,\omega_2) = \sum_{i<j} d(r^1_{ij},r^2_{ij})$ , where for Point Algebra $d(<,=)=d(>,=)=1$ and $d(<,>)=2$ . Let $\omega_1 \doteq >_{12}\wedge<_{23}\wedge>_{13}$ , $\omega_2 \doteq >_{12}\wedge<_{23}\wedge=_{13}$ , $\omega_3 \doteq >_{12}\wedge=_{23}\wedge>_{13}$ , $\omega_4 \doteq >_{12}\wedge>_{23}\wedge>_{13}$ , $\omega_5 \doteq =_{12}\wedge>_{23}\wedge>_{13}$ . Then

\begin{align*} \sum_{\omega \in {[{\mathcal{K}}]^C}} d(\omega_1,\omega) &= (2+0+2)+(1+0+2)=7; \\[3pt] \sum_{\omega \in {[{\mathcal{K}}]^C}} d(\omega_2,\omega) &= (2+0+1)+(1+0+1)=5\\[3pt] \sum_{\omega \in {[{\mathcal{K}}]^C}} d(\omega_3,\omega) &= (2+1+2)+(1+1+2)=9;\\[3pt] \sum_{\omega \in {[{\mathcal{K}}]^C}} d(\omega_4,\omega) &= (2+2+2)+(1+2+2)=11;\\[3pt] \sum_{\omega \in {[{\mathcal{K}}]^C}} d(\omega_5,\omega) &= (1+2+2)+(0+2+2)=9. \end{align*}

Therefore, we have ${[{\mathcal{K} \star_d \varphi_2}]^C} = \{ >_{12}\wedge<_{23}\wedge=_{13}\}$ . For manufacturing, it means ‘product $A_2$ should be manufactured before $A_1$ and $A_3$ , and product $A_1$ and $A_3$ should be manufactured at the same time’. Note that without the restriction C, the appropriate result would be ‘products $A_1$ , $A_2$ , $A_3$ should be manufactured at the same time’, that is $=_{12} \wedge =_{23} \wedge =_{13}$ . However, with the restriction C, we obtained a result that is the most appropriate one satisfying C. The result corresponds to the QCN $\mathcal{N}^\star_{12}$ as shown in Figure 1(c).

Note that in the above example, the restriction C not only requires that the scenarios are consistent but also excludes some consistent scenarios. This setting is more general than the revision of qualitative spatio-temporal information considered in Dufour-Lussier et al., (Reference Dufour-Lussier, Le Ber, Lieber and Martin2012), Hue and Westphal (Reference Hue and Westphal2012).

Moreover, the framework of belief revision under restrictions is even more general in the sense that one can revise beliefs of qualitative spatio-temporal information accordingly when the restriction changes; we illustrate the process in the example below.

Then suppose we get a new restriction C ^′ saying that ‘the relation between $v_2$ and $v_3$ can only be $\{>\}$ or $\{=\}$ (and the scenarios should still be satisfiable)’, that is, C ^′ is

\begin{align*}\{&<_{12}\wedge=_{23}\wedge<_{13},<_{12}\wedge>_{23}\wedge<_{13}, <_{12}\wedge>_{23}\wedge=_{13},\\&<_{12}\wedge>_{23}\wedge>_{13},=_{12}\wedge=_{23}\wedge=_{13},=_{12}\wedge>_{23}\wedge>_{13}, \\&>_{12}\wedge=_{23}\wedge>_{13},>_{12}\wedge>_{23}\wedge>_{13}\}.\end{align*}

Consider $\mathcal{N}_3$ shown in Figure 2(a). Let the belief set under C corresponding to $\mathcal{N}_3$ be $\mathcal{K}_{C}$ . Then

\begin{align*} {[{\mathcal{K}_{C}}]^C} =\{ <_{12}\wedge<_{23}\wedge<_{13},=_{12}\wedge<_{23}\wedge<_{13}\}. \end{align*}

Figure 2.

Revision of $\mathcal{N}_3$ when the restriction is changed, resulting in $\mathcal{N}_4$

We make use of the operator $\triangleright_d$ defined in (4) and the conceptual neighbourhood distance, while actually any operator satisfying ( $R \ast 1$ )-( $R \ast 7$ ) can be used. Then we have $[\mathcal{K_{C} \triangleright_d {C'}}]^{C'} = \{<_{12}\wedge=_{23}\wedge<_{13}\}$ . The corresponding QCN $\mathcal{N}_4$ is shown in Figure 2(b). Comparing $\mathcal{N}_4$ with $\mathcal{N}_3$ , we can see that the relation between $v_2$ and $v_3$ is changed from $\{<\}$ to $\{=\}$ because the new restriction requires that the relation between $v_2$ and $v_3$ should be either $\{>\}$ or $\{=\}$ , and the relation between $v_1$ and $v_2$ is changed from $\{<,=\}$ to $\{<\}$ accordingly such that the scenarios included in the result are satisfiable.

Our aforementioned setting concerning Point Algebra naturally extends to more complex calculi too. We can consider for instance the Region Connection Calculus ( $\mathsf{RCC}$ ), which is a first-order theory for representing and reasoning about mereotopological information (Randell et al., Reference Randell, Cui and Cohn1992). The domain of $\mathsf{RCC}$ comprises all possible non-empty regular subsets of some topological space. A fragment of $\mathsf{RCC}$ , called $\mathsf{RCC8}$ , makes use of the topological relations disconnected (DC), externally connected (EC), equal (EQ), partially overlapping (PO), tangential proper part (TPP), tangential proper part inverse (TPPi), non-tangential proper part (NTPP), and non-tangential proper part inverse (NTPPi) to encode knowledge about the spatial relations between regions in some topological space. These spatial relations constitute the set of atomic relations $R=\{EQ$ , DC, EC, PO, TPP, TPPi, NTPP, $NTPPi\}$ for $\mathsf{RCC8}$ , where each atomic relation of $\mathsf{RCC8}$ represents a particular topological configuration of two regions in some topological space. The atomic relations of $\mathsf{RCC8}$ are depicted in Figure 3.

Figure 3.

The atomic relations of ${\mathsf{RCC8}}$ , with $\boldsymbol{\cdot}{i}$ denoting the converse of $\boldsymbol{\cdot}$

We argue that belief revision under restrictions in the context of $\mathsf{RCC8}$ and its derivatives is relevant to various diverse research areas, such as image analysis (Randell et al., Reference Randell, Galton, Fouad, Mehanna and Landini2017), smart environments (Sioutis et al., Reference Sioutis, Alirezaie, Renoux and Loutfi2017), and neuro-symbolic reasoning (Alirezaie et al., Reference Alirezaie, Längkvist, Sioutis and Loutfi2019); we explain as follows. In Randell et al., (Reference Randell, Galton, Fouad, Mehanna and Landini2017) the authors consider an approach to programmatically correct image segmentation errors that fail to fulfil expected spatial relations in digitized histological scenes. The approach comprises sequences of operations that are applied to regions of a given spatial relation, and enables one to resegment an image that fails to conform to a valid histological model into one that does. As an example, by default $\mathsf{RCC8}$ allows any configuration (any consistent relations) between regions. However, in medical images various restrictions are entailed, such as the fact that cell nuclei must form parts of their host cells. Due to regions initially segmented out as cell nuclei being over-segmented, or variations in the histological stain density resulting in a less than optimal threshold level being selected, it may so happen that during the image segmentation process a segmented cell nucleus appears to extend outside the border of its host cell, which is medically impossible. The task then is to revise the segmentation to restore consistency and/or optimize the sequence of segmentation steps needed. To the best of our knowledge, so far this issue has been tackled in an ad hoc manner that pertains to the particulars of the domain under study (in the case of Randell et al., Reference Randell, Galton, Fouad, Mehanna and Landini2017, the medical domain, with tailored sequences of operations), and there does not exist a generic framework for formally revising such knowledge under a set of restrictions. For illustration, consider Figure 4 about the revision of beliefs about cell image segmentation. The original image of two cells is shown in (a), and one could have many possible segmentation results if cells and nuclei are segmented independently, which is common in practice (Randell et al., Reference Randell, Galton, Fouad, Mehanna and Landini2017). Some reasonable segmentation results would have the cell on the left ( $c_1$ ) smaller than the cell on the right ( $c_2$ ) and $c_1$ and $c_2$ not being disjoint. Let us consider this as our beliefs, which can be represented as a QCN $\mathcal{N}$ in (b) where R is the set of $\mathsf{RCC8}$ atomic relations and $n_1$ and $n_2$ are nuclei for $c_1$ and $c_2$ , respectively. It can be verified that every relation in $\mathcal{N}$ can be satisfied in some spatial configurations, which means that this QCN is perfectly fine in terms of consistency of the spatio-temporal knowledge base. However, in the medical domain, cell nuclei must be proper part of their host cells, that is $n_1 NTPP c_1$ and $n_2 NTPP c_2$ should act as the restriction C (we can consider that initially there was no restriction, so there is a change of restrictions). $\mathcal{N}$ , which corresponds to a set of beliefs as mentioned earlier, would be revised to $\mathcal{N}^C$ as shown in (c). Another circumstance is that there is a new evidence, saying that two cells should not overlap each other, which can be represented as $\varphi$ in (d) and it is actually $\varphi^C$ in (e) when there is a restriction C as before. Then with the proposed framework, the beliefs will be revised to $\mathcal{N}'$ and finally segmentation results like (g) will be considered valid.

Figure 4.

Revision of $\mathcal{N}_1$ by $\mathcal{N}_2$ under C, resulting in $\mathcal{N}^\star_{12}$

Similar circumstances happen in other domains. As noted in the beginning of this section, a limitation of current spatio-temporal revision frameworks, for example, Condotta et al., (Reference Condotta, Kaci and Schwind2008, Reference Condotta, Kaci, Marquis and Schwind2009b,a), Wallgrün and Dylla (Reference Wallgrün and Dylla2010), Hue and Westphal (Reference Hue and Westphal2012), Dufour-Lussier et al. (Reference Dufour-Lussier, Le Ber, Lieber and Martin2012, Reference Dufour-Lussier, Hermann, Ber and Lieber2014), is that revision of spatio-temporal information occurs unrestrictedly, or, to be exact, under the sole restriction that the end result maintains consistency of the spatio-temporal knowledge base. However, as noted in Sioutis et al., (Reference Sioutis, Alirezaie, Renoux and Loutfi2017), where smart environment applications are discussed, this is hardly a realistic case. The output of sensors that yield spatial or temporal knowledge might need to be restricted/filtered based on their location and/or the type of information that they provide. For example, it is impossible for a single subject to be present in two separate rooms, but this restriction may be revised if the subject is visited by someone. Finally, in Alirezaie et al., (Reference Alirezaie, Längkvist, Sioutis and Loutfi2019) an $\mathsf{RCC8}$ reasoner is employed to provide feedback and act as a referee upon a classifier, restricting certain impossibilities like water appearing where a shadow exists instead. In the future directions of that work the authors express the will to explore the reverse process, namely, the intention to use the classifier in order to enhance the capabilities of the reasoner, which would definitely require the reasoner to be extended with revision under (dynamic) restriction techniques.

5. Related work

To the best of our knowledge, the most closely related research on restrictions is about ‘integrity constraints’. Revision under integrity constraints has received attention in several previous works (Katsuno & Mendelzon, Reference Katsuno and Mendelzon1991; Grüne-Yanoff & Hansson, Reference Grüne-Yanoff and Hansson2009) (see also references therein). In particular, Katsuno and Mendelzon (Reference Katsuno and Mendelzon1991) defined operators for revision under some integrity constraints. An integrity constraint is a propositional formula that is invariant upon revision, and is always implied by the current belief of the agent. Revision under an integrity constraint IC is defined as $\mathcal{K} \circ^{IC} \varphi \equiv \mathcal{K} \circ (\mu \wedge IC)$ , and has several substantial differences from revision under restrictions. We explain as follows.

First, as illustrated in Remark 1, the operator $\circ^{IC}$ is not an AGM operator, whereas postulates to characterize rationality of it are not given in Katsuno and Mendelzon (Reference Katsuno and Mendelzon1991). Also, the situation where integrity constraints might change is excluded from discussion in Katsuno and Mendelzon (Reference Katsuno and Mendelzon1991). Moreover, this operator differs from what was defined in this paper for fixed restrictions. Particularly, in this paper, the revision operator $\star$ under fixed restrictions C can be seen as $\mathcal{K} \star \mu \equiv (\mathcal{K} \wedge C) \circ (\mu \wedge C)$ . Note that here we abused $\wedge$ to operate on sets of formulas to emphasize the difference, where $\mathcal{K} \wedge C$ and $\mu \wedge C$ actually mean $\operatorname{Cn}\!({\mathcal{K} \wedge \gamma})$ and $\mu \wedge \gamma$ respectively, and $\gamma=$ Form $ (C)$ is a formula whose worlds are exactly those in C (cf. Remark 1). The two operators are essentially different, which can be seen from the following example. Consider $\mathcal{K}$ being the belief set having worlds $\{\omega_1, \omega_2\}$ , the new evidence $\mu$ having worlds $\{\omega_3,\omega_4,\omega_5\}$ , and the restriction (integrity constraint) $C=\{\omega_1,\omega_3,\omega_4\}$ (see Figure 5 for illustration). Suppose we know the following distances $d(\omega_3,\omega_1) = 1, d(\omega_3,\omega_2)=5,d(\omega_4,\omega_1)=2, $ $d(\omega_4,\omega_2)=2$ . Then $d(\omega_3,\mathcal{K})=6$ and $d(\omega_4,\mathcal{K})=4$ , following the definition of distance between a world and a belief set in Equation (3). Since $\mu \wedge C$ has the set of worlds $\{\omega_3,\omega_4\}$ , and $\omega_4$ is closer to $\mathcal{K}$ than $\omega_3$ , we have that $\mathcal{K} \circ (\mu \wedge C)$ contains world $\omega_4$ . However, $(\mathcal{K} \wedge C) \circ (\mu \wedge C)$ contains world $\omega_3$ instead, as $\mathcal{K} \wedge C$ only has world $\omega_1$ and $\omega_3$ is closer to $\omega_1$ than $\omega_4$ . This illustrates that the revision operator defined in Katsuno and Mendelzon (Reference Katsuno and Mendelzon1991) is different from what is defined in this paper. The reason for this difference is because in our framework we discuss revision under a modified language where beliefs can only contain worlds from the restriction, whereas in Katsuno and Mendelzon (Reference Katsuno and Mendelzon1991) the discussion is still under the full language.

Figure 5.

An example illustrating the difference between revision under restriction and integrity constraints

Integrity constraints are also discussed in the context of merging (Lin & Mendelzon, Reference Lin and Mendelzon1996; Konieczny & Pérez, Reference Konieczny and Pérez2002; Qi et al., Reference Qi, Liu and Bell2006; Konieczny et al., Reference Konieczny, Marquis and Schwind2011). In Konieczny and Pérez (Reference Konieczny and Pérez2002), Lin and Mendelzon (Reference Lin and Mendelzon1996), the authors showed that a merging operator (called an IC merging operator) satisfying those rational postulates can induce an AGM revision operator. In fact, by restricting merging to only one belief set $\mathcal{K}$ , and taking the integrity constraint as the new evidence $\mu$ , an IC merging operator $\delta_{\mu}$ can naturally induce an AGM revision operator: $\mathcal{K} \circ \mu = \delta_{\mu}(\mathcal{K})$ . This is also discussed in Konieczny et al., (Reference Konieczny, Marquis and Schwind2011). However, this induced operator $\circ$ is not a revision operator under restriction: the integrity constraints in merging become the new evidence, and for revision with this induced operator, there is no restriction at all. It is also worth noting that all the previous works on revision or merging with integrity constraints did not consider how the current belief set would be affected when integrity constraints change, which corresponds to the case of dynamic restrictions in this article.

Non-prioritized belief revision is another related extension of traditional belief revision, which allows new evidence to be rejected based on some criteria. For example, in Booth et al., (Reference Booth, Fermé, Konieczny and Pérez2012), Hansson et al., (Reference Hansson, Fermé, Cantwell and Falappa2001), they equip each belief set with a set of credible formulas, and the new evidence is accepted only if it is one of the credible formulas. In other words, for each belief set $\mathcal{K}$ , there is some restriction C, and it requires that $[\mathcal{K}]\subseteq C$ . This is a special case of our consideration, where we can have $[\mathcal{K}] \not\subseteq C$ . This difference can lead to different revision capabilities, for example, when $[\mathcal{K}] = \{\omega_1,\omega_2\}$ , with credibility-limited revision, one can only deal with cases where the restriction C contains $\{\omega_1,\omega_2\}$ , while with our framework, we can also deal with cases where $[\mathcal{K}]\not\subseteq C$ , for example, $C=\{\omega_2,\omega_3\}$ . Moreover, for the case where the new evidence is not compatible with the restriction (i.e. when the new evidence is not consistent under the restriction), credibility-limited revision simply does not revise the current belief, whereas we follow AGM tradition to revise the current belief to include everything from C. A similar non-prioritized revision framework is also considered in Booth (Reference Booth2002) in terms of core beliefs, where new evidence would also be rejected if it contradicts with core beliefs. It further considers the revision of core beliefs when new evidence comes, which is different from our revision under dynamic restrictions, as we consider changes of beliefs when a restriction changes.

Yet another important extension of the AGM framework is iterated belief revision (Darwiche & Pearl, Reference Darwiche and Pearl1997). The main difference between these two theories is that the latter further considers rationality of revision in a continuous manner, while the former only considers revision in a one-step way. The proposed framework here can also be extended to iterated revision similarly by adding rational postulates to characterize continuous revision, but this is left for future work. For example, Darwiche and Pearl (Reference Darwiche and Pearl1997) argue that the total preorder in the revision result should contain necessary information from the original belief. The proposed framework here could also take this into consideration to extend to iterated belief revision. There are several other different directions on iterated revision, for example, Jin and Thielscher (Reference Jin and Thielscher2007), Ma et al., (Reference Ma, Liu and Benferhat2015), Konieczny and Pérez (Reference Konieczny and Pérez2000), Papini (Reference Papini2001), Boutilier (Reference Boutilier1996), which could be also considered for extending our framework.