Interval-Based Possibilistic Logic

1 Introduction

Possibilistic logic (e.g. [Dubois et al., 1994; Dubois and Prade, 2004]) is an important framework for representing and reasoning with uncertain and inconsistent pieces of information. Uncertainty is syntactically represented by a set of weighted formulas of the formK = {〈ϕi, αi〉 : i = 1, .., n} where ϕi's are propositional formulas and αi's are real numbers belonging to [0,1]. The pair 〈ϕi, αi〉 means that ϕi is certain (or important) to at least a degree αi. An inference machinery has been proposed in [Lang, 2000] to derive plausible conclusions from a possibilistic knowledge base, which needs log2(m) calls to the satisfiability test of a set of propositional clauses (SAT), where m is the number of different degrees used in K. Uncertainty is also represented at the semantic level by associating a possibility degree with each possible world (or interpretation).

2 Universit´e Paris Descartes LIPADE - France julien.rossit@parisdescartes.fr

Several extensions of possibilistic logic have been proposed to replace the unit interval [0, 1] by some complete lattice or even by a partial pre-order. In [Lafage et al., 1999], a set of assumptions which supports a formula is used instead of a real positive number. In [Dubois et al., 1992], the degrees are replaced by a set of positive values (not necessarily in [0, 1]) representing a time frame where the formulas are known to be true. In [Benferhat et al., 2004; Benferhat and Prade, 2006], a partially ordered extension of possibilistic logic has been proposed. However, these extensions either increases the computational complexity (e.g. when dealing with partially pre-ordered information) or fail to generalize possibilistic logic. For instance, the so-called timed possibilistic logic proposed in [Dubois et al., 1992] does not recover standard possibilistic logic when sets of times assigned to formulas are singletons belonging to [0, 1].

This paper is in the spirit of these extensions of possibilistic logic. It studies theoretical foundations, with an analysis of computational issues, of interval-based possibilistic logic. The question addressed in this paper is whether one can extends and increases the expressive power of standard possibilistic logic, by representing imprecision regarding uncertainty associated with formulas, without increasing the computational complexity of the reasoning process.

The framework considered in this paper is the one of interval-based possibilistic logic. At the syntactic level, pieces of information are represented by an interval-based possibilistic knowledge base, of the form IK = {〈ϕi, Ii〉 : i = 1, .., n} where Ii = [αi, βi] is a closed sub-interval of ]0, 1]. The pair 〈ϕi, Ii〉, called an interval-based weighted formula, means that the weight associated with ϕi is one of the elements in Ii. This disjunctive interpretation of 〈ϕi, Ii〉 should not be confused with the conjunctive interpretation (used in [Dubois et al., 1992]), which corresponds to the fact that ∀αi ∈ Ii, 〈ϕi, αi〉 is true. The conjunctive interpretation of intervals makes sense when considering temporal information, where 〈ϕi, Ii〉 means that ϕi is true in all the interval time Ii.

Similarly, the semantic of interval-based possibilistic logic is an interval-based possibility distribution, where a subinterval of [0,1] is assigned to each interpretation. Unlike standard possibilistic logic, an interval-based possibility distribution only induces a partial pre-order over the set of interpretations.

On the basis of a disjunctive interpretation of intervals, we propose to view an interval-based knowledge base as a family of compatible standard possibilistic knowledge bases. A compatible possibilistic base is obtained by considering a possible weight from the interval associated with each formula. The surprising and interesting result is that reasoning with the set of all compatible possibilistic bases is equivalent to define an inconsistency level of an interval-based possibilistic base that extends the one used in standard possibilistic logic. As a consequence, we show that reasoning from interval-based possibilistic knowledge bases is not more expensive than reasoning from standard possibilistic bases. Hence, we extend standard possibilistic logic framework without extra computational cost. We also provide a semantic characterization where an interval-based possibilistic knowledge base induces a unique partial pre-ordering on a set of interpretations.

Section 2 presents a brief refresher on possibilistic logic. Section 3 and Section 4 study the semantic and syntactic representations of interval-based possibilistic logic. Section 5 studies the inference process and its computational issues. Section 6 proposes alternative consequence relations from interval-based possibilistic bases by only considering a selection of compatible possibilistic bases. Section 7 discusses related works.

2 A brief refresher on possibilistic logic

2.1 Possibility distributions

