Sébastien Destercke
email: sebastien.destercke@hds.utc.fr

Sylvain Lagrue
email: sylvain.lagrue@hds.utc.fr

On cautiousness and expressiveness in interval-valued logic

Keywords: Logic, imprecise weights, skeptic inference, robust inferences, penalty logic

In this paper, we study how cautious conclusions should be taken when considering interval-valued propositional logic, that is logic where to each formula is associated a real-valued interval providing imprecise information about the penalty incurred for falsifying this formula. We work under the general assumption that the weights of falsified formulas are aggregated through a non-decreasing commutative function, and that an interpretation is all the more plausible as it is less penalized. We then formulate some dominance notions, as well as properties that such notions should follow if we want to draw conclusions that are at the same time informative and cautious. We then discuss the dominance notions in light of such properties.

Introduction

Logical frameworks have always played an important role in artificial intelligence, and adding weights to logical formulas allow one to deal with a variety of problems with which classical logic struggles [START_REF] Dubois | Weighted logics for artificial intelligence -an introductory discussion[END_REF].

Usually, such weights are assumed to be precisely given, and associated to an aggregation function, such as the maximum in possibilistic logic [START_REF] Dubois | Possibilistic logic: a retrospective and prospective view[END_REF] or the sum in penalty logic [START_REF] De Saint-Cyr | Penalty logic and its link with Dempster-Shafer theory[END_REF]. These approaches can typically find applications in non-monotonic reasoning [START_REF] Benferhat | Possibilistic and standard probabilistic semantics of conditional knowledge bases[END_REF] or preference handling [START_REF] Kaci | Reasoning with various kinds of preferences: logic, nonmonotonicity, and algorithms[END_REF].

However, as providing specific weights to each formula is likely to be a cognitively demanding tasks, many authors have considered extensions of these frameworks to interval-valued weights [START_REF] Gelain | Interval-valued soft constraint problems[END_REF][START_REF] Benferhat | Interval-based possibilistic logic[END_REF], where intervals are assumed to contain the true, ill-known weights. Such approaches can also be used, for instance, to check how robust conclusions obtained with precise weights are.

In this paper, we are interested in making cautious or robust inferences in such interval-valued frameworks. That is, we look for inference tools that will typically result in a partial order over the interpretations or world states, such that any preference statement made by this partial order is made in a skeptic way, i.e., it holds for any replacement of the weights by precise ones within the intervals, and should not be reversed when gaining more information. We simply assume that the weights are positive and aggregated by a quite generic function, meaning that we include for instance possibilistic and penalty logics as special cases.

We provide the necessary notations and basic material in Section 2. In Section 3, we introduce different ways to obtain partial orders over interpretations, and discuss different properties that corresponding cautious inference tools could or should satisfy. Namely, that reducing the intervals will provide more informative and non-contradictory inferences, and that if an interpretation falsify a subset of formulas falsified by another one, then it should be at least as good as this latter one. Section 4 shows which of the introduced inference tools satisfy which property.

Preliminaries

We consider a finite propositional language L. We denote by Ω the space of all interpretations of L, and by ω an element of Ω. Given a formula φ, ω is a model of φ if it satisfies it, denoted ω |= φ.

A weighted formula is a tuple φ, α where α represents the importance of the rule, and the penalty incurred if it is not satisfied. This weight may be understood in various ways: as a degree of certainty, as a degree of importance of an individual preference, . . . . We assume that α take their values on an interval of R + , possibly extended to include ∞ (e.g., to represent formulas that cannot be falsified). In this paper, a formula with α = 0 is understood as a totally unimportant formula that can be ignored, while a formula with maximal α is a formula that must be satisfied.

A (precisely) weighted knowledge base K = { φ i , α i : i = 1, . . . , n} is a set of distinct weighted formulas. Since these formulas are weighted, an interpretation can (and sometimes must, if K without weights is inconsistent) falsify some of them, and still be considered as valid. In order to determine an ordering between different interpretations, we introduce two new notations:

-F K (ω) = {φ i : ω |= φ i }, the set of formulas falsified by ω -F K (ω \ ω ) = {φ i : ω |= φ i ∧ ω |= φ i }
Let us furthermore consider an aggregation function ag : R n → R that we assume to be non-decreasing, commutative, continuous and well-defined 1 for any finite number n.

We consider that ag({α i : φ i ∈ F }) applied to a subset F of formulas of K measure the overall penalty corresponding to F , with ag(∅) = 0. Given this, we also assume that if ag receives two vectors a and b of dimensions n and n + m such that b has the same first n elements as a, i.e., b = (a, y 1 , . . . , y m ), then ag(a) ≤ ag(b). The idea here is that adding (falsified) formulas to a can only increase the global penalty. Classical options correspond to possibilistic logic (weights are in [0, 1] and ag = max) or penalty logic (weights are positive reals and ag = ). Based on this aggregation function, we define a given K the two following complete orderings between interpretations when weights are precise:

-ω K All ω iff ag({α i : φ i ∈ F K (ω)}) ≤ ag({α i : φ i ∈ F K (ω )}). -ω K Dif f ω iff ag({α i : φ i ∈ F K (ω \ ω )}) ≤ ag({α i : φ i ∈ F K (ω \ ω)}).
Both orderings can be read as ω ω meaning that "ω is more plausible, or preferred to ω , given K".

When the weights are precise, it may be desirable for All and Dif f to be consistent, that is not to have ω K All ω and ω ≺ K Dif f ω for a given K. It may be hard to characterize the exact family of functions ag that will satisfy this, but we can show that adding associativity and strict increasigness2 to the other mentioned properties ensure that results will be consistent.

Proposition 1. If ag is continuous, commutative, strictly increasing and associative, then given a knowledge base K, we have that

ω K All ω ⇔ ω K Dif f ω
Proof. Let us denote the sets {α i : Under these notations, we must show that ag(A, B)

φ i ∈ F K (ω)} and {α i : φ i ∈ F K (ω )}
≥ ag(A, C) ⇔ B ≥ C. That B ≥ C ⇒ ag(A, B) ≥ ag(A, C
) is immediate, as ag is non-decreasing. To show that B ≥ C ⇐ ag(A, B) ≥ ag(A, C), we can just see that if B < C, we have ag(A, B) < ag(A, C) due to the strict increasingness of ag.

Interval-valued logic, dominance notions and properties

In practice, it is a strong requirement to ask users to provide precise weights for each formula, and they may be more comfortable in providing imprecise ones. This is one of the reason why researchers proposed to extend weighted logics to interval-valued logics, where the knowledge base is assumed to have the form

K = { φ i , I i : i = 1, . . . , n} with I i = [a i , b i ] representing an interval of possible weights assigned to φ i .
In practice, this means that the result of applying ag to a set of formulas F is no longer a precise value, but an interval [ag, ag]. As ag is a non-decreasing continuous function, computing this interval is quite easy as

ag = ag({a i |φ i ∈ F }), ag = ag({b i |φ i ∈ F }),
which means that if the problem with precise weights is easy to solve, then solving it for interval-valued weights is equally easy, as it amounts to solve twice the problems for specific precise weights (i.e., the lower and upper bounds). A question is now to know how we should rank the various interpretations in a cautious way given these interval-valued formulas. In particular, this means that the resulting order between interpretations should be a partial order if we have no way to know whether one has a higher score than the other, given our imprecise information. But at the same time, we should try to not lose too much information by making things imprecise.

