Compatible-Based Conditioning in Interval-Based Possibilistic Logic

1 Introduction

Interval-based uncertainty representations are well-known frameworks for encoding, reasoning and decision making with poor information, imprecise beliefs, confidence intervals and multi-source information [Nguyen and Kreinovich, 2014; Dubois, 2006]. In this paper, we deal with interval-based possibilistic logic [Benferhat et al. , 2011] which extends possibilistic logic [Lang, 2001] such that the uncertainty is described with intervals of possible degrees instead of single certainty degrees associated with formulas. This setting is more flexible than standard possibilistic logic and allows to efficiently compute certainty degrees associated with derived conclusions. Target applications are those where uncertainty is given as intervals (eg. resulting from different/unreliable sources). An example of application is sensitivity analysis to study the effects of some variations in some parameters. Interval-based possibilistic logic is only specified for static situations and no form of conditioning has been proposed for updating the current knowledge and beliefs. Conditioning and belief change are important tasks for designing intelligent systems. Conditioning is concerned with updating

Vladik Kreinovich

Department of Computer Science University of Texas at El Paso, 500 W. University El Paso, Texas 79968, USA vladik@utep.edu

the current beliefs when a new sure piece of information becomes available. In the possibilistic setting, given a possibilistic knowledge base K or a possibility distribution π and a new evidence φ, conditioning allows to update the old beliefs, encoded by π or K, with φ. Conditioning in the standard possibilistic setting is studied in many works [Hisdal, 1978; L.M. De Campos and Moral, 1995; Dubois and Prade, 2006; Fonck, 1997; Dubois and Prade, 1997]. In [Benferhat et al. , 2013] the authors dealt with syntactic hybrid conditioning of standard (point-wise) possibilistic knowledge bases with uncertain inputs.

In [Benferhat et al. , 2011], the authors dealt with inference issues in the interval-based possibilistic setting but did not address the conditioning issue. Conditioning operators are designed to satisfy some properties such as giving priority to the new information and performing minimal change. In this paper, we deal with conditioning interval-based possibility distributions and interval-based possibilistic knowledge bases. The main contributions of the paper are:

1. Proposing a set of natural properties that an intervalbased conditioning operator should satisfy.
2. ii) Proposing a natural definition of conditioning an interval-based possibility distribution with a new evidence. This definition is safe since it takes into account all the compatible distributions.
3. iii) We show that when min-based conditioning is applied over the set of compatible distributions then the result is not guaranteed to be an interval-based distribution.
4. iv) We show that applying product-based conditioning leads to an interval-based possibility distribution. We provide the exact computations of lower and upper endpoints of intervals associated with each interpretation of the conditioned interval-based possibility distribution.
5. Lastly, we propose a syntactic counterpart of conditioning over interval-based possibilistic bases. The proposed conditioning does not induce extra computational cost. Conditioning an interval-based possibilistic knowledge base has the same complexity as conditioning a standard possibilistic knowledge base.

Before presenting our contributions, let us give a brief refresher on standard and interval-based possibilistic logics.

2 A refresher on standard possibilistic logic

We consider a finite propositional language. We denote by Ω the finite set of interpretations, and by ω an element of Ω. φ and ψ denote propositional formulas, and |= denotes the propositional logic satisfaction relation. Possibility theory is a well-known uncertainty framework particularly suited for representing and reasoning with uncertain and incomplete information [Dubois, 2006; 2014]. One of the main concepts of this setting is the one of possibility distribution π which is a mapping from the set of possible worlds or interpretations Ω to [0, 1]. π(ω) represents the degree of consistency (or feasibility) of the interpretation ω with respect to the available knowledge. By convention, π(ω)=1 means that ω is fully consistent with the available knowledge, while π(ω)=0 means that ω is impossible. π(ω)>π(ω′ ) simply means that ω is more consistent than ω′ . π is said to be normalized if there exists an interpretation ω such that π(ω)=1; otherwise it is said sub-normalized. Possibility degrees are interpreted either i) qualitatively (in min-based possibility theory) where only the "ordering" of the values is important, or ii) quantitatively (in product-based possibility theory) where the possibilistic scale [0,1] is numerical.

