Jonathan Ben-Naim
email: jbennaim@lif.univ-mrs.fr

Lif

Preferential and Preferential-discriminative Consequence Relations *

The present paper investigates consequence relations that are both non-monotonic and paraconsistent. More precisely, we put the focus on preferential consequence relations, i.e. those relations that can be defined by a binary preference relation on states labelled by valuations. We worked with a general notion of valuation that covers e.g. the classical valuations as well as certain kinds of many-valued valuations. In the many-valued cases, preferential consequence relations are paraconsistant (in addition to be non-monotonic), i.e. they are capable of drawing reasonable conclusions which contain contradictions. The first purpose of this paper is to provide in our general framework syntactic characterizations of several families of preferential relations. The second and main purpose is to provide, again in our general framework, characterizations of several families of preferentialdiscriminative consequence relations. They are defined exactly as the plain version, but any conclusion such that its negation is also a conclusion is rejected (these relations bring something new essentially in the many-valued cases). * This is an updated version of the paper of the same title published in The Journal of Logic and Computation. This version just contains a better presentation (so the numbering of definitions and propositions is different).

Background

Semantic structures

Definitions and properties

.

Definition 1

We say that S is a semantic structure iff S = F, V, |= where F is a set, V is a set, and |= is a relation on V × F.

Introduction

In many situations, we are confronted with incomplete and/or inconsistent information and the classical consequence relation proves to be insufficient. Indeed, in case of inconsistent information, it leads to accept every formula as a conclusion, which amounts to loose the whole information. Therefore, we need other relations leading to non-trivial conclusions in spite of the presence of contradictions. So, several paraconsistent consequence relations have been developed. In the present paper, we will pay attention in particular to certain many-valued ones [Bel77b, Bel77a, DdC70, CMdA00, dACM02, AA94, AA96, AA98]. They are defined in frameworks where valuations can assign more than two different truth values to formulas. In fact, they tolerate contradictions within the conclusions, but reject the principle of explosion according to which a single contradiction entails the deduction of every formula.

In case of incomplete information, the classical consequence relation also shows its limits. Indeed, no risk is taken, the conclusions are sure, but too few. We need other relations leading to accept as conclusions formulas that are not necessarily sure, but still plausible. Eventually, some "hasty" conclusions will be rejected later, in the presence of additional information. So, a lot of plausible (generally non-monotonic) consequence relations have been developed. Choice functions are central tools to define plausible relations [Che54, Arr59, Sen70, AM81, Leh02, Leh01, Sch92, Sch04]. Indeed, suppose we have at our disposal a function µ, called a choice function, which chooses in any set of valuations V , those elements which are preferred, not necessarily in the absolute sense, but when the valuations in V are the only ones under consideration. Then, we can define a plausible consequence relation in the following natural way: a formula α follows from a set of formulas Γ iff every model for Γ chosen by µ is a model for α.

In the present paper, we put the focus on a particular family of choice functions. Let us present it. Suppose we are given a binary preference relation ≺ on states labelled by valuations (in the style of e.g. [START_REF] Kraus | Nonmonotonic reasoning, preferential models, and cumulative logics[END_REF][START_REF] Schlechta | Coherent systems[END_REF]). This defines naturally a choice function. Indeed, choose in any set of valuations V , each element that labels a state which is ≺-preferred among those states which are labelled by the elements of V . Those choice functions which can be defined in this manner constitute the aforementioned family. The consequence relations defined by this family will be called preferential consequence relations.

For a long time, research efforts on paraconsistent relations and plausible relations were separated. However, in many applications, the information is both incomplete and inconsistent. For instance, the semantic web or big databases inevitably contain inconsistencies. This can be due to human or material imperfections as well as contradictory sources of information. On the other hand, neither the web nor big databases can contain "all" information. Indeed, there are rules of which the exceptions cannot be enumerated. Also, some information might be left voluntarily vague or in concise form. Consequently, consequence relations that are both paraconsistent and plausible are useful to reason in such applications.

Such relations first appear in e.g. [Pri91, Bat98, KL92, AA00, KM02]. The idea begins by taking a many-valued framework to get paraconsistency. Then, only those models that are most preferred according to some particular binary preference relation on valuations (in the style of [START_REF] Shoham | Reasoning About Change[END_REF][START_REF] Shoham | A semantical approach to nonmonotonic logics[END_REF]) are relevant for making inference, which provides plausibility. In [START_REF] Avron | Formula-preferential systems for paraconsistent non-monotonic reasoning[END_REF][START_REF] Avron | A formula-preferential base for paraconsistent and plausible reasoning systems[END_REF], A. Avron and I. Lev generalized the study to families of binary preference relations which compare two valuations using, for each of them, this part of a certain set of formulas it satisfies. The present paper follows this line of research by combining many-valued frameworks and choice functions.

More explicitly, we will investigate preferential consequence relations in a general framework. According to the different assumptions which will be made about the latter, it will cover various kinds of frameworks, including e.g. the classical propositional one as well as certain many-valued ones. Moreover, in the many-valued frameworks, preferential relations are paraconsistent (in addition to be plausible). However, they do not satisfy the Disjunctive Syllogism (from α and ¬α ∨ β we can conclude β), whilst they satisfy it in classical framework.

In addition, we will investigate preferential-discriminative consequence relations. They are defined exactly as the plain version, but any conclusion such that its negation is also a conclusion is rejected. In the classical framework, they do not bring something really new. Indeed, instead of concluding everything in the face of inconsistent information, we will simply conclude nothing. On the other hand, in the many-valued frameworks, where the conclusions are non-trivial even from inconsistent information, the discriminative version will reject the contradictions among them, rendering them all the more rational.

The contribution of the present paper can now be summarized in one sentence: we characterized, in a general framework, several (sub)families of preferential(-discriminative) consequence relations. In many cases, our characterizations are purely syntactic. This has a lot of advantages, let us quote some important ones. Take some syntactic conditions that characterize a family of those consequence relations. This gives a syntactic point of view on this family defined semantically, which enables us to compare it to conditions known on the "market", and thus to other consequence relations. This can also give rise to questions like: if we modified the conditions in such and such a natural-looking way, what would happen on the semantic side? More generally, this can open the door to questions that would not easily come to mind otherwise or to techniques of proof that could not have been employed in the semantic approach.

Several characterizations can be found in the literature for preferential relations (e.g. [Gab85, Mak89, Mak94, KLM90, LM92, Leh02, Leh01, Sch92, Sch96, Sch00, Sch04]). We will provide some new ones, though to do so we have been strongly inspired by techniques of K. Schlechta [START_REF] Schlechta | Coherent systems[END_REF]. In fact, our innovation is rather related to the discriminative version. To the author knowledge, the present paper is the first systematic work of characterization for preferential-discriminative consequence relations.

The rest of the paper is organized as follows. In Section 2.1, we introduce our general framework and the different assumptions which sometimes will be made about it. We will see that it covers in particular the many-valued frameworks of the well-known paraconsistent logics F OUR and J 3 . In Section 2.2, we present choice functions and some of their well-known properties. In Section 2.3, we define preferential(-discriminative) consequence relations and give examples in both the classical and the many-valued frameworks. We will also recall a characterization which involves the wellknown system P of Kraus, Lehmann, and Magidor. In section 3, we provide our characterizations. Finally, we conclude in Section 4.

Intuitively, F is a set of formulas, V a set of valuations for these formulas, and |= a satisfaction relation for these objects (i.e. v |= α means the formula α is satisfied in the valuation v, i.e. v is a model for α).

Notation 2 Let F, V, |= be a semantic structure, Γ ⊆ F, and V ⊆ V. Then,

M Γ := {v ∈ V : ∀ α ∈ Γ, v |= α}, T (V ) := {α ∈ F : V ⊆ M α }, D := {V ⊆ V : ∃ Γ ⊆ F, M Γ = V }.
Suppose L is a language, ¬ a unary connective of L, and F the set of all wffs of L. Then,

T d (V ) := {α ∈ F : V ⊆ M α and V ⊆ M ¬α }, T c (V ) := {α ∈ F : V ⊆ M α and V ⊆ M ¬α }, C := {V ⊆ V : ∀ α ∈ F, V ⊆ M α or V ⊆ M ¬α }.
Intuitively, M Γ is the set of all models for Γ and T (V ) the set of all formulas satisfied in V . Every element of T (V ) belongs either to T d (V ) or T c (V ), according to whether its negation is also in T (V ). D is the set of all those sets of valuations that are definable by a set of formulas and C the set of all those sets of valuations that do not satisfy both a formula and its negation. As usual, M Γ,α , T (V, v) stand for respectively M Γ∪{α} , T (V ∪ {v}), etc.

Remark 3

The notations M Γ , T (V ), etc. should contain the semantic structure on which they are based. To increase readability, we will omit it. There will never be any ambiguity. We will omit similar things with other notations in the sequel, for the same reason.

A semantic structure defines a basic consequence relation: Notation 4 We denote by P the power set operator. Let F, V, |= be a semantic structure. We denote by ⊢ the relation on

P(F ) × F such that ∀ Γ ⊆ F, ∀ α ∈ F, Γ ⊢ α iff M Γ ⊆ M α .
Let |∼ be a relation on P(F ) × F. Then, |∼(Γ) := {α ∈ F : Γ |∼ α}. Suppose L is a language, ¬ a unary connective of L, F the set of all wffs of L, and Γ ⊆ F. Then, we say that Γ is consistent iff ∀ α ∈ F, Γ ⊢ α or Γ ⊢ ¬α.

The following trivial facts hold, we will use them implicitly in the sequel: Remark 5 Let F, V, |= be a semantic structure and Γ, ∆ ⊆ F. Then:

M Γ,∆ = M Γ ∩ M ∆ ; ⊢(Γ) = T (M Γ ); M Γ = M ⊢(Γ) ; Γ ⊆ ⊢(∆) iff ⊢(Γ) ⊆ ⊢(∆) iff M ∆ ⊆ M Γ .
Sometimes, we will need some of the following assumptions about a semantic structure: Definition 6 Suppose F, V, |= is a semantic structure. Then, define the following assumptions about it:

(A1) V is finite.
Suppose L is a language, ¬ a unary connective of L, and F the set of all wffs of L. Then, define:

(A2) ∀ Γ ⊆ F, ∀ α ∈ F, if α ∈ T (M Γ ) and ¬α ∈ T (M Γ ), then M Γ ∩ M α ⊆ M ¬α .
Suppose ∨ and ∧ are binary connectives of L. Then, define:

(A3) ∀ α, β ∈ F, we have: M α∨β = M α ∪ M β ; M α∧β = M α ∩ M β ; M ¬¬α = M α ; M ¬(α∨β) = M ¬α∧¬β ; M ¬(α∧β) = M ¬α∨¬β .
Clearly, those assumptions are satisfied by classical semantic structures, i.e. structures where F , V, and |= are classical. In addition, we will see, in Sections 2.1.2 and 2.1.3, that they are satisfied also by certain many-valued semantic structures.

The semantic structure defined by F OUR

The logic F OUR was introduced by N. Belnap in [START_REF] Belnap | How computers should think[END_REF][START_REF] Belnap | A useful four-valued logic[END_REF]. This logic is useful to deal with inconsistent information. Several presentations are possible, depending on the language under consideration. For the needs of the present paper, a classical propositional language will be sufficient.