There are two classical ways to compare interval-valued scores that results in possible incomparabilities: Property 1 (Informational monotonicity) Assume that we have two knowledge bases K 1 = { φ 1 i , I i 1 : i = 1, . . . , n} and K 2 = { φ 2 i , I i 2 : i = 1, . . . , n} with φ 1 i = φ 2 i and I i 1 ⊆ I i 2 for all i. An aggregation method and the partial order it induces on interpretations is informational monotonic if

-Lattice ordering: [a, b] L [c, d] iff a ≤ c
ω K2 ω =⇒ ω K1 ω
That is, the more we gain information, the better we become at differentiating and ranking interpretations. If ω is strictly preferred to ω before getting more precise assessments, it should remain so after the assessments become more precise 3 . A direct consequence of Property 1 is that we cannot have ω K2 ω and ω

K1 ω, meaning that K1 will be a refinement of K2 . This makes sense if we aim for a cautious behaviour, as the conclusion we make in terms of preferred interpretations should be guaranteed, i.e., they should not be revised when we become more precise.

It should also be noted that violating this property means that the corresponding partial order is not skeptic in the sense advocated in the introduction, as a conclusion taken at an earlier step can be contradicted later on by gaining more information.

Property 2 (subset/implication monotonicity) Assume that we have a knowledge base K . An aggregation method and the partial order it induces on interpretations follows subset monotonicity if

F K (ω) ⊆ F K (ω ) =⇒ ω K ω for any pair ω, ω
This principle is quite intuitive: if we are sure that ω falsifies the same formulas than ω in addition to some others, then certainly ω should be less preferable/certain than ω.

Discussing dominance notions

Let us now discuss the different partial orders in light of these properties, starting with the lattice orderings and then proceeding to interval orderings.

Lattice orderings

Let us first show that All,L , Dif f,L do not satisfy Property 1 in general, by considering the following example:

Example 1. Consider the case where a i , b i ∈ R and ag = , with the following knowledge base on the propositional variables {p, q} φ 1 = p, φ 2 = p ∧ q, φ 3 = ¬q with the three following sets (respectively denoted K 1 , K 2 , K 3 ) of interval-valued scores

I K1 1 = [2.5, 2.5], I K1 2 = [0, 4], I K1 3 = [1, 5], I K2 1 = [2.5, 2.5], I K2 2 = [4, 4], I K2 3 = [1, 5], I K3 1 = [2.5, 2.5], I K3 2 = [4, 4], I K3 3 = [1, 1],
that are such that I K3 ⊆ I K2 ⊆ I K1 for all formulas. The resulting scores using the choice All following on the different interpretations are summarised in Table 1.

Figure 1 shows the different partial orders between the interpretations, according to All,L . We can see that ω 2 and ω 3 go from comparable to incomparable when going from K1 All,L to K2 All,L , and that the preference or ranking between them is even reversed when going from K1 All,L to K3 All,L . It should be noted that what happens to ω 2 , ω 3 for All,L is also true for

ω2 1 0 [0, 4] [4, 4] [4, 4] ω3 1 1 [1, 5] [1, 5] [1, 1] Table 1. Interval-valued scores from Example 1 ω1 ω0 ω3 ω2 K 1 All,L ω1 ω0 ω2 ω3 K 2 All,L ω1 ω0 ω2 ω3 K 3 All,L
Dif f,L . Indeed, F K (ω 2 ) = {p ∩ q} and F K (ω 3 ) = {¬q}, hence F K (ω 2 \ ω 3 ) = F K (ω 2 ) and F K (ω 3 \ ω 2 ) = ∅.
However, we can show that the two orderings based on lattice do satisfy subset monotonicity.

Proposition 2. Given a knowledge base K, the two orderings K All,L , K Dif f,L satisfy subset monotonicity.

Proof. For Dif f,L , it is sufficient to notice that if F K (ω) ⊆ F K (ω ), then F K (ω\ ω ) = F K (∅). This means that ag({α i : φ i ∈ F K (ω \ ω )}) = [0, 0], hence we necessarily have ω K Dif f,L ω . For All,L , the fact that F K (ω) ⊆ F K (ω ) means that the vectors a and a of lower values associated to {α i : φ i ∈ F K (ω)} and {α i : φ i ∈ F K (ω )} will be of the kind a = (a, a 1 , . . . , a m ), hence we will have ag(a) ≤ ag(a ). The same reasoning applied to upper bounds means that we will also have ag(a) ≤ ag(a ), meaning that ω K All,L ω .

From this, we deduce that lattice orderings will tend to be too informative for our purpose4 , i.e., they will induce preferences between interpretations that should be absent if we want to make only those inferences that are guaranteed (i.e., hold whatever the value chosen within the intervals I i ).

Strict orderings

In this section, we will study strict orderings, and will show in particular that while All,S provides orderings that are not informative enough for our purpose, Dif f,S does satisfy our two properties.

As we did for lattice orderings, let us first focus on the notion of informational monotonicity, and show that both orderings satisfy it. Proposition 3. Given knowledge bases K 1 , K 2 with φ 1 i = φ 2 i and I i 1 ⊆ I i 2 for all i ∈ {1, . . . , n}, the two orderings All,S , Dif f,S satisfy information monotonicity.

Proof. Assume that [a, b] and [c, d] are the intervals obtained from K 2 respectively for ω and ω after aggregation has been performed, with b ≤ c, hence ω K2 ,S ω with ∈ {All, Dif f }. Since ag is an increasing function, and as I i 1 ⊆ I i 2 , we will have that the intervals [a , b ] and [c , d ] obtained from K 1 for ω and ω after aggregation will be such that

[a , b ] ⊆ [a, b] and [c , d ] ⊆ [c, d], meaning that b ≤ b ≤ c ≤ c , hence ω K1
,S ω , and this finishes the proof.

Let us now look at the property of subset monotonicity. From the knowledge base K 1 in Example 1, one can immediately see that All,S is not subset monotonic, as

F K (ω 3 ) ⊆ F K (ω 1 ) and F K (ω 2 ) ⊆ F K (ω 0 ) ⊆ F K (ω 1
), yet all intervals in Table 1 overlap, meaning that all interpretations are incomparable. Hence All,S will usually not be as informative as we would like a cautious ranking procedure to be. This is mainly due to the presence of redundant variables, or common formulas, in the comparison of interpretations. In contrast, Dif f,S does not suffer from the same defect, as the next proposition shows. Proposition 4. Given a knowledge base K, the ordering Dif f,S satisfies subset monotonicity.

Proof. As for Proposition 2, it is sufficient to notice that if F K (ω) ⊆ F K (ω ), then F K (ω \ ω ) = F K (∅). This means that ag({α i : φ i ∈ F K (ω \ ω )}) = [0, 0], hence we necessarily have ω K Dif f,L ω .

Hence, the ordering Dif f,S satisfies all properties we have considered desirable in our framework. It does not add unwanted comparisons, while not losing information that could be deduced without knowing the weights.

Example 2. If we consider the knowledge base K 1 of Example 1, using Dif f,S we could only deduce the rankings induced by the facts that F K (ω 3 ) ⊆ F K (ω 1 ) and F K (ω 2 ) ⊆ F K (ω 0 ) ⊆ F K (ω 1 ), as ω 3 does not falsify any of the formulas that ω 2 and ω 0 falsify, hence we can directly compare their intervals. The resulting ordering is pictured in Figure 2.

Conclusions

In this paper, we have looked at the problem of making cautious inferences in weighted logics when weights are interval-valued, and have made first proposals to make such inferences. There is of course a lot that remains to be done, such as studying expressivity, representational or computational issues.