We consider a finite propositional language L. We denote by Ω the finite set of interpretations of L and by ω an element of Ω. A possibility distribution, denoted by π, is a function from Ω to [0, 1]. π(ω) represents the degree of compatibility (or consistency) of the interpretation ω with the available knowledge. π(ω) = 1 means that ω is fully consistent with available knowledge, while π(ω) = 0 means that ω is impossible. π(ω) > π(ω′ ) simply means that ω is more compatible than ω′ . A possibility distribution π is said to be normalized if there exists an interpretation ω such that π(ω) = 1. It is said to be subnormalized otherwise. Subnormalized possibility distributions encode inconsistent sets of beliefs.

A possibility distribution allows to define two functions from L to [0, 1] called possibility and necessity measures, denoted by Π and N, and defined by:

Π(ϕ) measures to what extent the formula ϕ is compatible with the available knowledge while N(ϕ) measures to what extent it is entailed.

Given a possibility distribution π encoding some available knowledge, a formula ϕ is said to be a consequence of π, defined by π |=π ϕ, iff Π(ϕ) > Π(¬ϕ). Intuitively, ϕ is a consequence of π if the best models of ϕ (namely the models of ϕ having a highest degree) are more plausible (or more preferred) than the best models of ¬ϕ.

2.2 Possibilistic knowledge bases

A possibilistic formula is a tuple 〈ϕ, α〉 where ϕ is an element of L and α ∈ (0, 1] is a valuation of ϕ representing N(ϕ).

Note that no formula can be of type 〈ϕ, 0〉 as it brings no information. A possibilistic base K = {〈ϕi, αi〉, 1 ≤ i ≤ n} is simply a set of possibilistic formulas.

An important notion that plays a central role in the inference process in the one of strict α-cut. A strict α-cut, denoted by Kα, is a set of propositional formulas defined by Kα = {ϕ : 〈ϕ, β〉 ∈ K and β > α}. The strict α-cut is useful to measure the consistency degree of K defined by Inc(K) = max{α : Kα is inconsistent or α = 0}.

If Inc(K) = 0 then K is said to be completely consistent. If a possibilistic base is partially inconsistent, then Inc(K) can be seen as a threshold below which every formulas is considered as not enough entrenched to be taken into account in the inference process. More precisely, we define the notion of core of knowledge base as composed of formulas with a certainty degree greater than Inc(K), namely

A formula ϕ is a consequence of a possibilistic base K, denoted by K ⊢π ϕ, iff Core(K) ⊢ ϕ.

A possibilistic knowledge base is one of well-known compact representations of a possibility distribution. Given a possibilistic base K, we can generate a unique possibility distribution where interpretations ω satisfying all propositional formulas in K have the highest possible degree π(ω) = 1 (since they are fully consistent), whereas the others are pre-ordered w.r.t. highest formulas they falsify. More formally:

The following completeness and soundness result holds:

3 Interval-based possibility distribution

The aim of this section is to study a more general framework, where uncertainty is not encoded with a single necessity value but by means of an interval of possible degrees. This framework allows to introduce an imprecision on priorities associated with beliefs. We use real number based intervals I = [α, β] ⊆ [0, 1] to encode uncertainty associated with formulas. We denote by I the set of all intervals over [0, 1].

Operations on intervals Given I1 = [α1, β1] and I2 = [α2, β2] two intervals, we define the following operations which will be used in the whole paper, and which will guarantee soundness of results presented in this paper. In particular, they allow the extension of standard possibilistic logic when intervals are singletons of the form [α, α].

• Max of intervals: Given a set of intervals Ii = [αi, βi] M{I1, . . . , In} = [max{α1, . . . , αn}, max{β1, . . . , βn}]
• Reverse of an interval: 1 ⊖ I1 = [1 - β1, 1 - α1]
• Comparing intervals: I1 ◁ I2 if β1 < α2

Intuitively, when I1 and I2 are associated with two formulas ϕ1 and ϕ2, then I1◁I2 means that the formula ϕ2 is strictly preferred to ϕ1. It is clearly a safe (but cautious) interpretation of preference. Indeed using the comparative relation ◁, 〈ϕ2, I2〉 is preferred to 〈ϕ1, I1〉 if whatever the degree assigned to ϕ2

