Philippe Besnard
email: besnard@irit.fr

Sylvie Doutre
email: doutre@irit.fr

Andreas Herzig
email: herzig@irit.fr

Encoding Argument Graphs in Logic

Argument graphs are a common way to model argumentative reasoning. For reasoning or computational purposes, such graphs may have to be encoded in a given logic. This paper aims at providing a systematic approach for this encoding. This approach relies upon a general, principle-based characterization of argumentation semantics.

1 Dung uses the term argumentation framework instead of argument graph.

Introduction

In order to provide a method to reason about argument graphs [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF], Besnard and Doutre first proposed encodings of such graphs and semantics in propositional logic [START_REF] Besnard | Checking the acceptability of a set of arguments[END_REF]. Further work by different authors following the same idea was published later, e.g. [START_REF] Egly | Answer-set programming encodings for argumentation frameworks[END_REF][START_REF] Amgoud | Argumentation frameworks as constraint satisfaction problems[END_REF][START_REF] Walicki | Finding kernels or solving SAT[END_REF][START_REF] Dyrkolbotn | The same, similar, or just completely different? Equivalence for argumentation in light of logic[END_REF][START_REF] Nofal | Algorithms for decision problems in argument systems under preferred semantics[END_REF]. However, all these approaches were devoted to specific cases in the sense that for each semantics, a dedicated encoding was proposed from scratch. We aim here at a generalization, by defining a systematic approach to encoding argument graphs (which are digraphs) and their semantics in a logic ⊢. Said differently, our objective is to capture the extensions under a given semantics of an argument graph in a given logic (be it propositional logic or any other logic). We hence generalize the approach originally introduced in [START_REF] Besnard | Checking the acceptability of a set of arguments[END_REF] by parametrizing the encoding in various ways, including principles defining a given semantics.

We consider abstract arguments first, and then provide guidelines to extend the approach to structured arguments (made up of a support that infers a conclusion).

Argument Graph and Semantics

Reminder

The notion of an argument graph has been introduced by Dung in [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] 1 . Definition 1. An argument graph is a couple G = (A, R) such that A is a finite set and R ⊆ A × A is a binary relation over A. The elements of the set of vertices A are viewed as a set of abstract arguments, the origin and the structure of which are unspecified. The edges R represent attacks: (a, b) ∈ R, also written aRb, means that a attacks b. A set of arguments S attacks an argument a if a is attacked by some element of S.

Dung introduced several semantics to define which sets of arguments can be considered as collectively acceptable: the admissible, stable, grounded, preferred and complete semantics. The application of a semantics to a given argument graph results in a set of acceptable sets, called extensions. As an example of a semantics, one may consider the stable semantics [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. Definition 2. Given an argument graph G = (A, R), a stable extension S ⊆ A is a set that satisfies the following two conditions:

1. it does not exist two arguments a and b in S such that aRb; 2. for each argument b ∈ S, there exists a ∈ S such that aRb (any argument outside the extension is attacked by the extension).

More generally, a semantics gives a formal definition of a method ruling the argument evaluation process. Extensions under a given semantics σ are called σ-extensions. E σ (G) denotes the set of the σ-extensions of an argument graph G. Following Dung, a huge range of semantics have been defined (see [START_REF] Baroni | Semantics of abstract argument systems[END_REF] for a comprehensive overview). For these semantics, the following notions are essential (where an argument graph

G = (A, R) is assumed). A set S ⊆ A is conflict-free iff ∃a, b ∈ S such that aRb. An argument a ∈ A is defended by S ⊆ A iff ∀b such that bRa, ∃c ∈ S such that cRb. A set of extensions E ⊆ E σ (G) is inclusive-maximal iff ∀E 1 , E 2 ∈ E, if E 1 ⊆ E 2 then E 1 = E 2 .
An admissible set is a conflict-free set that defends all its elements. A stable extension is an admissible set, but not all admissible sets are stable extensions.

The set of preferred extensions of an argument graph is the inclusive-maximal set of its admissible sets.

A number of complexity results have been established for decision problems in abstract argument graphs [START_REF] Dunne | Complexity of abstract argumentation[END_REF]. Two such problems are: Verification VER σ . Given a semantics σ, an argument graph G = (A, R) and a set S ⊆ A, is S a σ-extension of G? Existence EX σ . Given a semantics σ and an argument graph G = (A, R), does G have at least one σ-extension?

For instance, as regards the verification problem [START_REF] Dunne | Complexity of abstract argumentation[END_REF]: VER stable is in P, but VER preferred is coNP-complete. As regards the existence problem, the question of the existence of a stable extension, EX stable , is NP-complete.

Encoding

Given any semantics σ, our objective is to capture the σ-extensions of an argument graph (A, R) in a logic ⊢. The only requirements for this logic are that it should contain all the Boolean connectives (in order to capture "not", "and", and "or").

There are two ways to achieve our objective:

(α) By providing a formula θ σ whose models characterize the set E σ (G) of σextensions of G = (A, R). So the set Mod(θ σ ) of the models of θ σ is isomorphic to the set of σ-extensions of (A, R): every model of θ σ determines a σ-extension of (A, R) and vice-versa.2 (β) By providing a formula θ σ,S , depending on a subset S of A, that is satisfiable if and only if S is a σ-extension of (A, R).

Adopting terminology from [START_REF] Besnard | Checking the acceptability of a set of arguments[END_REF], we call (α) "the model checking approach" and (β) "the satisfiability approach" (answering the verification problem VER σ ).

In (α), we must provide a means to identify extensions in the encoding. (There might for instance be non-effective ways for a model to coincide with an extension.) In the rest of the paper, we will focus on the (β) approach.

An additional issue (γ) may be to find a formula (in the logic ⊢) that is satisfiable iff there exists a σ-extension for the argument graph (existence problem EX σ ). This issue is of interest for the stable semantics for instance, but not for other admissibility-based semantics (preferred, complete, grounded. . .), the empty set being always an admissible set.

Encoding Methodology

Now, we provide a methodology for encoding the σ-extensions of an argument graph in a given logic, following the satisfiability approach previously introduced. We are going to illustrate it by a case study in Section 5.

Encoding Extensions

At the abstract level, given a set of abstract arguments A = {a 1 , a 2 , . . .} and an argument graph G = (A, R), in order to construct θ σ,S , the following questions should be answered:

1. How to represent a subset S of the set of arguments A? For instance, it could be:

χ S = ai∈S a i ∧ aj ∈S ¬a j 2.
How to define that S is a σ-extension of G? For instance, if σ is the stable semantics then we might have:

S is a stable extension of G iff χ S |= a∈A (a ↔ b∈A:bRa ¬b)
In [START_REF] Besnard | Checking the acceptability of a set of arguments[END_REF], it was shown that a∈A (a ↔ b∈A:bRa ¬b) = θ stable . More generally, we are aiming at constructing θ σ,S enjoying the following equivalence:

S is a σ-extension of G iff χ S |= θ σ , i.e., θ σ,S is satisfiable iff χ S |= θ σ 3.
When a semantics involves a notion of maximality or minimality, how to capture the corresponding sets?

Encoding Set-Theoretic Relations

Our methodology for systematic encodings θ σ,S where S is the subset to be tested for being an extension relies on several building bricks and a rule as follows.

-Rule An encoding is of the form

θ σ,S = ϕ S ∧ ϕ S ∧ Ψ S
where ϕ S encodes the necessary conditions for membership in S, ϕ S encodes the sufficient conditions, and Ψ S is a Boolean combination over basic building bricks (intuitively, Ψ S expresses that S enjoys σ).

-Basic Building Bricks3

• Membership in a subset of the arguments: a is an argument in X ⊆ A is encoded as

ϕ (a∈X) =          ϕ (a∈S) if X = S a=x∈X ⊤ if X = S
where for each a ∈ A, we assume a generic formula4 ϕ (a∈S) expressing that "a is in the set of arguments S". • Subset X of the arguments:

ϕ X = a∈X ϕ (a∈X)
• Complement of X in the set of arguments:

ϕ X = a ∈X ¬ϕ (a∈X)
Intuitively, ϕ S expresses that S contains all the elements of S whereas ϕ S expresses that S contains only elements of S.

-Intermediate Building Bricks 1. X ⊆ Y This is captured as a∈A ϕ (a∈X) → ϕ (a∈Y )
2. X is maximal such that Ψ X holds This, which amounts to

Ψ X & ∀Y ⊇ X (Ψ Y → Y ⊆ X), is captured as Ψ X ∧ X⊆Y ∈2 A Ψ Y → a∈A (ϕ (a∈Y ) → ϕ (a∈X) ) 3. X is minimal such that Ψ X holds This, which amounts to Ψ X & ∀Y ⊆ X (Ψ Y → X ⊆ Y ), is captured as Ψ X ∧ X⊇Y ∈2 A Ψ Y → a∈A (ϕ (a∈X) → ϕ (a∈Y ) )
Please bear in mind that, as a consequence of the first building brick, the following holds: In all of the above clauses, whenever X = S (and similarly for Y and Z), ϕ (a∈X) must be encoded as a=x∈X ⊤ else it is encoded as ϕ (a∈S) .

As an illustration, here are the details for the case of maximality:

max: Let us assume that E satisfies Ψ ′ (hence Ψ ′ E holds). Then, for all S ⊂ E, θ σ,S def = ϕ S ∧ ϕ S ∧ Ψ ′ S ∧ S⊆Y ∈2 A Ψ ′ Y → a∈A (ϕ (a∈Y ) → ϕ (a∈S) )
is not satisfiable because the conjunct ϕ S is contradicted by means of

Ψ ′ Y → ϕ Y (for the case Y = E); for a ∈ E \ S, it happens that ϕ S entails ¬ϕ (a∈S) whereas Ψ ′ E → ϕ E yields ϕ (a∈S) (remember, Ψ ′ E holds).

Encoding Semantic Principles

Baroni and Giacomin have shown in [START_REF] Baroni | On principle-based evaluation of extension-based argumentation semantics[END_REF] that the existing argumentation semantics satisfy a number of principles. They have provided a comprehensive list of such principles. From some subsets of these principles, it is possible to characterize existing semantics. Based on such a general characterization of a semantics, the objective in this section is to encode into formulas the principles P 1 . . . P n that define the semantics. This requires two things. One is that we must prepare, from the building bricks listed in Section 3.2, encodings of statements (and their denials) such as:

-"a is in E" -"a attacks b" (in symbols, aRb) and set versions thereof -"S is maximal such that. . . " -. . . The other thing is to provide a concrete list of such principles P . In Section 2 we have already mentioned conflict-freeness, inclusion-maximality, and admissibility. We recall here some of the list in [START_REF] Baroni | On principle-based evaluation of extension-based argumentation semantics[END_REF]:

Conflict-Free Principle. A semantics σ satisfies the C-F principle iff ∀G, ∀E ∈ E σ (G), E is conflict-free.
From the building bricks in Section 3.

ϕ (c∈S) ) → ϕ (a∈S)
Conflict-Free Reinstatement Criterion. A semantics σ satisfies the CFR criterion iff ∀G, ∀E ∈ E σ (G), if a is defended by E and E ∪ {a} is conflictfree then a ∈ E. Now, the CFR criterion can be captured just as the reinstatement criterion, only adding (in the antecedent) a conjunct for conflict-freeness (see above the conflict-free principle).