It should also be noted that our approach can easily be extended to cases where weights are given by other uncertainty models. If I i is an uncertain quantity (modelled by a fuzzy set, a belief function, a probability, . . . ), we would then need to specify how to propagate them to obtain ag(F ), and how to compare these uncertain quantities.

  as realvalued vectors a = (x 1 , . . . , x n , y n+1 , . . . , y na ) and b = (x 1 , . . . , x n , z n+1 , . . . , z n b ), where x 1 , . . . , x n are the weights associated to the formulas that both interpretations falsify. Showing the equivalence of Proposition 1 then comes down to show ag(a) ≥ ag(b) ⇔ ag((y n+1 , . . . , y na )) ≥ ag((z n+1 , . . . , z n b )). Let us first remark that, due to associativity, ag(a) = ag(ag((x 1 , . . . , x n )), ag((y n+1 , . . . , y na ))) := ag(A, B), ag(b) = ag(ag((x 1 , . . . , x n )), ag((z n+1 , . . . , z n b ))) := ag(A, C).

  and b ≤ d. We then have [a, b] ≺ L [c, d] if one of the two inequalities is strict, and [a, b] [c, d] iff [a, b] = [c, d]. Incomparability of [a, b] and [c, d] corresponds to one of the two set being strictly included in the other. -Strict ordering: [a, b] S [c, d] iff b ≤ c. We then have [a, b] ≺ S [c, d] if b < c, and indifference will only happen when a = b = c = d (hence never if intervals are non-degenerate). Incomparability of [a, b] and [c, d] corresponds to the two sets overlapping. These two orderings can then be applied either to All or Dif f , resulting in four different extensions: All,L , All,S , Dif f,L , Dif f,S . A first remark is that strict comparisons are stronger than lattice ones, as the former imply the latter, that is if [a, b] S [c, d], then [a, b] L [c, d]. In order to decide which of these orderings are the most adequate, let us first propose some properties they should follow when one wants to perform cautious inferences.

Fig. 1 .

 1 Fig. 1. Orderings All,L of Example 1 on interpretations.

Fig. 2 .

 2 Fig. 2. Orderings Dif f,S of Example 2

Which is also necessary, as ag = max will not always satisfy Property 1

Note that we consider the new assessments to be consistent with the previous ones, as Ii 1 ⊆ Ii 2 .

Which does not prevent them to be suitable for other purposes.


Tristan Braquelaire

Marie Gasparoux

Mathieu Raffinot

Raluca Uricaru

On improving the approximation ratio of the r-shortest common superstring problem

The Shortest Common Superstring problem (SCS) consists, for a set of strings S = {s1, • • • , sn}, in finding a minimum length string that contains all s i,1≤i≤n , as substrings. While a 2 11 30 approximation ratio algorithm has recently been published, the general objective is now to break the conceptual lower bound barrier of 2. This paper is a step ahead in this direction. Here we focus on a particular instance of the SCS problem, meaning the r-SCS problem, which requires all input strings to be of the same length, r. Golonev et al. proved an approximation ratio which is better than the general one for r ≤ 6. Here we extend their approach and improve their approximation ratio, which is now better than the general one for r ≤ 7, and less than or equal to 2 up to r = 6.

Introduction

The Shortest Common Superstring problem (SCS) consists, for a set of strings S = {s 1 , • • • , s n } over a finite alphabet Σ (with no s i substring of s j ), in constructing a string s such that any element of S is a substring of s and s is of minimal length. For an arbitrary number of strings n, the problem is known to be NP-Complete [START_REF] Gallant | On finding minimal length superstrings[END_REF][START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF] and APX-hard [START_REF] Blum | Linear approximation of shortest superstrings[END_REF]. Lower bounds for the achievable approximation ratios on a binary alphabet have been given [START_REF] Ott | Graph-Theoretic Concepts in Computer Science[END_REF][START_REF] Karpinski | Improved inapproximability results for the shortest superstring and related problems[END_REF], and the best approximation ratio so far for the general case is 2 11 30 ≈ 2.3667 [START_REF] Paluch | Better approximation algorithms for maximum asymmetric traveling salesman and shortest superstring[END_REF], reached after a long series of improvements [START_REF] Li | Towards a DNA sequencing theory (learning a string)[END_REF][START_REF] Blum | Linear approximation of shortest superstrings[END_REF][START_REF] Kosaraju | Long tours and short superstrings[END_REF][START_REF] Chris | Algorithms and Data Structures: 4th International Workshop[END_REF][START_REF] Armen | A 2 2 3 superstring approximation algorithm[END_REF][START_REF] Breslauer | Rotations of periodic strings and short superstrings[END_REF][START_REF] Czumaj | Sequential and parallel approximation of shortest superstrings[END_REF][START_REF] Sweedyk | a 2 1 2 -approximation algorithm for shortest superstring[END_REF][START_REF] Teng | Approximating shortest superstrings[END_REF][START_REF] Kaplan | The greedy algorithm for shortest superstrings[END_REF][START_REF] Paluch | Simpler approximation of the maximum asymmetric traveling salesman problem[END_REF][START_REF] Mucha | Lyndon words and short superstrings[END_REF] leading to increasingly complex algorithms.

An SCS greedy algorithm is known to reach good performances in practice but its guaranteed approximation ratio has only been proved to be 3.5 [START_REF] Kaplan | The greedy algorithm for shortest superstrings[END_REF], while conjectured 2.

The general objective in this algorithmic domain is now to break the conceptual lower bound barrier of 2. This paper is a step ahead in this direction. Here, we focus on a particular instance of the SCS problem, r-SCS, when all strings of the set of strings are of length r. Improving the SCS, and in particular the r-SCS approximation ratio is interesting from both theoretical and practical reasons, in view of their numerous applications, like in bioinformatics and more precisely in the reconstruction of DNA sequences from reads, which are usually short, fixed-length DNA strings. Gallant et al. [START_REF] Gallant | On finding minimal length superstrings[END_REF] showed that the r-SCS problem stays NP-hard, except for the 2-SCS case that can be solved in polynomial time [START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF]. Golovnev et al. [START_REF] Golovnev | Approximating shortest superstring problem using de bruijn graphs[END_REF] proposed an approximation ratio for the r-SCS problem, which was better than the best general approximation ratio (i.e., the one for the general SCS problem) at the time their article was published (2 11 23 [START_REF] Mucha | Lyndon words and short superstrings[END_REF]) for r < 8. However, in the meantime, the general approximation ratio has been improved from 2 11 23 to 2 11 30 , thus canceling their result for r = 7. In this new context, the approximation ratio proved by Golovnev et al. for the r-SCS problem remains better than the actual general one for r < 7. In this article, we extend the approach of [START_REF] Golovnev | Approximating shortest superstring problem using de bruijn graphs[END_REF] and exhibit a new approximation ratio for the r-SCS problem β(r),

β(r) = max 0≤x≤r-1 min 4 + (r -2)(r -x -1) 2(r -x) , (r 2 -2r + 2) -(r -1)x r -x , r -2 3 x r -x
that allows us to remain competitive for r ≤ 7 and less than or equal to 2 for r ≤ 6

