# Analysis of the syntactic computation of Fagin-Halpern conditioning in possibilistic logic

Omar Et-Targuy, Salem Benferhat, Carole Delenne, Ahlame Begdouri

► To cite this version:

Omar Et-Targuy, Salem Benferhat, Carole Delenne, Ahlame Begdouri. Analysis of the syntactic computation of Fagin-Halpern conditioning in possibilistic logic. International Journal of Approximate Reasoning, 2025, 183, pp.109450. 10.1016/j.ijar.2025.109450. hal-05035649

HAL Id: hal-05035649

https://hal.science/hal-05035649v1

Submitted on 15 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

# Analysis of the syntactic computation of Fagin-Halpern conditioning in possibilistic logic

<figure><img src="image_3.png" /></figure>

Check for
updates

Omar Et-Targuy<sup>a,b,c,d,●,*</sup>, Salem Benferhat<sup>a</sup>, Carole Delenne<sup>c,d,1</sup>, Ahlame Begdouri<sup>b</sup>

## ARTICLE INFO

### Keywords:

Possibility theory

Fagin-Halpern conditioning

Possibilistic knowledge base

Uncertainty

## ABSTRACT

Conditioning is an essential operation in knowledge representation and uncertainty modeling. It enables a priori beliefs to be adjusted in response to new information considered to be fully certain. This work focuses on the computation of Fagin and Halpern (FH-)conditioning in the context where uncertain information is represented by weighted or possibilistic logic belief bases. Weighted belief bases are extensions of classical logic belief bases where a weight or degree of belief is associated with each propositional logic formula. This paper proposes a characterization of the syntactic computation of the revision of weighted belief bases in the light of new information, which is in full agreement with the semantics of the FH-conditioning of possibility distributions. We show that the size of the revised belief base is linear with respect to the size of the initial base and that the computational complexity amounts to performing $O(\log_2(n))$ calls to the propositional logic satisfiability tests, where $n$ is the number of different degrees of certainty used in the initial belief base. The last section of this paper examines both semantically and syntactically FH-conditioning under uncertain information, within the framework of possibility theory.

## 1. Introduction

Belief revision [55-58,42,38] is an important problem in knowledge representation and artificial intelligence. It consists in revising plausible beliefs of an agent in the light of new information, often considered to be completely certain and reliable. If the new information to be inserted is consistent with the a priori beliefs, then the revision comes down to simply add this information to the agent's beliefs. The problem arises when this new information contradicts a priori beliefs. In this case, the agent must decide which information to ignore or replace with other weaker, less informative and less precise information.

Agents' beliefs are modeled by uncertainty distributions $\mu$ (probability distribution, mass function [40,36], possibility distribution [35], ordinal conditional function OCF [50,51], etc.) which associate to each element of the universe of discourse (in our context, a set of propositional logic interpretations) a degree of plausibility. In probability theory, Bayesian conditioning (e.g. [59]) is widely used, especially in Bayesian networks [61,60,62], for the propagation of beliefs in the presence of new observations. For belief functions [63-66], Dempster's rule of conditioning [40,37] remains the reference operator for the revision of uncertain information.

<footnote><sup>a</sup> CRIL, CNRS UMR 8188, University of Artois, France</footnote>

<footnote><sup>b</sup> Université Sidi Mohamed Ben Abdellah (USMBA), Fez, Morocco</footnote>

<footnote><sup>c</sup> HSM, University of Montpellier, CNRS, IRD, Montpellier, France</footnote>

<footnote><sup>d</sup> Inria, Team Lemon, Montpellier, France</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>E-mail address: ettarguy@cril.fr (O. Et-Targuy).</footnote>

<footnote n="1">¹ Currently at: IUSTI, Aix Marseille University, CNRS, France.</footnote>
In possibility theory [67,80,79], conditioning was defined in different ways (e.g. [81–85,90]). Two distinct approaches, depending on how the degrees of uncertainty were interpreted, had been widely studied in the literature [35]. The first definition is the so-called product-based possibilistic conditioning which makes full use of the uncertainty interval [0, 1]. The second definition is called min-based possibilistic conditioning where only the relative order between uncertain information matters. Other forms of possibilistic conditioning have been explored in the literature, particularly the generalization of conditioning definitions to any t-norms (e.g. [86]) or the analysis of conditioning situations in the presence of an impossible event (e.g. [87,89,88,93]).

These standard conditioning operators (probabilistic Bayesian conditioning, Dempster's rule of conditioning, possibilistic min-based and product-based conditionings) have been very well studied in the literature, both from representational and computational points of view.

There is another form of conditioning, called Fagin and Halpern conditioning (noted FH-conditioning in the following), which is little considered in the literature, in particular from a computational point of view. This conditioning was introduced in the framework of belief functions theory in [24]. FH-conditioning provides a better characterization of the conditioned belief function than Dempster's in the context of belief functions being interpreted as lower and upper probabilities, induced by a particular family of probability distributions (see also [33] for a discussion whether FH-conditioning should be considered as a revision or prediction operator). Besides, still within the framework of the theory of belief functions, other theoretical justifications of FH-conditioning have been proposed in [43,34] and recent work have illustrated their use for object detection in the context of autonomous vehicles [39].

In the context of possibility theory, FH-conditioning has been approached only from a semantic point of view [44] and there is no work (to the best of our knowledge) that treats this conditioning from the point of view of syntactic representation of uncertain beliefs. In this paper, we are interested in addressing this computational issue by studying FH-conditioning in a framework where uncertain beliefs are represented by sets of weighted propositional logical formulas. In possibility theory, the available uncertain information is represented by a so-called possibilistic belief base, denoted by $\Sigma$ in the following. This weighted belief base is composed of a set of pairs $(\phi_i, \alpha_i)$ where $\phi_i$ is a propositional logic formula, and $\alpha_i$ is the minimum degree of certainty, specifically the degree of necessity in the sense of possibility theory, associated with $\phi_i$.

The question considered in this paper is how to revise a possibilistic weighted base $\Sigma$, in the light of a new totally certain information, denoted in this paper by $(\psi, 1)$, where $\psi$ is a propositional logic formula, while being in full agreement with the possibilistic semantics of FH-conditioning. The aim here is not to discuss the semantic foundations of FH conditioning, well covered in the literature, but rather to focus on the computational aspects of this conditioning when possibility distributions are compactly represented by sets of weighted formulas. To achieve this goal, we first propose an equivalent syntactic reformulation of the semantic definition of FH-conditioning as a sequence of three transformation operations of possibility distributions. For each of these semantic transformation operations, we propose their equivalent characterisation on the weighted belief bases. At the end of the third operation, we show that the final belief base obtained corresponds exactly to the application of FH-conditioning on weighted belief bases.

We provide in section 4.4 the spatial and temporal complexity analysis of the syntactic computation of FH-conditioning under certain inputs, while the case of uncertain inputs is treated in section 5.3.

We show that the size of the revised belief base is linear with respect to the size of the initial base. Moreover, the complexity of computing the FH-conditioning, from the weighted belief bases, comes down to the complexity of computing the degree of certainty of the new information $\psi$ from the initial base $\Sigma$, which is done in $log_2(n)$ calls to a satisfiability test of a set of propositional formulas (SAT). The last section of the paper deals, both syntactically and semantically, with the characterization of possibilistic FH-conditioning, in the presence of uncertain observations. The input in this framework is no longer a single fully certain formula, but a set of weighted uncertain formulas, mutually disjoint and composing a partition of the set of propositional logic interpretations. This paper is an extended and revised version of the conference paper [91].

The rest of the paper is organized as follows. Section 2 recalls possibilistic logic and presents weighted belief bases and their semantics. Section 3 introduces the notion of FH-conditioning from a semantic point of view. Section 4 contains the computation of the syntactic revision of the weighted belief bases and positions the computation of possibilistic FH-conditioning with respect to the computation of the two standard forms of possibilistic conditioning. Section 5 studies, first from a semantic point of view and then in detail from a syntactic and computational point of view, the extension of possibilistic FH-conditioning when the input is in the form of a set of uncertain observations. Section 6 discusses the positioning of FH-conditioning with respect to a belief revision or update operator. It then examines the potential extension of its syntactic computations to belief functions, conditional knowledge bases, and the updating process. The last section concludes the paper.

## 2. A brief review of possibilistic logic

Possibilistic logic [41,45] is a simple extension of a propositional logic. At the syntactical level, instead of considering that formulas of the propositional knowledge base have the same level of priority, we associate to each formula a degree which reflects its relative level of priority with respect to the other formulas in the knowledge base. The result is called a *possibilistic belief base*, also known as a *possibilistic knowledge base* or *weighted knowledge base*. The possibilistic logic semantics is also an extension of the one of propositional logic, which partitions the set of interpretations in two parts: the models and counter-models of the knowledge base. In possibilistic logic, we get a more refined partition, called a *possibility distribution*, where the counter-models of lower priority information will be preferred to counter-models of higher priority information. The notions of consistency and inference of propositional logic become gradual in possibilistic logic and give respectively the notions of possibility and necessity measures. Possibilistic logic shares some similarities with modal logic, particularly the dual notions of necessity and possibility. However, they differ in important aspects of belief revision. Possibilistic logic is gradual, which means it can handle different possibility and
necessity degrees. In addition, it is non-monotonic, meaning that the addition of new information can modify or invalidate certain previous conclusions (for more details on the links between possibilistic logic and modal logic, see for example [49]). Possibility theory and possibilistic logic are closely related to Ordinal Conditional Functions (OCF), also called ranking functions, introduced by Spohn [50,51]. OCFs are widely used models to represent the epistemic states of agents and to define belief revision methods [73,72,71,70,69,68].

In the following, we will denote the operators $\neg$, $\wedge$, and $\vee$, which correspond to negation, conjunction, and disjunction, respectively, in propositional logic. We denote by $\mathcal{L}$ a finite propositional language, with formulas represented by Greek letters; except for $\Omega$ and $\omega$. The symbols $\perp$ and $\top$ will be used to designate the contradictory and tautological formulas, respectively. The set $\Omega$ stands for the finite set of interpretations of $\mathcal{L}$, with each element $\omega$ belonging to $\Omega$. The satisfaction relation in propositional logic is symbolized by $\vdash$.

## 2.1. Possibility distributions

A possibility distribution $\pi$ is a mapping from the set of interpretations $\Omega$ to the interval $[0, 1]$. $\pi(\omega)$ represents the degree of consistency of the interpretation $\omega$ with the available knowledge. By convention:

* $\pi(\omega) = 1$ means that it is entirely possible for $\omega$ to be the real world.

* $\pi(\omega) = 0$ means that $\omega$ is certainly not the real world.

* $\pi(\omega_1) > \pi(\omega_2)$ simply means that $\omega_1$ is a preferred candidate than $\omega_2$ for being the real state of the world.

From a possibility distribution $\pi$, we can define the degree of possibility and the degree of certainty (or of necessity) of a formula $\phi$:

* $\Pi(\phi) = \max\{\pi(\omega) : \omega \in \Omega, \omega \nvDash \phi\}$ evaluates to what extend $\phi$ is consistent with the available knowledge expressed by $\pi$.

* $N(\phi) = 1 - \Pi(\neg\phi)$ is used to measure to what extent a proposition $\phi$ is entailed by the knowledge expressed by $\pi$.

A possibility distribution $\pi$ is said to be *normalized* if there exists an interpretation which is completely possible (i.e. $\exists\omega \in \Omega | \pi(\omega) = 1$). The normalization condition reflects the fact that all the available uncertain information encoded by the possibility distribution is consistent.

## 2.2. Possibilistic belief bases

At a syntactic level, uncertain information is represented by prioritized or weighted propositional logic knowledge bases, called *possibilistic belief bases*. It is represented by a finite set of weighted formulas (the higher the weight, the more certain the formula) $\Sigma = \{(\phi_i, \alpha_i), i = 1, ..., n\}$, where $\phi_i$ is an element of $\mathcal{L}$, and $\alpha_i \in [0, 1]$ is the weight, considered as a lower bound of the degree of necessity $N(\phi_i)$. Note that formulas with $\alpha_i = 0$ are not explicitly represented in the belief base; namely only beliefs which are somewhat accepted are explicitly represented in the possibilistic belief base.

Possibilistic belief bases are compact representations of possibility distributions. Indeed, one can associate with each possibilistic belief base $\Sigma$ a possibility distribution, denoted by $\pi_{\Sigma}$. Recall that the degree of possibility of an interpretation is its degree of consistency with the belief base. Consider the case where a possibilistic belief base only contains a single formula $\{(\phi, \alpha)\}$. If an interpretation $\omega$ satisfies the formula $\phi$ then this interpretation is completely consistent with $\phi$, hence $\pi_{\Sigma}(\omega) = 1$. If an interpretation $\omega$ does not satisfy the formula $\phi$, then its degree of possibility $\pi_{\Sigma}(\omega)$ is inversely proportional to the certainty $\alpha$ of $\phi$. Namely, the higher the degree of certainty $\alpha$ of $\phi$, the lower the degree of possibility $\pi_{\Sigma}(\omega)$. In particular, if $\phi$ is completely certain, i.e. $\alpha = 1$, then $\omega$ is completely impossible, i.e. $\pi_{\Sigma}(\omega) = 0$.

More generally, if $\Sigma$ contains more than one formula, then interpretations satisfying all formulas in $\Sigma$ will have the greatest degree of possibility, i.e. 1, and the other interpretations will be ranked with respect to the belief of greater weight that they falsify. More formally:

**Definition 1.** The possibility distribution associated with a possibilistic belief base $\Sigma$ is defined, for by [45]:

$$ \forall \omega \in \Omega, \quad \pi_{\Sigma}(\omega) = \begin{cases} 1 & \text{if } \forall (\phi_i, \alpha_i) \in \Sigma, \omega \nvDash \phi_i \\ 1 - \max\{\alpha_i : (\phi_i, \alpha_i) \in \Sigma, \omega \nvDash \phi_i\} & \text{otherwise} \end{cases} \qquad (1) $$

It is easy to check that the possibility distribution $\pi_{\Sigma}$ is normalized if and only if the set of the non-weighted propositional logic formulas obtained from $\Sigma$, i.e. $\{\phi_i : (\phi_i, \alpha_i) \in \Sigma\}$, is consistent in the sense of propositional logic.

In the following, we will use the following academic example to illustrate the different notions of the paper:

**Example 1.** Let $\Sigma = \{(p \vee \neg r, 0.91), (p \vee q, 0.35), (\neg p \vee \neg r, 0.69), (\neg p \vee r, 0.23), (q \vee \neg r, 0.82)\}$ be a possibilistic belief base. Table 1 presents the possibility distribution associated with $\Sigma$ using Equation (1).
<table><caption>**Table 1**
The possibility distribution associated with Σ.</caption><thead><tr><th>p</th><th>q</th><th>r</th><th>π<sub>Σ</sub>(ω)</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1</td><td>0.31</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0.77</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0.18</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0.77</td></tr><tr><td>0</td><td>1</td><td>1</td><td>0.09</td></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0.09</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0.65</td></tr></tbody></table>

The interpretation $¬pq¬r$ is the most preferred one since it is the only one that is consistent with $Σ$ as it satisfies all formulas of $Σ$. Hence, its possibility degree is 1. The interpretations $pq¬r$ and $p¬q¬r$ get the possibility degree 0.77 because they falsify the least certain belief in $Σ$, namely ($¬p ∨ r$, 0.23). The interpretation $¬p¬q¬r$ gets the possibility degree 0.65 because it falsifies ($p ∨ q$, 0.35). The next more plausible interpretations are $pqr$ and $p¬qr$ with possibility degrees of 0.31 and 0.18, respectively. Finally, the least preferred interpretations are $¬pqr$ and $¬p¬qr$ with the possibility degree 0.09, as they falsify the highest belief in $Σ$, namely ($p ∨ ¬r$, 0.91).

### 3. Semantic definition of Fagin-Halpern conditioning

This section deals with belief revision within the framework of possibility theory, a crucial topic in artificial intelligence and information systems management. The revision of a distribution of possibilities $π$ consists in readjusting the degrees of plausibility of the interpretations to give priority to new information, encoded by a propositional logic formula and noted $ψ$. In possibility theory, this revision process is carried out using the notion of *conditioning*, which transforms an *a priori* possibility distribution $π$ and a piece of information $ψ$ into a new, *a posteriori*, possibility distribution noted $π(·|ψ)$.

There are several natural properties for specifying the result of conditioning the distribution of possibilities $π$ with new information $ψ$, considered to be totally certain. The first requirement is that the conditioned (or revised) possibility distribution $π(·|ψ)$ must be normalized or consistent, i.e. there must exist $ω ∈ Ω$ such that $π(ω|ψ) = 1$. The second requirement is that the new information $ψ$ must be totally certain. In section 5, we will examine the case where the observation may be uncertain. This means that for any $ω ∈ Ω$ such that $ω$ falsifies $ψ$, we have $π(ω|ψ) = 0$. Furthermore, the new, revised possibility distribution $π(·|ψ)$ must not alter the relative order between $ψ$ models; that is, for all models $ω ∈ Ω$ and $ω' ∈ Ω$ such that $ω ⊢ ψ$ and $ω' ⊢ ψ$, if $π(ω) ≥ π(ω')$, then $π(ω|ψ) ≥ π(ω'|ψ)$.

Clearly, there are different ways to define $π(·|ψ)$ (e.g. [47]). Two main definitions have been proposed within the framework of possibility theory (e.g. [46]). The first definition, called min-based possibilistic conditioning, consists in i) setting the counter-models of the new information $ψ$ to 0, ii) setting the best models of $ψ$ to 1, and iii) letting the degrees of possibility of the other models of $ψ$ unchanged. The second definition, called product-based possibilistic conditioning, consists in i) setting the counter-models of the new information $ψ$ to 0, and ii) proportionally shifting the degrees of possibility of the models of $ψ$ up to obtain a normalized conditional possibility distribution.