The logic has been investigated intensively in e.g. [AA94, AA96, AA98], where richer languages, containing an implication connective ⊃ (first introduced by A. Avron [START_REF] Avron | Natural 3-valued logics : characterization and proof theory[END_REF]), were considered.

Notation 7

We denote by A a set of propositional symbols (or atoms). We denote by L c the classical propositional language containing A, the usual constants f alse and true, and the usual connectives ¬, ∨, and ∧. We denote by F c the set of all wffs of L c .

We recall a possible meaning for the logic F OUR (more details can be found in [CLM99, [START_REF] Belnap | How computers should think[END_REF][START_REF] Belnap | A useful four-valued logic[END_REF]). Consider a system in which there are, on the one hand, sources of information and, on the other hand, a processor that listens to them. The sources provide information about the atoms only, not about the compound formulas. For each atom p, there are exactly four possibilities: either the processor is informed (by the sources, taken as a whole) that p is true; or he is informed that p is false; or he is informed of both; or he has no information about p.

Notation 8 Denote by 0 and 1 the classical truth values and define:

f := {0}; t := {1}; ⊤ := {0, 1}; ⊥ := ∅.
The global information given by the sources to the processor can be modelled by a function s from A to {f , t, ⊤, ⊥}. Intuitively, 1 ∈ s(p) means the processor is informed that p is true, whilst 0 ∈ s(p) means he is informed that p is false. Then, the processor naturally builds information about the compound formulas from s. Before he starts to do so, the situation can be be modelled by a function v from F c to {f , t, ⊤, ⊥} which agrees with s about the atoms and which assigns ⊥ to all compound formulas. Now, take p and q in A and suppose 1 ∈ v(p) or 1 ∈ v(q). Then, the processor naturally adds 1 to v(p ∨ q). Similarly, if 0 ∈ v(p) and 0 ∈ v(q), then he adds 0 in v(p ∨ q). Of course, such rules hold for ¬ and ∧ too.

Suppose all those rules are applied recursively to all compound formulas. Then, v represents the "full" (or developed) information given by the sources to the processor. Now, the valuations of the logic F OUR can be defined as exactly those functions that can be built in this manner (i.e. like v) from some information sources. More formally,

Definition 9 We say that v is a four-valued valuation iff v is a function from F c to {f , t, ⊤, ⊥} such that v(true) = t, v(f alse) = f and ∀ α, β ∈ F c , 1 ∈ v(¬α) iff 0 ∈ v(α); 0 ∈ v(¬α) iff 1 ∈ v(α); 1 ∈ v(α ∨ β) iff 1 ∈ v(α) or 1 ∈ v(β); 0 ∈ v(α ∨ β) iff 0 ∈ v(α) and 0 ∈ v(β); 1 ∈ v(α ∧ β) iff 1 ∈ v(α) and 1 ∈ v(β); 0 ∈ v(α ∧ β) iff 0 ∈ v(α) or 0 ∈ v(β).
We denote by V 4 the set of all four-valued valuations.

The definition may become more accessible if we see the four-valued valuations as those functions that satisfy Tables 1, 2, and 3 below:

v(α) v(¬α) f t t f ⊤ ⊤ ⊥ ⊥ Table 1. v(β) f t ⊤ ⊥ v(α) f f t ⊤ ⊥ t t t t t ⊤ ⊤ t ⊤ t ⊥ ⊥ t t ⊥ v(α ∨ β) Table 2. v(β) f t ⊤ ⊥ v(α) f f f f f t f t ⊤ ⊥ ⊤ f ⊤ ⊤ f ⊥ f ⊥ f ⊥ v(α ∧ β) Table 3.
In the logic F OUR, a formula α is considered to be satisfied iff the processor is informed that it is true (it does not matter whether he is also informed that α is false).

Notation 10 We denote by |=

4 the relation on V 4 × F c such that ∀ v ∈ V 4 , ∀ α ∈ F c , we have v |= 4 α iff 1 ∈ v(α).
Proof systems for the consequence relation ⊢ based on the semantic structure F c , V 4 , |= 4 (i.e. the semantic structure defined by F OUR) can be found in e.g. [AA94, AA96, AA98].

Note that the F OUR semantic structure satisfies (A3). In addition, if A is finite, then (A1) is also satisfied. However, (A2) is not satisfied by this structure. In Section 2.1.3, we turn to a many-valued semantic structure which satisfies (A2).

The semantic structure defined by J 3

The logic J 3 was introduced in [START_REF] Schewe | Sur un problème de Jaśkowski[END_REF] to answer a question posed in 1948 by S. Jaśkowski, who was interested in systematizing theories capable of containing contradictions, especially if they occur in dialectical reasoning. The step from informal reasoning under contradictions and formal reasoning with databases and information was done in [START_REF] Carnielli | Formal inconsistency and evolutionary databases[END_REF] (also specialized for real database models in [START_REF] De Amo | A logical framework for integrating inconsistent information in multiple databases[END_REF]), where another formulation of J 3 called LFI1 was introduced, and its first-order version, semantics and proof theory were studied in detail. Investigations of J 3 have also been made in e.g. [START_REF] Avron | Natural 3-valued logics : characterization and proof theory[END_REF], where richer languages than our L c were considered.

The valuations of the logic J 3 can be given the same meaning as those of the logic F OUR, except that the consideration is restricted to those sources which always give some information about an atom. More formally,

Definition 11 We say that v is a three-valued valuation iff v is a function from F c to {f , t, ⊤} such that v(true) = t, v(f alse) = f and ∀ α, β ∈ F c , 1 ∈ v(¬α) iff 0 ∈ v(α); 0 ∈ v(¬α) iff 1 ∈ v(α); 1 ∈ v(α ∨ β) iff 1 ∈ v(α) or 1 ∈ v(β); 0 ∈ v(α ∨ β) iff 0 ∈ v(α) and 0 ∈ v(β); 1 ∈ v(α ∧ β) iff 1 ∈ v(α) and 1 ∈ v(β); 0 ∈ v(α ∧ β) iff 0 ∈ v(α) or 0 ∈ v(β).
We denote by V 3 the set of all three-valued valuations.

As previously, the definition may become more accessible if we see the three-valued valuations as those functions that satisfy Tables 4, 5, and 6 below:

v(α) v(¬α) f t t f ⊤ ⊤ Table 4. v(β) f t ⊤ v(α) f f t ⊤ t t t t ⊤ ⊤ t ⊤ v(α ∨ β) Table 5. v(β) f t ⊤ v(α) f f f f t f t ⊤ ⊤ f ⊤ ⊤ v(α ∧ β) Table 6.
We turn to the satisfaction relation.

Notation 12

We denote by |= 3 the relation on

V 3 × F c such that ∀ v ∈ V 3 , ∀ α ∈ F c , we have v |= 3 α iff 1 ∈ v(α).
Proof systems for the consequence relation ⊢ based on the semantic structure F c , V 3 , |= 3 (i.e. the semantic structure defined by J 3 ) have been provided in e.g. [START_REF] Avron | Natural 3-valued logics : characterization and proof theory[END_REF][START_REF] Schewe | Sur un problème de Jaśkowski[END_REF] and chapter IX of [START_REF] Epstein | The Semantic foundation of logic[END_REF]. The J 3 structure satisfies (A3) and (A2). In addition, if A is finite, then it satisfies (A1) too.

Choice functions

Definitions and properties

In many situations, an agent has some way to choose in any set of valuations V , those elements that are preferred (the bests, the more normal, etc.), not necessarily in the absolute sense, but when the valuations in V are the only ones under consideration. In Social Choice, this is modelled by choice functions [Che54, Arr59, Sen70, AM81, Leh02, Leh01].

Definition 13 Let V be a set, V ⊆ P(V), W ⊆ P(V), and µ a function from V to W. We say that µ is a choice function iff

∀ V ∈ V, µ(V ) ⊆ V .
Several properties for choice functions have been put in evidence by researchers in Social Choice. Let us present two important ones (a better presentation can be found in [START_REF] Lehmann | Nonmonotonic Logics and Semantics[END_REF]). Suppose W is a set of valuations, V is a subset of W , and v ∈ V is a preferred valuation of W . Then, a natural requirement is that v is a preferred valuation of V . Indeed, in many situations, the larger a set is, the harder it is to be a preferred element of it, and he who can do the most can do the least. This property appears in [START_REF] Chernoff | Rational selection of decision functions[END_REF] and has been given the name Coherence in [START_REF] Moulin | Choices functions over a finite set: A summary[END_REF].

We turn to the second property. Suppose W is a set of valuations, V is a subset of W , and suppose all the preferred valuations of W belong to V . Then, they are expected to include all the preferred valuations of V . The importance of this property has been put in evidence by [START_REF] Aizerman | New problems in the general choice theory: Review of a research trend[END_REF][START_REF] Aizerman | General theory of best variants choice: Some aspects[END_REF] and has been given the name Local Monotonicity in e.g. [START_REF] Lehmann | Nonmonotonic Logics and Semantics[END_REF].

Definition 14 Let V be a set, V ⊆ P(V), W ⊆ P(V), and µ a choice function from V to W. We say that µ is

coherent iff ∀ V, W ∈ V, if V ⊆ W, then µ(W ) ∩ V ⊆ µ(V ).
We say that µ is locally monotonic

(LM) iff ∀ V, W ∈ V, if µ(W ) ⊆ V ⊆ W, then µ(V ) ⊆ µ(W ).
In addition to their intuitive meanings, these properties are important because, as was shown by K. Schlechta in [START_REF] Schlechta | New techniques and completeness results for preferential structures[END_REF], they characterize those choice functions that can be defined by a binary preference relation on states labelled by valuations (in the style of e.g. [START_REF] Kraus | Nonmonotonic reasoning, preferential models, and cumulative logics[END_REF]). We will take a closer look at this in Section 2.2.2.

When a semantic structure is under consideration, two new properties can be defined. Each of them conveys a simple and natural meaning.

Definition 15 Let F, V, |= be a semantic structure, V ⊆ P(V), W ⊆ P(V), and µ a choice function from V to W. We say that µ is definability preserving (DP) iff

∀ V ∈ V ∩ D, µ(V ) ∈ D.
Suppose L is a language, ¬ a unary connective of L, and F the set of all wffs of L. We say that µ is coherency preserving (CP) iff

∀ V ∈ V ∩ C, µ(V ) ∈ C.
Definability Preservation has been put in evidence first in [START_REF] Schlechta | Some results on classical preferential models[END_REF]. One of its advantages is that when the choice functions under consideration satisfy it, we will provide characterizations with purely syntactic conditions. To the author knowledge, the present paper is the first to introduce Coherency Preservation. An advantage of this property is that when the choice functions under consideration satisfy it, we will not need to assume (A2) to show our characterizations (in the discriminative case).

Preference structures

Binary preference relations on valuations have been investigated by e.g. B. Hansson to give semantics for deontic logics [START_REF] Hansson | An analysis of some deontic logics[END_REF]. Y. Shoham rediscovered them to give semantics for plausible non-monotonic logics [START_REF] Shoham | Reasoning About Change[END_REF][START_REF] Shoham | A semantical approach to nonmonotonic logics[END_REF]. Then, it seems that Imielinski is one of the first persons to introduce binary preference relations on states labelled by valuations [START_REF] Imielinski | Results on translating defaults to circumscription[END_REF]. They have been used to give more general semantics for plausible non-monotonic logics, see e.g. [KLM90, LM92, Sch92, Sch96, Sch00, Sch04]. Let us present them.

Definition 16

We say that R is a preference structure on a set V iff R = S, l, ≺ where S is a set, l is a function from S to V, and ≺ is a relation on S × S.

In fact, preference structures are essentially Kripke structures. The difference lies in the interpretation of ≺. In a Kripke structure, it is seen as an accessibility relation, whilst, in a preference structure, it is seen as a preference relation. We recall a possible meaning for preference structures (see e.g. [START_REF] Kraus | Nonmonotonic reasoning, preferential models, and cumulative logics[END_REF][START_REF] Schlechta | Coherent systems[END_REF] for details about meaning). Intuitively, V is a set of valuations for some language L and S a set of valuations for some language L ′ richer than L. The elements of S are called states. l(s) corresponds precisely to this part of s that is about the formulas of L only. We call l a labelling function. Finally, ≺ is a preference relation, i.e. s ≺ s ′ means s is preferred to s ′ .

We turn to well-known properties for preference structures.

Definition 17 Suppose V is a set, R = S, l, ≺ is a preference structure on V, S ⊆ S, s ∈ S, V ⊆ V, and V ⊆ P(V).

We say that R is transitive (resp. irreflexive) iff ≺ is transitive (resp. irreflexive). We say that s is preferred in S iff ∀ s ′ ∈ S, s ′ ≺ s. L(V ) := {s ∈ S : l(s) ∈ V } (intuitively, L(V ) contains the states labelled by the elements of V ). We say that R is V-smooth (alias V-stoppered) iff ∀ V ∈ V, ∀ s ∈ L(V ), either s is preferred in L(V ) or there exists s ′ preferred in L(V ) such that s ′ ≺ s.

A preference structure defines naturally a choice function. The idea is to choose in any set of valuations V , each element which labels a state which is preferred among all the states labelled by the elements of V .

Definition 18 Suppose R = S, l, ≺ is a preference structure on a set V.

We denote by µ R the function from P(V) to

P(V) such that ∀ V ⊆ V, µ R (V ) = {v ∈ V : ∃ s ∈ L(v), s is preferred in L(V )}.
In Proposition 19 Taken from [START_REF] Schlechta | New techniques and completeness results for preferential structures[END_REF]. Let V be a set, V and W subsets of P(V), and µ a choice function from V to W. Then, (0) µ is coherent iff there exists a transitive and irreflexive preference structure R on V such that

∀ V ∈ V, we have µ(V ) = µ R (V ). Suppose ∀ V, W ∈ V, we have V ∪ W ∈ V and V ∩ W ∈ V. Then,
(1) µ is coherent and LM iff there exists a V-smooth, transitive, and irreflexive preference structure R on V such that ∀ V ∈ V, we have µ(V ) = µ R (V ).

In fact, in [START_REF] Schlechta | New techniques and completeness results for preferential structures[END_REF], the codomain of µ is required to be its domain: V. However, this plays no role in the proofs. Therefore, verbatim the same proofs are valid when the codomain of µ is an arbitrary subset W of P(V). Both myself and Schlechta checked it.

Preferential(-discriminative) consequence relations

Definitions

Suppose we are given a semantic structure and a choice function µ on the valuations. Then, it is natural to conclude a formula α from a set of formulas Γ iff every model for Γ chosen by µ is a model for α. More formally:

Definition 20 Suppose S = F, V, |= is a semantic structure and |∼ a relation on P(F ) × F. We say that |∼ is a preferential consequence relation iff there exists a coherent choice function µ from

D to P(V) such that ∀ Γ ⊆ F, ∀ α ∈ F, Γ |∼ α iff µ(M Γ ) ⊆ M α .
In addition, if µ is LM, DP, etc., then so is |∼.

These consequence relations are called "preferential" because, in the light of Proposition 19, they can be defined equivalently with preference structures, instead of coherent choice functions. They lead to "jump" to plausible conclusions which will eventually be withdrawn later, in the presence of additional information. Therefore, they are useful to deal with incomplete information. We will give an example with a classical semantic structure in Section 2.4.1.

In addition, if a many-valued semantic structure is considered, they lead to rational and nontrivial conclusions is spite of the presence of contradictions and are thus useful to treat both incomplete and inconsistent information. However, they will not satisfy the Disjunctive Syllogism. We will give an example with the F OUR semantic structure in Section 2.4.2. Now, we turn to a qualified version of preferential consequence. It captures the idea that the contradictions in the conclusions should be rejected.

Definition 21 Suppose L is a language, ¬ a unary connective of L, F the set of all wffs of L, F, V, |= a semantic structure, and |∼ a relation on P(F ) × F. We say that |∼ is a preferential-discriminative consequence relation iff there is a coherent choice function µ from

D to P(V) such that ∀ Γ ⊆ F, ∀ α ∈ F, Γ |∼ α iff µ(M Γ ) ⊆ M α and µ(M Γ ) ⊆ M ¬α .
In addition, if µ is LM, DP, etc., then so is |∼.

If a classical semantic structure is considered, the discriminative version does not bring something really new. Indeed, the only difference will be to conclude nothing instead of everything in the face of inconsistent information. On the other hand, with a many-valued structure, the conclusions are rational even from inconsistent information. The discriminative version will then reject the contradictions in the conclusions, rendering the latter all the more rational.

In Definitions 20 and 21, the domain of the choice function is D. This is natural as only the elements of D play a role in the definition of a preferential(-discriminative) consequence relation. This point of view has been adopted in e.g. [START_REF] Lehmann | Nonmonotonic Logics and Semantics[END_REF] (see Section 6). Now, one might want a definition with choice functions of which the domain is P(V). In fact, some families of relations can be defined equivalently with D or P(V). For instance, as is noted in [START_REF] Lehmann | Nonmonotonic Logics and Semantics[END_REF], if µ is a coherent choice function from D to P(V), then the function µ ′ from P(V) to P(V) defined by µ ′ (V ) = V ∩ µ(M T (V ) ) is a coherent choice function which agrees with µ on D.

Several characterizations for preferential consequence relations can be found in the literature (e.g. [KLM90, LM92, Leh02, Leh01, Sch92, Sch96, Sch00, Sch04]). In particular, we will recall (in Section 2.4) a characterization that involves the well-known system P of [START_REF] Kraus | Nonmonotonic reasoning, preferential models, and cumulative logics[END_REF].

As said previously, in the light of Proposition 19, preferential(-discriminative) consequence relations could have been introduced equivalently with preference structures. We opted for coherent choice functions for two reasons. First, they give a clearer meaning. Indeed, properties like Coherence have simple intuitive justifications, whilst preference structures contain "states", but it is not perfectly clear what a state is in daily life. By the way, in [KLM90], Kraus, Lehmann, and Magidor did not consider preference structures to be ontological justifications for their interest in the formal systems investigated, but to be technical tools to study those systems and in particular settle questions of interderivability and find efficient decision procedures (see the end of Section 1.2 of [START_REF] Kraus | Nonmonotonic reasoning, preferential models, and cumulative logics[END_REF]).

Second, in the proofs, we will work directly with choice functions and their properties, not with preference structures. By the way, the techniques developed in the present paper (especially in the discriminative case) can certainly be adapted to new properties.

The system P

Gabbay, Makinson, Kraus, Lehmann, and Magidor investigated extensively properties which should be satisfied by plausible non-monotonic consequence relations [Gab85, Mak89, Mak94, KLM90, LM92]. A certain set of properties, called the system P, plays a central role in this area. It is essentially due to Kraus, Lehmann, and Magidor [START_REF] Kraus | Nonmonotonic reasoning, preferential models, and cumulative logics[END_REF] and has been investigated further in [START_REF] Lehmann | What does a conditional knowledge base entail?[END_REF]. Let's present it.

Definition 22 Suppose L is a language containing the usual connectives ¬ and ∨, F the set of all wffs of L, F, V, |= a semantic structure, and |∼ a relation on F × F. Then, the system P is the set of the six following conditions: ∀ α, β, γ ∈ F,

Reflexivity α |∼ α Left Logical Equivalence ⊢ α ↔ β α |∼ γ β |∼ γ Right Weakening ⊢ α → β γ |∼ α γ |∼ β Cut α ∧ β |∼ γ α |∼ β α |∼ γ Cautious Monotonicity α |∼ β α |∼ γ α ∧ β |∼ γ Or α |∼ γ β |∼ γ α ∨ β |∼ γ
Note that α ∧ β is a shorthand for ¬(¬α ∨ ¬β). Similarly, α → β and α ↔ β are shorthands. Note again that P without Or is called C. The system C is closely related to the cumulative inference which was investigated by Makinson in [START_REF] Makinson | General theory of cumulative inference[END_REF]. In addition, it seems to correspond to what Gabbay proposed in [START_REF] Gabbay | Theoretical foundations for non-monotonic reasoning in expert systems[END_REF]. Concerning the rule Or, it corresponds to the axiom CA of conditional logic.

All the properties in P are sound if we read α |∼ β as "β is a plausible consequence of α". In addition, P is complete in the sense that it characterizes those consequence relations that can be defined by a smooth transitive irreflexive preference structure. This is what makes P central. More formally:

Definition 23 Suppose F, V, |= is a semantic structure. Then, D f := {V ⊆ V : ∃ α ∈ F, V = M α }.
Suppose L is a language containing the usual connectives ¬ and ∨, and F the set of all wffs of L. Then define the following condition:

∀ v ∈ V, ∀ α, β ∈ F, ∀ Γ ⊆ F, (KLM 0) v |= ¬α iff v |= α; (KLM 1) v |= α ∨ β iff v |= α or v |= β. (KLM 2) if for every finite subset ∆ of Γ, M ∆ = ∅, then M Γ = ∅.
Note that (KLM 2) is called "assumption of compactness" in [START_REF] Kraus | Nonmonotonic reasoning, preferential models, and cumulative logics[END_REF].

Proposition 24 [KLM90] Suppose L is a language containing the usual connectives ¬ and ∨, F the set of all wffs of L, F, V, |= a semantic structure satisfying (KLM 0)-(KLM 2), and |∼ a relation of F × F. Then, |∼ satisfies all the properties of P iff there exists a D f -smooth transitive irreflexive preference structure R on

V such that ∀ α, β ∈ F, α |∼ β iff µ R (M α ) ⊆ M β .
Note that |∼ is a relation on F × F, not P(F ) × F. This difference is crucial. Indeed, if we adapt the conditions of P in the obvious way to relations on P(F ) × F and if we replace D f by D in Proposition 24, then the latter does no longer hold. This negative result was shown by Schlechta in [START_REF] Schlechta | Some results on classical preferential models[END_REF]. Now, by Propositions 19 and 24, we immediately get the following representation theorem:

Proposition 25 Suppose Definition 20 (of preferential consequence relations) is adapted in the obvious way to relations on F × F (essentially, replace D by D f ), L is a language containing the usual connectives ¬ and ∨, F the set of all wffs of L, |∼ a relation on F × F, and F, V, |= a semantic structure such that (KLM 0)-(KLM 2) hold and

∀ V, W ∈ D f , V ∪ W ∈ D f and V ∩ W ∈ D f .
Then, LM preferential consequence relations are precisely those relations that satisfy the system P.

Example with a classical semantic structure

Let L be a classical propositional language of which the atoms are r, q, and p. Intuitively, r means Nixon is a republican, q means Nixon is a quaker, and p means Nixon is a pacifist. Let F be the set of all wffs of L, V the set of all classical two-valued valuations of L, and |= the classical satisfaction relation for these objects. Then, V is the set of the 8 following valuations: v 0 , v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , and v 7 , which are defined in the obvious way by the following table:

r q p v 0 0 0 0 v 1 0 0 1 v 2 0 1 0 v 3 0 1 1 v 4 1 0 0 v 5 1 0 1 v 6 1 1 0 v 7 1 1 1
Now, consider the class of all republicans and the class of all quakers. Consider that a republican is normal iff he is not a pacifist and that a quaker is normal iff he is a pacifist. And, consider that a valuation v is more normal than a valuation w from the point of view of a class C iff • Nixon is an individual of C in both v and w;

• Nixon is normal in v;

• Nixon is not normal in w.

In the following graph, there is an arrow from a valuation v to a valuation w iff v is more normal than w from the point of view of some class:

Given those considerations a natural preference structure on V is R = V, l, ≺ , where l is identity and ≺ is the relation such that ∀ v, w ∈ V, we have v ≺ w iff (1) or (2) below holds (i.e. there is an arrow from v to w):

(1) v |= r and v |= ¬p and w |= r and w |= ¬p;

(2) v |= q and v |= p and w |= q and w |= p.

Finally, let |∼ be the preferential consequence relation defined by the coherent choice function µ R .

Then, |∼ leads us to "jump" to plausible conclusions from incomplete information and to revise previous "hasty" conclusions in the face of new and fuller information. For instance, r |∼ ¬p and {r, p} |∼ ¬p and q |∼ p and {q, ¬p} |∼ p.

However, |∼ is not paraconsistent. In addition, some sets of formulas are rendered useless, because there is no preferred model for them, though there are models for them. For instance, {q, r} |∼ α, ∀ α ∈ F.

Example with the F OUR semantic structure

Consider the F OUR semantic structure F c , V 4 , |= 4 and suppose A = {r, q, p} (these objects have been defined in Section 2.1.2). In addition, make the same considerations about Nixon, the classes, normality, etc., as in Section 2.4.1, except that this time a valuation v is considered to be more normal than a valuation w from the point of view of a class C iff • in both v and w, the processor is informed that Nixon is an individual of C;

• in v, he is informed that Nixon is normal and not informed of the contrary;

• in w, he is not informed that Nixon is normal.

See Section 2.1.2 for recalls about the sources-processor systems. Given those considerations a natural preference structure on V 4 is R = V 4 , l, ≺ , where l is identity and ≺ is the relation such that ∀ v, w ∈ V 4 , we have v ≺ w iff (1) or (2) below holds (i.e. v is more normal than w from the point of view of some class):

(1) v |= r and v |= ¬p and v |= p and w |= r and w |= ¬p;

(2) v |= q and v |= p and v |= ¬p and w |= q and w |= p.

Let |∼ be the preferential consequence relation defined by the coherent choice function µ R .

Then, again we "jump" to plausible conclusions and revise previous "hasty" conclusions. For instance, r |∼ ¬p and {r, p} |∼ ¬p and q |∼ p and {q, ¬p} |∼ p.

In addition, |∼ is paraconsistent. For instance, {p, ¬p, q} |∼ p and {p, ¬p, q} |∼ ¬p and {p, ¬p, q} |∼ q and {p, ¬p, q} |∼ ¬q. And, it happens less often that a set of formulas is rendered useless because there is no preferred model for it, though there are models for it. For instance, this time, {q, r} |∼ p and {q, r} |∼ ¬p and {q, r} |∼ q and {q, r} |∼ ¬q and {q, r} |∼ r and {q, r} |∼ ¬r.

However, |∼ does not satisfy the Disjunctive Syllogism. Indeed, for instance, {¬r, r ∨ q} |∼ q.

Contributions

The main contributions of the present paper are summarized below. We characterized (in many cases, by purely syntactic conditions) families of preferential and preferential-discriminative consequence relations. Sometimes, we will need to make some assumptions about the semantic structure under consideration. However, no assumption will be needed for the three following families:

• the preferential consequence relations (Section 3.2);

• the DP preferential consequence relations (Section 3.1);

• the DP LM preferential consequence relations (Section 3.1).

We will assume (A1) and (A3) for:

• the CP preferential-discriminative consequence relations (Section 3.4);

• the CP DP preferential-discriminative consequence relations (Section 3.3);

• the CP DP LM preferential-discriminative consequence relations (Section 3.3).

And, we will need (A1), (A2), and (A3) for:

• the preferential-discriminative consequence relations (Section 3.4);

• the DP preferential-discriminative consequence relations (Section 3.3);

• the DP LM preferential-discriminative consequence relations (Section 3.3).

The non-discriminative and definability preserving case

The characterizations in this section have already been given in Proposition 3.1 of [START_REF] Schlechta | New techniques and completeness results for preferential structures[END_REF], under the assumption that a classical propositional semantic structure is considered. Using the same techniques as those of Schlechta, we show easily that his characterizations hold with any semantic structure.

The discriminative and definability preserving case

In this section, we will characterize certain families of DP preferential-discriminative consequence relations. To do so, we will develop new techniques (especially Lemmas 39 and 40 below). We need basic notations and an inductive construction:

Notation 33 N denotes the natural numbers including 0: {0, 1, 2, . . . , }. N + denotes the strictly positive natural numbers: {1, 2, . . . , }.

Z denotes the integers. Let i, j ∈ Z. Then, [i, j] denotes the set of all k ∈ Z such that i ≤ k ≤ j.

Let L be a language, ∨ a binary connective of L, F the set of all wffs of L, and β 1 , β 2 , . . . , β r ∈ F. Note that those conditions are purely syntactic when there is a proof system available for ⊢. As M ′ Γ = ∅, n(Γ) ≥ 1. In addition, we will show in Lemma 38 below that n(Γ) is finite and ∀ i ∈ N + with i ≤ n(Γ), M i Γ = ∅. Thus, β Γ is well-defined.

Notation 26

 26 Let F, V, |= be a semantic structure and |∼ a relation on P(F ) × F. Then, consider the following conditions: ∀ Γ, ∆ ⊆ F,(|∼0) if ⊢(Γ) = ⊢(∆), then |∼(Γ) = |∼(∆); (|∼1) ⊢(|∼(Γ)) = |∼(Γ); (|∼2) Γ ⊆ |∼(Γ); (|∼3) |∼(Γ, ∆) ⊆ ⊢(|∼(Γ), ∆);

Definition 35

 35 Whenever we write β 1 ∨ β 2 ∨ . . . ∨ β r , we mean (. . .((β 1 ∨ β 2 ) ∨ β 3 ) ∨ . . . ∨ β r-1 ) ∨ β r .Definition 34 Let L be a language, ¬ a unary connective of L, F the set of all wffs of L, F, V, |= a semantic structure, |∼ a relation on P(F ) × F, and Γ ⊆ F. Then,H 1 (Γ) := {¬β ∈ F : β ∈ ⊢(Γ, |∼(Γ)) \ |∼(Γ) and ¬β ∈ ⊢(Γ, |∼(Γ))}. Let i ∈ N with i ≥ 2. Then, H i (Γ) := {¬β ∈ F : β ∈ ⊢(Γ, |∼(Γ), H 1 (Γ), . . . , H i-1 (Γ)) \ |∼(Γ) and ¬β ∈ ⊢(Γ, |∼(Γ), H 1 (Γ), . . . , H i-1 (Γ)) Suppose L is a language, ¬a unary connective of L, ∨ a binary connective of L, F the set of all wffs of L, F, V, |= a semantic structure, and |∼ a relation on P(F ) × F. Then, consider the following conditions: ∀ Γ, ∆ ⊆ F, ∀ α, β ∈ F, (|∼6) if β ∈ ⊢(Γ, |∼(Γ)) \ |∼(Γ) and ¬α ∈ ⊢(Γ, |∼(Γ), ¬β), then α ∈ |∼(Γ); (|∼7) if α ∈ ⊢(Γ, |∼(Γ)) \ |∼(Γ) and β ∈ ⊢(Γ, |∼(Γ), ¬α) \ |∼(Γ), then α ∨ β ∈ |∼(Γ);(|∼8) if α ∈ |∼(Γ), then ¬α ∈ ⊢(Γ, |∼(Γ)); (|∼9) if ∆ ⊆ ⊢(Γ), then |∼(Γ) ∪ H(Γ) ⊆ ⊢(∆, |∼(∆), H(∆), Γ); (|∼10) if Γ ⊆ ⊢(∆) ⊆ ⊢(Γ, |∼(Γ), H(Γ)), then |∼(Γ) ∪ H(Γ) ⊆ ⊢(∆, |∼(∆), H(∆)); (|∼11) if Γ is consistent, then |∼(Γ) is consistent, Γ ⊆ |∼(Γ), and ⊢(|∼(Γ)) = |∼(Γ).

Proposition 36

 36 Suppose L is a language, ¬ a unary connective of L, ∨ and ∧ binary connectives of L, F the set of all wffs of L, F, V, |= a semantic structure satisfying (A1) and (A3), and |∼ a relation on P(F ) × F. Then, (0) |∼ is a CP DP preferential-discriminative consequence relation iff (|∼0), (|∼6), (|∼7), (|∼8), (|∼9), and (|∼11) hold; (1) |∼ is a CP DP LM preferential-discriminative consequence relation iff (|∼0), (|∼6), (|∼7), (|∼8), (|∼9), (|∼10), and (|∼11) hold.

F

  (Γ) := {¬β Γ } if M ′ Γ = ∅ ∅ otherwise G(Γ) := {α ∈ F : α ∈ |∼(Γ), ¬α ∈ |∼(Γ), and T d (M Γ,|∼(Γ),α ) ⊆ |∼(Γ)}

  [START_REF] Schlechta | New techniques and completeness results for preferential structures[END_REF], Schlechta showed that Coherence and Local Monotonicity characterize those choice functions that can be defined by a preference structure. Details are given in the proposition just below. It is an immediate corollary of Proposition 2.4, Proposition 2.15, and Fact 1.3 of[START_REF] Schlechta | New techniques and completeness results for preferential structures[END_REF].

Definition 37 Suppose L is a language, ¬ a unary connective of L, ∨ a binary connective of L, F the set of all wffs of L, F, V, |= a semantic structure satisfying (A1), |∼ a relation on P(F ) × F, and Γ ⊆ F. Then,M 1 Γ := {v ∈ M Γ,|∼(Γ) : ∃ β ∈ T (M Γ,|∼(Γ) ) \ |∼(Γ), v ∈ M ¬β }. Let i ∈ N with i ≥ 2. Then, M i Γ := {v ∈ M Γ,|∼(Γ) \M 1 Γ ∪. . .∪M i-1 Γ : ∃β ∈ T (M Γ,|∼(Γ) \M 1 Γ ∪. . .∪M i-1 Γ )\|∼(Γ), v ∈ M ¬β }. M ′ Γ := i∈N + M i Γ n(Γ) := |{i ∈ N + : M i Γ = ∅}| Suppose M 1 Γ = ∅. Then, we denote by β 1 Γ an element of F , chosen arbitrarily, such that ∃ r ∈ N + , ∃ v 1 , v 2 , . . . , v r ∈ V, and ∃ β 1 , β 2 , . . . , β r ∈ F with M 1 Γ = {v 1 , v 2 , . . . , v r }, β 1 Γ = β 1 ∨ β 2 ∨ . . . ∨ β r ,and ∀ j ∈ [1, r], β j ∈ |∼(Γ), M Γ,|∼(Γ) ⊆ M βj , and v j ∈ M ¬βj .As M 1 Γ = ∅ and M 1 Γ is finite (thanks to (A1)), such an element exists.Suppose i ∈ N, i ≥ 2, and M i Γ = ∅. Then, we denote by β i Γ an element of F , chosen arbitrarily, such that ∃ r ∈ N + , ∃ v 1 , v 2 , . . . , v r ∈ V, and ∃ β 1 , β 2 , . . . , β r ∈ F with M i Γ = {v 1 , v 2 , . . . , v r },β i Γ = β 1 ∨ β 2 ∨ . . . ∨ β r , and ∀ j ∈ [1, r], β j ∈ |∼(Γ), M Γ,|∼(Γ) \ M 1 Γ ∪ . . . ∪ M i-1 Γ ⊆ M βj , and v j ∈ M ¬βj . As M i Γ = ∅ and M iΓ is finite, such an element exists.Suppose M ′ Γ = ∅. Then,β Γ := β 1 Γ ∨ β 2 Γ ∨ . . . ∨ β n(Γ) Γ

Here are some quick results about the purely technical tools defined just above:Lemma 38 Suppose L is a language, ¬ a unary connective of L, ∨ a binary connective of L, F the set of all wffs of L, F, V, |= a semantic structure satisfying (A1), |∼ a relation on P(F ) × F, Γ ⊆ F, and i, j ∈ N + . Then,(0) if i = j, then M i Γ ∩ M j Γ = ∅; (1) if M i Γ = ∅, then M i+1 Γ = ∅;(2)T d (M Γ,|∼(Γ) ) ⊆ |∼(Γ) iff M 1 Γ = ∅;(3) if i ≥ 2, then T d (M Γ,|∼(Γ) \ M 1 Γ ∪ . . . ∪ M i-1 Γ ) ⊆ |∼(Γ) iff M i Γ = ∅; (4) n(Γ) is finite; (5) if i ≤ n(Γ), then M i Γ = ∅; (6) if i > n(Γ), then M i Γ = ∅; (7) if M ′ Γ = ∅, then M ′ Γ = M 1 Γ ∪ . . . ∪ M n(Γ) Γ

Proof Proof of (0), (1), and (2). Suppose M ′ Γ = ∅. Then, it suffices to show by induction:∀ i ∈ [1, n(Γ)], p 3 (i) (M 1 Γ ∪ . . . ∪ M i Γ ) ∩ M ¬(β 1 Γ ∨...∨β i Γ ) = ∅; p 2 (i) M Γ,|∼(Γ) ⊆ M β 1 Γ ∨...∨β i Γ ; p 1 (i) β 1 Γ ∨ . . . ∨ β i Γ ∈ |∼(Γ). As M 1 Γ = ∅, ∃ r ∈ N + , ∃ v 1 , v 2 , . . . , v r ∈ V, and ∃β 1 , β 2 , . . . , β r ∈ F, M 1 Γ = {v 1 , . . . , v r }, β 1 Γ = β 1 ∨ . . . ∨ β r , and ∀ j ∈ [1, r], β j ∈ |∼(Γ), M Γ,|∼(Γ) ⊆ M βj ,and v j ∈ M ¬βj . Then, it can be shown that: (0.0) p 3 (1) holds; (0.1) p 2 (1) holds; (0.2) p 1 (1) holds. Now, let i ∈ [1, n(Γ) -1] and suppose p 1 (i), p 2 (i), and p 3 (i) hold.As M i+1 Γ = ∅, ∃ r ∈ N + , ∃ v 1 , v 2 , . . . , v r ∈ V, and ∃ β 1 , β 2 , . . . , β r ∈ F, M i+1 Γ = {v 1 , . . . , v r }, β i+1 Γ = β 1 ∨ . . . ∨ β r , and ∀ j ∈ [1, r], β j ∈ |∼(Γ), M Γ,|∼(Γ) \ M 1 Γ ∪ . . . ∪ M i Γ ⊆ M βj ,and v j ∈ M ¬βj . Then, it can be shown that: (0.3) p 3 (i + 1) holds; (0.4) p 2 (i + 1) holds. Before turning to p 1 (i + 1), we need the following:(0.5) β 1 Γ ∨ . . . ∨ β i Γ ∨ β 1 ∨ β 2 ∨ . . . ∨ β r ∈ |∼(Γ); (0.6) p 1 (i + 1) holds. Proof of (0.0). If v j ∈ M 1 Γ , then v j ∈ M ¬βj . But, by (A3), M ¬β 1 Γ ⊆ M ¬βj .Proof of (0.1). We haveM Γ,|∼(Γ) ⊆ M β1 which is, by (A3), a subset of M β 1 Γ .Proof of (0.2). It suffices to show by induction:∀ j ∈ [1, r], q(j) β 1 ∨ . . . ∨ β j ∈ |∼(Γ).Obviously, q(1) holds. Let j ∈ [1, r -1]. Suppose q(j). We show q(j + 1). By (A3), we have M Γ,|∼(Γ) ⊆ M β1∨...∨βj . On the other hand, M Γ,|∼(Γ),¬(β1∨...∨βj ) ⊆ M Γ,|∼(Γ) ⊆ M βj+1 . Thus, by q(j) and (|∼7) (where α is β 1 ∨ . . . ∨ β j and β is β j+1 ), we getβ 1 ∨ . . . ∨ β j+1 ∈ |∼(Γ). 21 Proof of (0.3). Let v ∈ M 1 Γ ∪ . . . ∪ M i+1 Γ . We show v ∈ M ¬(β 1 Γ ∨...∨β i+1 Γ ) . Case 1: v ∈ M 1 Γ ∪ . . . ∪ M i Γ . Then, by p 3 (i), we have v ∈ M ¬(β 1 Γ ∨...∨β i Γ ) . But, by (A3), M ¬(β 1 Γ ∨...∨β i+1 Γ ) ⊆ M ¬(β 1 Γ ∨...∨β i Γ ) . Case 2: v ∈ M i+1 Γ . Then, ∃ j ∈ [1, r], v = v j . Thus, v ∈ M ¬βj . But, by (A3), M ¬(β 1 Γ ∨...∨β i+1 Γ ) ⊆ M ¬β i+1 Γ ⊆ M ¬βj . Proof of (0.4). By p 2 (i), M Γ,|∼(Γ) ⊆ M β 1 Γ ∨...∨β i Γ which is, by (A3), a subset of M β 1 Γ ∨...∨β i+1 Γ .Proof of (0.5). It suffices to show by induction∀ j ∈ [1, r]: q(j) β 1 Γ ∨ . . . ∨ β i Γ ∨ β 1 ∨ . . . ∨ β j ∈ |∼(Γ). We will show: (0.5.0) M Γ,|∼(Γ),¬(β 1 Γ ∨...∨β i Γ ) ⊆ M β1 .Then, by p 1 (i), p 2 (i), (0.5.0), and (|∼7) (where α is β 1 Γ ∨ . . . ∨ β i Γ and β is β 1 ), q(1) holds. Now, let j ∈ [1, r -1] and suppose q(j). Then, we will show:(0.5.1) M Γ,|∼(Γ),¬(β 1 Γ ∨...∨β i Γ ∨β1∨...∨βj) ⊆ M βj+1 .In addition, by p 2 (i) and (A3), we get:(0.5.2) M Γ,|∼(Γ) ⊆ M β 1 Γ ∨...∨β i Γ ∨β1∨...∨βj .By, (0.5.1), (0.5.2), q(j), and (|∼7) (where α is β 1 Γ ∨ . . . ∨ β i Γ ∨ β 1 ∨ . . . ∨ β j and β is β j+1 ), we get that q(j + 1) holds.Proof of (0.5.0).Let v ∈ M Γ,|∼(Γ),¬(β 1 Γ ∨...∨β i Γ ) . Then, v ∈ M ¬(β 1 Γ ∨...∨β i Γ ) . Thus, by p 3 (i), v ∈ M 1 Γ ∪ . . . ∪ M i Γ . Therefore, v ∈ M Γ,|∼(Γ) \ M 1 Γ ∪ . . . ∪ M i Γ ⊆ M β1 .Proof of (0.5.1).Let v ∈ M Γ,|∼(Γ),¬(β 1 Γ ∨...∨β i Γ ∨β1∨...∨βj) . Then, by (A3), v ∈ M ¬(β 1 Γ ∨...∨β i Γ ) . Therefore, by p 3 (i), v ∈ M 1 Γ ∪ . . . ∪ M i Γ . Therefore, v ∈ M Γ,|∼(Γ) \ M 1 Γ ∪ . . . ∪ M i Γ ⊆ M βj+1 .Proof of (0.6). By p 2 (i) and (A3), we get M Γ,|∼(Γ) ⊆ M β 1 Γ ∨...∨β i Γ ⊆ M β 1 Γ ∨...∨β i Γ ∨β1∨...∨βr . In addition, by (A3), we get M ¬(β 1 Γ ∨...∨β i Γ ∨β1∨...∨βr) = M ¬(β 1 Γ ∨...∨β i+1 Γ ) . Therefore, by (0.5) and (|∼6) (where α is β 1 Γ ∨ . . . ∨ β i+1 Γ and β is β 1 Γ ∨ . . . ∨ β i Γ ∨ β 1 ∨ . . . ∨ β r ), we get that p 1 (i + 1) holds. Proof of (3). Suppose M ′ Γ = ∅, v ∈ M Γ,|∼(Γ) \ M ′ Γ , and v ∈ M ¬βΓ .

Proof of (0.0). Let Γ, ∆ ⊆ F and suppose ⊢(Γ) = ⊢(∆). Then, M Γ = M ∆ . Thus, |∼(Γ) = T (µ(M Γ )) = T (µ(M ∆ )) = |∼(∆).

Proof of (0.1). Let Γ ⊆ F. Then, ⊢(|∼(Γ)) = ⊢(T (µ(M Γ ))) = T (M T (µ(MΓ)) ) = |∼(Γ).

Proof of (0.2). Let Γ ⊆ F. Then, Γ ⊆ T (M Γ ) ⊆ T (µ(M Γ )) = |∼(Γ).

Proof of (0.3). Let Γ ⊆ F. As, µ is DP, µ(M Γ ) ∈ D.

Proof of (0.4). Let Γ, ∆ ⊆ F. As, M Γ,∆ ⊆ M Γ and µ is coherent,

Proof of (0.5). Let Γ ⊆ F. Then, µ(M Γ ) = M |∼(Γ) , which is, by (|∼2), a subset of M Γ .

Proof of (0.6). Let Γ, ∆ ⊆ F and suppose

Proof of (1). Direction: "→". Verbatim the same proof as for (0), except that in addition µ is LM. We use it to show that |∼ satisfies (|∼4). Let Γ, ∆ ⊆ F and suppose Γ ⊆ ⊢(∆) ⊆ |∼(Γ). Then, by

Direction: "←". Verbatim the same proof as for (0), except that in addition (|∼4) is satisfied. We use it to show that µ is locally monotonic. Let Γ, ∆ ⊆ F and suppose

Proof Proofs of (0), (1), (2), and (3). Trivial.

Proof of (4). Obvious by (0) and (A1).

Proof of (5). Suppose ∃ i ∈ N + , M i Γ = ∅ and i ≤ n(Γ). Then, by (1), ∀ j ∈ N + , j ≥ i, M j Γ = ∅. Thus, |{j ∈ N + : M j Γ = ∅}| ≤ i -1 < n(Γ), which is impossible.

Proof of (6). Suppose ∃ i ∈ N + , M i Γ = ∅ and i > n(Γ). Then, by (1), ∀ j ∈ N + , j ≤ i, M j Γ = ∅. Thus, |{j ∈ N + : M j Γ = ∅}| ≥ i > n(Γ), which is impossible.

Proof of (7). Obvious by (6).

Proof of (8). Case 1:

). In addition, M 1 Γ = ∅. Thus, by (2), we are done. Case 2:

Then, we will show:

Proof of (7.0). We have

To show (7.0), it suffices to show by induction (in the decreasing direction):

Therefore, p(i -1) holds (take α ∧ ¬β).

Proof of (8). Suppose M ′ Γ = ∅. Now, suppose the contrary of what we want to show, i.e.

But, by (8), (7), and (5

Proof of (10).

Case 1:

Tc(µ(MΓ)) . Therefore, by (5), M Γ,|∼(Γ),H(Γ) = µ(M Γ ). Case 2: M ′ Γ = ∅. Obvious by (6).

And finally, by Lemma 39 (7), ∀ Γ ⊆ F, |∼(Γ) = T d (µ(M Γ )).

Proof of (0.0). Let Γ, ∆ ⊆ F and suppose ⊢(Γ) = ⊢(∆). Then,

Proof of (0.1). Let Γ ⊆ F and suppose Γ is consistent.

Proof of (0.2). Let Γ, ∆ ⊆ F and suppose

proof of (1). Direction: "→". Verbatim the proof of (0), except that in addition µ is LM. Then, by Lemma 40 (10) and LM, |∼ satisfies (|∼10). Direction: "←". Verbatim the proof of (0), except that in addition |∼ satisfies (|∼10). Then, by definition of µ and (|∼10), µ is LM.

Proof of (2). Direction: "→". Verbatim the proof of (0), except that µ is no longer CP, whilst (A2) now holds. Note that, in (0), CP was used only to show (|∼11) and (|∼9). But, (|∼11) is no longer required to hold. In addition, by Lemma 40 (9) and Coherence of µ, (|∼9) holds.

Direction: "←". Verbatim the proof of (0), except that (|∼11) does no longer hold, whilst (A2) now holds. However, in (0), (|∼11) was used only to show that µ is CP, which is no longer required. Note that we do not need to use (A2) in this direction.

Proof of (3). Direction "→". Verbatim the proof of (0), except that µ is no longer CP, whilst µ is now LM and (A2) now holds. Note that, in (0), CP was used only to show (|∼11) and (|∼9). But, (|∼11) is no longer required. In addition, by Lemma 40 (9) and Coherence of µ, (|∼9) holds.

(|∼4) if Γ ⊆ ⊢(∆) ⊆ |∼(Γ), then |∼(Γ) ⊆ |∼(∆).

Note that those conditions are purely syntactic when there is a proof system available for ⊢ (which is the case with e.g. the classical, F OUR, and J 3 semantic structures).

Proposition 27 Let S = F, V, |= be a semantic structure and |∼ a relation on P(F ) × F. Then, (0) |∼ is a DP preferential consequence relation iff (|∼0), (|∼1), (|∼2), and (|∼3) hold;

(1) |∼ is a DP LM preferential consequence relation iff (|∼0), (|∼1), (|∼2), (|∼3), and (|∼4) hold.

Proof Proof of (0). Direction: "→". By hypothesis, there exists a DP coherent choice function µ from D to P(V) such that ∀ Γ ⊆ F, |∼(Γ) = T (µ(M Γ )). We will show: (0.0) |∼ satisfies (|∼0); (0.1) |∼ satisfies (|∼1); (0.2) |∼ satisfies (|∼2). Before turning to (|∼3), we need a preliminary result: (0.3) ∀ Γ ⊆ F, we have µ(M Γ ) = M |∼(Γ) ; (0.4) |∼ satisfies (|∼3).

Direction: "←". Suppose |∼ satisfies (|∼0), (|∼1), (|∼2), and (|∼3). Let µ be the function from D to P(V) such that ∀ Γ ⊆ F, µ(M Γ ) = M |∼(Γ) . Then, µ is well-defined. Indeed, If Γ, ∆ ⊆ F and M Γ = M ∆ , then ⊢(Γ) = ⊢(∆), thus, by (|∼0), |∼(Γ) = |∼(∆). In addition, µ is obviously DP. We show the following which ends the proof: (0.5) µ is a choice function; (0.6) µ is coherent; (0.7) ∀ Γ ⊆ F, we have |∼(Γ) = T (µ(M Γ )).

The non-discriminative and not necessarily definability preserving case

In this section, we will characterize the family of all preferential consequence relations. Unlike in Section 3.1, our conditions will not be purely syntactic (i.e. using only ⊢, |∼, etc.). In fact, properties like Coherence cannot be translated in syntactic terms because the choice functions under consideration are not necessarily definability preserving. Indeed, we do no longer have at our disposal the equality: µ(M Γ ) = M |∼(Γ) , which is of great help to perform the translation and which holds precisely because of Definability Preservation.

In Proposition 5.2.11 of [START_REF] Schlechta | Coherent systems[END_REF], K. Schlechta provided a characterization of the aforementioned family, under the assumption that a classical propositional semantic structure is considered. Note that most of his work is done in a very general, in fact algebraic, framework. Only at the end, he applied his general lemmas in a classical framework to get the characterization. The conditions he gave, as ours, are not purely syntactic (e.g. they involve the notion of model, etc.). Moreover, some limits of what can be done in this area have been put in evidence by Schlechta. Approximatively, he showed in Proposition 5.2.15 of the same book that, in an infinite classical framework, there does not exist a characterization containing only conditions which are universally quantified, of limited size, and using only simple operations (like e.g. ∪, ∩, \).

The purpose of the present section is to provided a new characterization, more elegant than the one of Schlechta and that hold with any semantic structure. To do so, we have been inspired by the algebraic part of the work of Schlechta (see Proposition 5.2.5 of [START_REF] Schlechta | Coherent systems[END_REF]). Technically, the idea begins by building from any function f , a coherent choice function µ f such that whenever f "covers" some coherent choice function, it necessarily covers µ f . Definition 28 Let V be a set, V and W subsets of P(V), and f a function from V to W. We denote by µ f the function from

Lemma 29 Let V be a set, V and W subsets of P(V), and f a function from V to W. Then, µ f is a coherent choice function.

Proof µ f is obviously a choice function. It remains to show that it is coherent. Suppose V, W ∈ V, V ⊆ W , and v ∈ µ f (W ) ∩ V . We show v ∈ µ f (V ). To do so, suppose the contrary, i.e. suppose v ∈ µ f (V ). Then, as v ∈ V , we have

Lemma 30 Let V be a set, V, W, and X subsets of P(V), f a function from V to W, and µ a coherent choice function from

Now, everything is ready to show the representation result.

Notation 31 Let F, V, |= be a semantic structure and |∼ a relation on P(F ) × F. Then, consider the following condition:

Proposition 32 Let F, V, |= be a semantic structure and |∼ a relation on P(F ) × F. Then, |∼ is a preferential consequence relation iff (|∼5) holds.

Proof Direction: "→".

There exists a coherent choice function µ from

And finally, by Lemma 29, µ f is a coherent choice function. The proof of Proposition 36 has been relegated at the end of Section 3.3. We need first Notation 33, Definition 37 and Lemmas 38, 39, and 40 below. Here are some purely technical tools:

).

In addition, n(Γ) + 1 ≥ 2 and, by (6), M n(Γ)+1 Γ = ∅. Thus, by (3), we are done.

We turn to an important lemma. Its main goal is to show that the conditions (|∼6), (|∼7), and (|∼8) are sufficient to establish the following important equality:

, which provides a semantic definition of |∼ (in the discriminative manner).

Lemma 39 Suppose L is a language, ¬ a unary connective of L, ∨ and ∧ binary connectives of L, F the set of all wffs of L, F, V, |= a semantic structure satisfying (A1) and (A3), |∼ a relation on P(F ) × F satisfying (|∼6), (|∼7), and (|∼8), and Γ ⊆ F. Then,

). Then, by (0), (1), and definition of