Note that some theoretical variations of SCS have also been studied [START_REF] Yu | Approximation hardness of shortest common superstring variants[END_REF]. Here we neither dwell on these studies since their focus is far from ours, nor detail the greedy algorithm approximation conjecture, which is a subject in itself [START_REF] Tarhio | A greedy approximation algorithm for constructing shortest common superstrings[END_REF][START_REF] Kaplan | The greedy algorithm for shortest superstrings[END_REF][START_REF] Fici | On the greedy algorithm for the shortest common superstring problem with reversals[END_REF].

State of the art for the SCS and r-SCS problems

Given the immense number of results that have been published on the SCS problem, in this section we will only retrace those results that are relevant to this work.

Preliminary notations and definitions

Let Σ be a finite set of characters (or letters), ε the empty word, and w = w 1 . . . w p ∈ Σ * a string and ||w|| = p its length, with ||ε|| = 0. We denote pref(w, k), 1 ≤ k ≤ ||w|| (resp. suff(w, k)) the prefix (resp. suffix) of length k of w as the string w 1 . . . w k (resp. w ||w||-k+1 . . . w ||w|| ). We extend our notations with pref(w, 0) = suff(w, 0) = ε.

For two strings u, v we define the maximum overlap of u and v, denoted ov(u, v), as the longest suffix of u that is also a prefix of v.

The overlap graph built on a set of strings S is a complete directed graph with the vertex set V = S and the edges set E = {e i,j = (s i , s j )|∀s i , s j ∈ V }, with label l(e i,j ) = ov(s i , s j ) and weight w(e i,j ) = ||ov(s i , s j )||. Figure 1 shows the overlap graph built on SE, where SE = {ACGCA, CGCAT, GCATG, CGCAG, CAGTC, CAGCA, CATAA} is a set of strings that will be of use for illustrative purposes throughout this article. As in this work we focus on the r-SCS problem, note that, without loss in generality, we take SE as being a set of 5-length strings (r = 5).

Hamiltonian path approximation It is straightforward to see that finding a solution to the SCS problem comes to computing a Hamiltonian path of maximum weight (named H below) in the overlap graph (described above). Indeed, H would directly lead to a shortest superstring solution for the SCS problem, whose compression value (with respect to the naive superstring obtained by simply concatenating the n strings) would be equal to the weight of H, denoted by w(H).

The best existing approximation algorithm [START_REF] Kaplan | Approximation algorithms for asymmetric tsp by decomposing directed regular multigraphs[END_REF] for computing a weighted hamiltonian path (derived from the asymmetric maximum traveling salesman path, MAX ATSP), gives a hamiltonian path whose length is at least 2 3 of the weight of the longest path, i.e., 2 3 w(H). Therefore, this gives a superstring solution that is a 2.5-approximation for the SCS problem, which is far from the actual best known approximation ratio (2 11 30 ≈ 2.3667 [START_REF] Paluch | Better approximation algorithms for maximum asymmetric traveling salesman and shortest superstring[END_REF]) but it is important for the remaining of this paper.

2.1 r-SCS problem : the approach of Golovnev et al.

In this paper we extend the approach of Golovnev et al. [START_REF] Golovnev | Approximating shortest superstring problem using de bruijn graphs[END_REF] for the r-SCS problem, which we summarize in the remaining of this section. Golovnev et al. use a (r -1)-spectrum in order to translate the initial instance of the r-SCS problem in a 2-SCS instance, which they exactly solve with the approach described in [START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF]; this gives them a solution that, once translated back to the original problem, represents a good approximation of the optimal superstring for the original problem, given that the optimal is small.

In the remaining of this paper, we denote OPT(S) for S = {s 1 , • • • , s n } as the length of a shortest supertring of S. Clearly, when considering the r-SCS problem, OPT(S) = rn -w(H) (see the paragraph on the Hamiltonian path approximation).

k-spectrum and de Bruijn graphs

Given that a k-mer is a string of length k, in Golovnev et al. the notion of k-spectrum of the input set is defined as the set of k-mers issued from the sequences of the input set.

De Bruijn graphs are largely employed in next generation sequencing (NGS) data analysis, and specifically in genome assembly, as they display interesting properties like providing an intrinsic succinct representation of the data, and enabling the implementation of efficient methods for computing a superstring solution (which represents a reasonable approximation of the original genome sequence). A de Bruijn graph modeling a set of strings S is built on the k-spectrum of S as following: nodes are k-mers and oriented edges connect two k-mers if they overlap on exactly k -1 characters.

In this work, as in [START_REF] Golovnev | Approximating shortest superstring problem using de bruijn graphs[END_REF], the de Bruijn graph is used in a particular context : given an initial set of strings of length r, a de Bruijn graph is built on the (r -1)-spectrum corresponding to this set of strings. Figure 2 (left) shows this kind of de Bruijn graph built on the 4-spectrum of the set SE (containing strings of length 5).

2-SCS problem

The 2-SCS problem is a particular case of the r-SCS problem when r = 2, which deserves special attention since it has been shown in Crochemore et al. [START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF] that it is solvable in polynomial time, even when considering multiplicities (meaning that the strings must appear in the resulting superstring a given number of times). As our approach capitalizes on some technical parts from the method presented in [START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF], we give some insights on this method in the following of this section.

Let us consider the set of strings S 2 (composed of strings of length 2), where S 2 = {s 1 = α 1 β 1 , s 2 = α 2 β 2 , . . . , s n = α n β n }, with α i and β i two characters. Let us also take m i , positive integers indicating the multiplicity of the corresponding string s i .

In order to compute a superstring solution on this set, the approach of [START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF] is to build an oriented (possibly) multi-graph G from S 2 where nodes correspond to {α i |1 ≤ i ≤ n} ∪ {β i |1 ≤ i ≤ n} and each string s i = α i β i gives m i oriented edges from α i to β i . Then, the graph G is completed with a minimum number of oriented edges to form an eulerian path EP , that is a path passing through each and every edge exactly once. A superstring is then obtained by following the path EP and by concatenating the characters labeling each node the path goes through. Figure 3 illustrates the way this approach works on the set {AB, BC, BD, DE, FG, HI, JK}.

From r-SCS to 2-SCS and back

Golovnev et al. translate an r-SCS instance on a set S (composed of strings of length r) in a 2-SCS instance, by computing the (r -1)-spectrum of S and building a de Bruijn graph on this set of (r -1)-mers. By assigning a character to each (r -1)-mer, a string in S originally of length r, becomes a string of length 2 in the novel alphabet. Next, they exactly solve the 2-SCS problem with the method described in section 2.1.2, based on the graph illustrated in Figure 3, obtained from the de Bruijn graph on the (r -1)-spectrum of S. They eventually expand the resulting sequence (built on the new alphabet) by replacing each two letters (i.e., two original (r -1)-mers) connected by an edge in the graph with their corresponding r-mer. This leads to a superstring solution for the original r-SCS problem, not necessarily optimal, named τ ; see Figure 2 (right) for an illustration of the r-SCS solution computed with this procedure.

The length of τ can be compared to OP T (the length of the optimal superstring solution for the r-SCS problem), by observing that the number of (r -1)-overlap edges in an optimal weighted hamiltonian path (H) on the overlap graph, is necessarily less than or equal to the number of edges of the corresponding de Bruijn graph built on the (r -1)-spectrum.

Indeed, it is trivial to see that the number of edges in the de Bruijn graph is equal to the number of strings in S. See [START_REF] Golovnev | Approximating shortest superstring problem using de bruijn graphs[END_REF] for more details on this.

Two steps hierarchical SCS approximation

In this section we tackle the r-SCS problem for a set of strings S with a hierarchical 2-step procedure that generalizes the 2-SCS approach introduced by Golovnev et al.