These two definitions are formally described as follows for $Π(ψ) > 0$:

*   **Minimum-based conditioning:** Hisdal [82] suggested that the definition of a conditioning operator in a qualitative context should fulfill the condition:

$$ \forall \omega \Vdash \phi, \pi(\omega) = \min(\pi(\omega|\phi), \Pi(\phi)). $$

Dubois and Prade [92] proposed selecting the largest conditional possibility distribution that satisfies this condition, which leads to the following conditioning operator.

$$ \forall \omega \in \Omega, \quad \pi(\omega|_m \psi) = \begin{cases} 1, & \text{if } \pi(\omega) = \Pi(\psi) \text{ and } \omega \Vdash \psi \\ \pi(\omega), & \text{if } \pi(\omega) < \Pi(\psi) \text{ and } \omega \Vdash \psi \\ 0, & \text{if } \omega \nvDash \psi \end{cases} \qquad (2) $$

*   **Product-based conditioning:**

$$ \forall \omega \in \Omega, \quad \pi(\omega|_p \psi) = \begin{cases} \frac{\pi(\omega)}{\Pi(\psi)}, & \text{if } \omega \Vdash \psi \\ 0, & \text{otherwise} \end{cases} \qquad (3) $$

We emphasize that, within the scope of this article, the universe of discourse is finite and represented by the set of interpretations of propositional logic. Consequently, we do not consider cases where the universe of discourse is infinite. Furthermore, we restrict the comparative analysis in the rest of the article to conditioning operators based solely on the minimum and the product (for generalization to t-norms, please refer to [87,93,88]). We also assume throughout this article that the observation is somewhat
<caption>**Table 2**</caption>

Result of FH-conditioning by the new piece of information $\psi = \neg p \lor q \lor r$ of the possibility distribution of Example 1.

<table><thead><tr><th>p</th><th>q</th><th>r</th><th>π<sub>Σ</sub>(ω)|<sub>FH</sub> ¬p ∨ q ∨ r)</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1</td><td>0.574</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0.77</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0.439</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><td>0</td><td>1</td><td>1</td><td>0.281</td></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0.281</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0.738</td></tr></tbody></table>

certain, which allows us to exclude the case of conditioning with an impossible event. By convention, when $\Pi(\phi) = 0$, we assume that $\pi(\omega|\phi) = 1$ for all $\omega \in \Omega$, regardless of the conditioning operator chosen. This very particular case will not be addressed in the subsequent sections of this article.

There is an alternative to above two definitions, given by Equations (2) and (3), which has been very little explored in possibility theory, especially from computational point of views. This is the conditioning proposed by Fagin and Halpern [23] and introduced within the framework of belief functions. This definition of conditioning has been adapted to possibility theory and was directly defined on possibility measures (instead of possibility distributions) as follows [44]:

$$ \Pi(\phi|_{FH} \psi) = \frac{\Pi(\phi \land \psi)}{\Pi(\phi \land \psi) + N(\neg\phi \land \psi)} \quad (4) $$

We recall that in the above equation $N(\phi) = 1 - \Pi(\neg\phi)$. Now, if we restrict the definitions $\Pi(\cdot|_{FH} \psi)$ to interpretations, we get the definition of FH-conditioning on possibility distributions [44] given in Definition 2.

**Definition 2.** Let $\pi$ be a possibility distribution and let $\psi$ be a propositional logic formula. Then the FH-conditioning of $\pi$ by $\psi$, denoted by $\pi(\cdot|_{FH} \psi)$, is given by the following equation:

$$ \forall \omega \in \Omega, \quad \pi(\omega|_{FH} \psi) = \begin{cases} \max\left(\pi(\omega), \frac{\pi(\omega)}{\pi(\omega)+N(\psi)}\right) & \text{if } \omega \models \psi \\ 0 & \text{if } \omega \nvDash \psi \end{cases} \quad (5) $$

Where again we recall that $N(\psi) = 1 - \Pi(\neg\psi)$, with $\Pi(\psi) = \max\{\pi_{\Sigma}(\omega) : \omega \in \Omega \text{ and } \omega \models \psi\}$.

In the rest of the paper, and when there is no ambiguity, we will simply use $\pi(\cdot|\psi)$ instead of $\pi(\cdot|_{FH} \psi)$. Let us continue our example.

**Example 2.** Let us apply the possibilistic FH-conditioning at the semantic level to the possibility distribution $\pi_{\Sigma}$ given in the Example 1 by the new piece of information $\psi = \neg p \lor q \lor r$. Note that from Table 1, $\Pi(p \land \neg q \land \neg r) = 0.77$. Hence, $N(\neg p \lor q \lor r) = 0.23$. Table 2 gives the FH-conditioned possibility distribution.

Let us explain the result of FH-conditioning with the input represented by the propositional logic formula $\neg p \lor q \lor r$. The interpretation $p \neg q \neg r$ is not model of $\neg p \lor q \lor r$. Therefore, its conditional possibility degree is equal 0. The others interpretations are models of $\neg p \lor q \lor r$. Therefore, after conditioning, their possibility degree will be equal to $\max(\pi(\omega), \frac{\pi(\omega)}{\pi(\omega)+N(\neg p \lor q \lor r)})$.

## 4. Syntactic counterpart of possibilistic Fagin-Halpern conditioning

There is a clear interest in FH-conditioning for the revision of uncertain information within the framework of belief functions theory, both at the theoretical and the applications levels. In the framework of possibility theory, the very few works that exist (e.g. [44]) mainly concern semantic definitions of FH-conditioning (e.g. defined on the set of interpretations of propositional logic) or on discussions whether the FH-conditioning is a revision operator, a prediction operator or what is called a focusing operator (see [48] and [33] for more details).

However, unlike min-based and product-based conditioning (and also their hybrid version [25]) which have been well studied in the literature, there is no work (to the best of our knowledge) that deals with syntactic computation of possibilistic FH-conditioning applied on possibilistic belief bases. Defining a syntactic FH-conditioning, i.e. at the level of possibilistic knowledge bases, has clear computational advantages over an application of FH-conditioning at the semantic level, since obviously the size of the set interpretations is exponential with respect to the number of propositional symbols of the used language.

Fig. 1 summarizes the purpose of this section and is explained as follows:

* Inputs of our syntactic FH-conditioning computation are:
<figure><img src="image_4.png" /><figcaption>Fig. 1. Schema associated with the syntactic counterpart of Fagin and Halpern's conditioning.</figcaption></figure>

- a possibilistic belief base $\Sigma$,

- a totally certain new piece of information $(\psi, 1)$ that must be taken into account.

• Let $\pi_{\Sigma}$ be the possibility distribution associated with $\Sigma$ using Equation (1).

• Let $\pi_{\Sigma}(\cdot|\psi)$ be the conditional possibility distribution, resulting from the semantic application of FH-conditioning on $\pi_{\Sigma}$ after the integration of the new computing $(\psi, 1)$ using Equation (5).

• Our goal is to compute, from $\Sigma$ and the totally certain information $(\psi, 1)$, a new possibilistic belief base, denoted $\Sigma_{FH}$, such that:

$$ \forall \omega \in \Omega, \pi_{\Sigma_{FH}}(\omega) = \pi_{\Sigma}(\omega | \psi), \qquad (6) $$

where $\pi_{\Sigma_{FH}}$ is the possibility distribution associated with $\Sigma_{FH}$ using Equation (1).

The satisfaction of Equation (6) is necessary to have a syntactic computation that fully agrees with the semantic definition of FH-conditioning in possibility theory.

The following subsection first presents an equivalent definition of the FH conditioning into three elementary steps, each consisting of an elementary transformation of the possibility distributions. Then, we give the syntactic counterpart of each of these three steps; before finally putting together all the syntactical computations to achieve the objective of this section.

## 4.1. Possibilistic FH-conditioning in three main steps

The computation of the syntactic counterpart of Equation (5) is not immediate when starting directly from a knowledge base $\Sigma$ associated with the initial possibility distribution $\pi(\omega)$. Indeed, the semantic definition of conditioning given in Equation (5) involves multiple operations of different natures, making it difficult to obtain a syntactic representation in a single step. This equation first involves numerical operators (involving divisions and additions), which translate into some shifting operations on the weights of formulas from the initial base. It also includes a qualitative operation (here the maximum), which introduces a sort of weighted disjunction between the two knowledge bases associated with the distributions that would be combined using the maximum operator. Finally, some interpretations become impossible, suggesting the need to add fully certain information to exclude these interpretations. We are therefore going to describe it progressively in an alternative form by breaking down the semantic definition of FH-conditioning (given by Equation (5)) into three elementary steps of modification of possibility distributions.

Let $\pi_{\Sigma}$ be the initial possibility distribution associated with the initial possibilistic belief base $\Sigma$ (using Equation (1)). Let $(\psi, 1)$ be the new piece of information that should be taken into account. We define the three steps as follows:

• **Step 1: shifting the initial possibility distribution.** This step mainly consists of shifting each possibility degree $\pi_{\Sigma}(\omega)$ by integrating the necessity degree associated with the new information. The result of this modification of the initial possibility distribution is simply denoted $\pi_1$ and is formally defined as follows:

$$ \pi_1(\omega) = \frac{\pi_{\Sigma}(\omega)}{\pi_{\Sigma}(\omega) + N(\psi)} $$

where we recall that $N(\psi) = 1 - \Pi(\neg\psi)$, and $\Pi(\neg\psi) = \max\{\pi_{\Sigma}(\omega) : \omega \in \Omega \text{ and } \omega \nvDash \neg\psi\}$.
* **Step 2: combining possibility distributions.** This second step consists in combining with the maximum operator, the result of the possibility distribution of step 1 with the initial possibility distribution $\pi_\Sigma$.

The possibility distribution obtained at this stage is again simply denoted by $\pi_2$ and is defined as follows:

$$\pi_2(\omega) = \max(\pi_\Sigma(\omega), \pi_1(\omega))$$

* **Step 3: integrating new information.** This third and final step consists in integrating the new information $(\psi, 1)$ into the possibility distribution obtained in step 2. For this, we simply encode the new information $(\psi, 1)$ by a binary possibility distribution, where only possibility degree 1 (totally possible) and possibility degree 0 (totally impossible) are used. The possibility degree 1 is associated with models of $\psi$ while the possibility degree 0 is associated with its counter-models.

The possibility distribution obtained in step 3 is denoted by $\pi_3$ and is defined as:

$$\pi_3(\omega) = \min(\pi_2(\omega), \pi_\psi(\omega)),$$

where

$$\pi_\psi(\omega) = \begin{cases} 1, & \text{if } \omega \vdash \psi, \\ 0, & \text{otherwise} \end{cases}$$

It is not difficult to show, that at the end of the third step, the final obtained possibility distribution is exactly that resulting from applying FH-conditioning on $\pi_\Sigma$ with $(\psi, 1)$ and given by Equation (5); i.e. we have:

$$\forall \omega \in \Omega, \pi_3(\omega) = \pi(\omega |_{FH} \psi).$$

Thus, finding the syntactic counterpart of Equation (5) is equivalent to finding the syntactic counterpart of $\pi_3$.

The following three subsections give the syntactic counterparts of the possibility distributions obtained at each of the three steps described above.

### 4.1.1. Syntactic computation of Step 1: shifting the initial possibility distribution

We begin by giving the syntactic counterpart of the possibility distribution obtained in Step 1 and denoted by $\pi_1$. The following Proposition 1 provides a possibleistic belief base, denoted by $\Sigma_1$, which compactly encodes the distribution $\pi_1$. More precisely, the resulting possibilistic belief base $\Sigma_1$ is composed of two parts. The first part, denoted in Proposition 1 by $\Sigma_{11}$, consists in modifying the possibility degrees associated with each of the formulas of the initial base $\Sigma$, in order to reflect the shift made in this step 1 on the initial possibility distribution. The second part is composed of a single formula, which is a weighted contradiction, that expresses the fact that $\pi_1$ can be sub-normalized (i.e. there can be no interpretation $\omega$, such as $\pi_1(\omega) = 1$). We will see in the computation of the possibilistic belief base associated with Step 2 that this sub-normalization will be lifted and the result obtained at this step 2 is always normalized and consistent.

The precise result of the computation of the possibilistic belief base associated with the possibility distribution of step 1 is given in the following Proposition 1.

**Proposition 1.** Let $\Sigma = \{(\phi_i, \alpha_i), i = 1, ..., n\}$ be the initial belief base. Let $(\psi, 1)$ be the new piece of information. Let $\Sigma_1 = \{(\bot, 1 - \frac{1}{1+N(\psi)}\}\} \cup \Sigma_{11}$ be a belief base obtained from $\Sigma$, and $\Sigma_{11} = \{(\phi_i, 1 - \frac{1-\alpha_i}{1-\alpha_i+N(\psi)}), (\phi_i, \alpha_i) \in \Sigma\}$. Then, $\forall \omega \in \Omega$, we have:

$$\pi_{\Sigma_1}(\omega) = \pi_1(\omega) = \frac{\pi_{\Sigma}(\omega)}{\pi_{\Sigma}(\omega) + N(\psi)}, \qquad (7)$$

where $\pi_{\Sigma_1}(\omega)$ is the possibility distribution associated with $\Sigma_1$ and $\pi_1$ is the possibility distribution obtained at Step 1 described in subsection 4.1.

**Proof.** Let $\omega \in \Omega$. There are two cases to consider:

1. $\omega$ is a model of all formulas of $\Sigma$. Namely, $\pi_\Sigma(\omega) = 1$. In this case, $\omega$ is also a model of all formulas of $\Sigma_1$. Therefore:

$$\begin{aligned} \pi_{\Sigma_1}(\omega) &= 1 - \left(1 - \frac{1}{1 + N(\psi)}\right) \\ &= \frac{\pi_{\Sigma}(\omega)}{\pi_{\Sigma}(\omega) + N(\psi)}. \end{aligned}$$

2. $\omega$ falsifies at least a weighted formula from $\Sigma$. This also means that $\omega$ falsifies at least a weighted formula from $\Sigma_1$. In this case:

$$\begin{aligned} \pi_{\Sigma_1}(\omega) &= \min\{1 - \left(1 - \frac{1}{1 + N(\psi)}\right), \pi_{\Sigma_{11}}(\omega)\} \\ &= \min\{\frac{1}{1 + N(\psi)}, \pi_{\Sigma_{11}}(\omega)\} \\ &= \pi_{\Sigma_{11}}(\omega) \end{aligned}$$
<table><caption>**Table 3**
Possibility distribution $\pi_1(\omega)$ resulting from step 1.</caption><thead><tr><th>p</th><th>q</th><th>r</th><th>π<sub>1</sub>(ω)</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1</td><td>0.574</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0.77</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0.439</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0.77</td></tr><tr><td>0</td><td>1</td><td>1</td><td>0.281</td></tr><tr><td>0</td><td>1</td><td>0</td><td>0.813</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0.281</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0.738</td></tr></tbody></table>