Another main concept in possibility theory is the one of possibility measure, denoted Π(φ), and defined as follows:

A possibilistic base K={(ϕi, αi) : i=1, .., n} is a set of possibilistic formulas, where ϕi is a propositional formula and αi∈[0, 1] is a valuation of ϕi representing its certainty degree. Each piece of information (ϕi,αi) can be viewed as a constraint which restricts a set of possible interpretations. If an interpretation ω satisfies ϕi then its possibility degree is equal to 1, otherwise it is equal to 1-αi (the more ϕi is certain, the less ω is possible). Given a possibilistic base K, we can generate a unique distribution where interpretations ω satisfying all formulas in K have the highest possible degree π(ω)=1, whereas the others are pre-ordered with respect to the highest formulas they falsify. More formally: ∀ω∈Ω, πK(ω) =

3 A refresher on interval-based possibilistic logic

This section gives a refresher on interval-based possibilistic logic [Benferhat et al. , 2011] where the uncertainty is not described with single values but by intervals of possible degrees. We use closed sub-intervals I⊆[0, 1] to encode the uncertainty associated with formulas or interpretations. If I is an interval, then we denote by I and I its upper and lower endpoints respectively. When all I's associated with interpretations (resp. formulas) are singletons (namely I = I), we refer to standard (or point-wise) distributions (resp. standard possibilistic bases).

3.1 Interval-based possibility distributions

Let us recall the definition of an interval-based distribution:

Definition 1. An interval-based possibility distribution, denoted by Iπ, is a function from Ω to I. Iπ(ω)=I means that the possibility degree of ω is one of the elements of I. Iπ is said to be normalized if ∃ω∈Ω such that Iπ(ω)=1.

An interval-based possibility distribution is viewed as a family of compatible standard possibility distributions defined as follows:

Definition 2. Let Iπ be an interval based possibility distribution. A normalized possibility distribution π is said to be compatible with Iπ iff ∀ω∈Ω, π(ω)∈Iπ(ω).

We denote by C(Iπ) the set of all compatible possibility distributions with Iπ. In the rest of this paper, we consider only coherent interval-based possibility distributions, where ∀ω∈Ω, ∀α∈Iπ(ω), there exists a compatible possibility distribution π∈C(Iπ) such that π(ω)=α.

Given Iπ, we define an interval-based possibility degree of a formula φ as follows:

3.2 From interval-based possibilistic bases to interval-based possibility distributions

The syntactic representation of interval-based possibilistic logic generalizes the notion of a possibilistic base to an interval-based possibilistic knowledge base.

Definition 3. An interval-based possibilistic base, denoted by IK, is a set of formulas associated with intervals: IK = {(ϕ, I), ϕ ∈ L and I is a closed sub-interval of [0,1]}

As in standard possibilistic logic, an interval-based knowledge base IK is also a compact representation of an intervalbased possibility distribution IπIK [Benferhat et al. , 2011].

Definition 4. Let IK be an interval-based possibilistic base. Then:

where:

and

Definition 4 extends the one given by Equation 2 when I=I.

Example 1. Let IK={(a∧b, [.4, .7]), (a∨¬b, [.6, .9])} be an interval-based possibilistic base. The interval-based possibility distribution corresponding to IK according to Definition 4 is given in Table 1.

4 Properties of interval-based conditioning

In standard possibility theory, conditioning is concerned with updating the current knowledge encoded by a possibility distribution π when a completely sure event (evidence) is observed. There are several definitions of the possibilistic conditioning [Hisdal, 1978; L.M. De Campos and Moral, 1995; Dubois and Prade, 2006; Fonck, 1997; Dubois and Prade,

1997]. In the quantitative setting, the product-based conditioning [Shafer, 1976] is the most used one and it is defined as follows (for Π(φ) ̸= 0):

The min-based conditioning is defined as follows [Hisdal, 1978]:

When Π(φ)=0, then by convention ∀ω∈Ω, π(ω|⋄φ)=1 for both |⋄=|m and |⋄=|∗.