, which is impossible by Lemma 38 (6).

Proof of (4). Case 1:

Proof of (5). Direction: "⊆".

Case 1:

Consequently, by (0), (1), and (|∼6), we get α ∈ |∼(Γ), which is impossible. Case 2:

Direction: "⊇". Obvious by (4) and Lemma 38 (8).

Proof of (6). Direction: "⊆".

Case 1:

, we get, by (2), M Γ,|∼(Γ) ⊆ M ¬βΓ . Thus, by (0) and (1), we get

Direction: "⊇". Case 1: M ′ Γ = ∅. Verbatim the proof of Case 1 of direction "⊆". Case 2: M ′ Γ = ∅. Then, the following holds: (6.0) ∀i ∈ N + , M Γ,|∼(Γ),¬βΓ ⊆ M Γ,|∼(Γ),H1(Γ),...,Hi(Γ) . Now, suppose the contrary of what we want to show, i.e. suppose

, which is impossible by (6.0).

Proof of (6.0). We show by induction: ∀i ∈ N + , p(i) M Γ,|∼(Γ),¬βΓ ⊆ M Γ,|∼(Γ),H1(Γ),...,Hi(Γ) . We will show (6.0.0) p(1) holds. Let i ∈ N + , suppose p(i) holds, and suppose p(i + 1) does not hold.