Indeed, $\pi_{\Sigma_{11}}(\omega)$ is necessarily of the form $\frac{1-\alpha_i}{1-\alpha_i+N(\psi)}$ for some $(\phi_i, 1 - \frac{1-\alpha_i}{1-\alpha_i+N(\psi)})$ in $\Sigma_{11}$. We also have $\frac{1-\alpha_i}{1-\alpha_i+N(\psi)} < \frac{1}{1+N(\psi)}$ (we recall that $\alpha_i > 0$). Now, we develop the expression associated with $\pi_{\Sigma_1}$:

$$ 
\begin{aligned}
\pi_{\Sigma_1}(\omega) &= \pi_{\Sigma_{11}}(\omega) \\
&= \min\{1 - \left[1 - \frac{1-\alpha_i}{1-\alpha_i + N(\psi)}\right] : (\phi_i, 1 - \frac{1-\alpha_i}{1-\alpha_i + N(\psi)}) \in \Sigma_{11} \text{ and } \omega \not\vdash \phi_i\} \\
&= \min\{\frac{1-\alpha_i}{1-\alpha_i + N(\psi)} : (\phi_i, 1 - \frac{1-\alpha_i}{1-\alpha_i + N(\psi)}) \in \Sigma_{11} \text{ and } \omega \not\vdash \phi_i\} \\
&= \frac{\min\{1-\alpha_i : (\phi_i, \alpha_i) \in \Sigma \text{ and } \omega \not\vdash \phi_i\}}{\min\{1-\alpha_i + N(\psi) : (\phi_i, 1 - \frac{1-\alpha_i}{1-\alpha_i + N(\psi)}) \in \Sigma_{11} \text{ and } \omega \not\vdash \phi_i\}} \\
&= \frac{\pi_{\Sigma}(\omega)}{\pi_{\Sigma}(\omega) + N(\psi)} \quad \square
\end{aligned}
$$

Example 3 illustrates the computation of the possibilistic belief base given in the Proposition 1 on our running example.

**Example 3.** Let us consider the possibility distribution $\pi_{\Sigma}(\omega)$ of Example 1. Let $\psi = \neg p \vee q \vee r$ be the new piece of information. Table 3 gives the values of

$$ \pi_1(\omega) = \frac{\pi_{\Sigma}(\omega)}{\pi_{\Sigma}(\omega) + N(\neg p \vee q \vee r)} $$

Let us compute the belief base $\Sigma_1$ associated with $\pi_1$. From Proposition 1, the general form of $\Sigma_1$ is

$$ \Sigma_1 = \{ (\perp, 1 - \frac{1}{1 + N(\psi)}) \} \cup \Sigma_{11} $$

$$ \text{with } \Sigma_{11} = \{ (\phi_i, 1 - \frac{1-\alpha_i}{1-\alpha_i+N(\psi)}), (\phi_i, \alpha_i) \in \Sigma \} $$

Replacing $\psi$ by $\neg p \vee q \vee r$, we get:

$$ \Sigma_1 = \{ \perp, 0.187 \} \cup \{ (p \vee \neg r, 0.719), (p \vee q, 0.262), (\neg p \vee \neg r, 0.426), (\neg p \vee r, 0.23), (q \vee \neg r, 0.561) \} \quad (8) $$

One can easily check that if we compute the possibility distribution $\pi_{\Sigma_1}$ associated with the possibilistic belief base $\Sigma_1$, using Equation (1), we get exactly the one given in Table 3, which means that $\forall \omega \in \Omega, \pi_{\Sigma_1}(\omega) = \pi_1(\omega)$.

## 4.2. Syntactic computation of Step 2: combining possibility distributions

We now present the syntactic computation of Step 2. It consists in the computation of a possibilistic belief base, which we will denote $\Sigma_2$, whose associated distribution is equal to that obtained from step 2 and denoted by $\pi_2$.

We recall that $\pi_2$ is the maximum of $\pi_1$ (obtained in step 1) and the possibility distribution $\pi_{\Sigma}$ associated with the initial belief base $\Sigma$. There exists in the literature (e.g. [32]) a syntactic characterization of the combination by the maximum operator. However, such a characterization would yield a resultant possibilistic belief base of size equal to the product of the two sizes of the belief bases to be combined, i.e. in our case, $\mathcal{O}(|\Sigma|) \times (|\Sigma_1|)$, where $|\Sigma|$ (respectively $|\Sigma_1|$) is the number of weighted formulas in $\Sigma$ (respectively in $\Sigma_1$). Proposition 2 gives an alternative characteristic but with a better spatial complexity result. Indeed, as we will see, the resulting base associated to the syntactic combination based on the maximum of $\pi_1$ and $\pi_{\Sigma}$, is of linear size with respect to those of the possibilistic belief bases to be combined; and more precisely in $\mathcal{O}(\max(|\Sigma|, |\Sigma_1|))$.

Besides, as $\pi_{\Sigma}$ is normalized, the distribution $\pi_2$, defined as being the maximum of the distributions $\pi_{\Sigma}$ and $\pi_1$, is trivially also normalized. As a result, the weighted contradiction formula that was present in the resulting possibilistic belief base of step 1, will no longer be present in the belief base obtained at the end of step 2.
In summary, the computation of the possibilistic belief base associated with the possibility distribution of step 2 is given in the following Proposition 2.

**Proposition 2.**

• Let $\Sigma = \{(\phi_i, \alpha_i), i = 1, ..., n\}$ be the initial belief base and $\psi$ be the new piece of information.