from I2, it will be greater than each degree assigned to ϕ1 from I1. Other possible definitions of ◁ will be studied in section 6. Interval-based and compatible possibility distribution 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 only induces a partial pre-ordering between interpretations defined by ω < ω′ (ω′ is more preferred than ω) if and only if πI(ω) ◁ πI(ω′ ). Since ◁ is a partial pre-order, an interval-based possibility distribution only induces a partial pre-order on interpretation. We interpret an interval-based possibility distribution as a family of compatible standard possibility distributions defined by:

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

Of course, compatible distributions are not unique. We denote by Cmp(πI) the set of all compatible possibility distributions with πI . An interval-based possibility distribution is said to be normalized if there exists ω, s.t. πI(ω) = [1, 1]. One can easily check that πI is normalized if and only if each of its compatible possibility distribution is also normalized.

Necessity and possibility measures A natural way to define the counterparts of possibility and necessity measures associated with a formula ϕ from an interval-based possibility distribution is to use the set of all compatible distributions, namely:

Definition 2 Let πI be an interval-based possibility distribution and let ϕ be a formula. Then :

The interval of possibility degrees associated with a formula represents all possible values that can be obtained from the set of all compatible distributions. The following proposition shows that possibility and necessity measures can be equivalently and directly computed using interval-based possibility distributions.

Proposition 1 Let πI be an interval-based possibility distribution and let ϕ be a formula. Then :

with 1⊖ and M respectively the reverse and the max operations on intervals defined above.

One can show that in the particular case where intervals in a possibility distribution are only consisting of singletons, then our approach recovers the standard definitions of possibilistic logic measures. Namely:

Proposition 2 In the case where intervals within πI only consist in singletons (namely for all ω, πI(ω) = [α, α]) then i) πI has a unique compatible possibility distribution π and ii) ΠI(ϕ) = [Π(ϕ), Π(ϕ)] and NI(ϕ) = [N(ϕ), N(ϕ)] where N and Π are standard possibilistic measures.

Definition 3 Given an interval-based possibility distribution πI , a formula ϕ is said to be accepted or a consequence of πI , denoted by πI |=I ϕ, iff ΠI(¬ϕ) ◁ ΠI (ϕ).

It can be shown that Definition 3 can be restated in terms of compatible possibility distributions, namely:

Clearly, at the semantic level, the use of compatible possibility distributions represents a solid justification of the main concepts of interval-based possibilitic logic: interval-based possibility measure, necessity measure and normalized condition. Next section shows that this is also the case for syntactic representations of interval-based possibilistic logic.

4 Interval-based possibilistic bases

We now study the syntactic representation of interval-based possibilistic logic. We generalize the notion of a possibilistic base to an interval-based possibilistic knowledge base.

Definition 4 (Interval-based possibilistic base) An intervalbased possibilistic base, denoted by IK, is a multi-set of formulas associated with intervals:

The intuitive interpretation of 〈ϕ, I〉 is that the certainty degree of ϕ is one of the elements of I = [α, β]. As in the case of standard possibilistic bases, we do not allow α to be equal to 0, since only somewhat accepted pieces of information are explicitly represented. The use of open intervals and intervals that include 0 is left for further research.

An interval-based possibilistic base IK can be viewed as a family of standard possibilistic bases called compatible bases. A possibilistic base K is said to be compatible with IK iff there exists a bijective function from IK to K such that for each formula associated with an interval I in IK, the degree of this formula in K is an element of I. More formally:

Definition 5 (Compatible possibilistic base) A possibilistic base K is said to be compatible with an interval-based possibilistic base IK iff there exists a bijection f from IK to K s.t. f(〈ϕ, [α, β]〉) = 〈ϕ, δ〉 ∈ K s.t. α ≤ δ ≤ β

Namely, compatible possibilistic bases are obtained from interval-based possibilistic bases by replacing each intervalbased possibilistic formula 〈ϕ, I〉 by a standard possibilistic formula 〈ϕ, δ〉 where δ ∈ I. Each compatible possibilistic base is such that K = {〈ϕ, δ〉 : 〈ϕ, I〉 ∈ IK and δ ∈ I}.

We also denote by Cmp(IK) the infinite set of all compatible possibilistic bases associated with an interval-based possibilistic base IK.