But, by Lemma 38 (7), by (4), and p(i), we get

, which is impossible by Lemma 38 (6).

Proof of (6.0.0). Suppose the contrary of what we want to show, i.e. suppose

Proof of (7). Obvious by (5) and (6).

We turn to a second important lemma. Its main purpose is to show that any DP choice function µ representing (in the discriminative manner) a relation |∼ satisfies the following equality: µ(M Γ ) = M Γ,|∼(Γ),H(Γ) , which enables us to define µ from |∼.

Lemma 40 Suppose L is a language, ¬ a unary connective of L, ∨ and ∧ binary connectives of L, F the set of all wffs of L, F, V, |= a semantic structure satisfying (A1) and (A3), V ⊆ P(V), µ a DP choice function from D to V, |∼ the relation on

and Γ ⊆ F. Then:

(1) |∼ satisfies (|∼6);

(2) |∼ satisfies (|∼7);

(3) |∼ satisfies (|∼8);

(4)

If F, V, |= satisfies (A2) too, then:

If µ is coherency preserving, then again:

Proof Proof of (0). We show µ(M Γ ) ⊆ M |∼(Γ) . Let v ∈ µ(M Γ ) and α ∈ |∼(Γ). Then, α ∈ T d (µ(M Γ )). Thus, µ(M Γ ) ⊆ M α . Thus, v ∈ M α and we are done. In addition, obviously,