In addition to the criteria listed in [START_REF] Baroni | On principle-based evaluation of extension-based argumentation semantics[END_REF], we propose the following one: Another encoding is to be found in the example detailed in Section 5.

Complement
The stable semantics is characterized by the conflict-free principle and the complement attack criterion. The stable semantics satisfies the admissibility criterion as well.

A Case Study

There are two approaches, (a) and (f). One approach (a) introduces dedicated atoms in the object language to represent the attack relation. This means that there is a list of fresh Att xy atoms, one for each ordered pair of nodes (x, y) in the graph. The other approach (f) dispenses from such atoms, and the properties to be encoded must be expressed in such a way that reference to attacks can be captured as a range over conjunction or disjunction.

Example

Let us find θ σ,S for σ = stable. The definition for a set of arguments S being conflict-free is ∀a ∈ S ∃b ∈ S bRa

According to the (f)-approach, i.e., no dedicated atom is used, we must reformulate the condition as follows: for all a in S, it is not the case that there exists some b attacking a such that b is in S. The (f)-encoding for being conflict-free is

a∈S ¬ bRa ϕ (b∈S)
or, equivalently,

a∈S bRa ¬ϕ (b∈S)
In the case of stable extensions, we need to additionally encode the property of S attacking its complement:

∀a ∈ S∃b ∈ S bRa
According to the (f)-approach, we must reformulate the condition in the form: for all a not in S, there exists some b attacking a such that b is in S. Hence the (f)-encoding for S attacking its complement is

a ∈S bRa ϕ (b∈S)
Combining both conditions, we obtain the building brick Ψ S (introduced above: the general case) for stable extensions:

Ψ S = ( a∈S bRa ¬ϕ (b∈S) ) ∧ ( a ∈S bRa ϕ (b∈S) )
Conjoining with ϕ S and ϕ S , we obtain:

ϕ S ∧ ϕ S ∧ Ψ S = a∈S (ϕ (a∈S) ∧ bRa ¬ϕ (b∈S) ) ∧ a ∈S (¬ϕ (a∈S) ∧ bRa ϕ (b∈S) )
which is exactly the formula encoding stable extensions in Proposition 10 of [START_REF] Besnard | Checking the acceptability of a set of arguments[END_REF] where ϕ (x∈S) is the atom x.

Towards Encoding Graphs of Structured Arguments

The aim of this section is to indicate how the approach, designed for abstract argument graphs, may be extended to graphs with structured arguments. Our exposition follows [START_REF] Besnard | Special issue: Tutorials on structured argumentation[END_REF].

The very first issue is to choose how to represent nodes of an argumentation graph in this case. Then, arises the question of the representation of edges, and next, of how to define the extensions. Moreover, the properties of the logic underlying the arguments play a role now.

We assume that nodes in the graph (i.e., arguments) enjoy a minimal amount of structure as pairs (A i , c i ) where A i is a set of formulas, the premises of the argument, and c i is a formula, the claim of the argument. Importantly,

A i c i
In any case, our approach involves the following steps.

Representing nodes, with two options:

-Either every two arguments of the form (A i , c i ) and (A i , c ′ i ) are treated as two distinct entities, -or they are treated as equals. The former might be justified on the grounds that we have some (granted, rudimentary) structure within an argument (it is less abstract) and there must be the possibility to detail the content of the attack relation. We choose to leave these two options open.

Representing edges, with the question:

-Is it necessary that the attack relation be captured at the object level, i.e., by a formula of the logic? Whether representing or not (i.e., simply capturing constraints and conditions to be satisfied by the attack relation), we would need the language to include something capturing consistency (and presumably, inference, hence the need for the deduction theorem). E.g., there could be a modal possibility operator ⋄ and a naming device ⌈•⌉. All these would express consistency of support of two arguments in an extension, as for example in

⋄(A i ∧ A j ) → ¬⌈iRj⌉.
Another option would be to use QBF, as done in [START_REF] Arieli | A QBF-based formalization of abstract argumentation semantics[END_REF] to characterize the complexity, or to use Dynamic Logic of Propositional Assignments, as done in [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF] to provide a dynamic account of the construction of extensions. 3. Representing extensions.

As a start, we must decide whether ¬A i is to mean that (A i , c i ) fails to be in the extensions being tested. The answer determines whether or not an argument with the same support as an argument in the extension at hand has to be in the extension. Another point is that extensions are defined as conditions using the attack relation. This may mean building bricks, other than those we have examined, from which various notions of extensions can be defined. 4. Lastly, attention must be paid to properties of the logic that can play a role.

For example, contraposition and transitivity make the inference constraint to turn the conflict between arguments i and j into A i ¬A j as follows:

A i ¬c j (assumption) A j c j (assumption) ¬c j ¬A j (contraposition) A i ¬A j (transitivity)

Conclusion

We have proposed in this paper a methodology to encode an argument graph and a semantics in a given logic. Few constraints are imposed on the logic. We have considered abstract arguments, and we have given guidelines to extend the approach to structured, non-abstract arguments.

In this methodology, we have made the assumption that a semantics is defined by a set of principles. Even though evaluation principles have been put forward by [START_REF] Baroni | Semantics of abstract argument systems[END_REF][START_REF] Baroni | On principle-based evaluation of extension-based argumentation semantics[END_REF], the characterization of a semantics by a set of principles is an issue that has not been addressed yet. The example of the complement attack criterion (mandatory to characterize the stable semantics), shows that in current approaches, criteria are missing to obtain such a characterization.

In line with such a general characterization, it can be noticed that [START_REF] Baroni | SCC-recursiveness: A general schema for argumentation semantics[END_REF] contains a general recursive schema that captures all of Dung's semantics and that is able to capture other admissibility-based, or non-admissibility-based, semantics. However, the schema embeds a "base function", that basically characterizes the extensions of an argument graph made of only one strongly connected component; that is, the semantics is not described by the principles it is based on.

As regards computational issues, [START_REF] Charwat | Implementing abstract argumentation -A survey[END_REF] surveys implementations of abstract argument graphs. Many abstract semantics have been implemented, with various techniques, but none of these implementations is built from a principle-based characterization of the semantics.

We have encoded in this paper a number of semantic principles, but others remain to be defined (and encoded) in order to characterize the existing semantics, and possibly, new semantics as well.

Moreover, the guidelines given to extend the approach to structured, nonabstract arguments, will be further explored.

  2, conflict-freeness can be encoded as 5

bRa ¬(ϕ (a∈S) ∧ ϕ (b∈S) )

Inclusion-Maximality Criterion. A semantics σ satisfies the I-M criterion iff ∀G, E σ (G) is inclusive-maximal.

Here, an encoding has been already explicitly given in Section 3.2.

Encoding defence (for all b such that bRa, there exists c ∈ S such that cRb) is achieved by

bRa cRb ϕ (c∈S)

which can be used in the encoding of the next three principles that are based on defence, as follows.

Admissibility Criterion. A semantics σ satisfies the admissibility criterion iff ∀G, ∀E ∈ E σ (G), if a ∈ E then a is defended by E.

The admissibility criterion can be captured through