Overview of our method

In the first step of our approach we apply the same translation as in [START_REF] Golovnev | Approximating shortest superstring problem using de bruijn graphs[END_REF], meaning that from the original r-SCS problem, by using the (r -1)-spectrum of S, we obtain a 2-SCS instance. After computing an optimal solution for the 2-SCS problem with the algorithm presented in [START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF], and then applying the reverse translation, we obtain a first, unsophisticated solution. This solution is the same as the one output by [START_REF] Golovnev | Approximating shortest superstring problem using de bruijn graphs[END_REF], but their method stops here. In our case, we continue the initiated process by subsequently generating a set of "contigs", i.e., substrings of the superstring solution obtained by embedding strings from S if overlapping on exactly r -1 characters. Note that contigs correspond to paths in the de Bruijn graph, and that the length of a contig is at least r. This set of contigs is computed from the initial superstring solution by cutting the superstring up in chunks, every time the connection is not due to an edge in the graph but rather to an edge added by the eulerian path resolution procedure from [START_REF] Crochemore | Algorithms for three versions of the shortest common superstring problem[END_REF] (represented by dashed lines in Figure 4 (left)). Figure 4 (left) illustrates this process on our example set SE = {ACGCA, CGCAT, GCATG, CGCAG, CAGTC, CAGCA, CATAA} resulting in the set of contigs SE = {ACGCATG, CGCAG, CAGTC, CAGCA, CATAA}.

Second step on the generalized spectrum of contigs For the next step we extend the notion of k-spectrum to take as input a set of contigs of possibly different lengths, but all greater than k + 1 : the k-mers composing this new type of k-spectrum are the prefixes and suffixes of size k of the input contig sequences. In our case, we compute a (r -2)-spectrum on the set of contigs issued from the first step of the method.

We then build a kind of de Bruijn graph for which the nodes come from the (r -2)-spectrum of the contigs and for each contig sequence w, we add an oriented edge from pref(w, (r -2)) to suff(w, (r -2)) labeled by w. Figure 4 (right) shows such a graph built on the (r -2)-spectrum of the set of contigs SE . Finally, as in the first step, an eulerian path with minimal additional edges is computed on this graph, which gives a novel superstring solution for the r-SCS problem, that we call γ.

Algorithm

The intuition behind our algorithm is to push further the approach of Golovnev et al. by additionally taking into account the (r -2)-overlap edges from the overlap graph built on S. However, this extension is not straightforward since (a) choices of (r -1)-edge paths are made in the first step of our algorithm, which cannot be reconsidered in the following steps; these (r -1)-edge paths selected in the first step prevent us from using some (r -2) edges from the overlap graph, typically those branching inside a contig, and (b) the contigs possibly have different lengths (thus the translation into à 2-SCS instance is not straightforward). The algorithm, which is described more formally below, is illustrated in Figure 4 on our example set SE. 1 Build the de Brujn graph dB(r -1) on S as following: nodes are (r -1)-mers of all s i , 1 ≤ i ≤ n; for each s i , 1 ≤ i ≤ n add an edge from the node pref(s i , (r -1)) to the node suff(s i , (r -1)). The graph built in this manner can easily be transposed into a 2-SCS instance.

2 Solve the 2-SCS instance with the algorithm from Crochemore et al., giving a minimum size eulerian path in dB(r -1). Build the corresponding contigs, c 1 . . . c k of varying sizes (at least r), by removing all edges added by the eulerian computation procedure on dB(r -1).

We denote by S = {c 1 , . . . , c k } this new set of strings.

3 Build the special type of de Bruijn graph (described above), dB (r -2), on the generalized (r -2)-spectrum of S : all the (r -2)-mers at the extremities of c i , 1 ≤ i ≤ k, as nodes in the graph, and edges (corresponding to the contigs c i ), connect a node pref(c i , (r -2)) to a node suff(c i , (r -2)).

Analysis

Golonev et al. based their analysis on the property that the eulerian path they build on the de Bruijn graph for producing their superstring solution τ (corresponding to items 1 and 2 in Algorithm 1) contains all (r -1)-overlap edges from the overlap graph, and thus at least as many as the (r -1) edges taken in the hamiltonian path H built on the overlap graph. Our 2 steps algorithm is more difficult to analyse given that our γ superstring solution mixes (r -1) and (r -2) overlaps, and, if it also contains at least as many (r -1) overlaps as H, the number of (r -2) overlaps can be less than that used in H, due to the fact that we do not consider all (r -2) overlaps when building our generalized (r -2)-spectrum (see Section 3). The following property allows us to compare the number of (r -1) and (r -2) edges in H and in the eulerian path producing γ.

We denote v the number of edges of weight at most (r -3) in H and v = n -1 -v the number of edges with weights (r -1) and (r -2) in H.

Property 1 Let t be the number of (r -1) and (r -2) edges contained in γ. Then t ≥ v.

Proof. Let t 1 (resp. t 2 ) the number of (r-1) (resp. (r-2)) edges contained in γ and symmetrically v 1 (resp. v 2 ) the number of (r -1) (resp. (r -2)) edges contained in H. We know that t 1 ≥ v 1 and let ∆ 1 = t 1 -v 1 ≥ 0. It is straightforward that in the case where t 2 > v 2 the property holds. Assume now that t 2 ≤ v 2 and let ∆ 2 = v 2 -t 2 ≤ 0. We prove that in this case ∆ 1 ≥ ∆ 2 .

Indeed, let us suppose that H in the overlap graph passes through an (r -2)-overlap edge l = (o, d) (where o and d are nodes in OG corresponding to strings from S) that does not appear in the de Bruijn graph on the generalized (r -2)-spectrum (built on the set of contigs derived from the (r -1)-spectrum). This means that the origin o of l lies inside a contig c = s u s u+1 . . . s v : there exists u < j < v such that o = s j (beginning and end of c non included); Figure 5 illustrates this case. Note that given the first step of our algorithm, if o = s j precedes s j+1 in a contig c, this corresponds to a (r -1) edge from o = s j to s j+1 in the OG. As H is hamiltonian, H only passes once through o and thus (a) cannot pass through the (r -1) edge (o, s j+1 ); and (b) cannot pass twice through a (r -2) edge from o. Thus, we can exactly map each (r -2) edge from H, not appearing in the generalized (r -2)-spectrum, to a (r -1) edge of γ, not belonging to H, which proves that ∆

1 ≥ ∆ 2 . Therefore t = t 1 + t 2 ≥ v = v 1 + v 2 .2
Based on Property 1 we are able to bound the length of γ relatively to w(H). Indeed, as we are not able to compare exactly the number of (r -1) and (r -2) edges between γ and H, we consider these edges as a whole, by counting an (r -1)-overlap as an (r -2) one. Thus, compared to Golonev at al., our approach further capitalizes on large overlap edges in OG but introduces a bounded approximation in the analysis. Approximation ratios for r [START_REF] Czumaj | Sequential and parallel approximation of shortest superstrings[END_REF][START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF] where x = w(H) n , 0 x r 1 MAX-ATSP r

Figure 1 :

 1 Figure 1: Example of an overlap graph on SE. Large arrows in red correspond to (r -1)-length overlaps, while middle width dashed green ones represent (r -2)-length overlaps. The graph is complete, but for the sake of clarity 0-weighted edges are not represented in the figure.