Proof of (4). Case 1:

Then, by p(i), we obviously get p(i + 1).

Proof of (4.0). Suppose the contrary of p(1), i.e. suppose

Proof of (6). Suppose M ′ Γ = ∅. Direction: "⊆". Case 1:

By Lemma 39 (3), Lemma 38 (7), and

. By (0) and Lemma 39 (1),

. Therefore, by Lemma 38 (6), we get a contradiction. Case 2:

. Then, by Lemma 39 (6), Lemma 39 (4), Lemma 38 (7), and by (5), we get

). Direction: "⊇". By (0), (4), Lemma 39 (4), and Lemma 39 (6), we get

Proof of (7). Suppose M ′ Γ = ∅. Direction: "⊇". Suppose the contrary of what we want to show, i.e. suppose

Now comes the proof of Proposition 36 (which is stated at the beginning of Section 3.3).

Proof Proof of (0). Direction: "→". There exists a CP DP coherent choice function µ from D to P(V) such that ∀ Γ ⊆ F, |∼(Γ) = T d (µ(M Γ )). We will show: (0.0) |∼ satisfies (|∼0). By Lemma 40 (1), (2), and (3), |∼ satisfies (|∼6), (|∼7), and (|∼8). By Lemma 40 (10) and Coherence of µ, |∼ satisfies (|∼9). We will show: (0.1) |∼ satisfies (|∼11).