This section gives natural properties that a conditioning operation should satisfy when interval-based possibility distributions are used. Let us first fix the values of Iπ(.|φ) for degenerate possibility distributions Iπ when IΠ(φ)=0 or IΠ(φ)=0. If IΠ(φ)=0 then by convention, as in standard possibility distributions, ∀ω∈Ω, Iπ(ω|φ)=[1, 1]. Similarly, if IΠ(φ)=0 (and IΠ(φ)>0) then ∀ω∈Ω,

In the rest of this paper, we assume that Iπ is not degenerate with respect to φ. Namely, we assume first that IΠ(φ)>0. In an interval-based setting, a conditioning operator " | " should satisfy the following suitable properties:

• (IC1) Iπ(.|φ) should be an interval-based distribution.
• (IC2) ∀ω∈Ω, if ω⊭φ then Iπ(ω|φ)=[0, 0].
• (IC3) ∃ω∈Ω such that ω|=φ and Iπ(ω|φ)=1.
• (IC4) If ∀ω ⊭ φ, Iπ(ω)=[0, 0] then Iπ(.|φ) = Iπ.
• (IC5) ∀ω∈Ω, if ω|=φ and Iπ(ω)=[0, 0] then Iπ(ω|φ)=[0, 0].
• (IC6) ∀ω|=φ and ∀ω′ |=φ, if Iπ(ω)<Iπ(ω′ ) then Iπ(ω|φ)<Iπ(ω′ |φ).
• (IC7) ∀ω|=φ, ∀ω′ |=φ, if Iπ(ω)=Iπ(ω′ ) then Iπ(ω|φ)= Iπ(ω′ |φ).

Property IC1 simply states that the result of applying conditioning over an interval-based possibility distribution should result in an interval-based possibility distribution. Property IC2 requires that when the new sure piece of information φ is observed then any interpretation that is a counter-model of φ should be completely impossible. Property IC3 states that there exists at least a compatible possibility distribution π′ of Iπ(.|φ) where Π′ (φ)=1. Property IC4 states that if φ is already fully accepted (namely, all counter-models of φ are already impossible) then Iπ(.|φ) should be identical to Iπ. Property IC5 states that impossible interpretations (even if they are models of φ) remain impossible after conditioning. Properties IC6 and IC7 express a minimal change principle. IC6 states that the strict relative ordering between models of φ should be preserved after conditioning. IC7 states that equal models of φ should remain equal after conditioning.

5 Semantic-based conditioning using compatible possibility distributions

5.1 Definitions and property-based analysis

This section provides a natural and safe definition of conditioning an interval-based possibility distribution using the set of compatible possibility distributions. More precisely, conditioning an interval-based possibility distribution Iπ comes down to apply standard min-based or product-based conditioning on the set of all compatible possibility distributions C(Iπ) associated with Iπ. Namely,

Definition 5. The compatible-based conditioned intervalbased possibility distribution is defined as follows: ∀ω∈Ω, Iπ(ω|⋄φ)={π(ω|⋄φ) : π ∈ C(Iπ)}, where |⋄ is either |∗ or |m given by Equations (4) and (5) respectively.

Conditioning according to Definition 5 is safe since it relies on all the compatible distributions as opposed to a possible approach when only an arbitrary set of compatible distributions is used. Note that the idea of compatible-based conditioning in the interval-based possibilistic setting is somehow similar to conditioning in credal sets [Levi, 1980] and credal networks [Cozman, 2000] where the concept of convex set refers to the set of compatible probability distributions composing the credal set. Regarding the computational cost, conditioning in credal sets is done on the set of extreme points (edges of the polytope representing the credal set) but their number can reach N! where N is the number of interpretations [Wallner, 2007].

The first important issue with compatible-based conditioning of Definition 5 is whether conditioning an interval-based distribution Iπ with an evidence φ gives an interval-based distribution, namely whether the first property (IC1) is satisfied or not. The result is different using product-based or min-based conditioning. In case of min-based conditioning, Observation 1 states that the result of compatible-based conditioning using Definition 5 is not guaranteed to be an interval-based possibility distribution.

Observation 1

Let |m be the conditioning operator given by Equation 5. Then, there exists an interval-based possibility distribution, a propositional formula φ, and an interpretation ω such that Iπ(ω|mφ) is not an interval.