• Let $\Sigma_1$ be the belief base obtained from Proposition 1; namely, $\Sigma_1 = \{(\bot, 1 - \frac{1}{1+N(\psi)}\} \cup \Sigma_{11}$, with $\Sigma_{11} = \{(\phi_i, 1 - \frac{1-\alpha_i}{1-\alpha_i+N(\psi)}), (\phi_i, \alpha_i) \in \Sigma\}$.

• Let $\Sigma_2 = \{(\phi_i, \min(\alpha_i, 1 - \frac{1-\alpha_i}{1-\alpha_i+N(\psi)})), (\phi_i, \alpha_i) \in \Sigma\}$ be a belief base obtained from $\Sigma$.

Then, $\forall \omega \in \Omega$, we have:

$$ 
\begin{aligned}
\pi_{\Sigma_2}(\omega) &= \pi_2(\omega) \\
&= \max \left( \pi_{\Sigma}(\omega), \pi_{\Sigma_1}(\omega) \right) \\
&= \max \left( \pi_{\Sigma}(\omega), \frac{\pi_{\Sigma}(\omega)}{\pi_{\Sigma}(\omega) + N(\psi)} \right),
\end{aligned}
$$

where $\pi_{\Sigma_2}$ and $\pi_{\Sigma_1}$ denote the possibility distributions associated with the belief's bases $\Sigma$, $\Sigma_1$ and $\Sigma_2$ respectively. The distribution $\pi_2$ is the one obtained at Step 2 and described in subsection 4.1.

**Proof.** Let $\omega \in \Omega$. There are two cases to consider:

1. $\omega$ is a model of all formulas of $\Sigma$. Namely, $\pi_{\Sigma}(\omega) = 1$. In this case:

$$ \pi_{\Sigma_1}(\omega) = \frac{1}{1 + N(\psi)}, \quad \text{and} \quad \pi_{\Sigma_2}(\omega) = 1. $$

Therefore, we indeed have: $\pi_{\Sigma_2}(\omega) = \max(\pi_{\Sigma}(\omega), \pi_{\Sigma_1}(\omega)) = 1$.

2. $\omega$ falsifies at least a weighted formula from $\Sigma$. For sake of simplicity, we note:

• $\pi, \pi_1$, and $\pi_2$ instead of $\pi_{\Sigma}, \pi_{\Sigma_1}$, and $\pi_{\Sigma_2}$.

• $m$ the number of formulas from $\Sigma$ (resp $\Sigma_1$) falsified by $\omega$. Note that, by construction, $\Sigma$ and $\Sigma_1$ contain exactly the same propositional formulas. However, they differ on the weights associated with these formulas. Hence, $m$ is the same for both $\Sigma$ and $\Sigma_1$.

• $\{\alpha_1, ..., \alpha_m\}$ and $\{\beta_1, ..., \beta_m\}$ be the sets of weights associated with falsified formulas in $\Sigma$ and $\Sigma_2$ respectively, with $\beta_i = 1 - \frac{1-\alpha_i}{1-\alpha_i+N(\psi)}$.

By definition, we have for all $\omega \in \Omega$:

$$ 
\begin{aligned}
\pi_2(\omega) &= \min\{1 - \min(\alpha_i, \beta_i) : (\phi_i, \alpha_i) \in \Sigma \text{ and } (\phi_i, \min(\alpha_i, \beta_i)) \in \Sigma_2 \text{ and } \omega \notin \phi_i\} \\
&= \min\{\max(1 - \alpha_i, 1 - \beta_i) : i = 1, ..., m\}.
\end{aligned}
$$

For the sake of simplicity, we avoid repeating $(\phi_i, \alpha_i) \in \Sigma$, $(\phi_i, \min(\alpha_i, \beta_i)) \in \Sigma_2$, and $\omega \notin \phi_i$ in the following.

By distributing the min operator over the max operator, we obtain:

$$ \pi_2(\omega) = \max\{\min\{x_1, ..., x_m\} : x_i \in \{1 - \alpha_i, 1 - \beta_i\}, i = 1, ..., m\} $$

• If $\forall i = \{1, ..., m\}$ we have $x_i = (1 - \alpha_i)$ then: $\min\{x_i, ..., x_m\} = \min\{1 - \alpha_1, ..., 1 - \alpha_k, ..., 1 - \alpha_m\} = 1 - \alpha_k = \pi(\omega)$, for some $k \in \{1, ..., m\}$.

• If $\forall i = \{1, ..., m\}$ we have $x_i = (1 - \beta_i)$ then: $\min\{x_i, ..., x_m\} = \min\{1 - \beta_1, ..., 1 - \beta_t, ..., 1 - \beta_m\} = 1 - \beta_t = \pi_1(\omega)$, for some $t \in \{1, ..., m\}$.

• In cases where some $x_i$ values are equal to $(1 - \alpha_i)$ and others are equal to $(1 - \beta_i)$, we need consider the following three scenarios:

(a) $\min\{x_1, ..., x_m\} = 1 - \alpha_y$ for some $y \in \{1, ..., m\}$ and $\alpha_y \neq \alpha_k$. Then $x_k = 1 - \alpha_k = \pi(\omega)$, and $\pi_1(\omega) \ge \min\{x_1, ..., x_m\}$.

(b) $\min\{x_1, ..., x_m\} = 1 - \beta_z$ for some $z \in \{1, ..., m\}$ and $\beta_z \neq \beta_i$. Then $x_t = 1 - \alpha_t = \pi(\omega)$, and $\pi(\omega) \ge \min\{x_1, ..., x_m\}$.

(c) $\min\{x_1, ..., x_m\} = 1 - \alpha_y = 1 - \alpha_k = \pi(\omega)$, or $\min\{x_1, ..., x_m\} = 1 - \beta_z = 1 - \beta_k = \pi_1(\omega)$. Then trivially, $\max(\pi(\omega), \pi_1(\omega)) \ge \min\{x_1, ..., x_m\}$.

Therefore for any combination $\{x_1, ..., x_m\}$ where $\exists i \in \{1, ..., m\}$ such that $x_i = (1 - \alpha_i)'$s and where also $\exists i \in \{1, ..., m\}$ such that $x_j = (1 - \beta_j)'$s we have: $\pi(\omega) \ge \min\{x_1, ..., x_m\}$ and $\pi_1(\omega) \ge \min\{x_1, ..., x_m\}$.

Therefore:

$$ 
\begin{aligned}
\pi_2(\omega) &= \max\{\min\{x_1, ..., x_m\} : x \in \{1 - \alpha_i, 1 - \beta_i\}, i = 1, ..., m\} \\
&= \max\{\pi(\omega), \pi_1(\omega)\}. \quad \square
\end{aligned}
$$
Note that in Proposition 2, if a given $\omega \in \Omega$ is a model of all formulas of $\Sigma$, then $\pi_{\Sigma_1}(\omega) = \frac{1}{1+N(\psi)}$. However, if an interpretation $\omega \in \Omega$ is not a model of some formulas of $\Sigma$, then $\pi_{\Sigma_1}(\omega) = \frac{\pi_{\Sigma}(\omega)}{\pi_{\Sigma}(\omega)+N(\psi)}$. The following Example 4 illustrates Proposition 2.

**Example 4.** Let us consider the possibility distributions $\pi_{\Sigma}(\omega)$ and $\pi_1(\omega)$ of the Examples 1 and 3 respectively. Let $\psi = \neg p \lor q \lor r$ be the new piece of information. Recall that $N(\neg p \lor q \lor r) = 0.23$. Table 4 gives the values of $\pi_2(\omega) = \max(\pi_{\Sigma}(\omega), \pi_1(\omega))$.

<table><caption>**Table 4**
The possibility distribution $\pi_2(\omega)$.</caption><thead><tr><th>p</th><th>q</th><th>r</th><th>π<sub>Σ</sub>(ω)</th><th>π<sub>1</sub>(ω)</th><th>π<sub>2</sub>(ω)</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1</td><td>0.31</td><td>0.574</td><td>0.574</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0.77</td><td>0.77</td><td>0.77</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0.18</td><td>0.439</td><td>0.439</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0.77</td><td>0.77</td><td>0.77</td></tr><tr><td>0</td><td>1</td><td>1</td><td>0.09</td><td>0.281</td><td>0.281</td></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td><td>0.813</td><td>1</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0.09</td><td>0.281</td><td>0.281</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0.65</td><td>0.738</td><td>0.738</td></tr></tbody></table>

Let us compute, using Proposition 2, the belief base $\Sigma_2 = \{(\phi_i, \min(\alpha_i, 1 - \frac{1-\alpha_i}{1-\alpha_i+N(\psi)})), (\phi_i, \alpha_i) \in \Sigma\}$ for the new piece of information $\psi = \neg p \lor q \lor r$. We have:

$$ \Sigma_2 = \{(p \lor \neg r, \min(0.91, 0.719)), (p \lor q, \min(0.35, 0.262)), (\neg p \lor \neg r, \min(0.69, 0.426)), \\ (\neg p \lor r, \min(0.23, 0.23)), (q \lor \neg r, \min(0.82, 0.561))\} \\ = \{(p \lor \neg r, 0.719), (p \lor q, 0.262), (\neg p \lor \neg r, 0.426), (\neg p \lor r, 0.23), (q \lor \neg r, 0.561)\}. $$

Finally, one can check that computing the possibility distribution $\pi_{\Sigma_2}(\omega)$ for the belief base $\Sigma_2$, using Equation (1), leads exactly to the one of the above table, which means that $\forall \omega \in \Omega, \pi_{\Sigma_2}(\omega) = \pi_2(\omega)$.

### 4.3. Syntactic computation of Step 3: integrating new information

The last step consists in integrating, in the possibility distribution obtained in step 2, the fact that the new information $\psi$ is totally certain. The computation of the syntactic counterpart of this step is immediate as it simply amounts to adding to the possibilistic belief base, resulting from step 2, the weighted formula $(\psi, 1)$. More specifically, we have:

**Proposition 3.** Let $\Sigma = \{(\phi_i, \alpha_i), i = 1, \dots, n\}$ be the initial belief base. Let $\psi$ be a new piece of information. Let $\Sigma_2$ be the belief base obtained from Proposition 2. Let $\Sigma_3 = \Sigma_2 \cup \{(\psi, 1)\}$. Then, $\forall \omega \in \Omega$:

$$ \pi_{\Sigma_3}(\omega) = \begin{cases} \pi_{\Sigma_2}(\omega), & \text{if } \omega \models \psi, \\ 0, & \text{otherwise.} \end{cases} \qquad (9) $$

**Proof.** The proof is immediate using the definition of a possibility distribution associated with a belief base. Indeed, let $\omega$ be an interpretation. If $\omega$ is not model of $\psi$, then $\pi_{\Sigma}(\omega) = 0$ as it falsifies a fully certain formula $(\psi, 1)$. If $\omega$ is a model of $\psi$, then trivially $\pi_3(\omega) = \pi_2(\omega)$. $\square$

To sum up, Propositions 1-3 allow us to provide the syntactic counterpart of the possibilistic Fagin-Halpern conditioning defined by the Equation (5). The final possibilistic belief base is summarized by:

$$ \Sigma_{FH} = \{(\psi, 1)\} \cup \{(\phi_i, \min(\alpha_i, 1 - \frac{1-\alpha_i}{1-\alpha_i+N(\psi)})), (\phi_i, \alpha_i) \in \Sigma\} \qquad (10) $$

Our last example confirms that the final computation of the possibilistic belief base at the end of Step 3 represents the FH-conditioning defined on the initial distribution $\pi_{\Sigma}$.

**Example 5.** Let us consider the possibility distribution $\pi_2(\omega)$ of Example 4. Recall that the new piece of information is $\psi = \neg p \lor q \lor r$. Table 5 gives the values of $\pi_3(\omega) = \min(\pi_2(\omega), \pi_\psi(\omega))$, where we recall that:

$$ \pi_{\psi}(\omega) = \begin{cases} 1, & \omega \models \psi \\ 0, & \text{otherwise} \end{cases} $$

Using Equation (10), we get:
<table><caption>**Table 5**
The possibility distribution $\pi_3(\omega)$.</caption><thead><tr><th>p</th><th>q</th><th>r</th><th>π<sub>2</sub>(ω)</th><th>π<sub>3</sub>(ω)</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1</td><td>0.574</td><td>1</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0.77</td><td>1</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0.439</td><td>1</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0.77</td><td>0</td></tr><tr><td>0</td><td>1</td><td>1</td><td>0.281</td><td>1</td></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0.281</td><td>1</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0.738</td><td>1</td></tr></tbody></table>

$$ \Sigma_{FH} = \{(\neg p \lor q \lor r, 1)\} \cup \{(p \lor \neg r, 0.719), (p \lor q, 0.262), (\neg p \lor \neg r, 0.426), (\neg p \lor r, 0.23), (q \lor \neg r, 0.561)\}. $$

Finally, one can check that computing the possibility distribution $\pi_{\Sigma_{FH}}$ associated with the belief base $\Sigma_{FH}$, using Equation (1), gives exactly the same distribution given in the table above. This result is also identical to the possibility distribution given in Example 2 when applying the semantic FH-conditioning with $\psi = \neg p \lor q \lor r$.

We finish this section by giving the complexity results of computing the syntactic counterpart $\Sigma_{FH}$ (Equation (10)) of FH-conditioning. It is easy to check from Equation (10) that the spatial complexity is linear with respect to the size of the initial base $\Sigma$ and more precisely the size of the final belief base is in $O(|\Sigma|)$. This good result is obtained thanks to the decomposition of the FH-conditioning into three elementary operations. Indeed, as explained in subsection 4.2, a direct application of existing results in the literature (e.g. [32]) regarding Step 2 (the max-based combination of possibility distributions) would generate a quadratic spatial complexity with respect to the size of the initial belief base, i.e. in $O(|\Sigma|^2)$.

Regarding time complexity, the difficult task in Equation (10) is the computation of the degree of necessity $N(\psi)$ from the initial base. The complexity of reasoning in possibilistic logic has been well studied in the literature (e.g. [41]). The degree $N(\psi)$ is equal to the highest degree $\alpha_i$ such that $\{\phi_i|(\phi_i, \alpha_i) \in \Sigma \text{ and } \alpha_i \ge \alpha_j\}$ is consistent and infers $\psi$, where the notions of inference and consistency are those of propositional logic. If such a degree does not exist then $N(\psi) = 0$. If we note $n$ the number of different degrees in the possibilistic belief base $\Sigma$, then it is easy to provide a dichotomous search algorithm for calculating this largest weight $\alpha_i$ in $log_2(n)$ calls to the propositional logic satisfiability test.

## 4.4. Min-based and product-based conditioning vs FH-conditioning

This sub section briefly compares FH-conditioning with the two standard forms of possibilistic conditioning: min-based conditioning and product-based conditioning.

At the semantic level, FH-conditioning shares the following four properties with min-based and product-based conditioning (where $|_0$ stands for possibilistic conditioning operator):

* $\pi(\cdot|_0 \psi)$ is normalized (or consistent).

* $\forall \omega \in \Omega$, if $\omega \nvdash \psi$ then $\pi(\omega|_0 \psi) = 0$.

This property confirms that the new information $\psi$ is completely certain and therefore any counter-model of $\psi$ is considered impossible after the conditioning operation.

* $\forall \omega \in \Omega, \forall \omega' \in \Omega$ such that $\omega \Vdash \psi, \omega' \Vdash \psi$, we have:

$$ \pi(\omega) > \pi(\omega') \text{ iff } \pi(\omega|_0 \psi) > \pi(\omega'|_0 \psi). $$

This property means that the conditioning does not alter the relative order between the models of the new information $\psi$.

* $\forall \omega \in \Omega$, if $\pi(\omega) = 0$ then $\pi(\omega|_0 \psi) = 0$.

This property means that a priori impossible conditional interpretations will remain so after conditioning.

The three possibilistic conditioning (min-based conditioning, product-based conditioning and FH-conditioning) satisfy the above four properties.

There remains however the following property which is satisfied by two standard possibilistic conditioning (min-based and product-based conditioning) but which is not satisfied by the FH-conditioning

* if $N(\psi) > 0$ then $\forall \omega \in \Omega$ such that $\omega \Vdash \psi$, we have: $\pi(\omega) = \pi(\omega|_0 \psi)$.

This property means that if $\psi$ is a priori accepted (expressed by $N(\psi) > 0$ or by $\Pi(\psi) > \Pi(\neg\psi)$) then the degrees of possibilities on the models remain unchanged. This property is not satisfied with possibilistic FH-conditioning where the possibility degree of a model of $\psi$ can be modified, depending on the a priori degree of beliefs of $\psi$.

Moreover, it is easy to see in the Equation (10) that when $N(\psi) = 0$ then the revised base is simply equal to the new information $\{(\psi, 1)\}$. This behavior is different with min-based conditioning and product-based conditioning which retains part of the initial information even if the new information was not initially accepted.
At the syntactic level, the computational complexity of performing the FH-conditioning of a weighted knowledge base is the same as that of the standard possibilistic conditioning (min-based and product-based possibilistic conditioning) given in [52]. For the three possibilistic conditioning operators, the spatial complexity is linear in with respect to the size of the initial base Σ. As for the time complexity, the difficult task when performing the FH conditioning is to compute the necessity degree of N(ψ) from the initial weighted knowledge base. With min-based and product-based possibilistic conditioning, the most difficult task concerns the computation of inconsistency degrees of a weighted knowledge base. These two tasks – computing the degree of necessity of ψ or computing the degree of inconsistency of a weighted knowledge base – have the same level of computational complexity. Both tasks need O(log₂(n)) calls to the propositional logic satisfiability test, where n is the number of different degrees in the weighted knowledge base Σ.

# 5. Possibilistic FH-conditioning under uncertain inputs

This section discusses the possibilistic counterpart of FH-conditioning when the new information is uncertain. We begin by briefly describing conditioning under uncertain information within the framework of probability and possibility theories, and then discuss the possibilistic extension of FH-conditioning under uncertain inputs.

## 5.1. Probabilistic Jeffrey's rule

Conditioning in the presence of uncertain information has been widely studied in probability theory from an axiomatic, semantic, syntactic and computational point of view (in particular with Bayesian networks and the notion of virtual evidence (e.g. [74]). This rule continues to attract an interest in various fields of research, with many works aiming to explore and extend it to broader settings. For example, it is analyzed in the context of interval or imprecise probabilities [54], as well as in the context of ordinal conditional functions (OCFs) for belief revision [75–77].

The rule known as Jeffrey's rule [53] remains one of the most widely used methods for revising probability distributions in the light of new, uncertain information. This rule is based on the principle of probability kinematics, which aims to impose a minimal change in the initial probability distribution when integrating new information. Jeffrey's rule thus provides a means of revising an initial probability distribution, denoted p, into a new revised probability distribution, denoted p(.|Ψ), given an input with probabilities over a set of mutually exclusive and exhaustive events Ψ. In the context of this paper, we continue to represent information in terms of propositional logic formulas. In this case, p is defined over the set of propositional logic interpretations Ω. When there is no ambiguity, we simply write P(φ) instead of P([φ]) (where [φ] is a set of models of φ). The input Ψ = {⟨ψᵢ, βᵢ⟩} is composed of weighted formulas such that the formulas ψᵢ constitute a partition of the set of interpretations Ω. More precisely, for any (ψᵢ, βᵢ) and (ψⱼ, βⱼ) in Ψ, ψᵢ ∧ ψⱼ is inconsistent and ⋀(ψᵢ, βᵢ)∈Ψ ψᵢ is a tautology. The βᵢ are the new probability degrees of the ψᵢ after revision of p; of course they must sum to 1. We also assume that the initial probabilities of each ψⱼ are somewhat probable (i.e. ∀⟨ψⱼ, αⱼ⟩ ∈ Ψ, P(ψⱼ) > 0) where we avoid conditioning on impossible events.

Two principles are used to concretely define the Jeffrey's rule for revising the initial probability distribution p given the input Ψ. The first principle (known as the success principle) interprets each element (ψᵢ, βᵢ) as a constraint that the revised probability distribution must satisfy. More specifically, this principle requires that:

$$ \forall (\psi_i, \beta_i) \in \Psi, \quad P(\psi_i|\Psi) = \beta_i \qquad (11) $$

This first principle clearly gives to Jeffrey's rule the status of a revision operator (or priority merge operator), since the input has priority over the initial probability distribution.

The second principle (known as the principle of probabilistic kinematics) reflects the idea of minimal change in revision, and states that the revised probability distribution p' must not alter the conditional probability degrees of any event φ given the uncertain events Ψ. More specifically, let us denote p' = p(.|Ψ) the result of revising (or conditioning) p by Ψ. Then this second principle imposes the following constraint:

$$ \forall \phi_i, \forall (\psi_j, \beta_j) \in \Psi, P(\phi_i|\psi_j) = P'(\phi_i|\psi_j), \qquad (12) $$

where φᵢ is a propositional logic formula. The two principles (or constraints) described above induce one and only one way of revising a probability distribution p by the uncertain information given by Ψ. Let ω be a given interpretation from Ω. Let (ψᵢ, βᵢ) be an element of Ψ such that ω is a model of ψᵢ. Then, the new degree of probability of ω after taking into account the new information Ψ is defined by:

$$ p(\omega|\Psi) = \beta_i * p(\omega|\psi_i) \qquad (13) $$

Also, for any propositional logic formula φ, we have:

$$ P(\phi|\Psi) = \sum_{(\psi_i, \beta_i) \in \Psi} \beta_i * \frac{P(\phi \wedge \psi_i)}{P(\psi_i)}. \qquad (14) $$

**Example 6.** This example presents the initial and revised probability distributions p(ω) and p'(ω) over the set of interpretations Ω (see Table 6). The revised distribution p'(ω) is based on the new uncertain information Ψ, where Ψ = {(p, 0, 85), (¬p, 0.15)}. This
can be done applying Jeffrey's rule given that the uncertainty is bearing on an exhaustive and mutually exclusive set of events $\Psi$ (see Equation (13)). The obtained probability distribution $p'(\omega)$ is given in Table 6: We can easily verify that for all $(\psi_i, \beta_i) \in \Psi$,

<caption>Table 6</caption>

The probability distributions $p(\omega)$ and $p'(\omega)$.

<table><thead><tr><th>p</th><th>q</th><th>r</th><th>p'(ω)</th><th>p'(ω)</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1</td><td>0.05</td><td>0.10</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0.10</td><td>0.21</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0.12</td><td>0.25</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0.14</td><td>0.30</td></tr><tr><td>0</td><td>1</td><td>1</td><td>0.06</td><td>0.01</td></tr><tr><td>0</td><td>1</td><td>0</td><td>0.08</td><td>0.02</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0.16</td><td>0.03</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0.39</td><td>0.08</td></tr></tbody></table>

$P(\psi_i|\Psi) = \beta_i$. Moreover, for any propositional logic formula $\phi$ and for all $(\psi_j, \beta_j) \in \Psi$, it holds that $P(\phi|\psi_j) = P'(\phi|\psi_j)$.

## 5.2. Min-based and product-based possibilistic counterparts of Jeffrey's rule

Conditioning in the presence of uncertain information has also been studied within the framework of possibility theory. In particular, the counterparts of Jeffrey's rule have been defined for the two forms of standard possibilistic conditioning, i.e. min-based and product-based conditioning given in equations (2) and (3) respectively [78,94].

Let $\pi$ be a distribution and $\Psi = \{(\psi_i, \beta_i)\}$ the input that must be taken into account to revise $\pi'$. We always assume that the formulas $\psi_i$ induce a partition of $\Omega$. The elements $\beta_i$ represent the new possibility degrees for the $\psi_i$ values after revising the possibility distribution $\pi$, with the normalization constraint that at least one element must have a maximum value of 1. We assume that the initial possibility degrees of each $\psi_j$ are somewhat possible (i.e. $\forall(\psi_j, \alpha_j) \in \Psi$, $\Pi(\psi_j) > 0$) where we again avoid possibilistic conditioning on impossible events.

Let us now briefly recall the two definitions of the counterpart of Jeffrey's rule within the framework of possibility theory:

1. Possibilistic counterpart of Jeffrey's rule with product-based conditioning (denoted by $|_{\ast u}$): this counterpart gives a result similar to that of Jeffrey's probabilistic rule, except that marginalization in possibility theory uses the maximum operator instead of the sum. This gives (where $|_{\ast}$ is the standard product-based possibilistic conditioning given in Equation (3)):

$$ \begin{aligned} \Pi(\phi|_{\ast u} \Psi) &= \max_{(\psi_i, \beta_i) \in \Psi} \beta_i * \Pi(\phi|_{\ast} \psi_i) \\ &= \max_{(\psi_i, \beta_i) \in \Psi} \beta_i * \frac{\Pi(\phi \wedge \psi_i)}{\Pi(\psi_i)} \end{aligned} $$

2. Possibilistic counterpart of Jeffrey's rule with min-based conditioning (denoted by $|_{mu}$): this counterpart gives a more qualitative definition, where the order of the degrees of possibility is used instead of the exact numerical values of the degrees of possibility. In this counterpart, the operators $*$ (product) and $\Sigma$ (sum) are respectively replaced by the operators min (the minimum for combining the initial degrees of possibility with those in $\Psi$) and max (the maximum operator is used again for marginalization). This leads to (where $|_m$ is the standard min-based possibilistic conditioning given in Equation (2)):

$$ \Pi(\phi|_{mu} \Psi) = \max_{(\psi_i, \beta_i) \in \Psi} \min(\beta_i, \Pi(\phi|_m \psi_i)) \quad (15) $$

## 5.3. On the definition of FH-conditioning under uncertain input

This section now presents a definition of FH-conditioning under uncertain information using counterpart of Jeffrey rule in the framework of possibility theory. Generally speaking, conditioning under uncertain information $\Psi = \{(\psi_i, \beta_i)\}$ can be seen as a three-step process.

The first step consists in applying standard conditioning to each of the $(\psi_i, \beta_i)$ formulas in parallel. The parallel application is explained in particular by the nature of the input, where the formulas $\psi$ induce a partition of the ensemble of interpretations $\Omega$. As a result, modifications to the degrees of possibility (or probabilities) can be made independently within each formula $\psi_i$ of $\Psi$. At the end of this step, we have a normalized possibility distribution per formulas of input $\Psi = \{(\psi_i, \beta_i) : i = 1, \dots, u\}$.

The second step consists in integrating the $\beta_i$ weights of the $\psi_i$ formulas of input $\Psi$. In possibility theory, the product operator or the minimum operator are two candidates to integrate the weight of the input. Using the product operator preserves the order within each set of models of the $\psi_i$ formulas of the input. This is in the spirit of probabilistic kinematics, but also in the spirit of Darwiche and Pearl's postulates for iterated revision [56]. Using the minimum operator implies lowering the degree of possibility for all interpretations that exceed $\beta_i$ down to $\beta_i$, while keeping the degrees for other interpretations unchanged. In this paper, we opt
for the product operator as it does not alter the order between models of $\psi_i$. At the end of this second step, only distributions whose weight $\beta_i$ is equal to 1 are normalized.

The last step consists in aggregating the possibility distributions obtained during the previous step with the operator maximum. This allows to put all the possibility degrees together without changing the new degrees of each $\psi_i$ model of the input.

These three main steps, used to extend the FH-conditioning with an uncertain input $\Psi$, are precisely defined in the following. Let $\pi$ be a possibility distribution and $\Psi = \{(\psi_i, \beta_i) : i = 1, ..., u\}$ be the uncertain input. We denote by $\pi(\cdot|_{FHu}\Psi)$ the possibility distribution obtained after applying FH-conditioning of $\pi$ under the uncertain input $\Psi$. This conditioned possibility distribution is defined as follows:

* **Step 1:** For each uncertain element $(\psi_i, \beta_i)$ of $\Psi$ apply FH-conditioning of $\pi$ under $\psi_i$. The resulted possibility distributions are simply denoted by $\pi_{|\psi_i}$:

$$ \pi_{|\psi_i} = \pi(\cdot|_{FH}\psi_i). \qquad (16) $$

* **Step 2:** For each $\pi_{|\psi_i}$, the possibility distribution obtained in Step 1, apply a discount of $\beta_i$ where $\beta_i$ is the weight associated with the $\psi_i$ formula of the $\Psi$ input. The resulted possibility distributions of this second step are denoted by $\pi_{|(\psi_i, \beta_i)}$:

$$ \pi_{|(\psi_i, \beta_i)} = \beta_i * \pi_{|\psi_i}. \qquad (17) $$

* **Step 3:** This third and final step simply aggregates the different possibility distributions obtained in step 2 using the maximum aggregation operator. The result of this step is the possibility distribution, previously noted as $\pi(\cdot|_{FHu})$, which corresponds to the final result of the FH-conditioning of $\pi$ by $\Psi$:

$$ \pi(\cdot|_{FHu}\Psi) = \max_{(\psi_i, \beta_i) \in \Psi} \pi_{|(\psi_i, \beta_i)} \qquad (18) $$

We can easily verify that for any $(\psi_i, \beta_i)$ element of $\Psi$, we have:

$$ \pi(\psi|_{FHu}\Psi) = \beta_i $$

Note now that since $\psi_i$ are disjoint (and constitute a partition of $\Omega$) then if for any $j$ we have $N(\psi_j) > 0$ then the degrees of necessity of the other $\Psi$ formulas are equal to zero; i.e. $\forall k \neq j N(\psi_k) = 0$. In this case, the possibility degree associated with each model in $\psi_k$ is equal to its degree $\beta_k$ given in the input $\Psi$. This means that the order between models in the initial possibility distribution is not necessarily preserved. For the element $(\psi_j, \beta_j)$ where $N(\psi) > 0$, the order between the models of $\psi_j$ is preserved after conditioning. In other words, for all interpretations $\omega$ and $\omega'$ if $\omega \models \psi$ and $\omega' \models \psi$, then $\pi(\omega) > \pi(\omega')$ implies $\pi(\omega|\Psi) > \pi(\omega'|\Psi)$.

Based on these observations and the three-step decomposition of the definition of FH-conditioning under uncertain input, it is now possible to give the syntactic counterpart of FH-conditioning under uncertain information.

Let $\Sigma = \{(\phi_i, \alpha_i) : i = 1...n\}$ be a possibilistic knowledge base. Let $\pi_{\Sigma}$ be its associated possibility distribution given by Equation (1). We still denote $\Psi = \{(\psi_i, \beta_i) : i = 1...u\}$ the uncertain input, with $\beta_i$ representing, as we have defined it up to now, the new possibility degrees, and not the necessity degrees as in $\Sigma$, associated with $\psi_i$. We start by giving the syntactic counterparts of steps 1 and 2. An important element in the definition of FH-conditioning given in Equation (5) is the initial degree of necessity of the new information. Not surprisingly, in the syntactic characterizations below, we distinguish between cases where this degree of necessity is zero and those where it is non-zero.

* **Syntactic counterpart to step 1.** As a reminder, this step consists in applying the standard FH-conditioning to each of the input's $\psi_j$ formulas, which we noted as $\pi_{|\psi_j}$. We distinguish two cases to compute the syntactic counterpart of each $\pi_{|\psi_j}$, denoted by $\Sigma_{|\psi_j}$:

- Case $N(\psi_j) = 0$. In this case, applying Equation (5) the possibility distribution $\pi_{|\psi_j}$ simplifies to:

$$ \forall \omega \in \Omega, \quad \pi_{|\psi_j}(\omega) = \begin{cases} 1 & \text{if } \omega \models \psi_j \\ 0 & \text{otherwise (namely, if } \omega \nvDash \psi_j \end{cases} $$

In this case, its associated possibilistic knowledge base is simply composed of the following single formula:

$$ \Sigma_{|\psi_j} = \{(\psi_j, 1)\} \qquad (19) $$

- Case $N(\psi_j) > 0$. We will use in the following the index $c$ instead of $j$ for this case. The possibilistic knowledge base $\Sigma_{|\psi_c}$ is simply the one given in Equation (10), namely:

$$ \Sigma_{|\psi_c} = \{(\psi_c, 1)\} \cup \{(\phi_i, \min(\alpha_i, 1 - \frac{1-\alpha_i}{1-\alpha_i + N(\psi_c)})), (\phi_i, \alpha_i) \in \Sigma\} \qquad (20) $$

**Example 7.** Let us consider the same possibilistic belief base from Example 1, given by:

$$ \Sigma = \{(p \lor \neg r, 0.91), (p \lor q, 0.35), (\neg p \lor \neg r, 0.69), (\neg p \lor r, 0.23), (q \lor \neg r, 0.82)\}. $$

Table 7 presents the possibility distribution associated with $\Sigma$, denoted by $\pi_{\Sigma}(\omega)$, computed using Equation (1). Let's consider the
<caption>**Table 7**</caption>

The possibility distribution associated with $\Sigma$, along with the conditioned possibility distributions $\pi_{|\psi_1}$ and $\pi_{|\psi_2}$ where $\psi_1 = p$ and $\psi_2 = \neg p$.

<table><thead><tr><th>p</th><th>q</th><th>r</th><th>π<sub>Σ</sub>(ω)</th><th>π<sub>|ψ<sub>1</sub></sub></th><th>π<sub>|ψ<sub>2</sub></sub></th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1</td><td>0.31</td><td>1</td><td>0</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0.77</td><td>1</td><td>0</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0.18</td><td>1</td><td>0</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0.77</td><td>1</td><td>0</td></tr><tr><td>0</td><td>1</td><td>1</td><td>0.09</td><td>0</td><td>0.281</td></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0.09</td><td>0</td><td>0.281</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0.65</td><td>0</td><td>0.738</td></tr></tbody></table>

new uncertain information $\Psi = \{(p, 0.20), (\neg p, 1)\}$, where $\psi_1 = p$ and $\psi_2 = \neg p$. The table also shows the conditioned possibility distributions $\pi_{|\psi_1}$ and $\pi_{|\psi_2}$, calculated using Equation (5).

Let's compute the knowledge bases associated with $\psi_1$ and $\psi_2$ denoted by $\Sigma_{|\psi_1}$ and $\Sigma_{|\psi_2}$:

- For $\psi_1 = p$, the necessity measure $N(\psi_1) = 0$. This implies that the knowledge base $\Sigma_{|\psi_1} = \{(p, 1)\}$ using Equation (19).

- For $\psi_2 = \neg p$, the necessity measure is $N(\psi_2) = 0.23 > 0$. This implies that the knowledge base $\Sigma_{|\psi_2}$ is constructed as follows using Equation (20):

$$ \Sigma_{|\psi_2} = \{(\neg p, 1)\} \cup \{(p \lor \neg r, 0.719), (p \lor q, 0.262), (\neg p \lor \neg r, 0.426), \\ (\neg p \lor r, 0.23), (q \lor \neg r, 0.561)\} $$

We can easily check that the possibility distribution associated with $\Sigma_{|\psi_1}$ and $\Sigma_{|\psi_2}$ respectively corresponds exactly to $\pi_{|\psi_1}$ and $\pi_{|\psi_2}$ as shown in Table 7.

* **Syntactic counterpart to step 2.** We recall that in this step, the possibility distributions $\pi_{|\psi_j}$ are multiplied by their associated degrees $\beta_j$ in $\Psi$, resulting in possibility distributions denoted $\pi_{|(\psi_j, \beta_j)}$. We distinguish again two cases to compute the syntactic counterpart of each $\pi_{|(\psi_j, \beta_j)}$, denoted by $\Sigma_{|(\psi_j, \beta_j)}$:

- Case $N(\psi_j) = 0$, the possibility distribution $\pi_{|(\psi_j, \beta_j)}$ is sub-normalised (except when $\beta_j = 1$) and equals to:

$$ \forall \omega \in \Omega, \quad \pi_{|(\psi_j, \beta_j)}(\omega) = \begin{cases} \beta_j, & \text{if } \omega \nvDash \psi_j \\ 0, & \text{if } \omega \nvDash \psi_j \end{cases} $$

Since the possibility distribution $\pi_{|(\psi_j, \beta_j)}$ is sub-normalized (except for $\beta_j$'s which are equal to 1), it will be represented by the following incoherent knowledge base:

$$ \Sigma_{|(\psi_j, \beta_j)} = \{(\psi_j, 1), (\perp, 1 - \beta_j)\} \qquad (21) $$

Indeed, we can easily check that if $\omega$ falsifies $\psi_j$ then its degree of possibility equals 0, since the weight of $\psi_j$ in the above possibilistic knowledge base $\Sigma_{|\psi_j}$ is equal to 1. For other interpretations that are models of $\psi_j$, they automatically falsify the contradictory formula $(\perp, 1 - \beta_j)$ and hence they will have a possibility degree equal to $1 - (1 - \beta_j)$, i.e. $\beta_j$.

- Case $N(\psi_j) > 0$. We will use again and in the following the index $c$ instead of $j$ for this case. The possibility distribution $\pi_{|(\psi_c, \beta_c)}$ is also sub-normalised (except when $\beta_c = 1$). Thus in the knowledge base associated with $\pi_{|(\psi_c, \beta_c)}$, the formula $(\perp, 1 - \beta_c)$ will be added, reflecting the fact that the distribution is sub-normalized. To reflect that the degrees of the possibilities of $\pi_{|\psi_c}$ have been multiplied by $\beta_c$ we need to modify the weights $\alpha_c$ of the possibilistic knowledge base by $(1 - ((1 - \alpha_c) * \beta_c))$. More precisely:

$$ \Sigma_{|(\psi_c, \beta_c)} = \{(\perp, 1 - \beta_c)\} \cup \{(\phi_i, 1 - ((1 - \alpha_i) * \beta_c) : (\phi_i, \alpha_i) \in \Sigma_{|\psi_c}\} \qquad (22) $$

where $\Sigma_{|\psi_c}$ is given by Equation (20).

Let us first recall the notations: $\pi_{|\psi_c}$ is the possibility distribution resulting from the application of FH-conditioning with certain observation $\psi_c$ (where $N(\psi_c) > 0$), $\Sigma_{|\psi_c}$ is its compact representation, and $\pi_{|(\psi_c, \beta_c)}$ is the result of multiplying $\pi_{|\psi_c}$ by $\beta_c$.

Let us now show that $\Sigma_{|(\psi_c, \beta_c)}$ is indeed the compact representation of $\pi_{|(\psi_c, \beta_c)}$. Note first that the weight associated with the contradictory formula $(\perp, 1 - \beta_c)$ is smaller than the weight of any non-contradictory formula $(\phi_i, 1 - ((1 - \alpha_i) * \beta_c)i$, since trivially we have $(1 - ((1 - \alpha_i) * \beta_c) \ge 1 - \beta_c$.

Let $\omega$ be an interpretation. If $\omega$ satisfies all non-contradictory formulas $\phi_i$ then $\pi_{|\psi_c}(\omega)$. As trivially $\omega$ falsifies $(\perp, 1 - \beta_c)$ we then have $\pi_{|(\psi_c, \beta_c)}(\omega) = \beta_c$. So $\pi_{\Sigma_{|(\psi_c, \beta_c)}}(\omega) = \beta_c * \pi_{|\psi_c}(\omega)$ as expected.
<caption>**Table 8**</caption>

The possibility distributions $\pi_{|(\psi_1, \beta_1)}$ and $\pi_{|(\psi_2, \beta_2)}$, where $\psi_1 = p$ and $\psi_2 = \neg p$.

<table><thead><tr><th>p</th><th>q</th><th>r</th><th>π<sub>|(ψ₁,β₁)</sub></th><th>π<sub>|(ψ₂,β₂)</sub></th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1</td><td>0.20</td><td>0</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0.20</td><td>0</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0.20</td><td>0</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0.20</td><td>0</td></tr><tr><td>0</td><td>1</td><td>1</td><td>0</td><td>0.281</td></tr><tr><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0</td><td>0.281</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0.738</td></tr></tbody></table>

Let's now consider the case where $\omega$ falsifies at least one non-contradictory formula $\phi_i$. In this case,

$$ 
\begin{aligned}
\pi_{\Sigma_{|(\psi_1, \beta_1)}} &= 1 - \max\{1 - (1 - \alpha_i) * \beta_c : \omega \not\models \phi_i\} \\
&= \min\{1 - (1 - (1 - \alpha_i) * \beta_c) : \omega \not\models \phi_i\} \\
&= \min\{(1 - \alpha_i) * \beta_c : \omega \not\models \phi_i\} \\
&= \beta_c * \min\{(1 - \alpha_i) : \omega \not\models \phi_i\} \\
&= \beta_c * \pi_{|\psi_c}(\omega)
\end{aligned}
$$

**Example 8.** Let's continue the example by integrating the weights of the two formulas, $\psi_1$ and $\psi_2$, namely, $\beta_1 = 0.20$ and $\beta_2 = 1$, into the possibility distributions $\pi_{|\psi_1}$ and $\pi_{|\psi_2}$ using Equation (17). Table 8 presents the result of integrating the weights of $\psi_1$ and $\psi_2$, denoted by $\pi_{|(\psi_1, \beta_1)}$ and $\pi_{|(\psi_2, \beta_2)}$, respectively.

Now let's compute the two knowledge bases $\Sigma_{|(\psi_1, \beta_1)}$ and $\Sigma_{|(\psi_2, \beta_2)}$:

- Since the necessity measure $N(\psi_1) = 0$, then the knowledge base $\Sigma_{|(\psi_1, \beta_1)} = \{(p, 1), (\bot, 0.80)\}$, using Equation (21).

- Since the necessity measure $N(\psi_2) = 0.23 > 0$. This implies that the knowledge base $\Sigma_{|(\psi_2, \beta_2)}$ is calculated as follows using Equation (22):

$$ 
\Sigma_{|(\psi_2, \beta_2)} = \{(\neg p, 1)\} \cup \{(p \lor \neg r, 0.719), (p \lor q, 0.262), (\neg p \lor \neg r, 0.426), \\ (\neg p \lor r, 0.23), (q \lor \neg r, 0.561)\}
$$

We can check that the possibility distribution associated with $\Sigma_{|(\psi_1, \beta_1)}$ and $\Sigma_{|(\psi_2, \beta_2)}$ respectively corresponds exactly to $\pi_{|(\psi_1, \beta_1)}$ and $\pi_{|(\psi_2, \beta_2)}$.

* **Syntactic counterpart to step 3.** We recall that at the end of this last step we obtain the result of FH-conditioning under uncertain information $\Psi$. This step consists in aggregating the possibility distributions $\pi_{|(\psi_j, \beta_j)}$ with the maximum operator.

We introduce some notations and reformulations to facilitate the expression of the syntactic counterpart of the maximum operator used for aggregating the possibility distributions of $\pi_{|(\psi_j, \beta_j)}$. Let $\Psi = \{(\psi_j, \beta_j) : j = 1, ..., u\}$ be the uncertain input. Recall first that there is at most one element, which we denote $(\psi_c, \beta_c)$, such that $N(\psi_c) > 0$. Let $\Psi' = \Psi - \{(\psi_c, \beta_c)\}$ be the set of all elements $(\psi_j, \beta_j)$ such that $N(\psi_j) = 0$. Let's now consider the $\Psi'$ partition induced by the $\beta_j$'s weights of $\Psi'$. More precisely, let $\Psi' = (\Psi'_1, \Psi'_2, ..., \Psi'_y)$ be the partition of $\Psi'$, which means that $\Psi' = \Psi'_1 \cup \Psi'_2 \cup ... \Psi'_y$ and that $\forall j, k = 1, ..., y, \Psi'_j \cap \Psi'_k = \emptyset$ if $(j \neq k)$. This partition is such that the elements of $\Psi'_k = \{(\psi_{ik}, \beta_k) : i = 1, ..., y_k\}$ all have the same $\beta_k$ weight. Then, any element $(\psi_{ik}, \beta_k)$ of $\Psi'_k$ is of strictly greater weight than any element $(\psi_{jl}, \beta_l)$ of $\Psi'_l$ as soon as $k < l$. In particular, elements of $\Psi'_l$ have the highest weight (possibly 1) and elements of $\Psi'_y$ have the lowest weight (possibly 0). These re-writings and notations make it possible to describe more easily the distribution $\pi_{|(\psi_c, \beta_c)}$, which represents the results of aggregation with the maximum operator of the distributions $\pi_{|(\psi_k, \beta_k)}$ where $(\psi_k, \beta_k) \in \Psi'$. Indeed, we can easily check that:

$$ \forall \omega \in \Omega, \quad \pi_{\psi'}(\omega) = \max_{(\psi_k, \beta_k) \in \Psi'} \pi_{(\psi_k, \beta_k)}(\omega) $$

is equal to

$$ \forall \omega \in \Omega, \quad \pi_{|\psi'}(\omega) = \begin{cases} 0, & \forall k = 1, \dots, y, \forall (\psi_{ki}, \beta_{ki}) \in \Psi'_k, \omega \not\models \psi_{ki} \\ \beta_k, & \text{if } \exists \psi_{ki} \in \Psi'_k \text{ such that } \omega \nvDash \psi_{ki} \end{cases} \qquad (23) $$

It is now possible to give the possibilistic knowledge base, denoted $\Sigma_{|\psi'}$, which is the syntactic counterpart of the possibility distribution $\pi_{|\psi'}$. This possibilistic knowledge base is obtained by iteratively taking dis-junctions from $\Psi'_k$. Let us introduce
<table><caption>**Table 9**
The possibility distribution $\pi_{|\Psi'}$, where $\Psi' = \{(p, 0.20)\}$.</caption><thead><tr><th>p</th><th>q</th><th>r</th><th>π<sub>|Ψ'</sub></th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1</td><td>0.20</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0.20</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0.20</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0.20</td></tr><tr><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>

the following notation: if $A = \{(\psi_i, \beta_i) : 1, ..., m\}$ is a set of weighted formulas, then we simply denote $\bigvee A = \bigvee_{(\psi_i, \beta_i) \in A} \psi_i$ the dis-junction of its formulas. Then we have:

$$ \Sigma_{|\Psi'} = \{(\bigvee \Psi'_1 \cup \dots \cup \Psi'_y, 1), \\ (\bigvee \Psi'_1 \cup \dots \cup \Psi'_{y-1}, 1 - \beta_y), \\ (\bigvee \Psi'_1 \cup \dots \cup \Psi'_{y-2}, 1 - \beta_{y-1}), \\ \dots \\ (\bigvee \Psi'_1 \cup \Psi'_2, 1 - \beta_3), \\ (\bigvee \Psi'_1, 1 - \beta_2), \\ (\bot, 1 - \beta_1)\} \tag{24} $$

The weighted formulas of this possibilistic knowledge base $\Sigma_{|\Psi'}$ are presented in the order of their weights, from the highest ($\bigvee \Psi'_1 \cup \dots \cup \Psi'_y, 1$) to lowest priority formula ($\bot, 1 - \beta_1$). Thus, to check that the possibility distribution associated with $\Sigma_{|\Psi'}$ is exactly the same as that of $\pi_{|\Psi'}$, we can simply calculate the degrees of possibility of the interpretations, starting with the counter-models of the highest-priority formulas of $\Sigma_{|\Psi'}$ and ending with the counter-models of the lowest-priority formulas. In fact, the counter-models of ($\bigvee \Psi'_1 \cup \dots \cup \Psi'_y, 1$) have the degree of possibility 0. These counter-models correspond exactly to interpretations that are not models of any formula of $\Psi'$ (as indicated in the definition of $\pi_{|\Psi'}$). Then, the least plausible interpretations (of degree $\beta_k$) are exactly the counter-models of ($\bigvee \Psi'_1 \cup \dots \cup \Psi'_{y-1}, 1 - \beta_y$) or, said differently, the models of $\Psi'_y$. Proceeding progressively in this way, we end with the most plausible models, which have degree $\beta_1$ (because they need to falsify the least important formula ($\bot, 1 - \beta_1$)) and which are models of $\Psi'_1$ (the remaining set of interpretations).

**Example 9.** Recall that $\Psi = \{(p, 0.20), (\neg p, 1)\}$, with necessity degrees $N(p) = 0$ and $N(\neg p) = 0.23$. This implies that $\Psi' = \{(p, 0.20)\}$ since the $\Psi'$ contains only formulas with necessity degrees equal to 0. Using Equation (23), we can calculate the possibility distribution related to $\Psi'$, denoted by $\pi_{|\Psi'}$ as presented Table 9.

Now, the last step consists in giving the syntactic counterpart of the aggregation, with the maximum operator, of the possibility distribution $\pi_{|\Psi'}$ with that associated with $\pi_{|(\psi_c, \beta_c)}$. Recall that $\Psi = \Psi' \cup \{(\psi_c, \beta_c)\}$ and that $\{(\psi_c, \beta_c)\}$ is such that $N(\psi_c) > 0$. Recall also that the knowledge base $\Sigma_{|\Psi'}$ associated with $\pi_{|\Psi'}$ is given in Equation (24). Similarly, the knowledge base $\Sigma_{|(\psi_c, \beta_c)}$ associated with $\pi_{|(\psi_c, \beta_c)}$ is given by Equation (22). Following the characteristics given by [32]. The possibilistic knowledge base associated with:

$$ \pi_{|\Psi} = \max(\pi_{|\Psi'}, \pi_{|(\psi_c, \beta_c)}) \tag{25} $$

is

$$ \Sigma_{\Psi} = \{(\phi_i \vee \psi_j, \min(\alpha_i, \beta_j)) : (\psi_j, \beta_j) \in \Sigma_{|\Psi'} \text{ and } (\phi_i, \alpha_i) \in \Sigma_{|(\psi_c, \beta_c)}\} \tag{26} $$

**Example 10.** Now let's compute the final possibility distribution $\pi_{|\Psi}$ with the integration of the new piece of uncertain information $\Psi = \{(p, 0.20), (\neg p, 1)\}$ using Equation (25). The result is presented in Table 10.

Now let's compute the knowledge base associated to $\Psi$, namely $\Sigma_{\Psi}$ using Equation (26):

$$ \Sigma_{|\Psi} = \{(p \vee \neg p, 1), (p \vee (p \vee \neg r), 0.719), (p \vee (p \vee q), 0.262), (p \vee (\neg p \vee \neg r), 0.426), \\ (p \vee (\neg p \vee r), 0.23), (p \vee (q \vee \neg r), 0.561), (\bot \vee \neg p, 0.80), (\bot \vee p \vee \neg r, 0.719), \\ (\bot \vee p \vee q, 0.262), (\bot \vee \neg p \vee \neg r, 0.426), (\bot \vee \neg p \vee r, 0.23), (\bot \vee q \vee \neg r, 0.561)\}. $$
<table><caption>**Table 10**
The possibility distribution $\pi_{|\Psi}$.</caption><thead><tr><th>p</th><th>q</th><th>r</th><th>π<sub>|Ψ</sub></th><th>π<sub>|(Ψ<sub>c</sub>, β<sub>c</sub>)</sub></th><th>π<sub>|Ψ</sub></th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1</td><td>0.20</td><td>0</td><td>0.20</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0.20</td><td>0</td><td>0.20</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0.20</td><td>0</td><td>0.20</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0.20</td><td>0</td><td>0.20</td></tr><tr><td>0</td><td>1</td><td>1</td><td>0</td><td>0.281</td><td>0.281</td></tr><tr><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0</td><td>0.281</td><td>0.281</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0.738</td><td>0.738</td></tr></tbody></table>

$$ \equiv \{(p \lor \neg r, 0.719), (p \lor q, 0.262), (\neg p, 0.80)\}. $$

Finally, we can check that computing the possibility distribution $\pi_{\Sigma|\Psi}$ associated with the belief base $\Sigma|\Psi$, using Equation (1), results in the exact same distribution as the one provided in Table 10. This confirms that $\pi_{|\Psi} = \pi_{\Sigma|\Psi}$.

The computational and spatial complexity of calculating the counterpart of FH-conditioning under uncertain information depends not only on the size of the initial knowledge base $\Sigma$ but also on the size of the input $\Psi$. The most costly step is to check whether $N(\psi_j) > 0$ for each $(\psi_j, \beta_j)$ of $\Psi$. This step requires $|\Psi|$ (the size of $\Psi$) of satisfiability tests in propositional logic. Now, for the formula $\psi_c$ such that $N(\psi_c) > 0$, we also need to determine the exact value of this necessity degree $N(\psi_c)$. This step requires performing $\log_2(|\Sigma|)$ propositional logic satisfiability tests. Finally, all other computational operations are done in $O(1)$.

To sum up, in terms of computational complexity, the computation of the syntactic counterpart of FH-conditioning with uncertain input requires performing $|\Psi| + \log_2(|\Sigma|)$ propositional logic satisfiability tests.

For spatial complexity, the size of $\Sigma|\Psi'$ is equal to the size of $|\Psi'|$. The final base $\Sigma|\Psi'$, associated with FH-conditioning under uncertain input, is of size $|\Psi'| * |\Sigma|$ in the worst case.

# 6. Discussions

This section first examines whether FH-conditioning corresponds to a belief revision operator or an update operator. It then explores the feasibility of extending the syntactic computations of FH-conditioning to the framework of belief functions, conditional knowledge bases, and the updating process. In the following, depending on the context, we will use either the framework of propositional logic to represent the new information (which we will denote by $\psi$, as we have done so far in the paper) or the set-theoretic framework, working directly with the models of the new information, which we represent as subsets of $\Omega$ and denote simply by the first capital letters of the alphabet, $A, B$, etc.

## 6.1. Discussions on whether FH-conditioning is a belief revision operator or an update operator

If we refer to the original paper by Fagin and Halpern [24], two arguments support the view that FH-conditioning should be regarded as close to a belief revision operator rather than an update operator. Before detailing these arguments, let us briefly recall the distinction between belief revision and belief update. Belief revision is the process by which an agent modifies her beliefs about a static world in light of new observations considered fully certain. The reference work on this topic is [10], which introduced the so-called AGM postulates in the context of propositional logic. Belief update, in contrast, is the process by which an agent modifies her beliefs about an evolving world. This notion of update was formalized in [11] (see also [12]). In the framework of uncertainty theory, standard or Bayesian conditioning is often associated with a revision operator, whereas update is typically represented, as an example of an updating operator, by Lewis's imaging [13]. See also [19] for recent work on the relationship between the probability or possibility of conditionals and conditional probabilities or possibilities, which encompasses both classical conditioning and Lewis's imaging. Now, the following two arguments supporting the interpretation of FH-conditioning as a revision operator (and also what is called focusing in [16]) rather than an update operator rely on the use of standard conditioning as a basis for improving or defining FH-conditioning:

* The first argument is that in the original paper by Fagin and Halpern [24], there are more references to improving the standard conditioning in belief functions, known as Dempster's conditioning [14], where new information is interpreted as more a refinement of prior beliefs, hence as a revision operation. There is no reference to Lewis's imaging nor to the notion of action or intervention that would suggest an evolving world. This same observation is found in the work [31], which obtained the same definition of FH-conditioning but starting from fuzzy measures, which are functions from $2^\Omega$ to $[0, 1]$ that satisfy monotonicity and normalization conditions. In their work [31], the proposed conditioning does not refer to the notion of action or an evolving model, nor to the work on Imaging by Lewis. Therefore, it can be concluded from the work in [31] that FH-conditioning does not correspond to an updating operator. However, when this fuzzy measure framework is instantiated in the context of functions, the authors in [31] raise the point that conditioning is designed to modify interpretations where the new information is true without worrying about other interpretations. In this sense, Dubois and Prade [16,17] consider that FH-conditioning corresponds more to an operator known as a focusing rule. The major difference between revision and focusing depends on what is done with the
new information. If the new information leads to changing the available knowledge, it is called revision. If the new information consists of only changing the reference point from which queries can be processed in the context where the new information is true, it is called focusing. Revision goes further than focusing because it is not only about applying knowledge, but also about incorporating new information to refine prior knowledge. As Kern-Isberner in [15] notes, although revision and focusing differ, in practice, both involve conditioning operators, which makes them difficult to distinguish, for example, within the framework of probability theory. An interesting future task would be to propose counterparts to the AGM postulates for the focusing operator in uncertain theory frameworks to clarify the distinction between focusing and revision. An example of a postulate that could be weakened is the one concerning the situation where revision and expansion coincide (expansion simply involves adding the new information, which is appropriate when the information is consistent or inferred from the prior belief base). In particular, when $N(\psi) > 0$ (where $\psi$ is new information), the postulates $\Pi_4^*$ (along with $\Pi_3^*$) given in [17], as counterparts of the AGM postulates in the framework of possibility theory, impose that belief revision coincides with belief expansion, defined in this case as follows:

$$ \pi_{\text{expansion}}(\omega|\psi) = \begin{cases} \pi(\omega) & \text{if } \omega \vdash \psi, \\ 0 & \text{otherwise.} \end{cases} $$

This postulate $\Pi_4^*$ is not always satisfied, as the degrees of the models of $\psi$ may be modified, as we pointed out in this paper. On the other hand, the postulate $\Pi_3^*$ is always satisfied by possibilistic FH-conditioning. This postulate indicates that the possibility distribution obtained through FH-conditioning is less specific than the distribution obtained by expansion. It is therefore interesting to explore how to weaken this postulate $\Pi_4^*$ in order to characterize revision under FH-conditioning and capture the essence of this form of revision or focusing.

* The second argument for viewing FH-conditioning as a revision operator rather than an update operator is that the definition of FH-conditioning proposed in [24] is initially based on interpreting mass functions in terms of a family of probability distributions. Subsequently, standard Bayesian conditioning, which serves as the belief revision mechanism in probability theory, is applied to each probability distribution. More precisely, let $m$ be a mass function defined from $2^\Omega$ to [0, 1] and satisfying the normalization condition:

$$ \sum_{A \subseteq \Omega} m(A) = 1. $$

Let Bel and Pl denote the corresponding belief and plausibility functions associated with $m$, defined as follows:

$$ \text{Bel}(A) = \sum_{B \subseteq A} m(B), \quad \forall A \subseteq \Omega. $$

$$ \text{Pl}(A) = \sum_{B \cap A \neq \emptyset} m(B), \quad \forall A \subseteq \Omega. $$

The mass function $m$ can be interpreted as a family of probability distributions, denoted by $\mathcal{F}(m)$, which are compatible with $m$. These are the probability distributions constrained by the lower and upper bounds given by Bel and Pl, respectively:

$$ \mathcal{F}(m) = \{ p \mid \forall A \subseteq \Omega, \text{ Bel}(A) \le P(A) \le \text{Pl}(A) \}. $$

In the definition of $\mathcal{F}(m)$, lowercase $p$ represents a probability distribution, while uppercase $P$ denotes the probability measure associated with $p$, defined as $P(A) = \sum_{\omega \in A} p(\omega)$ for all $A \subseteq \Omega$. It turns out that the belief function Bel can be characterized as the lower envelope of $\mathcal{F}(m)$ (e.g., [18]):

$$ \text{Bel}(A) = \inf \{ P(A) \mid p \in \mathcal{F}(m) \}, \quad \forall A \subseteq \Omega. $$

Fagin and Halpern [24] follow the same principle and define conditioning as applying the lower envelope to the set of conditional probabilities $P(\cdot | A)$, where $P \in \mathcal{F}(m)$. Naturally, as in standard conditional probability, this definition is valid when $\text{Bel}(A) > 0$. They then show that for any $B \subseteq \Omega$ and for any $A \subseteq \Omega$,

$$ \begin{aligned} \text{Bel}_{FH}(B | A) &= \inf \{ P(B | A) \mid p \in \mathcal{F}(m) \}, \\ &= \frac{\text{Bel}(A \cap B)}{\text{Bel}(A \cap B) + \text{Pl}(B \cap A)}. \end{aligned} $$

Since standard probabilistic conditioning is viewed as a revision operator, this suggests that FH-conditioning should rather be seen as a revision operator in the sense of an observation that refines the current state of a static model. However, in this case, conditioning applies to a family of probability distributions, whereas belief revision in the AGM sense [10] applies to a single belief set.

## 6.2. Discussions on the applicability of the syntactic computation of FH-conditioning to conditional knowledge bases, belief functions, and the updating operator

In this paper, we have assumed that the initial beliefs are encoded as weighted knowledge bases. An interesting question would be to explore how to apply FH-conditioning if the starting point is a conditional knowledge base composed of conditional assertions.
The first point to note is that the interpretation of conditionals is often qualitative (in general, there is no explicit weight associated with them), whereas the definition of FH-conditioning, as given by Equation (5), is clearly numerical and involves operators such as division or addition. This is one of the points where, in the paper, we have focused on studying FH-conditioning from weighted belief bases rather than from conditional bases. Nevertheless, there exist semantics of conditionals that allow implicit weights (or ranks) to be extracted for assertions. These weights, for example, represent the level of typicality or exceptionality of a conditional, particularly in the context of non-monotonic reasoning. More precisely, consider a conditional knowledge base $\Delta = \{\psi_i | \phi_i : i = 1, \dots, n\}$, where $\phi_i$ and $\psi_i$ are propositional formulas, and where each conditional assertion $\psi_i | \phi_i$ in $\Delta$ can be interpreted as a constraint on a possibility distribution $\pi$, imposing that $\Pi(\phi_i \wedge \psi_i) > \Pi(\phi_i \wedge \neg \psi_i)$.

This knowledge base $\Delta$ can represent either a single possibility distribution—obtained by selecting the least specific distribution that satisfies the constraints (which amounts to accepting the property known as rational monotonicity, as in [3])—or a family of possibility distributions, in which case it corresponds to the System P model [20]. In the first case, one way to apply FH-conditioning is to transform the conditional knowledge base into a weighted propositional base, using, for example, System Z [2], also known as the rational closure of $\Delta$, and then apply FH-conditioning to the weighted base. The second case is more challenging, particularly from a computational perspective, as it requires handling multiple possibility distributions simultaneously. An open question for future research is whether inference in System P [20], which is semantically characterized by a set of possibility distributions, can be extended to incorporate FH-conditioning while preserving computational properties, as it is done for weighted bases in this paper.

We now discuss the feasibility of extending the syntactic computations of FH-conditioning developed in this paper to the belief functions framework. When the focal elements $A_1, \dots, A_n$ (those with a strictly positive mass $m(A_i)$) of a mass function are nested ($A_1 \subseteq A_2 \subseteq \dots \subseteq A_n$), we refer to these as consonant belief functions. In this case, the consonant belief function allows for the generation of a possibility distribution $\pi$ from the mass function $m$, where $\Pi(A) = Pl(A)$ and $N(A) = Bel(A)$ for every $A \subseteq \Omega$. This means that the work developed in this paper applies to a fragment of Dempster-Shafer theory based on consonant belief functions. Now, generalizing the results of this paper to apply to any mass function remains a challenge, especially from a computational perspective. Indeed, possibilistic logic is simply an extension of propositional logic, allowing inference mechanisms and consistency checks to be performed without significant additional computational cost. However, moving from possibility theory to belief functions often introduces significant computational or space complexity. For example, in [30], a propositional logic encoding of belief functions was proposed. However, as the author points out, what is gained in terms of a logic-based representation of belief functions is lost in computational complexity. Other approaches require richer languages, based on the interpretation that the degree of belief can be viewed as a probability of provability. Various studies have encoded $Bel(A)$ as a probability on the necessity of $A$, with necessity operator here is being formalized in a some modal logic such as S5. The paper [26] provides a thorough review of research on logical representations — generally computationally expensive — of belief functions. There remains another framework where FH-conditioning can be practically applied to general belief functions. This is within a graphical framework for representing uncertain information, such as valuation-based systems (e.g. [27]), belief function networks (e.g. [28]) or credal networks (e.g. [29]) for working with imprecise probabilities. This first requires defining a notion of independence based on the definition of FH-conditioning, which would allow for the decomposition of a mass function to represent it compactly, as has been done in probabilistic Bayesian networks. A further step would be to investigate how such a decomposition could facilitate the propagation of beliefs, especially when the initial DAG structure is compiled into another graphical structure, such as junction trees, to ensure efficient inference. These two interesting directions will be the focus of future work.

Another future work would be to explore the feasibility of adapting the syntactic computations developed in this paper to account for other forms of belief change, in particular updating operators. In the context of belief revision in uncertainty theories, the definitions of conditioning rely solely on the initial uncertainty distribution and the new information. Therefore, the syntactic construction depends only on the initial knowledge base (encoding the uncertainty distribution) and the new information.

In the case of updating, as described for instance by Lewis' Imaging operator [13], the situation is different. We still have the initial uncertainty distribution and the new information, but also a function that determines the proximity between the interpretations conditioned by each piece of information or formula. It is this proximity function, which is not unique, that makes the task of a syntactic computation of the counterpart of the work in this paper for updating difficult. More specifically, Lewis' Imaging operator [13] possesses a proximity function (or a selection function) such that for each $\omega \in \Omega$, and any set $A \subseteq \Omega$, there exists a single interpretation, denoted in the following by $\omega_A$, in $A$, defined as the closest interpretation to $\omega$. In the case where $\omega \in A$, the closest element $\omega_A$ is simply $\omega$ itself.

In the probabilistic framework, this updating rule can be formally expressed as:

$$ \forall \omega' \in \Omega, \quad p_A(\omega') = \begin{cases} \sum_{\omega \in \Omega : \omega' = \omega_A} p(\omega), & \text{if } \omega' \in A, \\ 0, & \text{if } \omega' \notin A. \end{cases} \qquad (27) $$

It is not difficult to see that the probability distribution $p_A$ is normalized, as the initial belief degrees of interpretations that do not belong to $A$ are simply transferred to the interpretations within $A$. Moreover, depending on the proximity function used between interpretations, it is possible that for an interpretation $\omega$ in $A$, we have $p(\omega) = 0$ but $p_A(\omega) > 0$. This supports the idea that Lewis's imaging is more of a belief change operator on a world that evolves, for instance, following an action.
In the context of possibility theory, this updating rule can be formally expressed as [17]:

$$ \forall \omega' \in \Omega, \quad \pi_A(\omega') = \begin{cases} \max_{\omega \in \Omega : \omega' = \omega_A} \pi(\omega), & \text{if } \omega' \in A, \\ 0, & \text{if } \omega' \notin A. \end{cases} $$

The Imaging rule is originally motivated by the study of conditional probabilities and the probability of conditionals. See also the recent work of [19], which revisits these studies within the framework of possibility theory and analyzes Lewis's triviality result as well as the Imaging rule in a possibility theory framework. In Lewis's work [13], two major references have influenced both knowledge representation and uncertainty theories for modeling belief changes and reasoning with conditionals. The first concerns the work in [1] on the probabilistic interpretation of conditionals: "the conditional (B | A) is interpreted as P(B | A) being very close to 1", which is considered one of the first probabilistic semantics of the System P for reasoning with conditionals in the context of non-monotonic reasoning [20]. The second relates to the work in [22], which proposes a qualitative interpretation of conditionals and, more importantly, introduces the notion of closeness (or selection function), stating that "for each interpretation ω of Ω, and for each subset A, there exists a closest interpretation to ω in A." These results opened the path for other standard probabilistic semantics of conditionals, in particular for System P [20], both in probability theory (e.g. [5]) and in possibility theory (e.g. [4]).

A possible direction for future research is to explore the adaptation of the syntactic characterizations studied in this paper to encode the Imaging rule within the framework of possibility theory; for both weighted knowledge bases and conditional knowledge bases. The first difficulty lies in the notion of proximity functions, which are not necessarily unique. Lewis [13] imposes only one very natural constraint: if an interpretation ω belongs to A, then the closest interpretation in A is ω itself. This constraint leaves room for a large number of proximity functions. Among them, distances between interpretations (e.g. [6,7,9,8]), widely used for defining belief change operators, are typically based on differences between propositional symbols. However, given ω ∈ Ω and A ⊆ Ω, if we apply Dalal's [6] or Hamming's distance d between interpretations and select a world ω' ∈ A for which the Hamming distance d(ω, ω') is the smallest, the result is not necessarily unique. This necessitates the use of an adaptation of the Imaging rule to cases where, given A and an interpretation w, there may exist more than one closest interpretation in A (see e.g. [17]).

Another possible approach, which would allow for a single interpretation close to ω_A, is to rely on the use of linear possibility distributions. A possibility distribution π is said to be linear if, for all ω and ω', we have either π(ω) > π(ω') or π(ω') > π(ω) (i.e. no equality).

Given a linear possibility distribution π, a set A and an interpretation ω, we can define the closest interpretation ω_A to ω in A as the most preferred one in A, namely:

$$ \omega_A = \begin{cases} \omega & \text{if } \omega \in A, \\ \omega' : \omega' \in A \text{ and } \forall \omega'' \in A, \pi(\omega') \ge \pi(\omega'') & \text{Otherwise, (namely } \omega \notin A \text{)} \end{cases} $$

The uniqueness of ω_A follows from the fact that we are using a linearly ordered possibility distribution. This solution ensures a single closest interpretation, as required by the definitions of Lewis's imaging. However, the initial belief degrees of all interpretations outside A are all transferred to the same interpretation—the one that is most preferred in A.

Linear possibility distributions play an important role in the definition of conditionals, as they serve as counterparts to classical propositional logic interpretations. Let us use $\varphi \Box \rightarrow \psi$ given in [13] to express that $\psi$ holds in the preferred interpretations of $\varphi$. In our context, the notion of preferred interpretations is defined with respect to the possibility distribution, that is, the interpretations that satisfy $\varphi$ and have the highest degree of possibility (which is unique for linear possibility distribution). This is equivalent to the strict inequality $\Pi(\varphi \wedge \psi) > \Pi(\varphi \wedge \neg \psi)$ that we mentioned earlier in this section. Now, in propositional logic, given an interpretation $\omega$ and a propositional logic formula $\varphi$, either $\omega$ satisfies $\varphi$ or $\omega$ satisfies its negation $\neg \varphi$. A linear possibility distribution plays exactly the same role for conditionals $\varphi \Box \rightarrow \psi$, from which either the conditional holds or it negated conditional $\varphi \Box \rightarrow \neg \psi$ holds, since there is a unique preferred interpretation of $\varphi$. This corresponds to what is called the conditional excluded middle law in [22] and in accordance with the axiom F of the logic C2 defined in [21].

There is already work that defines an update operator in belief functions based on Lewis's imaging. For example, in [17], we find (although briefly described) a proposal for an extension of Lewis's imaging. Inspired by the imaging principle, the idea is to transfer the weights of focal elements that do not satisfy the new information to the closest focal elements compatible with the new information.

Now, a future work would be to draw inspiration from the definition of FH-conditioning to develop its counterpart as an update operator. The idea is to view again a mass function m as a family of probability distributions $F(m)$. Instead of applying conditional probability to each of these probability distributions, the Lewis Imaging operator is applied in its place. More specifically, let $A \subseteq \Omega$. For each probability distribution $p \in F(m)$, let $p_A$ denote the updated probability distribution obtained by applying Lewis's updating equation, given by equation (27). Then, we define $F_A(m)$ as the set of all such updated distributions:

$$ F_A(m) = \{p_A : p \in F(m)\} $$

For any $B \subseteq \Omega$, let $Bel_A(B)$ denote the result of taking the infimum of $P_A(B)$ over all distributions in $F_A(m)$, that is,

$$ Bel_A(B) = \inf \{ P_A(B) : p \in F_A(m) \}. $$
By construction, Bel<sub>A</sub>(B) represents the counterpart of FH-conditioning, but with the use of Lewis's imaging, instead of standard probabilistic conditioning. A work to explore is first to study the properties of this operator, independently of the proximity function used, and especially whether it can be characterized as is done with FH-conditioning in order to obtain a compact representation that would avoid enumerating all compatible probability distributions.

## 7. Conclusion

This paper presented a syntactic approach to computing the revision of uncertain information within the framework of possibility theory. We focused on the Fagin and Halpern conditioning operation, which had been thoroughly studied in the literature from a semantic perspective but had received little attention from a computational standpoint. Our contribution specifically aimed to fill this gap. In particular, we proposed a method for computing the result of possibilistic FH-conditioning applied to possibilistic logic bases composed of weighted propositional formulas, in order to incorporate new observations that must be accepted. We showed that our syntactic computation is fully in agreement with the semantics defined by FH-conditioning on possibility distributions. This computation was performed without additional cost compared to the two existing forms of possibilistic conditioning, namely minimum-based and product-based possibilistic conditioning. Furthermore, we analyzed the computational complexity of our syntactic method, showing in particular that the spatial complexity of the conditioned belief base is linear with respect to the size of the initial belief base. In the last section, we examined the semantic counterpart, followed by a detailed analysis of the syntactic counterpart of FH-conditioning under uncertain inputs.

In Section 6, we have detailed various directions for future work. These include exploring the syntactic counterparts of FH-conditioning to work directly on conditional assertion bases instead of weighted propositional logic belief bases, studying the feasibility of syntactic computation of FH-conditioning for general belief functions, and extending FH-conditioning to account for update operators.

## CRediT authorship contribution statement

**Omar Et-Targuy:** Writing – review & editing, Writing – original draft, Validation, Methodology, Formal analysis, Conceptualization. **Salem Benferhat:** Writing – review & editing, Writing – original draft, Validation, Supervision, Resources, Methodology, Funding acquisition, Formal analysis, Conceptualization. **Carole Delenne:** Writing – review & editing, Writing – original draft, Validation, Supervision, Resources, Methodology, Funding acquisition, Formal analysis. **Ahlame Begdouri:** Writing – review & editing, Writing – original draft, Validation, Supervision, Resources, Methodology, Funding acquisition, Formal analysis, Conceptualization.

## Declaration of competing interest

The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: ET-TARGUY Omar reports financial support was provided by French National Research Agency. Benferhat Salem reports financial support was provided by European Commission Marie Skłodowska-Curie Actions. If there are other authors, they declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

## Acknowledgements

This research has received support from the European Union's Horizon research and innovation programme under the MSCA-SE (Marie Skłodowska-Curie Actions Staff Exchange) grant agreement 101086252; Call: HORIZON-MSCA-2021-SE-01; Project title: STARWARS (STormwAteR and WastewAteR networks heterogeneous data AI-driven management).

This research has also received support from the French national project ANR (Agence Nationale de la Recherche) CROQUIS (Collecte, représentation, complétion, fusion et interrogation de données hétérogènes et incertaines de réseaux d'eaux urbains).

The authors would like to thank the referees for their constructive comments, which helped improve the quality of this paper.

## Data availability

No data was used for the research described in the article.

## References

[1] Ernest W. Adams, The Logic of Conditionals/D, Reidel, Dordrecht, 1975.

[2] Judea Pearl, System Z: a natural ordering of defaults with tractable applications to nonmonotonic reasoning, in: Proceedings of the 3rd Conference on Theoretical Aspects of Reasoning About Knowledge, 1990, pp. 121–135.

[3] Daniel Lehmann, Menachem Magidor, What does a conditional knowledge base entail?, Artif. Intell. 55 (1) (1992) 1–60.

[4] Salem Benferhat, Didier Dubois, Henri Prade, Possibilistic and standard probabilistic semantics of conditional knowledge bases, J. Log. Comput. 9 (6) (1999) 873–895.

[5] Paul Snow, Diverse confidence levels in a probabilistic semantics for conditional logics, Artif. Intell. 113 (1–2) (1999) 269–279.

[6] Mukesh Dalal, Investigations into a theory of knowledge base revision: preliminary report, in: Proceedings of the Seventh National Conference on Artificial Intelligence, vol. 2, 1988, pp. 475–479.

[7] Andreas Herzig, Omar Rifi, Propositional belief base update and minimal change, Artif. Intell. 115 (1) (1999) 107–138.
[8] Arthur M. Keller, Marianne Winslett Wilkins, On the use of an extended relational model to handle changing incomplete information, IEEE Trans. Softw. Eng. 7 (1985) 620-633.

[9] Theofanis Aravanis, Relevance in belief update, J. Artif. Intell. Res. 72 (2021) 251-283.

[10] Carlos E. Alchourrón, Peter Gärdenfors, David Makinson, On the logic of theory change: partial meet contraction and revision functions, J. Symb. Log. 50 (2) (1985) 510-530.

[11] Hirofumi Katsuno, Alberto O. Mendelzon, On the difference between updating a knowledge base and revising it, in: KR, 1991, pp. 387-394.

[12] Arthur M. Keller, Marianne Winslett Wilkins, On the use of an extended relational model to handle changing incomplete information, IEEE Trans. Softw. Eng. 7 (1985) 620-633.

[13] David Lewis, Probabilities of conditionals and conditional probabilities, in: IFS: Conditionals, Belief, Decision, Chance and Time, 1976, pp. 129-147.

[14] Glenn Shafer, A Mathematical Theory of Evidence, Princeton University Press, 1976.

[15] Gabriele Kern-Iserner, Conditionals in Nonmonotonic Reasoning and Belief Revision: Considering Conditionals as Agents, Springer, 2001.

[16] Didier Dubois, Henri Prade, Focusing versus updating in belief function theory, in: Advances in the Dempster-Shafer Theory of Evidence, 1994, pp. 71-95.

[17] Didier Dubois, Henri Prade, A survey of belief revision and updating rules in various uncertainty models, Int. J. Intell. Syst. 9 (1994).

[18] Glenn Shafer, Constructive probability, Synthese 48 (1) (1981) 1-60.

[19] Tommaso Flaminio, Lluis Godo, Giuliano Rosella, Possibility of conditionals and conditional possibilities: from the triviality result to possibilistic imaging, in: Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, vol. 21, 2024, pp. 372-382.

[20] Sarit Kraus, Daniel Lehmann, Menachem Magidor, Nonmonotonic reasoning, preferential models and cumulative logics, Artif. Intell. 44 (1-2) (1990) 167-207.

[21] David Lewis, Completeness and decidability of three logics of counterfactual conditionals, Theoria 37 (1) (1971) 74-85.

[22] Robert C. Stalnaker, A defense of conditional excluded middle, in: William L. Harper, Robert Stalnaker, Glenn Pearce (Eds.), Ifs: Conditionals, Belief, Decision, Chance, and Time, D. Reidel, Dordrecht, 1980, pp. 87-104.

[23] Ronald Fagin, Joseph Y. Halpern, A new approach to updating beliefs, preprint, arXiv:1304.1119, 2013.

[24] Ronald Fagin, Joseph Y. Halpern, A new approach to updating beliefs, in: UAI '90: Proceedings of the Sixth Annual Conference on Uncertainty in AI, Elsevier, 1990, pp. 347-374.

[25] Salem Benferhat, Celia da Costa Pereira, Andrea Tettamanzì, Syntactic computation of hybrid possibilistic conditioning under uncertain inputs, in: IJCAI, 2013, pp. 739-745.

[26] Didier Dubois, Lluis Godo, Henri Prade, An elementary belief function logic, J. Appl. Non-Class. Log. 33 (3-4) (2023) 582-605.

[27] Prakash P. Shenoy, A valuation-based language for expert systems, Int. J. Approx. Reason. 3 (5) (1989) 383-411.

[28] Radim Jirousek, On conditional belief functions in directed graphical models in the Dempster-Shafer theory, Int. J. Approx. Reason. 160 (2023) 108976.

[29] Fabio G. Cozman, Credal networks, Artif. Intell. 120 (2) (2000) 199-233.

[30] Laurence Cholvy, Towards a logical belief function theory, J. Appl. Log. 13 (4) (2015) 441-457.

[31] Luis M. de Campos, María T. Lamata, Serafín Moral, The concept of conditional fuzzy measure, Int. J. Intell. Syst. 5 (3) (1990) 237-246.

[32] Salem Benferhat, Claudio Sossai, Merging uncertain knowledge bases in a possibilistic logic framework, preprint, arXiv:1301.7359, 2013.

[33] Thierry Denœux, Didier Dubois, Henri Prade, Representations of uncertainty in AI: beyond probability and possibility, in: Pierre Marquis, Odile Papini, Henri Prade (Eds.), A Guided Tour of Artificial Intelligence Research, vol. I, Springer, 2020, pp. 119-150.

[34] Ronald Meester, Timber Kerkvliet, A new look at conditional probability with belief functions, Stat. Neerl. 73 (2) (2019) 274-291.

[35] Didier Dubois, Henri Prade, Possibility theory and its applications: where do we stand?, in: Janusz Kacprzyk, Witold Pedrycz (Eds.), Springer Handbook of Computational Intelligence, Springer, 2015, pp. 31-60.

[36] John C. Aldrich, A. Philip Dawid, Thierry Denoeux, Prakash P. Shenoy, Vladimir Vovk, Glenn Shafer - A short biography, Int. J. Approx. Reason. 141 (2022) 5-10.

[37] Radim Jirousek, Václav Kratochvíl, Prakash P. Shenoy, On conditional belief functions in the Dempster-Shafer theory, in: Sylvie Le Hégarat-Mascle, Isabelle Bloch (Eds.), BELIEF 2022: 7th International Conference on Belief Functions, in: LNCS, vol. 13506, Springer, 2022, pp. 207-218.

[38] Nicolas Schwind, Sébastien Konieczny, Jean-Marie Lagniez, Pierre Marquis, On computational aspects of iterated belief change, in: IJCAI 2020, 2020, pp. 1770-1776.

[39] Lalatha G. Polpitiya, Kamal Premaratne, Manohar N. Murthi, Stephen J. Murrell, Dilip Sarkar, Efficient computation of conditionals in the Dempster-Shafer belief theoretic framework, IEEE Trans. Cybern. 52 (5) (2022) 2931-2941.

[40] Glenn Shafer, A Mathematical Theory of Evidence, Princeton University Press, 1976.

[41] Jérôme Lang, Possibilistic logic: complexity and algorithms, in: Jürg Kohlas, Serafín Moral (Eds.), Handbook of Defeasible Reasoning and Uncertainty Management Systems, Springer, 2000, pp. 179-220.

[42] Peter Gärdenfors, Belief Revision, Cambridge University Press, 1992.

[43] Jean Dezert, Albena Tchamova, Deqiang Han, Total belief theorem and conditional belief functions, Int. J. Intell. Syst. 33 (12) (2018) 2314-2340.

[44] Didier Dubois, Henri Prade, Bayesian conditioning in possibility theory, Fuzzy Sets Syst. 92 (2) (1997) 223-240.

[45] Didier Dubois, Jérôme Lang, Henri Prade, Handbook of Logic in Artificial Intelligence and Logic Programming, Tome 3: Nonmonotonic Reasoning and Uncertain Reasoning, Chapitre Possibilistic Logic, Oxford Science Publications, 1994.

[46] Didier Dubois, Henri Prade, Possibilistic logic: a retrospective and prospective view, Fuzzy Sets Syst. 144 (1) (2004) 3-23.

[47] Bernadette Bouchon-Meunier, Giulianella Coletti, Christophe Marsala, Independence and possibilistic conditioning, Ann. Math. Artif. Intell. 35 (2002) 107-123.

[48] Didier Dubois, Henri Prade, Focusing vs. belief revision: a fundamental distinction when dealing with generic knowledge, in: International Joint Conference on Qualitative and Quantitative Practical Reasoning, 1997, pp. 96-107.

[49] Mohua Banerjee, Didier Dubois, Lluis Godo, Henri Prade, On the relation between possibilistic logic and modal logics of belief and knowledge, J. Appl. Non-Class. Log. (2018).

[50] Wolfgang Spohn, Ordinal conditional functions: a dynamic theory of epistemic states, in: Causation in Decision, Belief Change, and Statistics, 1988, pp. 105-134.

[51] Wolfgang Spohn, The Laws of Belief - Ranking Theory and Its Philosophical Applications, Oxford University Press, 2014.

[52] Salem Benferhat, Didier Dubois, Henri Prade, Mary-Anne Williams, A practical approach to revising prioritized knowledge bases, Stud. Log. 70 (1) (2002) 105-130.

[53] R.C. Jeffrey, The Logic of Decision, McGraw-Hill, New York, 1965.

[54] Karim Tabia, Analysis of Jeffrey's rule of conditioning in an imprecise probabilistic setting, in: The Thirty-First International FLAIRS Conference, 2018.

[55] Hirofumi Katsuno, Alberto O. Mendelzon, Propositional knowledge base revision and minimal change, Artif. Intell. 52 (3) (1991) 263-294.

[56] Adnan Darwiche, Judea Pearl, On the logic of iterated belief revision, Artif. Intell. 89 (1-2) (1997) 1-29.

[57] Eduardo Fermé, Sven Ove Hansson, AGM 25 years: twenty-five years of research in belief change, J. Philos. Log. 40 (2011) 295-331.

[58] Hans Rott, Shifting priorities: simple representations for twenty-seven iterated theory change operators, in: Towards Mathematical Philosophy: Papers from the Studia Logica Conference Trends in Logic IV, Springer, 2009, pp. 269-296.

[59] Edwin T. Jaynes, Probability Theory: The Logic of Science, Cambridge University Press, 2003.

[60] Judea Pearl, Models, Reasoning and Inference, Cambridge University Press, Cambridge, UK, 2000.

[61] Adnan Darwiche, Modeling and Reasoning with Bayesian Networks, Cambridge University Press, 2009.

[62] Judea Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Elsevier, 2014.
[63] Glenn Shafer, A Mathematical Theory of Evidence, Princeton University Press, 1976.

[64] Thierry Denoeux, A neural network classifier based on Dempster-Shafer theory, IEEE Trans. Syst. Man Cybern., Part A, Syst. Hum. 30 (2) (2000) 131–150.

[65] Thierry Denoeux, A k-nearest neighbor classification rule based on Dempster-Shafer theory, IEEE Trans. Syst. Man Cybern. 25 (5) (1995) 804–813.

[66] Prakash P. Shenoy, On distinct belief functions in the Dempster-Shafer theory, in: International Symposium on Imprecise Probability: Theories and Applications, 2023, pp. 426–437.

[67] Didier Dubois, Henri Prade, Possibility Theory: An Approach to Computerized Processing of Uncertainty, Plenum Press, 1988.

[68] Didier Dubois, Henri Prade, Belief change and possibility theory, in: Belief Revision, 1992, pp. 142–182.

[69] Mary-Anne Williams, Transmutations of knowledge systems, in: Principles of Knowledge Representation and Reasoning, 1994, pp. 619–629.

[70] Mary-Anne Williams, Hans Rott (Eds.), Frontiers in Belief Revision, vol. 22, Springer, 2001.

[71] Gabriele Kern-Isberner, Conditionals in Nonmonotonic Reasoning and Belief Revision: Considering Conditionals as Agents, Springer, 2001.

[72] Kai Sauerwald, Gabriele Kern-Isberner, Christoph Beierle, A conditional perspective for iterated belief contraction, in: ECAI 2020, IOS Press, 2020, pp. 889–896.

[73] Gabriele Kern-Isberner, Jesse Heyninck, Christoph Beierle, Conditional independence for iterated belief revision, in: IJCAI, 2022, pp. 2690–2696.

[74] Hei Chan, Adnan Darwiche, On the revision of probabilistic beliefs using uncertain evidence, Artif. Intell. 163 (1) (2005) 67–90.

[75] Niels Skovgaard-Olsen, Ranking theory and conditional reasoning, Cogn. Sci. 40 (4) (2016) 848–880.

[76] Jianbing Ma, Weiru Liu, Salem Benferhat, A belief revision framework for revising epistemic states with partial epistemic states, Int. J. Approx. Reason. 59 (2015) 20–40.

[77] Meliha Sezgin, Gabriele Kern-Isberner, Christoph Beierle, Ranking kinematics for revising by contextual information, Ann. Math. Artif. Intell. 89 (10) (2021) 1101–1131.

[78] Salem Benferhat, Karim Tabia, Karima Sedki, Jeffrey's rule of conditioning in a possibilistic framework: an analysis of the existence and uniqueness of the solution, Ann. Math. Artif. Intell. 61 (2011) 185–202.

[79] Lotfi Asker Zadeh, Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets Syst. 1 (1) (1978) 3–28.

[80] Ronald R. Yager, On the relationship between fuzzy sets and possibility theory, Fuzzy Sets Syst. 5 (1) (1981) 3–24.

[81] Didier Dubois, Henri Prade, Possibility theory, in: Granular, Fuzzy, and Soft Computing, Springer, 2023, pp. 859–876.

[82] Ellen Hisdal, Conditional possibilities independence and noninteraction, Fuzzy Sets Syst. 1 (4) (1978) 283–297.

[83] Irwin R. Goodman, Hung T. Nguyen, A theory of conditional information for probabilistic inference in intelligent systems: II. Product space approach, Inf. Sci. 76 (1–2) (1994) 13–42.

[84] Giulianella Coletti, Davide Petturiti, Finitely maxitive T-conditional possibility theory: coherence and extension, Int. J. Approx. Reason. 71 (2016) 64–88.

[85] Gert De Cooman, Possibility theory II: conditional possibility, Int. J. Gen. Syst. 25 (4) (1997) 325–351.

[86] Peter Walley, Gert De Cooman, Coherence of rules for defining conditional possibility, Int. J. Approx. Reason. 21 (1) (1999) 63–107.

[87] Tommaso Flaminio, Lluis Godo, Sara Ugolini, Canonical extension of possibility measures to Boolean algebras of conditionals, in: European Conference on Symbolic and Quantitative Approaches with Uncertainty, Springer, 2021, pp. 543–556.

[88] Bernard De Baets, Elena Tsiporkova, Radko Mesiar, Conditioning in possibility theory with strict order norms, Fuzzy Sets Syst. 106 (2) (1999) 221–229.

[89] Tommaso Flaminio, Lluis Godo, Hykel Hosni, On Boolean algebras of conditionals and their logical counterpart, in: ECSQARU 2017: Symbolic and Quantitative Approaches to Reasoning with Uncertainty, in: LNCS, vol. 10369, Springer, 2017, pp. 246–256.

[90] Gert De Cooman, Integration and conditioning in numerical possibility theory, Ann. Math. Artif. Intell. 32 (2001) 87–123.

[91] Omar Ettarguy, Ahlame Begdouri, Salem Benferhat, Carole Delenne, Syntactic computation of Fagin-Halpern conditioning in possibility theory, in: Proceedings of the 24th International Conference on Logic for Programming, Artificial Intelligence and Reasoning, 2023, pp. 164–180.

[92] Didier Dubois, Henri Prade, The logical view of conditioning and its application to possibility and evidence theories, Int. J. Approx. Reason. 4 (1) (1990) 23–46.

[93] Giulianella Coletti, Barbara Vantaggi, T-conditional possibilities: coherence and inference, Fuzzy Sets Syst. 160 (3) (2009) 306–324.

[94] Didier Dubois, Henri Prade, A synthetic view of belief revision with uncertain inputs in the framework of possibility theory, Int. J. Approx. Reason. 17 (2) (1997) 295–324.