Direction: "←". Suppose |∼ satisfies (|∼0), (|∼6), (|∼7), (|∼8), (|∼9), and (|∼11). Then, let µ be the function from

We will show: (0.2) µ is well-defined. Clearly, µ is a DP choice function. In addition, as |∼ satisfies (|∼9), µ is coherent. We will show:

Similarly, by Lemma 40 (9) and Local Monotonicity of µ, (|∼10) holds.

Direction: "←". Verbatim the proof of (0), except that (|∼11) does no longer hold, whilst (|∼10) and (A2) now holds. Note that, in (0), (|∼11) was used only to show that µ is CP, which is no longer required. Now, by definition of µ and by (|∼10), µ is LM. Note that we do not need to use (A2) in this direction.

The discriminative and not necessarily definability preserving case

Unlike in Section 3.3, the conditions of this section will not be purely syntactic. The translation of properties like Coherence in syntactic terms is blocked because we do no longer have the following useful equality: µ(M Γ ) = M Γ,|∼(Γ),H(Γ) , which holds when the choice functions under consideration are definability preserving (but this is not the case here). Thanks to Lemmas 29 and 30 (stated in Section 3.2), we will provide a solution with semi-syntactic conditions.

Notation 41 Let L be a language, ¬ a unary connective of L, F the set of all wffs of L, F, V, |= a semantic structure, and |∼ a relation on P(F ) × F. Then, consider the following condition:

Proposition 42 Let L be a language, ¬ a unary connective of L, ∨ and ∧ binary connectives of L, F the set of all wffs of L, F, V, |= a semantic structure satisfying (A1) and (A3), and |∼ a relation on P(F ) × F. Then, Proof Proof of (1). Direction: "→". There exists a coherent choice function µ from

Then, |∼ satisfies obviously (|∼0).

Let f be the function from

Consequently, by Lemma 40 (1), (2), and (3), |∼ satisfies (|∼6), (|∼7), and (|∼8).

In addition, by Lemma 40

Direction: "←". Suppose (|∼0), (|∼6), (|∼7), (|∼8), and (|∼12) hold. Let f be the function from

But, by Lemma 29, µ f is a coherent choice function.

Proof of (0). Direction: "→". Verbatim the proof of (1), except that (A2) does no longer hold, whilst µ is now CP. Note that (A2) was used only to apply Lemma 40 (9) to get ∀ Γ ⊆ F, f (M Γ ) = M Γ,|∼(Γ),H(Γ) . But, we will get this equality by another mean.

Therefore f is CP. Consequently, by Lemma 40 (10), we get ∀ Γ ⊆ F, f (M Γ ) = M Γ,|∼(Γ),H(Γ) . In addition, by verbatim the proof of (0.1) of Proposition 36, |∼ satisfies (|∼11).

Direction: "←". Verbatim the proof of (1), except that (A2) does no longer hold, whilst |∼ now satisfies (|∼11). But, in this direction, (A2) was not used in (0). It remains to show that µ f is CP. By verbatim the proof of (0.3) of Proposition 36, we get that f is CP. Let V ∈ D ∩ C. Then, f (V ) ∈ C. Thus, M T (µ f (V )) ∈ C. Thus, µ f (V ) ∈ C and we are done.

Conclusion

We provided, in a general framework, characterizations for families of preferential(-discriminative) consequence relations. Note that we have been strongly inspired by the work of Schlechta in the non-discriminative case, whilst we developed new techniques and ideas in the discriminative case. In many cases, our conditions are purely syntactic. In fact, when the choice functions under consideration are not necessarily definability preserving, we provided solutions with semi-syntactic conditions. We managed to do so thanks to Lemmas 29 and 30. An interesting thing is that we used them both in the plain and the discriminative versions. This suggests that they can be used in yet other versions. In addition, we are quite confident that Lemmas 39 and 40 can be used to characterize other families of consequence relations defined in the discriminative manner by DP choice functions (not necessarily coherent, unlike all the families investigated here).

Acknowledgements

I owe very much to Karl Schlechta for his hints, advice, constructive criticism, and more. I acknowledge also Arnon Avron for valuable discussions.


Tristan Cazenave

Fabien Teytaud

Beam Nested Rollout Policy Adaptation

The Nested Rollout Policy Adaptation algorithm is a tree search algorithm known to be efficient on combinatorial problems. However, one problem of this algorithm is that it can converge to a local optimum and get stuck in it. We propose a modification which limits this behavior and we experiment it on two combinatorial problems for which the Nested Rollout Policy Adaption is known to be good at.

Introduction

. The idea behind the NMC algorithm can been seen as a Meta Monte-Carlo algorithm. This is a recursive algorithm. The first level of the search consists in simply performing a Monte-Carlo simulation, i.e. each decision is chosen randomly until no more possible decision are available. At the end, the score of the position that has been reached is sent back. This first level is called the level 0. For each other level lvl > 0, the search consists in launching a NMC algorithm with a level lvl -1 for each possible decision. Such as for the level 0, the score for each reached position is sent back, and the decision with the best score is chosen. This algorithm is presented in Section 3. The NRPA algorithm is based on this idea, except that a level 0 policy is learned by gradient ascent and is used instead of the Monte-Carlo policy. This algorithm is presented in Section 4. One problem of this algorithm is that it can converge to local optima due to its simple learning. In this work, we propose a modification in order to improve the behavior of the NRPA algorithm in front of local optima. The principle of the modification consists in keeping a beam of different sequences (with their corresponding policies).

The paper is organized as follows. The next section (Section 2) presents the two problems studied in this work, the Traveling Salesman Problem with Time Windows in Section 2.1 and the Morpion-Solitaire puzzle in Section 2.2. In Section 3, the Nested Monte-Carlo Search is presented, in Section 4 we present the Nested Rollout Policy Adaptation algorithm, and in Section 5 the improvement done on the NRPA algorithm. Finally, in Section 6 we present comparisons between the NRPA algorithm and the algorithm designed in this work.

Problems

In this Section we present two well-known combinatorial problems. The first one, presented in Section 2.1 is the Traveling Salesman Problem with Time Windows. The second problem is the puzzle called Morpion-Solitaire and is presented in Section 2.2. The NRPA algorithm has been already used for solving these two problems [START_REF] Christopher | Nested rollout policy adaptation for monte carlo tree search[END_REF][START_REF] Cazenave | Application of the nested rollout policy adaptation algorithm to the traveling salesman problem with time windows[END_REF].

The Traveling Salesman Problem with Time Windows

The Traveling Salesman Problem (TSP) is a well-known logistic problem. Given a list of cities and their pairwise distances, the goal is to find the shortest possible path that visits each city only once. The path has to start and finish at a given depot. The TSP problem is NP-hard [START_REF] Johnson | Computational complexity and the traveling salesman problem[END_REF]. The Traveling Salesman Problem with Time Windows (TSPTW) is a problem based on the TSP. Inputs are the same, but a difficulty is added. In this version, a time interval is defined for each city, and each city has to be visited within its corresponding period of time.

Formally, the TSPTW can be defined as follows. Let G be an undirected complete graph. G = (N, A), where N = 0, 1, . . . , n corresponds to a set of nodes and A = N ×N corresponds to the set of edges between the nodes. The node 0 corresponds to the depot. Each city is represented by the n other nodes. A cost function c : A → R is given and represents the distance between two cities. A solution to this problem is a sequence of nodes P = (p 0 , p 1 , . . . , p n ) where p 0 = 0 and (p 1 , . . . , p n ) is a permutation of [1, N ]. Set p n+1 = 0 (the path must finish at the depot), then the goal is to minimize the function defined in Equation 1.

cost(P ) = n k=0 c(a(p k , p k+1 )) (1)
As said previously, the TSPTW version is more difficult because each city i has to be visited in a time interval [e i , l i ]. This means that a city i has to be visited before l i . It is possible to visit a city before e i , but in that case, the new departure time becomes e i . Consequently, this case may be dangerous as it generates a penalty. Formally, if r p k is the real arrival time at node p k , then the departure time d p k from this node is

d p k = max(r p k , e p k ).
In the TSPTW, the function to minimize is the same as for the TSP (Equation 1), but a set of constraints is added and must be satisfied. Let us define Ω(P ) as the number of violated windows constraints by tour (P). Two constraints are defined. The first constraint is to check that the arrival time is lower than the fixed time. Formally,

∀p k , r p k < l p k .
The second constraint is the minimization of the time lost by waiting at a city. Formally,

r p k+1 = max(r p k , e p k ) + c(a p k ,p k+1 ).
With algorithms used in this work, paths with violated constraints can be generated. As presented in [START_REF] Rimmel | Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows[END_REF], a new score T cost(p) of a path p can be defined as follows:

T cost(p) = cost(p) + 10 6 * Ω(p), with, as defined previously, cost(p) the cost of the path p and Ω(p) the number of violated constraints. 10 6 is a constant chosen high enough so that the algorithm first optimizes the constraints.