ϕ (a∈S) → ( bRa cRb ϕ (c∈S) )

Reinstatement Criterion. A semantics σ satisfies the reinstatement criterion iff ∀G, ∀E ∈ E σ (G), if a is defended by E then a ∈ E.

The reinstatement criterion can be captured by means of ( bRa cRb

  Attack Criterion. A semantics σ satisfies this criterion iff ∀G, ∀E ∈ E σ (G) it holds that ∀b ∈ A if b ∈ E then ∃a ∈ E such that aRb. The complement attack criterion can be captured by means of

a∈A ¬ϕ (a∈S) → bRa ϕ (b∈S)

In the case that Mod(θσ) is isomorphic to Eσ(G) then the following consequence holds: θσ ⊢ ϕ iff ϕ encodes a ⊢-definable property of G.

Remember that an empty conjunction, i.e., a conjunction C(x) γ[x] whose condition C(x) holds for no x, amounts to ⊤. An empty disjunction, i.e., a disjunction C(x) γ[x] whose condition C(x) holds for no x, amounts to ⊥.

By generic formula, we mean a formula that is constructed in a systematic way, by contrast to ad-hoc formulas with no common form. For example, ϕ (a∈S) can be a (provided that, for all arguments a, there is an atom a in the language). This is generic because all such formulas have the same form: an atom naming an argument.

Please observe that S instead of E occurs in the specification of the formula because we construct a formula (parameterized by S) which is satisfiable iff S is an extension.

Acknowledgements. This work benefited from the support of the AMANDE project (ANR-13-BS02-0004) of the French National Research Agency (ANR).


Claudette Cayrol
email: ccayrol@irit.fr

Didier Dubois
email: dubois@irit.fr

Fayc ¸al Touazi
email: faycal.touazi@irit.fr

On the Semantics of Partially Ordered Bases

This paper presents first results toward the extension of possibilistic logic when the total order on formulas is replaced by a partial preorder. Few works have dealt with this matter in the past but they include some by Halpern, and Benferhat et al. Here we focus on semantic aspects, namely the construction of a partial order on interpretations from a partial order on formulas and conversely. It requires the capability of inducing a partial order on subsets of a set from a partial order on its elements. The difficult point lies in the fact that equivalent definitions in the totally ordered case are no longer equivalent in the partially ordered one. We give arguments for selecting one approach extending comparative possibility and its preadditive refinement, pursuing some previous works by Halpern. It comes close to non-monotonic inference relations in the style of Kraus Lehmann and Magidor. We define an intuitively appealing notion of closure of a partially ordered belief base from a semantic standpoint, and show its limitations in terms of expressiveness, due to the fact that a partial ordering on subsets of a set cannot be expressed by means of a single partial order on the sets of elements. We also discuss several existing languages and syntactic inference techniques devised for reasoning from partially ordered belief bases in the light of this difficulty. The long term purpose is to find a proof method adapted to partially ordered formulas, liable of capturing a suitable notion of semantic closure.

Introduction

The basic concept of ordered knowledge base expressing the relative strength of formulas has been studied for more than twenty years in Artificial intelligence. To our knowledge this concept goes back to Rescher's work on plausible reasoning [START_REF] Rescher | Plausible Reasoning[END_REF]. The idea of reasoning from formulas of various strengths is even older, since it goes back to antiquity with the texts of Theophrastus, a disciple of Aristotle, who claimed that the validity of a chain of reasoning is the validity of its weakest link. Possibilistic logic [START_REF] Dubois | Possibilistic logic[END_REF] is a typical example of logic exploiting a totally ordered base and implementing the weakest link principle. It is an extension of propositional logic, sound and complete with respect to a semantics in terms of possibility theory, where a set of models is replaced by a possibility distribution on the interpretations (which are then more or less plausible). It enables problems of inconsistency management [START_REF] Benferhat | Inconsistency management and prioritized syntax-based entailment[END_REF], of revision [START_REF] Dubois | Epistemic entrenchment and possibilistic logic[END_REF] and of information fusion [START_REF] Benferhat | Logique possibiliste et fusion d'informations[END_REF] to be handled in a natural way.

This simple approach has limitations in expressive power. We may go beyond it in several respects:

extending the syntax to give a meaning to negations and disjunctions of weighted formulas, thus joining the syntactic framework of modal logic [START_REF] Dubois | Régles et métarègles en théorie des possibilités[END_REF]; improving the treatment of the degrees attached to the formulas via a refinement of the induced possibility distribution, possibly by means of a partial order [START_REF] Benferhat | Inconsistency management and prioritized syntax-based entailment[END_REF]; making the approach more qualitative, by replacing the weights of certainty by the elements of a lattice, or by a partial order over a finite set of formulas [START_REF] Benferhat | Encoding formulas with partially constrained weights in a possibilistic-like many-sorted propositional logic[END_REF].

This paper paves the way to the systematic study of the last two points, based on scattered existing works. Possibilistic logic exploits the equivalence between the deductive closure of a set of weighted formulas, and a possibility distribution on the interpretations. In case of logical inconsistency, it reasons with the formulas whose certainty level exceeds the global inconsistency degree, leaving out some highly uncertain formulas not concerned by inconsistency (this is called "the drowning effect"). Our idea is to preserve this kind of relation between semantics and syntax in the setting of weaker algebraic frameworks (with partial preorders), while proposing concepts of partially ordered closure accordingly. The following questions seem natural:

-Is it possible to represent a partially ordered set of formulas by a partially ordered set of models? -Is it possible to represent a partially ordered set of models by a partially ordered set of formulas? -Is it possible to define inference rules that account for such a semantics?

To address these questions, we first review how to go from a partial ordering on a set to a partial ordering on its subsets. This point, already reviewed by Halpern [START_REF] Halpern | Defining relative likelihood in partially-ordered preferential structures[END_REF], is tricky because equivalent definitions in the case of a total order are no longer so in the partially ordered setting. Properties of partial orders among sets induced by partial order on elements are studied in detail. Then these results are applied to the definition of semantic inference from partially ordered knowledge bases. This definition poses the problem of representing the semantics of a partially ordered base in terms of a single partial order of its interpretations. We show that in general the partial order on formulas cannot be recovered from the partial order on interpretations it induces, contrary to the totally ordered case. Finally we briefly review existing proposals of syntactic inference that may be used to reason from partially ordered formulas, in the light of this limitation.

Comparing sets of totally ordered elements

Let (S, ≥) be a totally ordered set and let A and B be subsets of S. To extend ≥ to 2 S , a natural idea is to compare A with B by means of logical quantifiers. So, four kinds of relations can be defined:

Definition 1 -Unsafe dominance: A u B iff ∃a ∈ A, b ∈ B, a ≥ b -Optimistic dominance: A o B iff ∀b ∈ B, ∃a ∈ A, a ≥ b -Pessimistic dominance: A p B iff ∀a ∈ A, ∃b ∈ B, a ≥ b -Safe dominance: A s B iff ∀a ∈ A, ∀b ∈ B, a ≥ b
Strict counterparts of these definitions, namely ≻ u , ≻ o , ≻ p , ≻ s can be similarly defined, replacing (S, ≥) by its strict part (S, >) Note that relations ≻ x are not the strict parts of x . The four kinds of weak relations in this definition can be rewritten by comparing their maximal (resp. minimal) elements. Denoting by max(A) (resp. min(A)) any maximal (resp. minimal) element in A:

-Unsafe dominance: A u B iff max(A) ≥ min(B) -Optimistic dominance: A o B iff max(A) ≥ max(B) -Pessimistic dominance: A p B iff min(A) ≥ min(B) -Safe dominance: A s B iff min(A) ≥ max(B) Note that A u B iff ¬(B ≻ s A).
The strict safe dominance ≻ s is a strict partial order that can compare disjoint sets only; and s is not even reflexive. The unsafe dominance is not transitive even if reflexive. The optimistic and pessimistic comparisons are total orders dual to each other in the following sense:

A o B iff B ′
p A where ≥ ′ denotes the inverse of ≥ on S, defined by a ≥ ′ b iff b ≥ a. It is interesting to highlight the point that the latter comparisons can be defined equivalently as:

-Optimistic dominance: A o B iff ∃a ∈ A, ∀b ∈ B, a ≥ b; -Pessimistic dominance: A p B iff ∃b ∈ B, ∀a ∈ A, a ≥ b
These notions can be applied to the representation of uncertainty. Let S denote a set of states. Assume π a possibility distribution on S such that π(s) is the plausibility degree that s is the real world. Let Π the associated possibility measure defined by Π(A) = max s∈A π(s) and N the dual necessity measure defined by [START_REF] Dubois | Possibilistic logic[END_REF]. We have:

N (A) = min s ∈A 1 -π(s) = 1 -Π(A)
-Π(A) ≥ Π(B) iff max(A) ≥ max(B) (this is A o B) -N (A) ≥ N (B) iff max(B) ≥ max(A) (this is B o A)
So the optimistic comparison between A and B is a comparative possibility measure in the sense of Lewis [START_REF] Lewis | Counterfactuals and comparative possibility[END_REF] (see also [START_REF] Dubois | Belief structures, possibility theory and decomposable confidence measures on finite sets[END_REF]), and the optimistic comparison between A and B, which expresses relative certainty, is related to epistemic entrenchment in revision theory [START_REF] Alchourrón | On the logic of theory change: partial meet contraction and revision functions[END_REF]. In the uncertainty framework, safe dominance is never used as it is not representable by a monotonically increasing set function. On the other hand, the pessimistic ordering is monotonically decreasing with inclusion. In the following, we thus concentrate on the optimistic comparison o .

The above definitions also apply to the representation of preferences. Then stating A B accounts for an agent declaring that the truth of the proposition whose models form the set A is preferred to the truth of the proposition whose models form the set B. Interpreting such a statement requires the knowledge of the attitude of the agent, which leads to choosing between the four orderings considered above. The safe dominance is natural in this setting as a very conservative risk-free understanding of A B, akin to interval orderings [START_REF] Fishburn | Interval Orderings[END_REF]. Pessimistic and optimistic dominance are milder views, and both make sense, as explored by Benferhat et al. [START_REF] Benferhat | Towards a possibilistic logic handling of preferences[END_REF], Kaci and van den Torre [START_REF] Kaci | Reasoning with various kinds of preferences: Logic, nonmonotonicity and algorithms[END_REF][START_REF] Kaci | Working With Preferences: Less Is More[END_REF], contrary to the case of representing the plausibility and certainty of formulas. However, preference modelling is not in the scope of this paper.

Let ☎ be a reflexive relation that compares subsets A and B of S, and ✄ its strict part. We enumerate different properties that may be satisfied by these relations in the scope of modeling relative uncertainty.

Compatibility with set-theoretic operations (inclusion, intersection, union)

-Compatibility with Inclusion (CI)

If B ⊆ A then A ☎ B -Orderliness (O) If A ✄ B, A ⊆ A ′ , and B ′ ⊆ B, then A ′ ✄ B ′ -Stability for Union (SU) If A ☎ B then A ∪ C ☎ B ∪ C -Preadditivity (P) If A ∩ (B ∪ C) = ∅ then (B ☎ C iff A ∪ B ☎ A ∪ C) -Self-duality (D) A ☎ B iff B ☎ A Note that (CI)
is never satisfied by a non-reflexive relation while (O) makes sense for a reflexive relation too. (SU) does not make sense for an asymmetric relation (take C = S). Preadditivity and self-duality, like (O) make sense for both ☎ and its strict part. All these properties have been studied in the case of total orders: (CI) and (O) are expected when A ✄ B expresses a greater confidence in A than in B; (SU) characterizes possibility relations o (Lewis [START_REF] Lewis | Counterfactuals and comparative possibility[END_REF], Dubois [START_REF] Dubois | Belief structures, possibility theory and decomposable confidence measures on finite sets[END_REF]). Preadditivity and self-duality hold for probability measures [START_REF] Fishburn | The axioms of subjective probability[END_REF], but also for the relation

A ✄ B iff A \ B ≻ o B \ A [17]. 2. Properties reflecting a qualitative point of view -Qualitativeness (Q) If A ∪ B ✄ C and A ∪ C ✄ B, then A ✄ B ∪ C -Negligibility (N) If A ✄ B and A ✄ C, then A ✄ B ∪ C (Q) is
satisfied by strict parts of possibility relations (≻ o , but not o ) and is found in non-monotonic logic. Negligibility also works for o , it says that one cannot compensate for the low plausibility of a set by adding elements of low plausibility. 3. Properties concerning the deductive closure of partially ordered bases (see Friedman and Halpern [START_REF] Friedman | Plausibility measures: A user's guide[END_REF], Dubois and Prade [START_REF] Dubois | Numerical representations of acceptance[END_REF] and Halpern [START_REF] Halpern | Defining relative likelihood in partially-ordered preferential structures[END_REF]):

-Conditional Closure by Implication (CCI)

If A ⊆ B and A ∩ C ✄ A ∩ C then B ∩ C ✄ B ∩ C -Conditional Closure by Conjunction (CCC) If C ∩ A ✄ C ∩ A and C ∩ B ✄ C ∩ B then C ∩ (A ∩ B) ✄ C ∩ A ∩ B -Left Disjunction (OR) If A ∩ C ✄ A ∩ C and B ∩ C ✄ B ∩ C then (A ∪ B) ∩ C ✄ (A ∪ B) ∩ C -Cut (CUT) If A ∩ B ✄ A ∩ B and A ∩ B ∩ C ✄ A ∩ B ∩ C then A ∩ C ✄ A ∩ C -Cautious Monotony (CM): If A ∩ B ✄ A ∩ B and A ∩ C ✄ A ∩ C then A ∩ B ∩ C ✄ A ∩ B ∩ C
These properties are rather intuitive when the relation A ✄ A is interpreted as "A is an accepted belief", and A ∩ C ✄ A ∩ C as "A is an accepted belief in the context C" [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF][START_REF] Friedman | Plausibility measures: A user's guide[END_REF][START_REF] Dubois | Ordinal and probabilistic representations of acceptance[END_REF]. They hold in the total order setting for the optimistic relation ≻ o , but they are not interesting to consider for reflexive relations (e.g. o ).

Proposition 1 It is easy to see that, for any relation ≫:

(Q), A ≫ B ∪ C. So ≫ satisfies (N). Suppose C ∩A ≫ C ∩A and C ∩B ≫ C ∩B. Let A ′ = A∩B∩C, B ′ = A∩C ∩B, C ′ = A ∩ B ∩ C and D ′ = C ∩ B ∩ A. So, we have A ′ ∪ B ′ ≫ C ′ ∪ D ′ and A ′ ∪ C ′ ≫ B ′ ∪ D ′ . Hence from (O), A ′ ∪ B ′ ∪ D ′ ≫ C ′ , then from (Q) A ′ ≫ B ′ ∪ C ′ ∪ D ′ . So, A ∩ B ∩ C ☎ C ∩ (A ∪ B) = C ∩ A ∩ B. So ≫ satisfies (CCC). Suppose A ∪ C ≫ B ∪ C. Then by (O), A ∪ (C ∪ B) ≫ C. Hence from (Q), A ≫ B ∪ C, then (O) again: A ≫ B.
So ≫ satisfies the converse of (SU).

Comparing sets of partially ordered elements

In this section, we start from a partially ordered set (S, ≥) and we consider the construction of a relation ☎ induced by ≥ for comparing subsets of S. In the scope of representing comparative belief and plausibility, the last section has shown that we can restrict to the optimistic comparison of sets. In the following, we focus on the generalization of optimistic dominance to the case of partially ordered sets. It has been noticed (see section 2) that there are two possible definitions of the optimistic dominance, that are equivalent in the total order setting. However they are no longer so in the partial order setting, as first noticed by Halpern [START_REF] Halpern | Defining relative likelihood in partially-ordered preferential structures[END_REF]. As a consequence, in order to define a semantics for partially ordered logical bases, we have to study these different relations and to choose an appropriate one according to the properties they satisfy.

As usual, given a reflexive and transitive relation on S, denoted by ≥, s ′ > s is an abbreviation for "(s ′ ≥ s) and not (s ≥ s ′ )". The relation > is the strict partial order determined by ≥. It is an irreflexive and transitive relation on S. s ′ ∼ s is an abbreviation for "(s ′ ≥ s) and (s ≥ s ′ )". The relation ∼ is the equivalence relation determined by ≥. s ′ ≈ s is an abbreviation for "(neither (s ′ ≥ s) nor (s ≥ s ′ )". It is the incomparability relation determined by ≥. If this relation is empty, the relation ≥ is a total preorder. On the contrary, given a transitive and asymetric relation >, the relation s ′ ≈ s if and only if neither s ′ > s nor s > s ′ is its associated incomparability relation (while s ′ ∼ s reduces to the equality relation).

Let (S, ≥) a partially ordered set, and X ⊆ S. s ∈ X is maximal for ≥ in X if and only if we do not have s ′ > s for any s ′ ∈ X. M (X, ≥) (M (X) for short) denotes the set of the maximal elements in X according to ≥.

The optimistic comparison between A and B is based on the comparison between M (A) and M (B). In the total order case, it can be defined in two ways, which are no longer equivalent in the partial case. We call them weak optimistic dominance and strong optimistic dominance in the following.

Weak optimistic dominance

Here again, various definitions can be proposed according to whether one starts from a strict order or not on S.

Definition 2 (Weak optimistic dominance)

Weak optimistic strict dominance:

A ≻ wos B iff A = ∅ and ∀b ∈ B, ∃a ∈ A, a > b.

Weak optimistic loose dominance:

A wol B iff ∀b ∈ B, ∃a ∈ A, a ≥ b.

Strict order determined by

wol : A ≻ wol B iff A wol B and ¬(B wol A).
In other words,

A ≻ wol B iff ∀b ∈ B, ∃a ∈ A, a ≥ b and ∃a ′ ∈ A, ∀b ∈ B, either a ′ > b or a ′ ≈ b.
These relations are respectively denoted by ≻ s , s and ≻ ′ by Halpern [START_REF] Halpern | Defining relative likelihood in partially-ordered preferential structures[END_REF]. The relation ≻ wos is a strict partial order (asymetric and transitive) on 2 S . We have always A ≻ wos ∅, except if A is empty. The relation wol is reflexive and transitive and such that A wol ∅, but not

∅ wol B except if B is empty. Finally, if A ≻ wos B then A ≻ wol B. The converse is generally false except if ≥ is a complete order.
The following proposition shows that the weak optimistic dominance is appropriate for representing relative plausibility.

Proposition 2 The weak optimistic strict dominance ≻ wos is a strict partial order which satisfies Qualitativeness (Q), Orderliness (O), Left Disjunction (OR), (CUT) and (CM). The weak optimistic loose dominance wol satisfies Compatibility with inclusion (CI), Orderliness (O), Negligibility (N), Stability for union (SU). The relation ≻ wol satisfies Orderliness (O) and Conditional Closure by Implication (CCI).

Corollary 1 The weak optimistic strict dominance ≻ wos satisfies the converse of (SU), Negligibility (N), Conditional Closure by Implication (CCI) and Conditional Closure by Conjunction (CCC).

Note that, as shown by Halpern [START_REF] Halpern | Defining relative likelihood in partially-ordered preferential structures[END_REF], the relation wol is generally not qualitative and the relation ≻ wol does not satisfy the property of Negligibility. Moreover, the relation ≻ wol neither satisfies the property OR nor the property CUT as shown below:

Example 1 Let S = {a, b, c, d, e, f, g, h} be a partially ordered set with f ∼ h, e ∼ g, f > a, e > b, a > c and b > d.

OR : Let A = {a, c, e, g}, B = {b, d, f, h} and C = {a, b, e, f } be three subsets of S.

We have b,c,d,e,f,g,h},B = {a,b,c,e,g, h} and C = {a, b, d, g, h} be three subsets of S.

A ∩ C ≻ wol A ∩ C and B ∩ C ≻ wol B ∩ C but not (A ∪ B) ∩ C ≻ wol (A ∪ B) ∩ C. CUT : Let A = {a,
We have A∩B ≻ wol A∩B and A∩B∩C ≻ wol A∩B∩C but not A∩C ≻ wol A∩C.

It is clear that as a result, the relation ≻ wos is the richest one to represent relative plausibility. But note that it has no non trivial associated equivalence relation (but for A ∼ wos B if and only if A = B).

Strong optimistic dominance

The alternative approach, not considered by [START_REF] Halpern | Defining relative likelihood in partially-ordered preferential structures[END_REF], consists in assuming, if A ✄ B, that one element in A dominates all elements in B. As before, various definitions can be proposed according to whether one uses a strict order or not on S. Note that with the above definitions, if

A = ∅, A ≻ Sos ∅ and never ∅ ≻ Sos B. The relation ≻ Sos is a strict partial order on 2 S . Finally, if A ≻ Sos B then A ≻ Sol B.
Obviously, the strong relations are stronger than the weak relations, namely: If A ≻ Sos B then A ≻ wos B and if A Sol B then A wol B. The converse is true only if ≥ is a complete order on S. So, we also have: If A ≻ Sos B then A ≻ wol B. However there is no entailment between the relations ≻ Sol and ≻ wol as shown by the following counterexamples:

Example 2 Let S = {a 1 , a 2 , b 1 , b 2 , b 3 } with a 1 ∼ b 1 > b 3 and a 2 > b 2 . Then {a 1 , a 2 } ≻ wol {b 1 , b 2 , b 3 }, but it is false that {a 1 , a 2 } ≻ Sol {b 1 , b 2 , b 3 }. Example 3 Let S = {a 1 , a 2 , b 1 , b 2 , b 3 } with a 1 ∼ b 1 > b 3 , and a 1 > b 2 > a 2 . Then {a 1 , a 2 } ≻ Sol {b 1 , b 2 , b 3 }, but it is false that {a 1 , a 2 } ≻ wol {b 1 , b 2 , b 3 }.
As indicated by Benferhat, Lagrue, Papini [START_REF] Benferhat | Reasoning with partially ordered information in a possibilistic logic framework[END_REF], the relation ≻ Sos contains many incomparabilities, and Sol does not satisfy Compatibility with Inclusion. Indeed, if A ⊆ B, it is not obvious that there exists b ∈ B such that b ≥ a, ∀a ∈ A. In fact, Sol is thus not even reflexive, even if it is transitive. Finally, A ≻ Sos B implies A ≻ Sol B. The converse is not true except when ≥ is a complete order on S. As for properties:

= {a, c}. We have A ∩ B ≻ Sos A ∩ B , A ∩ B ∩ C ≻ Sos A ∩ B ∩ C but we don't haveA ∩ C ≻ Sos A ∩ C. So (CUT) is not satisfied.
Lastly, suppose ∃a ∈ A∩C, ∀x ∈ A∩C a > x, and ∃b ∈ B∩C, ∀x ∈ B∩C b > x then if a and b are not comparable, there may be no c ∈ (A ∪ B) ∩ C that alone can dominate all elements in (A ∪ B) ∩ C. So (OR) is not satisfied either.

So the weak optimistic dominance is a richer concept than the strong one.

Refinement of partial preorders induced between subsets

None of the relations presented in the above sections satisfies the property of Preadditivity, which considers that the common part of two sets should play no role in the comparison. A preadditive approach for comparing two sets A and B consists in eliminating the common part and then comparing A \ B and B \ A. This is not a new idea (see [START_REF] Halpern | Defining relative likelihood in partially-ordered preferential structures[END_REF] for a bibliography). In the following we consider the refinement of the weak optimistic dominance. These relations are respectively denoted by ✄ 6 , ✄ 4 and ✄ 5 in Halpern [START_REF] Halpern | Defining relative likelihood in partially-ordered preferential structures[END_REF]. The two first relations are thoroughly studied in [START_REF] Cayrol | Management of preferences in assumption-based reasoning[END_REF] and [START_REF] Geffner | Default reasoning: Causal and Conditional Theories[END_REF]. They coincide with ≻ wos and wol on disjoint sets. When S is totally ordered, the relations ≻ wol a weak form of Qualitativeness:

If A ∩ B = A ∩ C = B ∩ C then (If A ∪ C ≻ wos d B and A ∪ B ≻ wos d C then A ≻ wos d (B ∪ C)).
Note that since ≻ wos d is equal to ≻ wos on disjoint sets, it satisfies (CCI), (CCC), (OR), CUT and CM as well.

The next property relates the optimistic dominance to the preadditive dominance.

Proposition 5 ≻ wos d refines ≻ wos and its dual variant:

-If A ≻ wos B then A ≻ wos d B. -If B ≻ wos A then A ≻ wos d B. -If A ≻ wos d B then A wol B and B wol A.
The preadditive dominance based on the weak optimistic dominance is thus welladapted to plausible reasoning with partially ordered knowledge bases. Note that the properties of Conditional Closure by Implication (CCI) and Conditional Closure by Conjunction (CCC) are essential to extract a deductively closed set of most plausible formulae.

From weak optimistic dominance to a partial order on elements

Halpern [START_REF] Halpern | Defining relative likelihood in partially-ordered preferential structures[END_REF] studied the problem to know if a preorder on 2 S can be generated by a preorder on S. The only known result deals with total preorders: If ☎ is a total preorder on 2 S that satisfies the properties of orderliness and qualitativeness, then there exists a total preorder ≥ on S such that ☎ and wol coincide on 2 S (a similar result where one replaces these properties by stability for the union is already in [START_REF] Dubois | Belief structures, possibility theory and decomposable confidence measures on finite sets[END_REF], because in this case indeed a comparative possibility measure [START_REF] Lewis | Counterfactuals and comparative possibility[END_REF] is characterized by a complete preorder of possibility on S).

In the partial order case, if a strict order ✄ on 2 S is generated by a strict order > on S, one must have {a} ✄ {b} whenever a > b. Conversely, suppose ✄ satisfies the properties of orderliness and negligibility and define the relation a > ✄ b by {a} ✄ {b}. Then, A ≻ wos B means ∀b ∈ B, ∃a ∈ A, a > ✄ b that is to say ∀b ∈ B, ∃a ∈ A, {a} ✄ {b}. We have:

-If A ≻ wos B then A ✄ B.
-Conversely, if A ✄ B, it is easy to prove that ∀b ∈ B, A ✄ {b}. But nothing proves that ∃a ∈ A such that {a} ✄ {b}.

So, the situation of partial orders is strikingly different from the case of total orders. Even equipped with the properties of orderliness and negligibility, a partial order on subsets is generally NOT characterized by its restriction on singletons.

Another way to induce a partial order on 2 S from a partial order > on S is to consider the partial order > as a family of total orders > i extending (or compatible with) this partial order. Let A and B two subsets of S, and let ✄ i denote the partial order on 2 S induced by ≻ i . Then two methods for building a partial order on 2 S can classically be proposed [START_REF] Yahi | A lexicographic inference for partially preordered belief bases[END_REF]:

Cautious principle considering all the total orders on S compatible with >: A ✄ B iff ∀i = 1, . . . , n, A ✄ i B Bold principle considering at least one total order on S compatible with

>: A ✄ B iff ∃i, A ✄ i B
It turns out that if we consider the family of total orders > i extending a partial order > on S, the cautious principle enables the weak optimist dominance ≻ wos to be recovered:

Proposition 6 Let A, B two subsets of S. We have:

A ≻ wos B ⇐⇒ ∀i = 1..n A ≻ i o B
As a consequence, a weak optimistic strict order on subsets is characterised by several total orderings on elements, not by a single partial order on elements. Given the properties satisfied by ≻ wos , this result clearly bridges the gap between the weak optimistic dominance and the partially ordered non-monotonic inference setting of Kraus, Lehmann and Magidor [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF] interpreting the dominance A ≻ wos B when A ∩ B = ∅ as the default inference of A from A ∪ B. -∀i = 1, 2, max(A) > i max(B), and it holds that A ≻ wos B.

max(C) > 2 max(B), max(B) > 1 max(C). Neither C ≻ wos B nor B ≻ wos C.

Representations of an epistemic state

Let us first formalize the concept of epistemic state based on the notion of partial order, from a syntactic and semantic point of view. In the following, V will denote a set of propositional variables, L a propositional language on V , and K a finite base of formulas built on L.

Syntactic representation

From the syntactic point of view, we can view an epistemic state as a finite set of propositional formulas equipped with a partial preorder. Let (K, >) be a partially ordered base of formulas. If φ and ψ are two formulas of K, ψ > φ is interpreted by "ψ is more likely than φ" (typically the first one is more certain or plausible as the second one). It can more generally be interpreted in terms of "priority". If ψ > φ is viewed as a constraint, the presence of the likelihood relation can be a cause of inconsistency. For instance, it seems irrational to assert φ > ψ when φ |= ψ. It can be regarded as a semantic contradiction.

In the particular case where the preorder is total, there is a alternative representation by means of a stratified base (K 1 , • • • , K n ) where all the elements of K i are set at the same priority level, and those of K i are strictly preferred to those of K j if i > j. However, possibilistic logic [START_REF] Dubois | Possibilistic logic[END_REF] does not consider stratification as a strict ordering constraint. It interprets φ ∈ K i as assigning a minimal absolute level to φ, that may fail to be its final one, i.e. φ can end up at some level j > i in the totally ordered deductive closure (which represents an epistemic entrenchment relation). Therefore, the stratification of the base is never an additional source of inconsistency. On the contrary, if when ψ ∈ K i and φ ∈ K j , j > i is understood as a constraint ψ > φ, it means that the stratified knowledge base is viewed as a fragment of a likelihood relation (epistemic entrenchment or necessity measure). The complexity of finding the deductive closure is higher in the last situation due to the possibility of a semantic contradiction between the likelihood relation at the syntactic level and logical entailment.

Semantic representation

Let Ω be the set of interpretations of L. At the semantic level, suppose that an epistemic state is modelled by a partial preorder on the interpretations of a propositional language, (Ω, ✄). If ω and ω ′ represent two elements of Ω, the assertion ω ′ ✄ ω is interpreted as ω ′ being more plausible than ω. In the knowledge representation literature, the main concern is often to extract the closed set of accepted beliefs K ✄ (or belief set) associated with (Ω, ✄). It is often defined as the deductively closed set of formulas whose models form the set M (Ω, ✄) of most plausible models. Our aim is to go further and to define a deductive closure which is a partial order induced by (Ω, ✄) on the language, (Ω, ✄) being itself induced by a partially ordered base (K, >). The idea is to attach a semantics to φ > ψ in terms of a partial order on the interpretations, and then to build a partial order on L which is, as much as possible, in agreement with (K, >). The question is thus to go from (K, >) to (Ω, ✄) and back, namely:

From (K, >) to (Ω, ✄): Starting from a partially ordered base, the problem is to build a partial preorder on the set of interpretations of K. A natural approach is to compare two interpretations ω and ω ′ by comparing subsets of formulas of K built from these interpretations.

A first proposal is to compare two interpretations ω and ω ′ by comparing the two subsets of formulas of K respectively satisfied by each of these interpretations. That is to say: ω ′ is more plausible than ω if for each formula φ satisfied by ω, there exists a formula preferred to φ and satisfied by ω ′ .

A dual proposal consists in comparing ω and ω ′ by comparing the two subsets of formulas of K respectively falsified by each of these interpretations. That is to say: ω ′ is more plausible than ω if for each formula φ ′ falsified by ω ′ , there exists a formula falsified by ω preferred to φ ′ .

From (Ω, ✄) to (L, ≻): Starting from a partial preorder on Ω, the problem is to build a partial preorder on the set of the formulas of the language L. To this end, it is natural to compare two formulas φ and φ ′ by comparing subsets of interpretations built from these formulas. In the same way as above, a first proposal is to compare φ and ψ by comparing the sets of models of these formulas. One can alternatively compare φ and ψ by comparing their sets of counter-models, that is the models of ¬ψ and ¬φ.

In fact the choice between the two alternative approaches must be guided by the meaning of the relations on the families of sets. If (K, >) is interpreted in terms of relative certainty as in possibilistic logic, it is natural to compare the subsets of falsified formulas of K for assessing the relative plausibility of interpretations. Indeed, an interpretation ω is all the less plausible as it violates more certain propositions.

In the same way, starting from a plausibility relation on the interpretations (Ω, ✄), we can express the idea of relative certainty φ ≻ ψ on the language, by comparing sets of models of ¬ψ and ¬φ; for instance, in the case of a total order, a relation of comparative necessity, dual to comparative possibility, can be defined by φ ≻ N ψ iff ¬ψ ≻ o ¬φ 1 .

1 relation ≻o is introduced in Definition 1.
This approach was thoroughly studied within the possibilistic framework for completely ordered bases [START_REF] Dubois | Possibilistic logic[END_REF], but much less often in the partially ordered case [START_REF] Benferhat | Reasoning with partially ordered information in a possibilistic logic framework[END_REF]. Some questions will arise naturally from this research program:

-Is the partial preorder ≻ built on L from (Ω, ✄) compatible with (K, >)? A strict meaning of compatibility would require that > is preserved and refined. Note that this is not the case in possibilistic logic if the lower bounds on certainty weights are not in conformity with classical deduction. Here again, it may happen that the relation ≻ on formulas induced from ✄ does not preserve the original ordering (K, >), since the latter can be in conflict with semantic entailment, if supplied by some expert.

-Is the preorder built on Ω from (K, >) unique? The answer is almost obviously no, as it depends on how the ordering > is understood in terms of a relation between sets of models of formulas appearing in K.

-Is it still possible to use a principle of minimal commitment in order to select a complete preorder on Ω in a non arbitrary way? In possibilistic logic [START_REF] Dubois | Possibilistic logic[END_REF], this is the principle of minimal specificity that yields the least informative possibility distribution on Ω (akin to the most compact ranking in system Z [START_REF] Pearl | System Z: A natural ordering of defaults with tractable applications to default reasoning[END_REF]).

The two transformations: from (K, >) to (Ω, ✄) and from (Ω, ✄) to (L, ≻) can be reduced to the problem of extending a partial order on a set S to a partial order on the set of the subsets of S, discussed in Section 4.

Optimistic dominance on partially ordered belief bases

As in possibilistic logic, we assume that the relation > expresses relative certainty, therefore we use the definitions based on falsified formulas. According to the previous sections, two approaches can be followed, using the weak optimistic dominance and its preadditive refinement. In the following, we consider both approaches consecutively. We do not consider the strong optimistic dominance as it allows to compare much less subsets, and we restrict here to strict dominance.

Weak optimistic dominance semantics

Let (K, >) be a finite partially ordered set of formulas of the propositional language L build on V . K(ω) (resp. K(ω)) denotes the subset of formulas of K satisfied (resp. falsified) by the interpretation ω ∈ Ω. [φ] denotes the set of the models of φ, a subset of Ω.

Definition 5 [From (K, >) to (Ω, ✄)] ∀ω, ω ′ ∈ Ω, ω ✄ wos ω ′ iff K(ω ′ ) ≻ wos K(ω)
In the spirit of possibilistic logic, it defines the dominance on interpretations in terms of the violation of the most certain formulas. But here these formulas may be incomparable.

Definition 6 [From (Ω, ✄) to (L, ≻ N )] ∀φ, ψ ∈ L, φ ≻ N ψ iff [ψ] ✄ wos [φ].
In the case of a total order, it would define a necessity relation on the language. The partially ordered deductive closure of (K, >) is then defined by

C(K, >) ≻ N = {(φ, ψ) ∈ L 2 : φ ≻ N ψ}.
And we denote (φ, ψ) ∈ C(K, >) ≻ N by K |= wos φ ≻ N ψ. Besides, in agreement with [START_REF] Dubois | Ordinal and probabilistic representations of acceptance[END_REF], one may extract from C(K, >) ≻N the set of accepted beliefs when φ is known to be true as A φ (K, >) ≻ N = {ψ : (φ → ψ, φ → ¬ψ) ∈ C(K, >) ≻ N }. Note that these are generic definitions that make sense for any variant of the optimistic strict order on K.

Proposition 7

the relation ✄ wos respects inclusion: If K(ω) ⊆ K(ω ′ ) then ω ✄ wos ω ′ does not hold; and ✄ wos is orderly too. -If the relation > is the strict part of a total preorder, possibilistic logic is recovered (order "best out " in [START_REF] Benferhat | Inconsistency management and prioritized syntax-based entailment[END_REF]).

-If φ is a logical consequence of ψ, it does not hold that ψ ≻ N φ. -≻ N verifies the converse of the stability for intersection: if φ ∧ χ ≻ N ψ ∧ χ, then φ ≻ N ψ.
As a consequence, if the partial order on K violates the partial order induced by classical inference, ≻ N will not refine it, but will correct it. If (by mistake) we set (K ′ , >) = {x ∧ y > x}, note that we still have that xy ✄ wos {xȳ, xy, xȳ} but not xȳ ✄ wos {xy, xȳ}. Then K ′ |= wos x ∧ y ≻ N x, that is, we correct this inconsistency via the semantics.

However, the fact, pointed out in Section 2, that a partial order over a power set cannot be characterized by a single partial order on the set of elements may cause some available pieces of knowledge in (K, >) to be lost in C(K, >) ≻ N , as shown thereafter.

Example 9 Let (K, >) = {x, ¬x ∨ y, x ∧ y, ¬x} be a partially ordered base, where > is the strict partial order given as follows: ¬x ∨ y > x ∧ y > ¬x and x > ¬x.

Let us apply the definitions 5 and 6:

-

From (K, >) to (Ω, ✄): we obtain xy ✄ wos {xy, xȳ, xȳ} -From (Ω, ✄) to (L, ≻ N ): we obtain x ≻ N ¬x, x ∧ y ≻ N ¬x and ¬x ∨ y ≻ N ¬x but not ¬x ∨ y ≻ N x ∧ y
We notice that, in the final order over formulas, ¬x ∨ y and x ∧ y become incomparable. The reason is that some information has been lost when going from (K, >) to (Ω, ✄). Indeed, if the strict partial order > of the base K is interpreted as the strict part ≻ N of a necessity ordering, applying Definition 6 enables the following constraints to be obtained: One observes that the impossibility of representing the partial order (K, >) by a partial ordering on interpretations is the cause for losing the piece of information ¬x ∨ y ≻ N x ∧ y. It suggests that the partially ordered deductive closure C(K, >) ≻ N is too weak to account for semantic entailment in partially ordered knowledge bases.

-Due to ¬x ∨ y ≻ N x ∧

Preadditive semantics

Under the preadditive semantics, the weak optimistic semantics in Definitions 5 and 6 is strengthened as follows:

Definition 7 Let ω, ω ′ be two interpretations: -If φ is a proper logical consequence of ψ, then φ ≻ d ψ.

-From (K, >) to (Ω, ✄): ω ✄ wos d ω ′ iff K(ω) ≻ wos d K(ω ′ ). -From (Ω, ✄) to (L, ≻ d ): φ ≻ d ψ iff [φ] ✄ wos d [ψ].
-if χ ∧ (φ ∨ ψ) = ⊥ then φ ≻ d ψ implies φ ∧ χ ≻ d ψ. -φ ∧ χ ≻ d ψ ∧ χ implies φ ≻ d ψ Example 9 (continued) -From (K, >) to (Ω, ✄): xy ✄ wos d {xy, xȳ, xȳ}; -From (Ω, ✄) to (L, ≻ d ): • x ≻ d x ∧ y ≻ d ¬x • ¬x ∨ y ≻ d x ∧ y ≻ d ¬x
We notice that the relation ≻ d has preserved and extended the initial strict partial order.

However, the relation ≻ d does not always preserve the initial strict partial order as shown thereafter.

Example 10 Let (K, >) = {x, ¬x ∨ ¬y, x ∧ y, ¬x} be a partially ordered base, where > is the strict partial order given as follows: ¬x ∨ ¬y > x ∧ y > ¬x and x > ¬x.

-From (K, >) to (Ω, ✄): we obtain xȳ ✄ wos d {xy, xy, xȳ} -From (Ω, ✄) to (L, ≻ d ): we obtain ¬x ∨ ¬y ≻ d x ∧ y, ¬x ∨ ¬y ≻ d ¬x, x ≻ d x ∧ y but not x ∧ y ≻ d ¬x.

Finally, let us consider the particular case of flat bases, interpreted as containing formulas that are all equivalent or all incomparable. The former case corresponds to classical logic. Suppose formulas in K are either incomparable or equivalent (for no φ, ψ ∈ K do we have φ > ψ). Then the set of logical consequences is no longer flat. The induced orderings are as follows.

-From (flat) K to (Ω, ✄):

ω ′ ✄ wos d ω iff K(ω ′ ) ⊃ K(w) -From (Ω, ✄) to (L, ≻ d ): φ ≻ d ψ iff ∀ω ′ ∈ [ψ] \ [φ], ∃w ∈ [φ] \ [ψ] such that K(ω) ⊃ K(ω ′ ).
Thus it is easy to see that, for flat bases, φ ≻ d ψ if and only if φ is a proper logical consequence of ψ, which enriches the semantics of classical logic.

Towards syntactic inference with partially ordered belief bases

Once the semantics of partially ordered belief bases and their deductive closure are well-defined, the next step is to devise a syntactic inference relation ⊢ that enables to directly build the ordered deductive closure C(K, >) ≻ from (K, >) (for a suitable choice of ≻) in agreement with the semantics, namely (K, >) ⊢ φ ≻ ψ, whenever (φ, ψ) ∈ C(K, >) ≻ . It appears that this question has been little discussed in the partially ordered case, except by Halpern [START_REF] Halpern | Defining relative likelihood in partially-ordered preferential structures[END_REF] and more recently by Benferhat and Prade [START_REF] Benferhat | Encoding formulas with partially constrained weights in a possibilistic-like many-sorted propositional logic[END_REF], with very different approaches.

Several methods of inference from a partially ordered belief base have been proposed. Is is possible to:

1. map (K, >) to a partially ordered set (L K , >) of absolute levels of certainty, and replace (K, >) by a possibilistic knowledge base B made of pairs (φ, λ), λ ∈ L K , such that whenever φ > ψ, (φ, λ), (ψ, µ) ∈ B and λ > µ. Then we can adapt the techniques of possibilistic logic to this setting. 2. consider a partial order as a family of total orders that extend it. So, a partially ordered base is seen as a set of (virtual) stratified bases. 3. reason directly with formulas φ > ψ in a suitable language. 4. reason in a classical way with consistent subsets of formulas extracted using the partial order.

The first approach was studied by Benferhat and Prade [START_REF] Benferhat | Encoding formulas with partially constrained weights in a possibilistic-like many-sorted propositional logic[END_REF]. Let (L K , >) be a finite ordered set associated with K by a homomorphism ι :

K → L K such that φ ≥ ψ ∈ K iff ι(φ) ≥ ι(ψ). Let us denote {µ : µ ≥ λ} by λ ↑ . The inequality λ 1 ≥ λ 2 in (L K , ≥) is encoded by A 2 ∨ ¬A 1 with A i = λ ↑
i , and the pair (φ, λ) is encoded by ¬A ∨ φ, with A = λ ↑ . Then classical propositional deduction can be used.

Actually, there is a more direct way to apply possibilistic logic to the partially ordered case. It is well-known that in standard possibilistic logic B ⊢ (φ, λ) ⇐⇒ B λ ⊢ φ where B λ is the set of formulas with weights at least λ. In the partially ordered case, we could define, when ψ ∈ K, K ⊢ φ ≻ ψ by K > ψ ⊢ φ where K > ψ = {α ∈ K : α > ψ} and likewise K ⊢ φ ψ by K ≥ ψ ⊢ φ where K ≥ ψ = {α ∈ K : ψ > α}. For instance if statements φ i > ψ i in (K, >) are interpreted on the set 2 Ω by [ψ i ] ✄ [φ i ] where the relation ✄ satisfies Negligibility and Orderliness, it does hold that [ψ] ✄ [φ] whenever K > ψ ⊢ φ. A particular case occurs when ✄ is ≻ wos . However, as shown in Example 9, if the consequence φ ≻ ψ is interpreted as φ ≻ N ψ using Definitions 5 and 6 (that is,via a partial order on interpretations derived from (K, >)) it may fail to hold that φ ≻ N ψ whenever K > ψ ⊢ φ (in Example 9, φ > ψ appears in (K, >), and is absent from the semantic closure). This fact indicates a weakness in the semantics based on a partial order on interpretations, as opposed to a more complex semantics based on the partial ordering on subsets of interpretations reflecting (K, >).

The second approach is described by Yahi and al [START_REF] Yahi | A lexicographic inference for partially preordered belief bases[END_REF]. (K, >) is viewed as a set of possible stratifications of K. So ψ ≥ φ of (K, >) means that ψ is more certain than φ (in the sense of possibilistic logic) in all the stratified bases compatible with (K, >). Results in the previous section indicate the strong link between this view and the weak optimistic relation ≻ wos (hence its dual ≻ N and their preadditive refinement ≻ d ). Note that in the first approach [START_REF] Benferhat | Encoding formulas with partially constrained weights in a possibilistic-like many-sorted propositional logic[END_REF], the partial order on L K is actually viewed as a set of possible total orders. The weights are symbolic in the sense of being partially unknown quantities on a totally ordered scale. To use this approach in practice may turn out to be difficult, because the set of total extensions of a given partial order may be large.

In the third approach, the problem is to consider expressions of the form φ ≻ ψ as the basic syntactic entities of the language encoding the preferences. It requires a higher order language for handling atomic propositions of the form φ ≻ ψ, their conjunctions, disjunctions and negations, with specific axioms for describing properties of the relation >. For instance, with the axiom: if ψ |= φ then ¬(ψ ≻ φ), semantical contradictions will be found, thus enabling to repair the partially ordered base. This approach, which is the most natural one, goes back to Lewis [START_REF] Lewis | Counterfactuals and comparative possibility[END_REF] conditional logics (see also Hájek [START_REF] Hájek | The Metamathematics of Fuzzy Logics[END_REF], p. 212) in the case of total preorders, for possibility theory). Halpern [START_REF] Halpern | Defining relative likelihood in partially-ordered preferential structures[END_REF] has outlined such a logic to handle the relation ≻ wos . This is certainly the most general approach with the richest language. Especially it would readily allow for a semantics in terms of a partial order over the set of subsets of interpretations of the language, which would obviate difficulties pointed out by Examples 9 and 10 when we use a partial ordering on interpretations. However only a subset of the consequences (K, >) from a set of φ ≻ ψ statements will correspond to the (properly defined) semantic closure C(K, >) (since, for instance, the latter does not contain disjunctions of such statements).

In the fourth approach [START_REF] Benferhat | Reasoning with partially ordered information in a possibilistic logic framework[END_REF], the partial order on K is just used to select preferred consistent subsets of formulas, and the deductive closure is a classical set of accepted beliefs. So, as pointed out in Benferhat and Yahi [START_REF] Benferhat | Etude comparative des relations d'inférence à partir de bases de croyance partiellement ordonnées[END_REF], the deductive closure of a partially ordered base (K, >) is just a deductively closed set (in the classical sense), obtained from preferred subbases. Then the inference (K, >) ⊢ φ is defined by: φ is consequence of all the preferred subsets of formulas. The notion of preference can be defined in various ways based on the partial order. This order between formulas is to some extent lost by the process of inference. In particular this kind of approach reduces to classical inference when K is classically consistent. By construction, this approach does not enable to deduce preferences between formulas, but essentially extracts accepted beliefs.

In the future, we plan to investigate whether or not the above syntactic inference schemes are sound (and if possible complete) with respect to our notion of partialorder-driven semantic closure. We have already noticed that a semantics based on a single partial ordering over interpretations may be problematic as seen in Example 9. This result motivates the use of a modal-like language with formulas of the form φ > ψ, φ ≥ ψ, or φ ∼ ψ with relational semantics on the powerset of the set of interpretations of the language where φ, ψ are expressed, whereby φ > ψ is viewed as a relation between [ψ i ] and [φ i ], etc. Then the properties of the semantic relation can be used as inference rules at the syntactic level. However, one may wish to restrict the inference machinery to consequences of the form φ ≻ ψ and φ ψ.

Conclusion

The issue addressed in this paper concerns the extension of possibilistic logic when formulas weighted by certainty levels are replaced by a partial order on the belief base. Defining proper semantics for such partially ordered bases requires the study of how to go from a partial order on elements to a partial order on subsets of such elements and conversely. Some preliminary results are offered in this paper. They indicate that many important concepts in the case of complete orders have several non equivalent definitions in the partial case. When going from a partial order on a set to a partial order on its subsets, it seems that the weak optimistic relation possesses the best properties. Moreover it seems that a straightforward adaptation of possibilistic logic to the partial order setting is not possible.

The question then becomes the one of finding the most natural understanding of a base partially ordered in terms of relative certainty. Our paper explains how to go from formulas to models and back, thus defining a semantic notion of deductive closure. We indicate that the expressive power of a partial order on the set of interpretations is limited, and one must stick to a partial order on its power set, or alternatively a set of total orders on the set of interpretations, to be on the safe side. Existing works proposing proof methods have been reviewed, but they all consider different points of view on the definition of inference in the partially ordered context, sometimes with unclear semantics. In contrast, our purpose is to eventually define a semantic closure that preserves and extends the partial order on K to the whole language, while correcting the initial assessment to make it comply with the classical deduction. Once this issue has been clarified, we have to choose an appropriate syntax, an axiomatization and a syntactic inference method. Some hints are provided above, but this is left for further research.

This work has potential applications for the revision and the fusion of beliefs, as well as preference modeling [START_REF] Dubois | Conditional preference nets and possibilistic logic[END_REF].

1 . 1 .

 11 (O) implies CCI. 2. If the relation ≫ is qualitative (Q) and orderly (O), then it satisfies Negligibility (N) and (CCC), and the converse of (SU): If A ∪ C ≫ B ∪ C then A ≫ B. Proof: Suppose A ⊆ B and A∩C ≫ A∩C. We have A∩C ⊆ B ∩C and B ∩C ⊆ A∩C. Hence from (O), B ∩ C ≫ B ∩ C. 2. Assume that ≫ satisfies (Q) and (O). Suppose A ≫ B and A ≫ C. Then, by (O), A ∪ B ≫ C and A ∪ C ≫ B. Hence from

Definition 3 (

 3 Strong optimistic dominance) 1. Strong optimistic strict dominance: A ≻ Sos B iff ∃a ∈ A, ∀b ∈ B, a > b 2. Strong optimistic loose dominance: A Sol B iff ∃a ∈ A, ∀b ∈ B, a ≥ b 3. Strict order determined by Sol : A ≻ Sol B iff A Sol B and ¬(B Sol A). In other words, A ≻ Sol B iff ∃a ∈ A, ∀b ∈ B, a ≥ b and ∀b ∈ B, ∃a ∈ A, either a > b or a ≈ b.

Proposition 3

 3 The strong optimistic strict dominance ≻ Sos is a strict order satisfying Orderliness (O) and Cautious Monotony (CM) However it fails to satisfy Negligibility, Qualitativeness, CUT and Left Disjunction (OR), as shown by the following examples. Example 4 Let S = {a 1 , a 2 , b, c} with a 1 > b and a 2 > c, and the subsets A = {a 1 , a 2 }, B = {b} and C = {c}. We have A ≻ Sos B , A ≻ Sos C but we don't haveA ≻ Sos (B ∪ C). So (N) is not satisfied. Due to Proposition 1, the relation ≻ Sos fails to satisfy Qualitativeness as well. Example 5 Let S = {a, b, c, d} with a > b and c > d, and the subsets A = {a, b, c, d}, B = {a, c, d} and C

Example 6 CProposition 4

 64 wol d , nor its strict part are transitive, as indicated by the following counterexample. Let S = {a 1 , a 2 , a 3 , b 1 , b 2 , c} with a 1 ∼ a 2 ∼ b 1 , a 1 > c and a 3 > b 2 . Let A = {a 1 , a 2 , a 3 }, B = {b 1 , b 2 }, C = {a 1 , a 2 , c}. We have A wol d but not C wol d B but we don't have A wol d C. The relation ≻ wos d seems to be more appropriate due to the following properties: The relation ≻ wos d is a strict partial order that satisfies: -Strict compatibility with Inclusion (SCI): if A ⊂ B then B ≻ wos d A. -Self-duality (D) and Preadditivity (P) a weak form of Negligibility: If A ∩ B = A ∩ C then (If A ≻ wos d B and A ≻ wos d C then A ≻ wos d (B ∪ C)).

Example 7

 7 Let (S, >) = {a, b, c, d, e} be the partially ordered set defined by e > c > a > d, c > b > d. Let > 1 , > 2 be the two linear orders that extend the partial order > defined by e > 1 c > 1 b > 1 a > 1 d and e > 2 c > 2 a > 2 b > 2 d. Let A = {e, c}, B = {b, d} and C = {a, d}:

Example 8 (

 8 K, >) = {x > x ∧ y}. As usual, the four interpretations are denoted by xy, xȳ, xy, xȳ. Clearly K(xy) = ∅, K(xȳ) = {x ∧ y}, K(xy) = K(xy) = K. Hence, xy ✄ wos {xȳ, xy, xȳ} and xȳ ✄ wos {xy, xȳ}. Then it is easy to see that K |= wos x ≻ N y (since [¬y] = {xȳ, xȳ} ✄ wos [¬x] = {xy, xȳ} but K |= wos y ≻ N x ∧ y, since it does not hold that [¬x ∨ ¬y] = {xy, xȳ, xȳ} ✄ wos [¬y] = {xȳ, xȳ}.

Proposition 8

 8 The notion of semantic consequence and deductive closure are defined similarly, replacing ≻ N by ≻ d . The following results hold: It is clear that: the relation ✄ wos d strictly respects inclusion: If K(ω) ⊂ K(ω ′ ) then ω ′ ✄ wos d ω.

  y we must have xy ✄ xȳ or xȳ ✄ xȳ -Due to x ∧ y ≻ N ¬x we must have xy ✄ xȳ and xy ✄ xy or xȳ ✄ xy and xy ✄ xȳ or xȳ ✄ xȳ -Due to x ≻ N ¬x we must have xy ✄ xy or xȳ ✄ xy and xy ✄ xȳ or xȳ ✄ xȳ It is easy to see that these constraints imply that xy ✄ {xy, xȳ, xȳ} and (xy ✄ xȳ or xȳ ✄ xȳ). That is stronger than the partial order ✄ wos and not representable by a single partial order.