Given an interval-based possibilistic base IK, we define two particular compatible possibilistic bases IKlb and IKub by selecting either lower bounds of intervals (pessimistic point of view) or upper bounds of intervals (optimistic point of view):

Example 1 We will use the following interval-based possibilistic base to illustrate main concepts of this paper:

Table 1: Examples of compatible bases

4.1 Inference from compatible bases

The inference relation from an interval-based possibilistic formula can be defined from the set of compatible bases. Namely, a formula ϕ is a plausible conclusion from an interval-based possibilistic base IK iff it can be deduced from each possibilistic base in Cmp(IK). Namely:

where ⊢π is defined is section 2.2.

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

As in standard possibilistic logic, an interval-based knowledge base IK is also a compact representation of an interval-based possibility distribution πIK. The possibility distribution can be equivalently obtained using: i) an extension of the definition of πK given in Section 2.2 to deal with intervals, ii) possibility distributions associated with compatible bases, and iii) the two particular compatible bases IKlb and IKub. This is summarized by Definition 6 and Proposition 3

Definition 6 (Interval-based possibility distribution) Let IK be an interval-based possibilistic base, then:

where πK is a standard possibilistic distribution associated with the compatible base K.

Proposition 3 πIK given in Definition 6 is equivalent to:

1. πIK(ω) = [πIKub (ω), πIKlb (ω)], namely πIK(ω) is bounded by weights associated with ω with respect to the particular bases IKlb and IKub

An important result is that inference relation from πIK is equivalent to consider the inference relation based on all compatible bases. Namely, the following completeness and soundness result also holds for interval-based possibilistic logic:

Proposition 4 Let IK be an interval-based possibilistic base then IK |=c ϕ iff ΠIK(¬ϕ) ◁ ΠIK (ϕ).

Example 2 From Example 1, we have IKlb = {〈a, .7〉, 〈a ∧ b, .55〉, 〈¬a, .5〉, 〈¬b, .1〉} and IKub = {〈a, .9〉, 〈a ∧ b, .8〉, 〈¬a, .6〉, 〈¬b, .3〉}. Table 2 gives the possibility distribution induced by IKlb and IKub.

From Table 2, we have, for instance, πIK |= a since ΠIK(¬a) = [.5, .6] ◁ ΠIK(a) = [.7, .9].

5 Computational issues analysis

5.1 Inconsistency degree

The previous section provides the definition of an inference relation from an interval-based possibilistic belief base using the concept of compatible bases or its associated interval-based possibility distribution. This section focuses on computational issues by proposing a syntactic characterization of inference relation. It is based on a natural extension of the notion of inconsistency degree and the notion of core of a possibilistic base used in standard possibilistic logic (see Section 2).

Again, one way to define the inconsistency associated with an interval-based possibilistic base is to consider the set of all inconsistency values associated with each possibilistic base which is compatible with IK. Namely:

Definition 7 (Interval-based inconsistency degree) Let IK be an interval-based possibilistic base then:

The following proposition shows that Inc(IK), the set of inconsistency degrees associated with all compatible bases, is an interval. Namely:

Proposition 5 Let IK be an interval-based possibilistic base then Inc(IK) = [Inc(IKlb), Inc(IKub)].

5.2 Core of an interval-based possibilistic base

The core of IK is simply the set of propositional formulas whose associated intervals are higher than Inc(IK) with respect to ◁ given in the section 4.1. Namely:

Definition 8 Let IK be an interval-based possibilistic base then Core(IK) = {ϕ : 〈ϕ, I〉 ∈ IK and Inc(IK) ◁ I}.

Proposition 6 shows that Core(IK) is consistent and is included in the core of each compatible base, namely:

Proposition 6 Let IK be an interval-based possibilistic base then:

1. Core(IK) is consistent;

Lastly, the following proposition shows that plausible conclusions derived from Core(IK) are the same as the ones obtained from the whole set of compatible bases. As a corollary they are also the same as the ones provided at the semantical level.

Proposition 7 Let IK be an interval-based possibilistic base then ∀ψ ∈ L:

Example 3 From Example 1, we have IKlb = {〈a, .7〉, 〈a ∧ b, .55〉, 〈¬a, .5〉, 〈¬b, .1〉} and IKub = {〈a, .9〉, 〈a ∧ b, .8〉, 〈¬a, .6〉, 〈¬b, .3〉}. Hence, we obtain Inc(IKlb) = .5 and Inc(IKub) = .6 and then Inc(IK) = [.5, .6].