A survey of efficient methods for solving the TSPTW can be found in [START_REF] López | Beam-ACO for the travelling salesman problem with time windows[END_REF]. Existing methods for solving the TSPTW are numerous. First, branch and bound methods were used [START_REF] Baker | An exact algorithm for the time-constrained traveling salesman problem[END_REF][START_REF] Christofides | State-space relaxation procedures for the computation of bounds to routing problems[END_REF]. Later, dynamic programing based methods [START_REF] Dumas | An optimal algorithm for the traveling salesman problem with time windows[END_REF], heuristics based algorithms [START_REF] Solomon | Algorithms for the vehicle routing and scheduling problems with time window constraints[END_REF][START_REF] Gendreau | A generalized insertion heuristic for the traveling salesman problem with time windows[END_REF] and methods based on constraint programming [START_REF] Focacci | A hybrid exact algorithm for the tsptw[END_REF][START_REF] Pesant | An exact constraint logic programming algorithm for the traveling salesman problem with time windows[END_REF] have been published. More recently, ant colony optimization algorithms have been used [START_REF] López | Beam-ACO for the travelling salesman problem with time windows[END_REF] and have established new state of the art scores. Works based on the NMC have been proposed in [START_REF] Rimmel | Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows[END_REF] and on the NRPA in [START_REF] Cazenave | Application of the nested rollout policy adaptation algorithm to the traveling salesman problem with time windows[END_REF].

Morpion-Solitaire

Morpion-Solitaire is an NP-hard pencil-and-paper puzzle played on a square grid. A move consists in adding a circle (on one possible intersection on the grid) such that a line containing five circles can be drawn. The new line is then added to the grid. Lines can be horizontal, vertical or diagonal. The initial grid contains some starting circles, as shown in Figure 1. Two versions of this puzzle exist, the touching version and the disjoint version. In this paper, we are interested in the first one, the disjoint version, for which a circle can not belong to two lines that have the same direction. The best human score for this version of the puzzle is 68 moves [START_REF] Demaine | Morpion solitaire[END_REF]. The Nested Monte-Carlo search found a score of 80 moves [START_REF] Cazenave | Nested Monte-Carlo search[END_REF], and [START_REF] Christopher | Nested rollout policy adaptation for monte carlo tree search[END_REF] found a new record with 82 moves.

Nested Monte-Carlo Search

The basic idea of Nested Monte-Carlo Search is to perform a principal playout with a bias on the selection of each decision based on the results of a Monte-Carlo tree search [START_REF] Cazenave | Nested Monte-Carlo search[END_REF].

The base level of the search build random solutions (i.e. playouts), random decision are chosen until the end at this level. When a solution is completely built, the score of the position that has been reached is sent back.

At each decision of a playout of level 1 it chooses the decision that gives the best score when followed by a random playout. Similarly for a playout of level n it chooses the decision that gives the best score when followed by a playout of level n -1.

When a search at the highest level is finished and there is time left, another search is performed at the highest level, and so on until the thinking time is elapsed.

Nested Monte-Carlo search has been successful in establishing world records in single player games such as Morpion Solitaire or SameGame [START_REF] Cazenave | Nested Monte-Carlo search[END_REF]. It provides a good balance between exploration and exploitation and it automatically adapts its search behavior to the problem at hand without parameters tuning. Figure 2 illustrates a level 1 Nested Monte-Carlo search. Three selections of cities at level 1 are shown. The leftmost tree shows that, at the root, all possible cities are tried and that for each possible decision a playout follows it. Among the three possible cities at the root, the rightmost city has the best result of 30, therefore this is the first decision played at level 1. This brings us to the middle tree. After this first city choice, playouts are performed again for each possible city following the first choice. One of the cities has result 20 which is the best playout result among his siblings. So the algorithm continues with this decision as shown in the rightmost tree. This algorithm is presented in Algorithm 1. At each choice of a playout of level 1 it chooses the city that gives the best score when followed by a single random playout. Similarly for a playout of level n it chooses the city that gives the best score when followed by a playout of level n -1.

Algorithm 1

The Nested Rollout Policy Adaptation algorithm (NRPA) is an algorithm that learns a playout policy. There are different levels in the algorithm. Each level is associated to the best sequence found at that level. The playout policy is a vector of weights that are used to calculate the probability of choosing a city. A city is chosen proportionally to the exponential of its associated weight. Learning the playout policy consists in increasing the weights associated to the best cities and decreasing the weights associated to the other cities. The algorithm is given in Algorithm 2. The idea of Beam Nested Rollout Policy Adaptation is to combine a beam search with the Nested Rollout Policy Adaptation algorithm. Instead of memorizing one sequence at each level of the algorithm, a set of the best sequences is memorized at each level. The size of the beam for a given level is the number of sequences in the set of this level. Note that the sequences are not memorized alone. Each memorized sequence is associated to a score and a policy. The algorithm is given in Algorithm 3. In the algorithm r is a score, s is a sequence and p is a policy.

Algorithm 2

As can be seen in the algorithm, a recursive call is performed for each sequence in the set of best sequences for each level. At the end of the algorithm a set of the best sequences and the associated policies and scores is returned. This set is used to adapt the policies at the upper level and these adapted policies are inserted in the set of best sequences at the upper level. When all the sequences coming from the calls at the lower level have been inserted, only the B best ones are kept (B being the size of the beam at that level).

The Adapt function that learns the policy is the same as in the original NRPA algorithm.

Algorithm 3 Beam

Experimental Results

We apply the beam NRPA algorithm to two applications, the TSPTW, presented in Section 2.1 and the Morpion-Solitaire puzzle, presented in Section 2.2. Results are presented respectively in Section 6.1 and in Section 6.2. We define the complexity of the algorithm as the total number of evaluations (rollout) done by the algorithm. Formally, for the beam NRPA algorithm, the complexity is

C = (N * B) lvl
with B the size of the beam, lvl the level of the algorithm and N the number of iterations done for the learning. Experimentally, we have found that having a beam size B > 1 only for the level 1 was the best choice in terms of complexity. The complexity becomes then

C = N lvl * B
. For all our experiments, the size of the beam is fixed to 1 for all levels above 1 and is changed at level 1. Consequently, increasing the complexity comes to increase the size of the beam at level 1. In order to have comparable complexities for both beam NRPA and NRPA algorithms, we repeat the NRPA algorithm B times, and we take the best value found during the B runs as the return value of the algorithm.

Traveling Salesman Problem with Time Windows

In a first experiment on the TSPTW, we compare the best score found by the two algorithms on two fixed problems from the set of problems from [START_REF] Potvin | The vehicle routing problem with time windows part II: genetic search[END_REF]. The two problems are the problem rc203.1, which is a simple one, with 19 cities, and the rc202.3, which has 29 cities and is then harder. We measure the average traveling score as a function of C. We experiment N = {20, 50, 100} and B = {2, 4, 8, 16, 32, 64} for N = 20, B = {2, 4, 8, 16} for N = 50 and B = {2, 4, 8} for N = 100. Results for the problem rc203.1 are presented in Figure 3. We experiment three different values of N in level 2. The beam NRPA is always better than the classic algorithm for all complexities (i.e., for all different sizes of beam). N = 20 and N = 50 for the beam algorithm are the only versions that are able to find valid paths (i.e. without violated constraints).

For the second problem (rc202.3), results are presented in Figure 4. Here again, it is always better to use the beam NRPA algorithm. We can note that, because this problem is harder, a larger value of N is needed, meaning that more time need to be spent during the learning phase. Best results are found with the beam NRPA algorithm with N = 50 and N = 100.

The last experiment on the TSPTW, is to run the beam NRPA algorithm on all problems from the set of problems from [START_REF] Potvin | The vehicle routing problem with time windows part II: genetic search[END_REF], and to compare our results with the results found by the NRPA algorithm from [START_REF] Cazenave | Application of the nested rollout policy adaptation algorithm to the traveling salesman problem with time windows[END_REF]. Results are presented in Table 1.

As expected, we can see that the beam NRPA algorithm is always able to find better scores than the NRPA algorithm. The beam NRPA is able to find 63% of state of the art scores, and this without any expert knowledge. Expert knowledge can be added to the beam NRPA algorithm, in the same way as in the NRPA version from [START_REF] Cazenave | Application of the nested rollout policy adaptation algorithm to the traveling salesman problem with time windows[END_REF].

Morpion-Solitaire

The second experimented application is the Morpion-Solitaire puzzle. As for the two first experiments on the TSPTW, we measure the best score found by the beam NRPA and the NRPA algorithms as a function of the complexity in level 2. For this application, the higher scores the better. Results are presented in Figure 5. For beam sizes larger than 2, results are always better for the beam NRPA algorithm. For B = 2, results are equivalent.

Conclusion

In this work we show how to improve the Nested Rollout Policy Adaptation algorithm. For both applications, results are good for a beam size of 4. When the size of the beam increases, results are even better. On the first experimented application, the traveling salesman problem with time windows, we do not use any expert knowledge. Our goal was then, not to find new records, but to show the efficiency of having numerous learned policies. The classic NRPA algorithm find 43% of state of the art records, whereas the beam NRPA algorithm is able to find 63% of records. Only for 2 problems we are not able to find equal or better scores than the NRPA algorithms. For all other problems, scores are equal or better for the beam NRPA algorithm. On the Morpion Solitaire puzzle, we reach the current record (82 moves), but we are not able to beat it. However, as shown in Figure 5 best scores are found faster with the beam algorithm than with the classic NRPA algorithm. This behaviour has been also observed for the traveling salesman problem with time windows (Figures 4 and3). As pointed out in the future works of the NRPA algorithm's author in [START_REF] Christopher | Nested rollout policy adaptation for monte carlo tree search[END_REF], realizing a parallel version of the NRPA algorithm is a challenging work. The beam NRPA algorithm has the advantage to be easily parallelizable, because, all policies from the beam can be evaluated in parallel. An interesting future work is to keep distances between all the sequences from the beam. Having such a modification should be much more robust in front of local optima.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Example of a puzzle. Circles represent initial points and numbers represent the moves.This 82 moves grid found by our algorithm equalizes the world record established by Rosin[START_REF] Christopher | Nested rollout policy adaptation for monte carlo tree search[END_REF] through a different solution.

Fig. 3 .

 3 Fig. 3. Experience on the problem rc203.1 with level 2. The lower the better. Average on 30 runs. Best results are found by the beam NRPA algorithm with N = 20. In this experiment, only the beam NRPA algorithm is able to find a valid path, without violated constraints. The best known score for this problem is 453.48. This score is reached for the Beam NRPA with N = 20.

Fig. 4 .

 4 Fig. 4. Experience on the problem rc202.3 with level 2. The lower the better. Average on 30 runs. Best results are found by the beam NRPA algorithm with N = 50 and N = 100. The best known score for this problem is 837.72

Fig. 5 .

 5 Fig. 5. Experience on the Morpion-Solitaire puzzle with level 2. The higher the better. Best results are found by the beam NRPA algorithm with N = 100. Each point is an average of 30 runs.

  Nested Rollout Policy Adaptation

	end while
	return (score (node), seq, pol)
	else
	beam ← {(∞,{},pol)}
	for N iterations do
	newBeam ← {}
	for (r,s,p) in beam do
	insert (r,s,p) in newBeam
	beam1 ← beamNRPA (level -1,p)
	for (r1, s1, p1) in beam1 do
	p1 ← Adapt(p,s1)
	insert (r1,s1,p1) in newBeam
	end for
	end for
	beam ← B best scores of newBeam
	end for
	return beam
	end if

beamNRPA (level,pol) if level = 0 then node ← root ply ← 0 seq ← {} while there are possible decisions do CHOOSE seq[ply] ← child i the with probability proportional to exp(pol[code(node,i)]) node ← child(node, seq [ply]) ply ← ply + 1