Example 2 (Counter-example).

Let Iπ be the normalized interval-based distribution of Table 2. Let φ=a be the new evidence. The compatible-based conditioned distribution Iπ(.|mφ) is obtained by conditioning Iπ following Definition 5 with |⋄ = |m.

From Table 2, Iπ(a¬b|mφ) is not an interval. Indeed, one can check that for every compatible distribution π of Iπ, such that π(a¬b)∈[.4, .7[ we have π(a¬b|mφ)∈[.4, .7[ (since π(ab)≥.7). Now, for compatible distributions where π(a¬b)=.7 we have either π(a¬b|mφ)=.7 (if π(ab)>.7) or π(a¬b|mφ)=1 (if π(ab)=.7). Hence, π(a¬b|mφ)=[.4, .7]∪{1} which is not an interval.

Contrary to the min-based conditioning, using the productbased one, conditioning an interval-based distribution Iπ with φ using Equation 4 gives an interval-based distribution.

Proposition 1. Let Iπ be an interval-based distribution. Let φ be the new evidence and |∗ be the standard productbased conditioning given by Equation 4. Then ∀ω∈Ω, Iπ(ω|∗φ)=[minπ∈C(IπIK)(π(ω|∗φ)), maxπ∈C(IπIK)(π(ω|∗φ))] is an interval.

In the rest of the paper, we only consider product-based conditioning. Hence, we only use Iπ(.|φ) and π(.|φ) instead of Iπ(.|∗φ) and π(.|∗φ) to avoid heavy notations. The following proposition states that the compatible-based conditioning given in Definition 5 satisfies properties IC1-IC7.

Proposition 2. Let Iπ be a normalized interval-based possibility distribution. Let φ be the new evidence such that IΠ(φ)>0. Then the updated interval-based possibility distribution computed according to Definition 5 satisfies properties IC1-IC7.

5.2 Computing lower and upper endpoints of Iπ(.|φ)

The objective now is to determine the lower and upper endpoints of Iπ(.|φ). Let us start with a particular case of interval-based distributions Iπ where in each compatible distribution π∈C(Iπ), φ is accepted (namely, Π(φ)>Π(¬φ)). In this case, the computation of Iπ(.|φ) is immediate:

Proposition 3. Let Iπ be an interval-based possibility distribution and φ be a propositional formula such that IΠ(φ)=1 and IΠ(¬φ)<1. Then

We now consider the complex case where IΠ(¬φ)=1, namely there exists at least a compatible possibility distribution π where φ is not accepted. Recall that by Equation (4) ∀ω∈φ, π(ω|φ)= π(ω) Π(φ) . Therefore, intuitively to get, for in-

stance, the lower endpoint Iπ(ω|φ), it is enough to select a compatible distribution π that provides the smallest value for π(ω) (namely, if possible π(ω)=Iπ(ω)) and the largest value for Π(φ) (namely, if possible Π(φ)=IΠ(φ)). The following two propositions give these bounds depending whether there exist a unique interpretation or several interpretations having their upper endpoints equal to IΠ(φ).

Proposition 4. Let Iπ be an interval-based distribution such that IΠ(¬φ)=1. If there exist more than one model of φ having their upper endpoints equal to IΠ(φ), then ∀ω∈Ω:

The next proposition concerns the particular situation where there exists exactly one interpretation ω∗ , model of φ, such that Iπ(ω∗ )=IΠ(φ). In this case, comparing to Proposition 4, only the lower endpoint of the interpretation ω∗ will differ. More precisely:

Proposition 5. Let Iπ be an interval-based possibility distribution such that IΠ(¬φ)=1. Assume that there exists exactly one interpretation ω∗ , model of φ, such that Iπ(ω∗ )=IΠ(φ).

• If ω̸=ω∗ then Iπ(ω|φ) is the same as the one given in Proposition 4, namely: Iπ(ω|φ)=

• If ω=ω∗ , let secondbest(Iπ)=max{Iπ(ω′ ): ω′ |=φ and Iπ(ω′ )̸=IΠ(φ)}. Then:

Table 3: Example of conditioning an interval-based possibility distribution using Proposition 5.

Next section provides the syntactic counterpart of the compatible-based conditioning.

6 Syntactic characterization of compatible-based conditioning

Given an interval-based knowledge base IK and a new evidence φ, conditioning at the syntactic level comes down to altering IK into IKφ such that the induced posterior interval-based possibility distribution IπIKφ equals the posterior interval-based possibility distribution IπIK(.|φ) obtained by conditioning IπIK with φ as illustrated in Figure 1.

The aim of this section is then to compute a new intervalbased knowledge base, denoted for the sake of simplicity by IKφ, such that:

where IπIKφ is the interval-based distribution associated with IKφ using Definition 4, and IπIK(.|φ) is the result of conditioning IπIK using the compatible-based conditioning presented in the previous section (Propositions 4 and 5).

To achieve this aim, we need to provide methods that directly operate on the interval-based knowledge base IK:

• to check whether IΠIK(φ)=0 (resp. IΠIK (φ)=0) or not,
• to check whether IΠIK(¬φ)=1 or not,
• to compute IΠIK (φ) and IΠIK(φ),
• to compute secondbest(IπIK),
• to check whether there exists a unique interpretation ω∗ such that Iπ(ω∗ )=IΠ(φ), and lastly
• to compute IKφ.

Recall that an interval-based possibility distribution where IΠIK(φ)=0 expresses a very strong conflict with the evidence φ. Namely, IK strongly contradicts the formula φ.

Proposition 6. Let IK be an interval-based possibilistic base and IπIK be its associated interval-based distribution. Then,

1. IΠIK(φ)=0 iff {ψ : (ψ, I)∈IK and I=[1, 1]}∪{φ} is inconsistent. In this case, IKφ=∅.
2. ii) IΠIK (φ)=0 iff {ψ : (ψ, I)∈IK and I=1} ∪ {φ} is inconsistent. In this case, IKφ={(φ, [1, 1]), (¬φ, [0, 1])}.

Example 4. Let IK={(¬a, [1, 1]), (a∨¬b, [.4, .6])} be an interval-based possibilistic knowledge base. The associated interval-based possibility distribution is given in Table 4. Let φ=a be the new evidence.

In the following, we assume that IK is such that φ is somewhat possible, hence its associated interval-based possibility distribution IπIK (namely IΠIK (φ)>0).

6.2 Checking whether IΠIK(¬φ)̸=1 or not

This subsection shows how to syntactically check if φ is accepted or not, namely whether IΠIK(¬φ)=1 or not.

Proposition 7. Let IK be an interval-based possibilistic base and IπIK be its associated possibility distribution. Then: IΠIK(¬φ)̸=1 iff {ψ : (ψ, I)∈IK and I>0} ∪ {¬φ} is inconsistent. In this case: IKφ=IK ∪ {(φ, [1, 1])}.

6.3 Computing IΠIK(φ) and IΠIK(φ)

The computation of IΠIK (φ) and IΠIK(φ) comes down to computing the inconsistency degrees of two particular standard possibilistic knowledge bases (considering only lower and upper endpoints of intervals associated with formulas) as it is stated by the following proposition:

Proposition 8. Let IK be an interval-based knowledge base. Let IK={(ψ, I) : (ψ, I)∈IK} and IK={(ψ, I) : (ψ, I)∈IK}. Then:

In Proposition 8, Inc(K) is the inconsistency degree of a standard possibilistic knowledge base K and it is defined with the notion of α-cut by:

and Kα is defined by Kα={ϕ : (ϕ, β) ∈ K and β≥α}.

6.4 Checking the uniqueness of models of φ having upper endpoints equal to IΠIK(φ)

We need to show how to syntactically check whether, or not, there exists a unique interpretation ω∗ , model of φ, such that IπIK(ω∗ )=IΠIK(φ). If an interpretation ω, model of φ, is such that IπIK(ω)=IΠIK(φ) then ω is a model of Φ={ψ : (ψ, I)∈IK and I>Inc(IK ∪ {(φ, 1)})} ∪ {φ}. Besides, if for some ω′̸=ω, IπIK(ω′ )<IΠIK(φ) then this means that ω′ falsifies at least one formula from Φ ∪ {φ}.

Additionally, assume that there exists a unique model ω∗ of φ such that IπIK(ω∗ )=IΠIK(φ). We are interested to know whether ∀ω′̸=ω∗ , Iπ(ω′ )=[0, 0]. It is enough to check that all formulas in {ψ : (ψ, I)∈IKand I>Inc(IK∪{(φ, 1)})} have their associated interval I equal to [1,1]. The main results of this section are summarized in the following proposition:

Proposition 9. Let IK be an interval-based knowledge base. Let IπIK be its associated possibility distribution. Let Φ={ψ: (ψ, I)∈IK and I>Inc(IK∪{(φ, 1)})} ∪ {φ}. Then:

• Φ ∪ {φ} admits a unique model iff there exists a unique interpretation ω∗ , model of φ, such that IπIK(ω∗ )=IΠIK(φ).
• Φ ∪ {φ} admits a unique model and each formula in Φ has [1,1] as certainty-based interval weight iff there exists ω∗ model of φ such that Iπ(ω∗ )=IΠIK(φ) and ∀ω′̸=ω∗ , Iπ(ω′ )=[0, 0].

6.5 Computing secondbest(IK)

Recall that IK={(ψ, I) : (ψ, I)∈IK} and that secondbest(IK) is only computed in the situation where there exists exactly one interpretation ω∗ , model of φ, such that IΠ(φ)=Iπ(ω∗ ). In order to easily define secondbest(IπIK), we first let L={α1,. . ., αn} to be the different degrees present in IK, with α1>. . .>αn. Then we define (Aα1 , Aα2 , . . ., Aαn ) as the WOP (well ordered partition) associated with IK, obtained by letting:

Namely, Aαi is the subset of IK composed of all weighted formulas having a certainty degree equal to αi. Then:

Proposition 10. Assume that there exists exactly one interpretation ω∗ , model of φ, such that IΠIKφ (φ)=IπIKφ (ω∗ ). Let (Aα1 ,Aα2 , . . . ,Aαn ) be the WOP associated with IK, where Aαi 's are given by Equation (6). Define secondbest(IK)=1 - min{αi : αi>Inc(IK ∪ {(φ, 1)}) and Aαi is a non-tautological formula }. Then secondbest(IK)=secondbest(IπIK).

6.6 Computing IKφ

We are now ready to give the syntactic computation of IKφ when IΠIK(¬φ) = 1. In order to simplify the notations, we now denote:

The two following propositions provide the syntactic computation of IKφ depending whether Φ∪{φ} admits more than one model or not:

Proposition 11 (General case: Φ ∪ {φ} has more than one model). Assume that Φ ∪ {φ} has strictly more than one model. Then: IKφ={(φ, [1, 1])} ∪ {(ψ, [max (0, α) , α]) : (ψ, I)∈IK, and I≥Inc(IK ∪ {(φ, 1)})}.

Proposition 12 (Particular case: Φ ∪ {φ} has exactly one model). Assume that Φ ∪ {φ} admits a unique model.

1. If each formula in Φ has an interval equal to [1,1], then: IKφ={(ψ, [1, 1]):(ψ,[1, 1])∈IK and Inc(IK ∪ {φ, 1})<1}∪{(φ,[1, 1])}.
2. If there exists a formula in Φ with a certainty interval different from [1,1]. Then: IKφ={(φ,[1, 1])}∪{(ψ,[max (0, α) , α]) : (ψ, I)∈IK, and I>Inc(IK ∪ {(φ, 1)})} ∪ {(ψ, [0,max(0, 2α)]) : (ψ, I)∈IK, and I=Inc(IK ∪ {(φ, 1)}) > 0}.

Note that item 1 corresponds to the case where secondbest(IK)=0.

Example 5. Let us consider Example 1 with the new evidence being φ=¬a. From this example, Φ={a∨¬b} and Φ∪{φ} has exactly one model. We face the case of Proposition 12, 2nd item. Therefore, IKφ={(¬a, [1, 1]), (a∧b, [0, .1/.4]), (a∨¬b, [0, .5/.6])}.

Computing IπIKφ according to Definition 4, gives exactly the same distribution as the one of Example 3 when conditioned on φ=¬a using Propositions 4 and 5.

Algorithm 1 summarizes the main steps for computing IKφ.

Algorithm 1 Syntactic counterpart of conditioning

Input: An interval-based logic base IK and a new evidence φ Output: A new interval-based possibilistic base IKφ such that

end if

The nice features of the proposed conditioning is that:

i) It extends the one used in standard possibility theory: namely when all intervals I, associated with interpretations, are singletons, then ∀ω∈Ω, Iπ(ω|φ)= [π(ω|φ),π(ω|φ)] where π is the unique compatible distribution associated with Iπ. ii) When formulas in IK are in a clausal form then computing the conditioning of an interval-based possibilistic base has the same complexity as the one of conditioning standard possibilistic knowledge bases (namely, when I's are singletons). Indeed, for standard possibilistic knowledge bases K the hardest task consists in computing Inc(K) which can be achieved in time in O(log2(m).SAT ) where SAT is a satisfiability test of a set of propositional clauses and m is the number of different weights in K. For an interval-based knowledge base, the main (hard) tasks in computing IKφ are:

• The computation of Inc(IK∪{(φ,1)}) and Inc(IK ∪ {(φ, 1)}). This is done in O(log2(m).SAT ) where SAT is a satisfiability test of a set of propositional clauses and m is the number of different weights in IK and IK,

• The test whether the sub-bases A or B are consistent or not. This needs only one call to a SAT solver.
• The computation of secondbest(Iπ)=1-min{αi: αi>Inc(IK∪{(φ,1)}) and Aαi is a non-tautological formula} (see Proposition 10). This needs: i) the computation of Inc(IK∪{(φ,1)}), done again in O(log2(m).SAT), and ii) checking for the lowest αi such that Aαi is a non-tautological formula, which is done in linear time (w.r.t the number of clauses in IK).
• Lastly, checking whether Φ={ψ: (ψ, I)∈IK, and I>Inc(IK∪{(φ, 1)})}∪{φ} admits a unique model. This can be done using two calls to a SAT solver. Indeed, checking whether there exists a unique interpretation ω∗ such that IπIK(ω∗ )=IΠIK(φ) comes down to checking whether the formula Φ∪{φ} has a unique model. If this formula is under the clausal form, then this problem is the one of Unique-SAT. This can be done by launching two calls to a SAT solver: the first call is applied to the formula Φ. When it returns a model ω (recall that Φ∪{φ} is consistent), then a second call to a SAT solver with the formula Φ∧¬ω is performed (where ¬ω is a clause composed of the disjunction of literals that are not true in ω). If a SAT solver declares that the extended formula has no model, then we conclude that there exists a unique interpretation ω∗ such that IπIK(ω∗ )=IΠIK(φ). Otherwise the formula Φ∪{φ} has at least two models.

To summarize, the overall complexity is:

Proposition 13. Computing IKφ is O(log2(m).SAT ) where SAT is a satisfiability test of a set propositional clauses and m is the number of different weights in IK and IK.

Proposition 13 shows that the syntactic computation of conditioning an interval-based possibilistic base has exactly the same computational complexity of computing productbased conditioning of standard possibilistic knowledge bases.

7 Conclusions

Interval-based possibilistic logic offers an expressive and a powerful framework for representing and reasoning with uncertain information. This setting was only specified for static situations and no form of conditioning has been proposed for updating the knowledge and the beliefs. In this paper, we showed that conditioning can be handled in a natural and safe way and without extra computational cost. More precisely, we proposed a compatible-based conditioning of interval-based possibilistic knowledge bases. This conditioning reflects viewing an interval-based possibilistic base as a set of compatible bases. We showed that when min-based conditioning is applied over the set of compatible distributions then the obtained result is not guaranteed to be an interval possibility distribution while applying product-based conditioning on the set compatible possible distributions gives an interval-based possibility distribution. We provided the exact computations of lower and upper endpoints of intervals associated with each interpretation of the conditioned intervalbased possibility distributions. Lastly, we provided a syntactic counterpart of the compatible-based conditioning that does not imply extra computational cost.