Thus, Core(IK) = {a}. One can check that conclusions obtained in Example 3 are equivalent to the ones using Core(IK).

5.3 Computational complexity

This subsection analyses computational complexity of our inference process. Recall that the decision problem "Is a formula ψ a consequence of a standard possibilistic base?" is Δ2p -complete [Nebel, 1994]. Since when intervals are singletons the inference from interval-based possibilistic bases corresponds to the one of standard possibilistic logic, our inference relation is at least in Δ2p . In fact, it is Δ2p - complete:

Proposition 8 The decision problem "Is a formula ψ a consequence of an interval-based possibilistic base?" is a Δ2p - complete problem.

Proposition 8 shows that interval-based possibilistic bases offer more flexibility for representing uncertain information without extra computational cost. The computational complexity of reasoning from such bases indeed is the same order of magnitude as the one obtained from standard possibilistic bases.

Now we explicit an algorithm (Algorithm 1) which is in O(log2(n) ∗ SAT) where SAT is the propositional satisfiability test and n = max(mlb,mub), where mlb (resp. mub) is the number of different degrees in IKlb (resp. IKub). The algorithm first computes Core(IK). This is done by determining IKlb and IKub and their associated inconsistency degrees (Steps 1-5). These steps need 2.log2(n) calls to a SAT oracle. Steps 6-10 compute Core(IK) from IK by considering propositional formulas ϕ such that their associated interval is greater than Inc(IK). This step is in O(|IK|) where |IK| is the number of formulas in IK. The last step needs one call to SAT to check whether ψ is a consequence of Core(IK). Hence, deriving plausible conclusions can be achieved in O(log2(N)) calls to the SAT problem.

6 Other interpretations of intervals

In the previous section, we considered a safe interpretation of interval-based possibilistic knowledge bases (resp. possibility distributions) by considering all possible compatible knowledge bases (resp. possibilistic distributions). This leads to a cautious but safe inference relation based on Core(IK) which uses the comparative relation ◁. The comparative relation ◁ was used in order to recover the inference from all standard compatible bases. The question considered in this section is whether one may go beyond this inference relation by considering other comparative relations rather than the one used in the previous section, namely ◁. We recall that I ◁ I ′ holds iff every element of I ′ is preferred to every element of I. Of Algorithm 1 Computing inferences for interval-based possibilistic knowledge bases

Input: IK, ψ Output: True if ψ is a consequence of IK. False otherwise.

• 1: Compute IKlb
• 2: Compute Inc(IKlb)
• 3: Compute IKub
• 4: Compute Inc(IKub)
• 5: Inc(IK) ← [Inc(IKlb), Inc(IKub)]
• 6: Core(IK) ← ∅
• 7: for all 〈ϕ, I〉 ∈ IK do
• 8: if Inc(IK) ◁ I then
• 9: Core(IK) ← Core(IK) ∪ {ϕ}
• 10: end if
• 11: end for
• 12: return CoreIK ⊢ ψ

course, the obtained inference relations should also extend possibilistic logic inference when intervals are singletons. In this section, we propose to consider alternative definitions of preference and their consequences in terms of inferences in our framework.

Definition 9 Let I = [α, β] and I ′ = [α′ , β′ ] be two intervals in I. Then the following pre-orders are defined by:

• I ◁1 I ′ iff α < α′ and β < β′ ;
• I ◁2 I ′ iff α < α′ ;
• I ◁3 I ′ iff β < β′ .

Intuitively, I ◁1 I ′ can be understand as "there exists an element in I ′ which is preferred to any element of I". I ◁2 I ′ can be understand as "the least element in I is less preferred than the least element in I ′ ". I ◁3 I ′ is dual to ◁2 and can be understand as "the best element in I is less preferred than the best element in I ′ ".

Clearly, the following statements hold: (i) if I ◁ I ′ then I ◁1 I ′ ; (ii) if I ◁1 I ′ then I ◁2 I ′ and I ◁3 I ′ ; (iii) if I ◁2 I ′ and I ◁3 I ′ then I ◁1 I ′ .