Figure 2 :Figure 3 :

 23 Figure 2: (left) A de Bruijn graph (edges correspond to strings in the initial set) built on the 4-spectrum of the set SE = {ACGCA, CGCAT, GCATG, CGCAG, CAGTC, CAGCA, CATAA}. (right) An example of an eulerian path (with minimal additional edges depicted by dashed lines) on this graph (right figure). The boxed node is the first node of the path and traversing the path leads to the following superstring: τ SE = CAGCACATAACAGTCACGCATGCGCAG.

Figure 4 :Algorithm 1 :

 41 Figure 4: (left) Example of an eulerian path (depicted by dashed lines) with minimal additional edges, built on the (r-1)-spectrum of SE. The boxed node is the start of the path. The expression of the path leads to the following set SE of contigs: CAGCA, CATAA, CAGTC, ACGCATG, CGCAG. (right) A minimal additional edges eulerian path built on the (r -2)-spectrum on the set of contigs SE . This second eulerian path starts with the boxed node ACG and ends with TAA, thus producing the following superstring solution on SE : ACGCATGCGCAGCACAGTCCATAA.

Figure 5 :

 5 Figure 5: Illustration of the proof of Property 1. The green dashed edges are (r -2)-overlap edges that are not considered in the generalized (r -2)-spectrum. In the case where H passes through such an edge (o, o ) (resp. (o , x)), we can uniquely associate to this edge the (r -1)-overlap edge (o, z) (resp. (o , z )) represented by thick black edges.

Figure 6 :

 6 Figure 6: Comparison of our bound (in red) to MAX-ATSP, to the best general bound of 2 11 30 , and to that of Golonev et al.

Figure 7 : 1 min (r 2 -

 712 Figure 7: Extension of our approach by considering two additional levels, i.e. (r -3) and (r -4) overlaps.

Solve the new 2-SCS instance on dB (r -2) with the algorithm by Crochemore et al. and output the corresponding superstring named γ.

Our ratio β(r) is of

In Figure 6 we compare the MAX-ATSP bound, the best general bound of 2 11 30 , Golonev et al. bound and ours, for 6 ≤ r ≤ 9 and 0 ≤ x ≤ r. The plots show that our approach gives better results than Golovnev et al. for 5 < r < 8. However, beyond this limit of r = 8, our bound is not better than the 2 11 30 general approximation ratio.

4 Generalization of the hierarchical approach on more than two steps

In order to push further our approach, we could consider three levels instead of two, by taking into account (r -3) edges in addition to (r -1) and (r -2) ones. Indeed, Property 1 can be directly extended to this case. However, our method requires to bound the weight of all edges in our superstring with the minimum overlap, (r -3) in this case. This can be pushed even further by considering four levels, and so on. However, in Figure 7 one can see that by extending the hierarchical approach, the approximation ratio becomes worse than that of the 2level approximation algorithm (presented in the previous section) for r = 7 and r = 8. Indeed, the approximation we introduced in the weight computation is too loose compared to the precision we gain by considering the additional levels.


Raphaël Cerf

Barbara Dembin

Vanishing of the anchored isoperimetric profile in bond percolation at p c

. We extend adequately the definition for p = pc, in finite boxes. We prove a partial result which implies that, if the limit defining the anchored isoperimetric profile at pc exists, it has to vanish.

Introduction

The most well-known open question in percolation theory is to prove that the percolation probability vanishes at p c in dimension three. In fact, the interesting quantities associated to the model are very difficult to study at the critical point or in its vicinity. We study here a very modest intermediate question. We consider the anchored isoperimetric profile of the infinite open cluster, defined for p > p c , whose existence has been recently proved in [START_REF] Dembin | Existence of the anchored isoperimetric profile in supercritical bond percolation in dimension two and higher[END_REF]. We extend adequately the definition for p = p c , in finite boxes. We prove a partial result which implies that, if the limit defining the anchored isoperimetric profile at p c exists, it has to vanish. The Cheeger constant. For a graph G with vertex set V and edge set E, we define the edge boundary ∂ G A of a subset A of V as

∂ G A = e = x, y ∈ E : x ∈ A, y / ∈ A .
We denote by |B| the cardinal of the finite set B. The Cheeger constant of the graph G is defined as

ϕ G = min |∂ G A| |A| : A ⊂ V, 0 < |A| ≤ |V | 2 .
This constant was introduced by Cheeger in his thesis [START_REF] Cheeger | A lower bound for the smallest eigenvalue of the laplacian[END_REF] in order to obtain a lower bound for the smallest eigenvalue of the Laplacian.

The anchored isoperimetric profile ϕ n (p). Let d ≥ 2. We consider an i.i.d. supercritical bond percolation on Z d , every edge is open with a probability p > p c (d), where p c (d) denotes the critical parameter for this percolation. We know that there exists almost surely a unique infinite open cluster C ∞ [START_REF] Grimmett | Percolation, volume 321 of Grundlehren der Mathematischen Wissenschaften[END_REF]. We say that H is a valid subgraph of C ∞ if H is connected and 0 ∈ H ⊂ C ∞ . We define the anchored isoperimetric profile ϕ n (p) of C ∞ as follows. We condition on the event {0 ∈ C ∞ } and we set

ϕ n (p) = min |∂ C∞ H| |H| : H valid subgraph of C ∞ , 0 < |H| ≤ n d .
The following theorem from [START_REF] Dembin | Existence of the anchored isoperimetric profile in supercritical bond percolation in dimension two and higher[END_REF] asserts the existence of the limit of nϕ n (p) when p > p c (d). We wish to study how this limit behaves when p is getting closer to p c . To do so, we need to extend the definition of the anchored isoperimetric profile so that it is well defined at p c (d). We say that H is a valid subgraph of C(0), the open cluster of 0, if H is connected and 0 ∈ H ⊂ C(0). We define ϕ n (p) for every p ∈ [0, 1] as

ϕ n (p) = min |∂ C(0) H| |H| : H valid subgraph of C(0), 0 < |H| ≤ n d .
In

(p) = θ(p)δ ϕ(p) + (1 -θ(p))δ 0 ,
where θ(p) is the probability that 0 belongs to an infinite open cluster. The techniques of [START_REF] Dembin | Existence of the anchored isoperimetric profile in supercritical bond percolation in dimension two and higher[END_REF] to prove the existence of this limit rely on coarse-graining estimates which can be employed only in the supercritical regime. Therefore we are not able so far to extend the above convergence at the critical point p c . Naturally, we expect that n ϕ n (p c ) converges towards 0 as n goes to infinity, unfortunately we are only able to prove a weaker statement.

Theorem 1.2. With probability one, we have

lim inf n→∞ n ϕ n (p c ) = 0 .
We shall prove this theorem by contradiction. We first define an exploration process of the cluster of 0 that remains inside the box [-n, n] d . If the statement of the theorem does not hold, then the cluster of 0 satisfies a d-dimensional anchored isoperimetric inequality. It follows that the number of sites that are revealed in the exploration of the cluster of 0 will grow fast enough of order n d-1 . Then, we can prove that the intersection of the cluster that we have explored with the boundary of the box [-n, n] d is of order n d-1 . Using the fact that there is no percolation in a half-space, we obtain a contradiction. Before starting the precise proof, we recall some results from [START_REF] Dembin | Existence of the anchored isoperimetric profile in supercritical bond percolation in dimension two and higher[END_REF] on the meaning of the limiting value ϕ(p).

The Wulff theorem. We denote by L d the d-dimensional Lebesgue measure and by H d-1 denotes the (d -1)-Hausdorff measure in dimension d. Given a norm τ on R d and a subset E of R d having a regular enough boundary, we define I τ (E), the surface tension of E for the norm τ , as

I τ (E) = ∂E τ (n E (x))H d-1 (dx) .
We consider the anisotropic isoperimetric problem associated with the norm τ :

minimize I τ (E) L d (E) subject to L d (E) ≤ 1 . (1)
The famous Wulff construction provides a minimizer for this anisotropic isoperimetric problem. We define the set W τ as

W τ = v∈S d-1 x ∈ R d : x • v ≤ τ (v) ,
where • denotes the standard scalar product and S d-1 is the unit sphere of R d . Up to translation and Lebesgue negligible sets, the set

1 L d ( W τ ) 1/d W τ
is the unique solution to the problem (1).

Representation of ϕ(p).

In [START_REF] Dembin | Existence of the anchored isoperimetric profile in supercritical bond percolation in dimension two and higher[END_REF], we build an appropriate norm β p for our problem that is directly related to the open edge boundary. We define the Wulff crystal W p as the dilate of W βp such that L d (W p ) = 1/θ(p), where θ(p) = P(0 ∈ C ∞ ). We denote by I p the surface tension associated with the norm β p . In [START_REF] Dembin | Existence of the anchored isoperimetric profile in supercritical bond percolation in dimension two and higher[END_REF], we prove that

∀p > p c (d) ϕ(p) = I p (W p ) .

Proofs

We prove next the following lemma, which is based on two important results due to Zhang [START_REF] Zhang | Critical behavior for maximal flows on the cubic lattice[END_REF] and Rossignol and Théret [START_REF] Rossignol | Existence and continuity of the flow constant in first passage percolation[END_REF]. To alleviate the notation, the critical point p c (d) is denoted simply by p c . Let B be a subset of R d having a regular boundary and such that L d (B) = 1/δ. As the map p → θ(p) is non-decreasing and L d (W p ) = 1/θ(p), we have

∀p > p c L d (W p ) ≤ L d (B) .
Moreover as W p is the dilate of the minimizer associated to the isoperimetric problem (1), we have

∀p > p c I p (W p ) ≤ I p (B) .
In [START_REF] Zhang | Critical behavior for maximal flows on the cubic lattice[END_REF], Zhang proved that β pc = 0. In [START_REF] Rossignol | Existence and continuity of the flow constant in first passage percolation[END_REF], Rossignol and Théret proved the continuity of the flow constant. Combining these two results, we get that lim p→pc p>pc β p = β pc = 0 and so lim p→pc p>pc

I p (B) = 0 .
Finally, we obtain lim p→pc p>pc

I p (W p ) = 0 .
This yields the result.

Proof of theorem 1.2. We assume by contradiction that

P lim inf n→∞ n ϕ n (p c ) = 0 < 1 .
Therefore there exist positive constants c and δ such that

P lim inf n→∞ n ϕ n (p c ) > c = lim n→∞ P inf k≥n k ϕ k (p c ) > c = δ . (2)
Therefore, there exists a positive integer n 0 such that

P inf k≥n0 k ϕ k (p c ) > c ≥ δ 2 . (3)
In what follows, we condition on the event

inf k≥n0 k ϕ k (p c ) > c .
Note that on this event, 0 is connected to infinity by a p c -open path. For H a subgraph of Z d , we define

∂ o H = e ∈ ∂H, e is open . Note that if H ⊂ C ∞ , then ∂ C∞ H = ∂ o H. Moreover, if H is equal to C(0), the open cluster of 0, then ∂ C(0) H = ∂ o H = ∅.
We define next an exploration process of the cluster of 0. We set C 0 = {0}, A 0 = ∅. Let us assume that C 0 , . . . , C l and A 0 , . . . , A l are already constructed. We define

A l+1 = x ∈ Z d : ∃y ∈ C l x, y ∈ ∂ o C l and C l+1 = C l ∪ A l+1 .
We have

∂ o C l ⊂ { x, y ∈ E d : x ∈ A l+1 } so that |∂ o C l | ≤ 2d|A l+1 |.
Since A l+1 and C l are disjoint, we have

|C l+1 | = |C l | + |A l+1 | ≥ |C l | + |∂ o C l | 2d . ( 4
)
Let us set α = 1/n d 0 so that |C 0 | = αn d 0 . Let k be the smallest integer greater than 2 d+1 d/c. We recall that c and n 0 were defined in ( 2) and ( 3). Let us prove by induction on n that

∀n ≥ n 0 |C (n-n0)k | ≥ αn d . (5)
This is true for n = n 0 . Let us assume that this inequality is true for some integer

n ≥ n 0 . If |C (n+1-n0)k | ≥ n d , then we are done. Suppose that |C (n+1-n0)k | < n d .
In this case, for any integer l ≤ k, we have also |C (n-n0)k+l | < n d , and since C (n-n0)k+l is a valid subgraph of C(0) and ϕ n (p c ) > c/n, we conclude that

|∂ o C (n-n0)k+l | |C (n-n0)k+l | ≥ c n and so |∂ o C (n-n0)k+l | ≥ αcn d-1
. Thanks to inequality (4) applied k times, we have

|C (n+1-n0)k | ≥ α n d + ck 2d n d-1 .
As k ≥ 2 d+1 d/c, we get

|C (n+1-n0)k | ≥ α(n d + 2 d n d-1 ) ≥ α(n + 1) d .
This concludes the induction. Let η > 0 be a constant that we will choose later. In [START_REF] Barsky | Percolation in half-spaces: equality of critical densities and continuity of the percolation probability[END_REF], Barsky, Grimmett and Newman proved that there is no percolation in a half-space at criticality. An important consequence of the result of Grimmett and Marstrand [START_REF] Grimmett | The supercritical phase of percolation is well behaved[END_REF] is that the critical value for bond percolation in a half-space equals to the critical parameter p c (d) of bond percolation in the whole space, i.e., we have P(0 is connected to infinity by a p c -open path in N × Z d-1 ) = 0 , so that for n large enough,

P(∃γ a p c -open path starting from 0 in N × Z d-1 such that |γ| ≥ n) ≤ η .
In what follows, we will consider an integer n such that the above inequality holds. By construction the set C n is inside the box [-n, n] d . Starting from this cluster, we are going to resume our exploration but with the constraint that we do not explore anything outside the box [-n, n] d . We set C 0 = C n and A 0 = ∅. Let us assume C 0 , . . . , C l and A 0 , . . . , A l are already constructed. We define

A l+1 = x ∈ [-n, n] d : ∃y ∈ C l x, y ∈ ∂ o C l and C l+1 = C l ∪ A l+1 .
We stop the process when A l+1 = ∅. As the number of vertices in the box [-n, n] d is finite, this process of exploration will eventually stop for some integer l. We have that |C l | ≤ n d and n φk (p c ) > c so that

|∂ o C l | ≥ c n |C l | ≥ c n |C n | .
Moreover, for n ≥ kn 0 , we have, thanks to inequality (5),

|C n | ≥ C n k k ≥ C ( n k -n0)k ≥ α n k d .
We suppose that n is large enough so that n ≥ kn 0 and n k ≥ n/2k. Combining the two previous display inequalities, we conclude that

|∂ o C l | ≥ cα 2 d k d n d-1 .
Therefore, for n large enough, there exists one face of [-n, n] d such that there are at least cαn

Moreover, we have

E(X n ) ≥ cα 2d2 d k d n d-1 P X n > cα 2d2 d k d n d-1 . (8)
Finally, combining inequalities ( 7) and (8), we get

P X n > cα 2d2 d k d n d-1 ≤ 2dη3 d-1 2 d k d cα .
Therefore, we can choose η small enough such that This contradicts inequality [START_REF] Rossignol | Existence and continuity of the flow constant in first passage percolation[END_REF] and yields the result.

P X n > cα 2d2 d k d n d-1 ≤ δ 10d

Lemma 2 . 1 .

 21 We have lim p→pc p>pc θ(p)δ Ip(Wp) + (1 -θ(p))δ 0 = δ 0 . Proof. If lim p→pc θ(p) = 0, then the result is clear. Otherwise, let us assume that lim p→pc p>pc θ(p) = δ > 0 .

≥ δ 2 . ( 6 )

 26 d-1 /(2 d k d 2d) vertices that are connected to 0 by a p c -open path that remains inside the box [-n, n] d and so P   there exists one face of [-n, n] d with at least cαn d-1 /(2 d k d 2d) vertices that are connected to 0 by a p c -open path that remains inside the box [-n, n] d   Let us denote by X n the number of vertices in the face {-n} × [-n, n] d-1 that are connected to 0 by a p c -open path inside the box [-n, n] d . We have E(X n ) ≤ ({-n} × [-n, n] d-1 ) ∩ Z d P   ∃γ a p c -open path starting from 0 in N × Z d-1 such that |γ| ≥ n   ≤ (2n + 1) d-1 η .

  and so using the symmetry of the lattice P   there exists one face of [-n, n] d such there are at least cαn d-1 /(2 d k d 2d) vertices that are connected to 0 by a p c -open path that remains inside the box [-n, n] d   ≤ 2d P X n > cα 2d2 d k d n d-1 ≤ δ 5.


L Kasprzak

S Legand

V Broudic

F Cochin

S Necib

 Acidification with H 3 PO 4 (25 %) of a small volume of the leachate solution,  N 2 gas bubbles in the solution to drag CO 2 ,  Collect of inorganic carbon in a NaOH solution,  Organic carbon is kept in the vessel. Analytical strategy for measurement of C-14 in leachate of irradiated zirconium alloy hulls

Extern sample transfer

-Hulls M5® and MOX D4 -NaOH 0.01 mol⋅L

PWR Dismantling

Hulls after reprocessing at AREVA -La Hague Repository (in project) With a half-life of 5,730 years, Carbon-14 ( 14 C) is a key radionuclide in safety assessments for geological disposal of long-lived waste. In zirconium alloy claddings, neutron activation of 14 N, impurity element of these alloys, is the main source of 14 C . 17 O coming from the UO 2 (or (U-Pu)O 2 ) oxide fuel and from water coolant is also a significant precursor of 14 C in the zirconia oxide layers formed in reactor on the internal and external sides of cladding respectively . => The method has been tested with a mixture of an inorganic molecule and an organic molecule labelled with 14 C: Na 2 CO 3 et C 6 H 12 O 6 .

Work

Step 3: Results for M5-type hull and D4-type hull leachates

Analysis of Carbon-14 LASE LRMO

Conclusions

Objectives and analytical process

Background

Step 1: Organic (TOC) and inorganic (TIC) carbon total concentrations

Step 2: Identification and quantification of carboxylic acids by ionic chromatography (IC)

Step

Organic anions :

-Acetate/formate in blank solutions ( contamination?) -Glycolate/oxalate come only from hull leaching solutions  14 C could be quantified in the leachate of M5-type and D4-type hulls; the partition of organic/inorganic 14 C has been measured :

Other organic/inorganic unidentified compounds

• Releases of total 14 C and organic 14 C by M5-type hull higher than by D4-type hull,

• Less than 20 % of organic 14 C released after 6 months for the D4-type hull against 50 % for M5-type hull,

• The organic 14 C represents less than 3.10 -4 % of TOC for M5-hull and 3.10 -5 % of TOC for D4-hull .  From theory calculations, diffusion coefficient of 14 C within Zr-metal and Zirconia is very low. However, measurements of 14 C in solution indicate its possible diffusion through Zr metal and/or Zr oxide layer by other mechanism such as diffusion through the grain boundaries.  For the organic carbon, only two carboxylic acids (glycolic and oxalic acids) have been detected and/or quantified in the leachate.

  The project has received funding from the European Union's Seventh Framework Programme for research, technological development and demonstration under grant agreement no. 604779, the CAST project The authors are grateful to F. Casanova, D. Lebeau, S. Guégan, M. Giuliani, S. Bourdjou, C. Moreau from CEA and B. Cvetkovic from PSI for their technical and scientific contributions.

  Package 3 (WP3) is related to Zircaloy in the CAST (Carbon-14 Source Term) project. It aims to obtain a better understanding 14 C behaviour in waste Zr fuel claddings under disposal conditions with regard to 14 C inventory (and origins), release from waste packages and speciation of released 14 C. Zircaloy-based alloy hulls, M5-type hull (UOX) and D4-type hull (MOX), supplied by AREVA-La-Hague, have been leached in a basic solution simulating the pH of cementitious water (NaOH solution, pH 12, anoxic conditions) in the hot cells of ATALANTE facility (CEA Marcoule). These samples come from the reprocessing of irradiated spent fuel in PWR reactors. Leachates have been analyzed to allow detection and quantification of organic and inorganic compounds in solution. Measurement of 14 C by Accelerator Mass Spectrometry (AMS) LASE  Measurement of total 14 C by pyrolysis followed by liquid scintillation counting  Development of an analytical method for organic/inorganic 14 C partition  Measurement of the organic/inorganic 14 C partition LRMO  Organic/inorganic partition of total carbon by Carbon Analyzer  Speciation of organic compounds by ionic chromatography  Carbon mass balance If 14 C activity < DL of Liquid Scintillation CountingStep 1: Total 14 C determinationStep 2: Method for organic and inorganic 14 C partition Pyrolysis of the sample on a tri-tube pyrolysis furnace followed by liquid scintillation counting DL = 0.5 Bq/mL (0.2 mL of sample) Organic 14 C: Pyrolysis followed by LSC or AMS measurement of a small volume of solution, which is kept in the vessel, Inorganic 14 C : Total 14 C * -organic 14 C * 14 C Total: Pyrolysis followed by LSC or AMS measurement of a small volume of the leachate solution.

No evolution between 14 days and 6 months for 14 C released in leachate.

					Partition
	Samples Blank (in hot cell) M5-type hull 14 Days M5-type hull 6 Months D4-type hull 14 Days D4-type hull 6 Months	Total 14 C Bq.g -1 of hull < 0.3 Bq.g -1 (DL LSC) 186 ± 12 192 ± 6 40 ± 6 48 ± 8	Organic 14 C Bq.g -1 of hull 0.75 ± 0.44 Bq.g -1 * 85 ± 12 83 ± 12 7 ± 1* 6 ± 2*	Inorganic 14 C Bq.g -1 of hull < 0.3 Bq.g -1 (DL LSC) 101 ± 12 110 ± 12 33 ± 1 42 ± 2	Organic / Inorganic % Not possible 46/54 43/57 17/83 13/87	 Total 14 C of leachate D4-type hull >> Total 14 C of leachate D4-type hull  Inorganic 14 C of leachate D4-type hull >> inorganic 14 C of leachate M5-type hull
					* AMS value

Example of IC chromatogram obtained on the D4 hull leaching solution M5-type hull leachate D4-type hull leachate