These comparative relations give birth to new inferences in the interval-based possibilistic framework by replacing in Definition 8 ◁ by ◁1, ◁2 or ◁3. The obtained definitions are denoted by Core◁i (IK) and their associated inference relations, denoted by ⊢i, are defined by: ∀ϕ ∈ L, IK ⊢i ϕ iff Core◁i (IK) ⊢ ϕ

Example 4 Let IK2 = {〈a, [.4, .9]〉, 〈¬a ∨¬b, [.2, .7]〉, 〈¬a ∨ b, [.3, .5]〉} be the interval-based possibilistic base represented by Figure 1.

The inconsistency degree of IK2 is Inc(IK2) = [.2, .5]. In this example, we have: using ◁, we have Core(IK2) = ∅; using ◁1, IK2 ⊢1 ψ iff Core◁1 (IK2) = {a} ⊢ ψ; using ◁2,

The following propositions summarizes main results of our inference relations:

Proposition 9 Let IK be an interval-based possibilistic base

• For all ◁i, Core◁i (IK) is consistent.
• For all i = 1, ... , 3, the decision problem "Is a formula ϕ a consequence of a standard possibilistic base IK using ⊢i?" is Δ2p -complete.
• If intervals are singletons, then for all ◁i, ⊢i is equivalent to ⊢c. Namely, ⊢i extends standard possibilistic inference.
• For all ◁i, ⊢c is more cautious than ⊢i.
• ⊢1 is more cautious than ⊢2 and ⊢3.

However, ⊢2 is incomparable with ⊢3, as shown by Example 4 where IK2 ⊢2 a ∧ b and IK2 ⊢3 a ∧ ¬b.

7 Related works

In [Dubois et al., 1992], it has been proposed an extension of possibilistic logic in order to deal with temporal information. Formulas are valued with finite sets of values whose boundaries are any real number (they can be interval and they are not necessarily in [0, 1]) representing the time frame where the formula is certainly true, i.e. the necessity value is true for every element of the intervals. The underpinning semantics is different from the present work. It is thus dual to our interpretation, where we used disjunctive interpretation by considering only one element in the interval. Therefore, the tools and all operators used in [Dubois et al., 1992] (such as the intersection and the union operators) differ from the ones used in this paper. The difference between the two approaches is explained by different interpretations associated with intervals. Their framework makes sense for reasoning with temporal information where our framework is more oriented to situations where the uncertainty rank is imprecise. However, an important difference is that our approach extends the standard possibilistic logic while the proposal made in [Dubois et al., 1992] does not. Indeed, for instance if ω1 and ω2 are the only models of ϕ, and if π(ω1) = [.3, .3], π(ω2) = [.4, .4] (namely singletons), then with our approach we get Π(ϕ) = [.4, .4], while in [Dubois et al., 1992] we get Π(ϕ) = [.3, .4] and we are no longer in standard possibilistic logic.

The logic of supporters proposed by Lafage and al. [Lafage et al., 1999] is very close to the one given in [Dubois et al., 1992]. The main difference consists again in the meaning of intervals: they are considered as justification (in the sense of ATMs) of a formula. This approach also has a conjunctive interpretation.

In a recent paper, Marquis and ¨Ozt¨urk [Marquis and ¨Ozt¨urk, 2009] propose to encode preferences by means of formulas weighted by intervals. The intervals do not represent a certainty degree associated with the formula but a knowledge about some numerical value. For example, a formula 〈height, ≥, 6, ≤, 7〉 represents the belief that the value height is included between 6 and 7. The aim of their paper is to compactly encode interval orders on interpretations using these weighted formulas. They study some families of aggregation operators, provide several complexity results on dominance and consistency useful in decision theory and deal with preferences. Their work is dedicated to decision problems and they do not investigate the inference problems.

Conclusion

This paper proposed foundations of reasoning with intervalbased possibilistic bases that extends the standard possibilistic framework in the case where all intervals are singletons. The flexibility in representing uncertain information is done using the concept of compatible bases. We showed that possibility measures, necessity measures and possibility distributions can be conveniently computed in the interval-based possibilistic framework without extra computational cost. The deduction problem in the interval-based context is Δ2p -complete.

This paper also provided three additional consequence relations that are only based on selection of compatible possibility distributions. Finally, when intervals are singletons, all consequence relations presented in this paper collapse with the one used in standard possibilistic logic. A future work is to study the fusion and revision process in the interval-based possibilistic logic framework.