Eric Duchêne

Marc Heinrich

Richard Nowakowski

Partizan subtraction games are combinatorial games where two players, say Left and Right, alternately remove a number n of tokens from a heap of tokens, with n ∈ S L (resp. n ∈ S R ) when it is Left's (resp. Right's) turn. The first player unable to move loses. These games were introduced by Fraenkel and Kotzig in 1987, where they introduced the notion of dominance, i.e., an asymptotic behavior of the outcome sequence where Left always wins if the heap is sufficiently large. In the current paper, we investigate the other kinds of behaviors for the outcome sequence. In addition to dominance, three other disjoint behaviors are defined, namely weak dominance, fairness and ultimate impartiality. We consider the problem of computing this behavior with respect to S L and S R , which is connected to the well-known Frobenius coin problem. General results are given, together with arithmetic and geometric characterizations when the sets S L and S R have size at most 2.

Introduction

Partizan subtraction games were introduced by Fraenkel and Kotzig in 1987 [START_REF] Fraenkel | Partizan Octal Games: Partizan Subtraction Games[END_REF]. They are 2-player combinatorial games played on a heap of tokens. Each player is assigned a finite set of integers, respectively denoted S L (for the Left player), and S R (for the Right player). A move consists in removing a number m of tokens from the heap, provided m belongs to the set of the player. The first player unable to move loses. When S L = S R , the game is impartial and known as the standard subtraction game-see [START_REF] Berlekamp | Winning Ways for your Mathematical Plays[END_REF].

We now recall the useful notations and definitions coming from combinatorial game theory. More information can be found in the reference book [START_REF] Siegel | Combinatorial Game Theory[END_REF]. There are two basic outcome functions: for a position g, o L (g) = L, if Left moving first has a winning strategy; R, otherwise; and o R (g) = R, if Right moving first has a winning strategy; L, otherwise.

It is usual to talk of the outcome of a position g and the associated outcome function o(g),

• For o L (g) = o R (g) = L-Left wins regardless of who moves first, written o(g) = L;

• For o L (g) = o R (g) = R-Right wins regardless of who moves first, written o(g) = R;

• For o L (g) = L, o R (g) = R-the player who starts has a winning strategy, o(g) = N ;

• For o L (g) = R, o R (g) = L-the second player has a winning strategy, o(g) = P.

In outcome function, there should be a reference to the game/rules. In this paper, the position will be a number but the rules will be clear from the context so the rules will not be included in the function.

A partizan subtraction game G with rules (S L , S R ) will be denoted (S L , S R ) in the rest of the paper. A game position of G will be simply denoted by an integer n corresponding to the size of the heap. The outcome sequence of G is the sequence of the outcomes for n = 0, 1, 2, 3, . . ., i.e., o(0), o [START_REF] Berlekamp | Winning Ways for your Mathematical Plays[END_REF], o(2), . . .. A well-known result ensures that the outcome sequence of any impartial subtraction game is ultimately periodic [START_REF] Siegel | Combinatorial Game Theory[END_REF]. Note that in that case, the outcomes only have the values P and N since the game is impartial. In [START_REF] Fraenkel | Partizan Octal Games: Partizan Subtraction Games[END_REF], this result is extended to partizan subtraction games.

Theorem 1 (Fraenkel and Kotzig [START_REF] Fraenkel | Partizan Octal Games: Partizan Subtraction Games[END_REF]). The outcome sequence of any partizan subtraction game is ultimately periodic. In this particular case, the periodicity of the sequence can be easily proved by showing by induction that the outcome is L for n ≥ 4.

Such a behavior where the outcome sequence has period 1 is rather frequent for partizan subtraction games. In that case, the period is only L or R. In their paper, Fraenkel and Kotzig called this property dominance. More precisely, we say that S L ≻ S R -or that S L dominates S R -if there exists an integer n 0 such that the outcome of the game (S L , S R ) is always L for all n ≥ n 0 . By symmetry, a game satisfying S L ≺ S R is always R for all sufficiently large heap sizes. When a game neither satisfies S L ≻ S R nor S L ≺ S R , the sets S L and S R are said to be incomparable, denoted by S L ∥S R . In [START_REF] Fraenkel | Partizan Octal Games: Partizan Subtraction Games[END_REF], several instances have been proved to satisfy the dominance property (i.e., the games ({1, 2m}, {1, 2n + 1}) and ({1, 2m}, {1, 2n})), or to be incomparable like ({a}, {b}). It is also shown that the dominance relation is not transitive. Note that in [START_REF] Plambeck | Notes on Partizan Subtraction Games[END_REF], the game values (i.e., a refinement of the outcome notion) have been computed for the games ({1, 2}, {1, k}).

In the literature, partizan taking and breaking games have not been so much considered. A more general version, where it is also allowed to split the heap into two heaps, was introduced by Fraenkel and Kotzig in [START_REF] Fraenkel | Partizan Octal Games: Partizan Subtraction Games[END_REF], and is known as partizan octal games. A particular case of such games, called partizan splittles, was considered in [4], where, in addition, S L are S R are allowed to be infinite sets. Another variation with infinite sets is when S L and S R make a partition of N [START_REF] Larsson | Wythoff partizan subtraction[END_REF]. In such cases, the ultimate periodicity of the outcome sequence is not necessarily preserved.

In the current paper, we propose a refinement of the structure of the outcome sequence for partizan subtraction games. More precisely, when the sets S L and S R are incomparable, different kinds of periodicity can occur. The following definition presents a classification for them. Definition 3. The outcome sequence of G = Subtraction(S L , S R ) is:

• SD (Strongly Dominating) for Left (resp. Right ), and we write S L ≻ S R (resp. S L ≺ S R ) if any position n large enough has outcome L (resp. R). In other words, the period is reduced to L (resp. R);

• WD (Weakly Dominating) for Left (resp. Right ), and we write S L > w S R if the period contains at least one L and no R (or resp. one R and no L);

• F (Fair) if the period contains both L and R.

• UI (Ultimately Impartial) if the period contains no L and no R.

Remark 4. Note that inside a period, not all the combinations of P, N , L and R are possible. For example, in a game that is not UI, a period that includes P must include N . Indeed, assume on the contrary it is not the case and let n be a position of outcome P in the period, where the period has length p. The paper is organized as follows. In Section 2, we consider the two decision problems related to the computation of the outcome of a game position and of the behavior of the outcome sequence. Links with the Frobenius coin problem and the knapsack problem are given. Then, we try to characterize the behavior of the outcome sequence (SD, WD, F or UI) according to S L and S R . When S L is fixed, Section 3 gives general results about strong and weak dominance according to the size of S R . In Section 4 and 5, we characterize the behavior of the outcome sequence when

|S R | = 1 and |S L | ≤ 2. Section 6 is devoted to the case |S L | = |S R | = 2,
where it is proved that the sequence is mostly strongly dominating.

Complexity

Computing the outcome of a game position is a natural question when studying combinatorial games. For partizan subtraction games, we know that the outcome sequence is eventually periodic. This implies that, if S L and S R are fixed, computing the outcome of a given position n can be done in polynomial time. However, if the subtraction sets are part of the input, then the algorithmic complexity of the problem is not so clear. This problem can be expressed as follows: psg outcome Input: two sets of integers S L and S R , a game position n Output: the outcome of n for the game (S L , S R )

In the next result, we show that this problem is actually NP-hard. Theorem 6. psg outcome is NP-hard, even in the case where the set of one of the players is reduced to one element.

Proof. We use a reduction to Unbounded Knapsack Problem defined as follows.

Unbounded Knapsack Problem

Input: a set S and an integer n Output: can n be written as a sum of non-negative multiples of S?

Unbounded Knapsack Problem was shown to be NP-complete in [START_REF] Lueker | Two NP-Complete Problems in Nonnegative Integer Programming[END_REF]. Let (S, n) be an instance of unbounded knapsack problem, where S is a finite set of integers, and n is a positive integer. Without loss of generality, we can assume that 1 ̸ ∈ S since otherwise the problem is trivial. We consider the partizan subtraction game where Left can only play 1, and Right can play any number x such that x + 1 ∈ S. In other words, we have S L = {1} and S R = S -1. We claim that for this game, Right has a winning strategy playing second if and only if n can be written as a sum of non-negative multiples of elements of S.

Observe that during one round (i.e., one move of Left followed by one move of Right), if x is the number of tokens that were removed, then x ∈ S. Suppose that Right has a winning strategy, and consider any play where Right plays according to this strategy. Then Right makes the last move, and after this move no token remains. Indeed, if there was at least one token remaining, then Left could still remove this token and continue the game. At each round an element of S was removed, and at the end, no tokens remains. This implies that n is a sum of non-negative multiples of S.

In the other direction, if n is a sum of non-negative multiples of S, we can write n = x∈S n x x. A winning strategy for Right is simply to play n x times the move x -1 for each x ∈ S.

Remark 7. In the case of impartial subtraction games (i.e., S L = S R ), there is no known result about the complexity of this problem. This is surprising as these games have been thoroughly investigated in the literature.

The second question that emerged from partizan subtraction games is the behavior of the outcome sequence, according to Definition 3. It can also be formulated as a decision problem.

psg sequence

Input: two sets of integers S L and S R Output: is the game (S L , S R ) SD, WD (and not SD), F or UI ? Unlike psg outcome, the algorithmic complexity is open for psg sequence. The next sections will consider this problem for some particular cases. In addition, one can wonder whether the knowledge of the sequence could help to compute the outcome of a game position. The answer is no, even if the game is SD: Proposition 8. Let S L = {a 1 , . . . , a n } be such that gcd(a 1 + 1, . . . , a n + 1) = 1, and let S R = {1}. The game (S L , S R ) is SD for Left but computing the length of the preperiod is NP-hard.

The proof will be based on the well-known coin problem (also called Frobenius problem).

coin problem Input: a set of n positive integers a 1 , . . . , a n such that gcd(a 1 , . . . , a n ) = 1 Output: the largest integer that cannot be expressed as a linear combination of a 1 , . . . , a n . This value is called the Frobenius number. For n = 2, the Frobenius number equals a 1 a 2 -a 1 -a 2 [8]2 . No explicit formula is known for larger values of n. Moreover, the problem has been proved to be NP-hard in the general case [START_REF] Alfonsín | Complexity of the Frobenius problem[END_REF].

Proof of Proposition 8. Under the assumptions of the proposition, we will show that the length of the preperiod is exactly the Frobenius number of {a 1 + 1, . . . , a n + 1}. Indeed, let N be the Frobenius number of {a 1 +1, . . . , a n +1}. Then N +1, N +2 . . . can be written as a linear combinations of {a 1 +1, . . . , a n +1}. Note that in the game (S L , S R ), any round (sequence of two moves) can be seen as a linear combination of {a 1 + 1, . . . , a n + 1}, as Left plays an a i and Right plays 1. Hence if Right starts from N + 1, Left follows the linear combination for N + 1 to choose her moves, so as to play an even number of moves until the heap is empty. For the same reasons, if Right starts from N + 2, Left has a winning strategy as a second player. Since Right's first move is necessarily 1, it means that Left has a winning strategy as a first player from N + 1. Thus the position satisfies o(N + 1) = L. Using the same arguments, this remains true for all positions greater than N + 1. In other words, it proves that the game is SD for Left. Now, we consider the position N and show that o(N ) ̸ = L. Indeed, assume that Right starts and Left has a winning strategy. It means that an even number of moves will be played. According to the previous remark, the sequence of moves that is winning for Left is necessarily a linear combination of {a 1 + 1, . . . , a n + 1}. This contradicts the Frobenius property of N . This correlation between partizan subtraction games and the coin problem will be reused further in this paper.

When S L is fixed

In this section, we consider the case where S L is fixed and study the behaviour of the sequence when S R varies. In particular, we look for sets S R that make the game (S L , S R ) favorable for Right. This can be seen as a prelude to the game where players would choose their sets before playing: if Left has chosen her set S L , can Right force the game to be asymptotically more favorable for him?

3.1. The case |S R | > |S L |
If S R can be larger than S L , then it is always possible to obtain a game favorable for Right, as it is proved in the following theorem. Theorem 9. Let S L be any finite set of integers. Let p be the period of the impartial subtraction game played with S L and let S R = S L ∪ {p}. Then Right strongly dominates the game (S L , S R ), i.e., the game (S L , S R ) is ultimately R.

Proof. Let n 0 be the preperiod of the impartial subtraction game played on S L and m be the maximal value of S L . We prove that Right wins if he starts on any heap of size n > n 0 + p, which implies that the outcome on (S L , S R ) is R for any heap of size n > n 0 + p + m.

If n is an N -position for the impartial subtraction game on S L , then Right follows the strategy for the first player, never uses the value p, and wins.

If n is a P-position, Right takes p tokens, leaving Left with a heap of size n -p > n 0 which is, using periodicity, also a P-position in the impartial game. After Left's move, we are in the case of the previous paragraph and Right wins.

Note that in the previous theorem, S R contains the set S L , and thus has a large common intersection. We prove in the next theorem that if S R cannot contain any value in S L , then it is still possible to have a game that is at least fair for Right (i.e., it contains an infinite number of R-positions). Note that we do not know if for any set S L , there is always a set S R with |S R | = |S L | + 1 and S R ∩ S L = ∅ that is (weakly or strongly) dominating for Right. Consequently, if Right has a small advantage on the size of the set, he can ensure that the sequence of outcomes contains an infinite number of R-positions. So having a larger subtraction set seems to be an important advantage. However, having a larger set is not always enough to guarantee dominance. Indeed, we have the following result.

Theorem 11. Let G = (S L , S R ) be a partizan subtraction game. Assume that |S L | ≥ 2 and that G is eventually L, with preperiod at most p. Let x 1 , x 2 ∈ S L , with x 1 < x 2 , and let d be an integer with

d > p + max(S R ∪ {x 2 -x 1 }), then G d = (S L , S R ∪ {d}) is eventually L with preperiod at most (d + x 2 )⌈ d+x2 x2-x1 ⌉
Proof. Let G, d, x 1 and x 2 be as in the statement of the theorem. We first prove the following claim.

Claim 12. In the game Suppose now that Left wins playing first on n, and let y ∈ S L be a winning move for Left. Then Left wins playing second on n -y, and using the induction hypothesis, she wins playing second on n -y + d + x. Consequently, y is a winning move for Left on n + d + x.

G d , if o L (n) = L (resp. o R (n) = L)
For i ≥ 0, denote by X i the set of integers k < d + x 2 such that the position i(d + x 2 ) + k is L for G d . To prove the theorem, it is enough to show that if i is large enough, then X i = [0, x 2 + d[. From the claim above, we know that X i ⊆ X i+1 .

Additionally, using the hypothesis on d, we have that [p + 1, d -1] ⊆ X 0 . Finally, we have the following property. For any

x ≥ 0, if x ∈ X i , then x -(x 2 -x 1 ) mod (d + x 2 ) ∈ X i+1 . Indeed, if x ∈ X i , then i(d + x 2 ) +
x is an L-position, and using the claim above, so is i(d

+ x 2 ) + x + d + x 1 = (i + 1)(d + x 2 ) + x -(x 2 -x 1 ). Let 0 ≤ x < d + x 2 , and write (d -x) mod (d + x 2 ) = α(x 2 -x 1 ) + β the euclidian division of (d -x) mod (d + x 2 ) by (x 2 -x 1 ). We have 0 < β ≤ x 2 -x 1 , and α ≤ ⌈ d+x2 x2-x1 ⌉.
This can be rewritten as:

x = (d -β) -α(x 2 -x 1 ) mod (d + x 2 )
Since we know that d -β ≥ p by assumption on d, we have that (d -β) ∈ X 0 , and using the observation above, this implies that x ∈ X α ⊆ X ⌈ d+x 2

x 2 -x 1 ⌉ .
Consequently, G d is ultimately L, and the preperiod is at most

(d + x 2 )⌈ d+x2 x2-x1 ⌉.
By applying iteratively Theorem 11 with a game that is SD for Left (like the game of Example 2), we obtain the following corollary.

The case |S R | ≤ |S L |

We first consider the case S L = {1, . . , k} and prove that the game is always favorable to Left and that S L strongly dominates in all but a few cases. Proof.

1. In this case, the game is purely periodic, with period PL c N k . This can be proved by induction on the size of the heap n. If 0 < n ≤ c, only Left can play and the game is trivially L. Otherwise, let x = n mod c + k + 1. If x = 0, then if the first player removes i tokens, the second player answers by removing c + k + 1 -i tokens, leading to the position n -c -k -1 which is P by induction, and so is n. If 0 < x < c + 1, when Left starts she takes one token, leading to a L or a P-position, and wins. If she is second, she plays as before to n -c -k -1 which is a L-position. Finally, if x ≥ c + 1, both players win playing first by playing x -c for Left and x for Right.

2. We show that if n > 0 is such that Right wins playing second on n, this implies that S R contains k consecutive integers. Let n 0 be the smallest positive integer such that o L (n o ) = R. We know that n 0 > k since otherwise Left can win playing first by playing to zero. Since Right has a winning strategy playing second then Right has a winning first move on all the position n-i for 1 ≤ i ≤ k. This means that for each of these positions, Right has a winning move to some position m i where o L (m i ) = R. By minimality of n 0 , this implies that m i = 0, and consequently n -i ∈ S R for all 1 ≤ i ≤ k. Consequently, if S R does not contain k consecutive integers, there is no position n > 0 such that Right wins playing second. In particular, there is no R nor P-positions in the period. By Remark 4, this implies that the period only contains L-positions, meaning that the game is strongly dominating for Left.

The set S L = {1, . . . , k} is somehow optimal for Left, since the exceptions of strongly domination for Left in the previous lemma appear for any set of k elements: Lemma 16. For any set S L , there is a set S R with |S R | = |S L | and S R ∩ S L = ∅ such that Left does not strongly dominate.

Proof. Let S R = n 0 -S L for an integer n 0 larger than all the values of S L and such that S R S L = ∅. Then Right wins playing second in all the multiples of n 0 .

When one set has size 1

We now consider the case where one of the set, say S R has size 1. As seen in Section 2, the study of the game is closely related to Unbounded Knapsack Problem and to the coin problem. Indeed, Right does not have any choice and thus the result is only depending on the possibility or not for n to be decomposed as a combination of the values in S L + S R . Our aim in this section is to exhibit the precise periods.

Case |S

L | = |S R | = 1
In this really particular case, the game is always WD for the player that have the smallest integer.

Lemma 17. Let S L = {a} and S R = {b} with a < b. The outcome sequence of S = (S L , S R ) is purely periodic, the period length is a + b and the period is P a L b-a N a . In particular, the game is weakly dominating for Left.

Proof. We prove that for all n ≥ 0, if one of the player has a winning move playing first (resp. second) on n, then he also has one playing first (resp. second) on n+a+b. Indeed, suppose for example that Left has a winning move on position n playing first (the other cases are treated in the same way). If Left plays first on position n + a + b, then after two moves, it's again Left 's turn to play, and the position is now n, and Left wins the game.

The result then follows from computing the outcome of the positions n ≤ a + b. These outcomes are tabulated in Table 1.

Heap sizes

Left move range Right move range Outcome [0, a -1] no moves no moves In these cases, we are able to give the complete periods.

P [a, b -1] [0, b -a -1] no moves L [b, b + a -1] [b -a, b -1] [0, a -1] N [b + a, b + 2a -1] [b, b + a -1] [a, 2a -1] P [b + 2a, 2b + 2a -1] [b + a, 2b + a -1] [2a, b + 2a -1] L Table 1:
Theorem 18. Let a, b and c be three positive integers, and let g = gcd(a + c, b + c).

The game ({a, b}, {c}) is:

• strongly dominated by Left if g ≤ c,

• weakly dominated by Left with period

(P g-c L 2c-g N g-c ) if c < g < 2c,
• ultimately impartial with period

(P c N c ) if g = 2c ,
• weakly dominated by Right with period

(P c R g-2c N c ) if g > 2c .
Proof. Throughout this proof we write n = qg + r, with 0 ≤ r < c. We start by proving the following claim which holds in all four cases.

Claim 19. If (n mod g) < c then o R (n) = L for large enough n.

Proof. After both players play once, the number of tokens decreases by either a + c or b + c depending on which move Left played. By the results on the coin problem, we know that if q is large enough, then qg can be written as α(a + c) + β(b + c), with α and β two non-negative integers. If Left is playing second, a strategy can be to play a α times, and b β times. After these moves, it is Right's turn to play, and the position is r < c. Consequently Right now has no move and loses the game.

We will now use this claim to prove the result in the four different cases.

For the first case, we have g ≤ c. For any integer n, we have (n mod g) < g ≤ c. Consequently, by Claim 19, there is an integer n 0 such that for any n ≥ n 0 , o R (n) = L. This also implies that for any n ≥ n 0 + a, 0 L (n) = L since she plays to n -a > n 0 and, by the claim, o R (n -a) = L. Thus the outcome is L for any position n large enough.

For the three remaining cases, we will show that the following four properties holds when n is large enough. The result of the theorem immediately follows from these four properties. We now prove these four points.

1. This point is exactly the claim above.

2. If r ≥ g -c, and n is large enough, then Left can play a. The position after the move is such that n -a ≡ r -a ≡ r + c mod g. Moreover, since g -c ≤ r < g, we know that g ≤ r + c < g + c. From item 1, we know that o R (n) = L if n -a is large enough, so Left has a winning strategy as a first player if r ≥ g -c.

3. If r ≥ c, and Right plays first, then whatever Left plays, after an even number of moves, Right still has a move available. Indeed, let n ′ be the position reached after an even number of moves. The number of tokens removed, n-n ′ , is a multiple of g. Consequently, n ′ = (n mod g). Since (n mod g) ≥ c, this implies that n ′ ≥ c, and Right can play c. This proves that Right will never be blocked, and Left will eventually lose the game. When c > b and b ≥ 2a, which is included in the first case, we know the whole outcome sequence. This will be useful in next section.

Theorem 20. The outcome sequence of the game ({a, b}, {c}), with c > b and b ≥ 2a, is the following:

P a L c-a N a L ∞ .
Proof. We show the result by induction on n, the position of the game.

• If n < a, then neither player has a move and thus o(n) = P.

• If a ≤ n < c, then only Left has a valid move and thus o(n) = L.

• If c ≤ n < a + c, then Right has a winning move to a position n -c ≤ a which has outcome P, and Left has a winning move to a position with outcome either P or L, and thus o(n) = L.

• Finally, if n ≥ a + c, then Right has no winning move, and Left has at least one winning move. Indeed, since k ≥ a, we cannot have at the same time n -a and n -a -k in the interval [c, a + c[. So at least one of n -a and n -a -k is not in this interval, and is either a P-position or a L-position by induction.

When both sets have size 2

The goal of this section is to investigate the sequence of outcomes for the game G = (S L , S R ) with S L = {a, b} and S R = {c, d}. In particular, if we suppose that a and b are fixed, we would like to characterize for which positions the game G is eventually L. The picture on Figure 1 gives an insight of what is happening. On the figure on the left, we have an example with b ≥ 2a. In this case, the game G is almost always eventually L, except when the point (c, d) is close to the diagonal, i.e., when |d -c| is close to zero. When (c, d) is close to the diagonal, the behavior seems more complicated, and we will not give a characterization here. When b < 2a, the behavior is more complicated, but shares some similarities with the previous case. From the picture on the right in Figure 1 we can see that there are some lines such that if the point (c, d) is far enough from these lines, then the game is eventually L. Again, when the point is close to these lines, the behavior is more complex, and we will not try to characterize it here. In all cases, we can see that if a and b are fixed, for almost all of the choices of c and d, Left dominates.

In the rest of this section, we will assume that we have d > c > b. We start by the case b ≥ 2a which is easier to analyze.

Case b ≥ 2a

We start by the case where b ≥ a, and show that in this case G is ultimately L if (c, d) is far enough from the diagonal.

Theorem 21. If b ≥ 2a, and d > c+b, then S L ≻ S R . More precisely, the outcome sequence is:

P a L c-a N a L d-c-a N a L ∞ .
Proof. Again, we will show this result by induction on n, the starting position of the game. Let G ′ be the game ({a, a + k}, {c}). If n < d, then G played on n has the same outcome as G ′ , since playing d is not a valid move for Right in this case. Consequently we can just apply Theorem 20, and get the desired result. Otherwise, there are two possible cases:

General case

In the general case, we will again prove that if we fix a and b, for most choices of c and d the outcome is ultimately L. The exceptional cases are slightly more complicated to characterize. The characterization is related to the following definition.

Definition 22. Given an integer a, and a real number α ≥ 1, we denote by T a,α the set of points defined by:

• T 0,α = {(c, d) : gcd(c, d) ≥ max(c,d) α };
• for a ≥ 1, T a,α is obtained from T 0,α by a translation of vector (-a, -a).

We can remark that, for any α and β with β ≥ α, we have T 0,α ⊆ T 0,β . We now prove some properties of the sets T a,α which will be usefull for the proofs later on.

Lemma 23. Assume that there are some positive integers x, y, u and v such that xu -yv = 0 with (u, v) ̸ = (0, 0). Then (x, y) ∈ T 0,max(u,v) .

Proof. Up to dividing u and v by gcd(u, v), we can assume that u and v are coprime. Then, the equation is xu = yv. Consequently, u is a divisor of yv, and since u and v are coprimes, this means that u is a divisor of v. We can write y = gu, and consequently we have xu = yv = vgu. This means that x = vg, and g = gcd(x, y). Consequently, max(x,y) gcd(x,y) = max(u, v), and (x, y) ∈ T 0,max(u,v) .

Given two points p = (x, y) and p ′ = (x ′ , y ′ ), we denote by d(p, p ′ ) the distance between these two points according to the 1-norm: Lemma 24. Assume that there are some positive integers x, y, u, v and a such that |xu -yv| ≤ a, then d((x, y), T 0,max(u,v) ) ≤ a(u + v).

d(p, p ′ ) = |x -x ′ | + |y -y ′ |. If D is a subset of N
Proof. Let r = xu -yv, with |r| ≤ a, and g = gcd(u, v). By definition, r is a multiple of g, and we can write r = qg for some integer q. Additionally, by Bézout's identity, we know that there exists two integers u ′ and v ′ such that uu ′ + vv ′ = g, and |u ′ | ≤ u and |v ′ | ≤ v. Consider the point (x ′ , y ′ ), with x ′ = x -qu ′ , and y ′ = y + qv ′ . We have the following:

x ′ u -y ′ v = xu + yv -q(uu ′ + vv ′ ) = r -qg = 0.
By Lemma 23, we know that (x ′ , y ′ ) ∈ T 0,max(u,v) . Additionally, d((x, y),

(x ′ , y ′ )) = |qu ′ | + |qv ′ | ≤ |r|(u + v) ≤ a(u + v).
This proves the Lemma.

For any a and α, the set T a,α satisfies the following properties.

Lemma 25. For any a and α, the set T a,α is the union of a finite set of lines.

Proof. Since T a,α can be obtained from T 0,α by a translation, we only need to prove the result in the case a = 0. Let D be the union of the lines with equation xu -yv = 0, for all u, v ≤ α. The set D is the union of a finite number of lines. By Lemma 23, we know that D ⊆ T 0,α . Reciprocally, let (x, y) be a point in T 0,α , and let g = gcd(x, y). We can write x = x ′ g, and y = y ′ g for some integers x ′ and y ′ . We have the following:

xy ′ -yx ′ = x ′ y ′ g -y ′ gx = 0
Additionally, we have x ′ = x g ≤ x max(x,y) α ≤ α, and similarly for y ′ . Consequently, (x, y) ∈ D, and T 0,α = D.

The goal in the remaining of this section is to prove the following theorem. Given two integers i and j, we define the following intervals:

• I P i,j = [α i,j , α i,j + a -(i + j)(b -a)[ • I N i,j = [β i,j , β i,j + a -(i + j -1)(b -a)[
where

• α i,j = i(d + b) + j(c + b),
• and β i,j = α i,j -b.

Denote by I P the set ∪ i,j I P i,j , and similarly, I N = ∪ i,j I N i,j . Note that

I P i,j is empty if i + j ≥ ⌈ a k ⌉, and I N i,j is empty if i + j ≥ ⌈ a k ⌉ + 1.
Our goal is to show that, under the conditions in the statement of the theorem, the set I N is the set of Npositions, I P the set of P-positions, and all the other positions have outcome L. In particular, since both I P and I N are finite, this will imply that the outcome sequence is eventually L. Before showing this, we prove that under the conditions of the theorem the intervals I P i,j and I N i,j satisfy the following properties.

Lemma 27. Fix the parameters a and b, and let A = ⌈ a b-a ⌉+ 1. Assume that c and d are such that d((c, d), T b,A ) ≥ 2A(a + 2b), then the intervals I N i,j and I P i,j satisfy the following properties:

(i) they are pairwise disjoint, (ii) there is no interval I P i ′ ,j ′ or I N i ′ ,j ′ intersecting any of the b positions preceding

I N i,j , (iii)
I P i,j + c = I N i,j+1 , (iv)
I P i,j + d = I N i+1,j , (v) (I N i,j + a) ∩ (I N i,j + b) = I P i,j .
Proof. The points (iii), (iv) and (v) are just consequences of the definitions of I P i,j and I N i,j . Consequently, we only need to prove the two other points. We know that I N i,j and I P i,j are empty when i+j ≥ ⌈ a b-a ⌉+1 = A, consequently, we will assume in all the following that the indices i, j, i ′ and j ′ are all upper bounded by A. We first show the following claim. The rest of the proof will simply consists in applying this claim several times.

Claim 28. Assume that there is an integers B, and indices i, j, i ′ , j ′ ≤ A, such that one of the following holds:

• |α i,j -α i ′ ,j ′ | ≤ B • |β i,j -β i ′ ,j ′ | ≤ B • |α i,j -β i ′ ,j ′ | ≤ B
Then in all three cases we have d((c, d), T b,A ) ≤ 2A(B + b).

Proof. The first two cases are equivalent to the inequality |(i-i ′ )(d+b)+(j -j ′ )(c+ b)| ≤ B, and the result follows by applying Lemma 24. The third case is equivalent to

|(i -i ′ )(d + b) + (j -j ′ )(c + b) + b| ≤ B. Using the triangle inequality, this implies |(i -i ′ )(d + b) + (j -j ′ )(c + b)| ≤ B + b,
and the result follows from Lemma 24.

We will prove the points (i) and (ii) by proving their contrapositives. In other words, assuming that one of these two conditions does not hold, we want to show that d((c, d), T b,α ) ≤ 2α(a + b).

We first consider the point (i). First, assume that there are two intervals I P i,j and I P i ′ ,j ′ such that the two intervals intersect. Then, the Left endpoint of one of these two intervals is contained in the other interval. Without loss of generality, we can assume that α i,j ∈ I P i ′ ,j ′ . This implies:

α i ′ ,j ′ ≤ α i,j ≤ α i ′ ,j ′ + a -(b -a)(i ′ + j ′ ) 0 ≤ α i,j -α i ′ ,j ′ ≤ a -(b -a)(i ′ + j ′ ) ≤ a By claim 28, this implies d((c, d), T b,A ) ≤ 2A(a + b).
Similarly, if we assume that I N i,j and I N i ′ ,j ′ intersect, then this implies without loss of generality that β i,j ∈ I N i ′ ,j ′ , and consequently, 0 ≤ β i,j -β i ′ ,j ′ ≤ a-(i+j-1)k ≤ a. Again, using Claim 28, this implies d((c, d), T b,A ) ≤ 2(a + b)A.

Finally, if I N i ′ ,j ′ and I P i,j intersect, then either 0 ≤ α i,j -

β i ′ ,j ′ ≤ a if α i,j ∈ I N i ′ ,j ′ or 0 ≤ β i ′ ,j ′ -α i,j ≤ a if β i ′ ,j ′ ∈ I P i,j .
In both cases, the claim 28 gives the desired result.

The proof for the point (ii) is essentially the same as above. If I N i ′ ,j ′ intersects one of the b positions preceding I N i,j , then we have the two inequalities:

β i ′ ,j ′ + a -(i ′ + j ′ -1)k ≥ β i,j -b β i ′ ,j ′ ≤ β i,j
From these inequalities we can immediately deduce -a -b ≤ β i ′ ,j ′ -β i,j ≤ 0. The inequality d((c, d), T a+k,A ) ≤ 2A(3a + 2k) follows immediately from Claim 28. Similarly, if the interval I P i ′ ,j ′ intersects one of the b positions preceding I N i,j , then we have the two inequalities:

α i ′ ,j ′ + a -(i ′ + j ′ )(b -a) ≥ β i,j -b α i ′ ,j ′ ≤ β i,j
This implies -(a + b) ≤ α i ′ ,j ′ -β i,j ≤ 0, and again the result holds by claim 28.

We now have all the tools needed to prove the theorem.

Proof of Theorem 26. Let a, b, c, d be integers, and let A = ⌈ a b-a ⌉, and assume that d((c, d), T b,A ) ≥ 2A(a + 2b). We know that the four properties of Lemma 27 hold. We will show by induction on n that for any position n ≥ 0, if n ∈ I P , then n is a P-position, if n ∈ I N , then it is an N -position, and otherwise it is an L-position. The inductive case is treated in the same way as the base case.

First, assume that n ∈ I N i,j for some indices i and j such that i + j ≥ 1. Left has a winning move by playing a. Indeed, the interval I N i,j has length at most a, and using the condition (ii) from Lemma 27 and the induction hypothesis, n-a is a L-position. If i > 0, then Right playing c leads to the position n -c ∈ I P i-1,j by condition (iii). This position is a P-position using the induction hypothesis. If j > 0, then similarly, Right can play d, and put the game in the position n -d ∈ I P i,j-1 by condition (iv). This position is a P-position using the induction hypothesis.

Suppose now that n ∈ I P i,j . If i and j are both zero, then neither player has any move, and n is a P-position. Otherwise, if Left plays either a or b, this leads to a position n ′ ∈ I N i,j by condition (v). Using the induction hypothesis, n ′ is an N -position, and Left has no winning move. Right's only possible winning move would be to a P-position n ′ . Using the induction hypothesis this means n ′ ∈ I P . However, this would mean by conditions (iii) and (iv) that n ∈ I N , which is a contradiction of the property (i) that I N and I P are disjoint. Consequently, Right has no winning move.

Finally, suppose that n ̸ ∈ I P ∪I N . We will show that Left has a winning move on n, and Right does not. Since I P 0,0 = [0, a[, we can assume n ≥ a, and Left can play a. Suppose that Left's move to n -a is not a winning move, and let us show that Left has a winning move to n -a -k. Since Left's move to n -a is not a winning move, this means that n -a ∈ I N i,j for some integer i, j with i + j ≥ 1. Consequently we have n ≥ b, and playing b is a valid move for Left. By condition (v), we cannot have n -b ∈ I N i,j since otherwise we would have n ∈ I P i,j . Moreover, we cannot have either n -b ∈ I N i ′ ,j ′ for some (i ′ , j ′ ) ̸ = (i, j) since it would contradict condition (ii). Consequently, n -b ∈ I L , and using the induction hypothesis, this is a winning move for Left. The only possible winning move for Right would be to play to a position n ′ which is a P-position. Using the induction hypothesis, this means that n ′ ∈ I P . However using the conditions (iii) and (iv) this would also imply n ∈ I N , a contradiction.

Corollary 29. Under the conditions of the theorem, the game G is ultimately L.

Proof. Since I N i,j and I P i,j are both empty if i + j > a, the two sets I L and I N are finite, and the result follows from the theorem.

Example 2 .

 2 Consider the partizan subtraction game G = ({1, 2}, {1, 3}). The outcome sequence of G is P N L N L L L L • • •

  Let a ∈ S L . Now the position n + a is in the period, and o(n + a) = L since Left can win going first and, by assumption, o(n + a) ̸ = N . For the same reason, o(n + 2a) = L. By repeating this argument, o(n + ka) = L for all k. Since n is in the period, we now have P = o(n) = o(n + pa) = L, a contradiction. If the literature detailed above give examples of SD and UI games (as impartial subtraction games are UI), we will see later in this paper examples of WD games (e.g. Lemma 15). The example below shows an example of a fair game. Example 5. Let S L = {c, c + 1} and S R = {1, b} with b = c(c + 1) and c > 1. Then the game (S L , S R ) is F. Proof. We proceed by induction on the size of the heap, in order to show there are infinitely many L and R. Since c > 1, we have o(1) = R, and o(c + 1) = L. Now we assume that for some n, o(n) = L, and show that o(n + b + c) = L. In the position n + b + c, Left considers these as the two heaps n and b + c, and if Right removes 1, Left regards this as a move in the n component else it is a move in the second heap. Left moving first applies her winning strategy on n and then, regardless of whether Left moved first or second, responds in the remnants of n heap whenever Right removes 1 token. If at some point, Right chooses to remove b tokens, then Left answers immediately by removing c tokens, eliminating the second heap. In that case, Left wins at the end by applying her winning strategy on n. On the contrary, if Right never plays b, then Left empties the n component and it is Right's turn from the b + c position. Again, from b + c, playing b is a losing move for Right. If he plays 1, then Left plays c + 1, leading to the position b -2 = (c -1)(c + 2). All the next legal moves of Right are 1, and all the answers of Left are c + 1, which guarantees to empty the position and hence win the game. Assume now that o(n) = R and we show that o(n + b + c) = R. As previously, Right considers this position as the two heaps n and b + c. He applies his winning strategy on n and any move c of Left leads Right to answer by removing b tokens, leaving a winning position for Right. Hence assume that Left plays c + 1 until Right wins on n. At this point, Left has to play from a position k + b + c with k < c. If k = 0, then Left loses for the same reasons as in the above case (as the position b + c is P). Otherwise, any move c or c + 1 of Left is followed by a move b of Right, leading to a position with at most k tokens, from which Left cannot play and loses.

Theorem 10 .

 10 For any set S L , there exists a set S R with S L ∩ S R = ∅ and |S R | = |S L | + 1 such that the resulting game contains an infinite number of R-positions.Proof. Let n be any integer such that the set A = {n -m, m ∈ S L } is a set of positive integers that is disjoint from S L . Putting S R = A ∪ {n} gives a set that satisfies the condition of the theorem and the game (S L , S R ).We claim that o(kn) = R for k = 1, 2, . . .. If Left starts on a position kn by removing m tokens, then Right can answer by taking n -m tokens and leaves (k -1)n tokens, and by induction, Right wins. If Right starts, he takes n tokens and, again, Left has a multiple of n and loses.

•

  then Left has a winning strategy on n + (d + x) as first (resp. second player), with x ∈ S L .Proof of Claim 12. We will show the result by induction on n.First, assume o R (n) = L. We will show that there is a winning strategy for Left playing second on n + d + x. Starting from the position n + d + x, there are three possible cases:• Right plays y ∈ S R ,with y ≤ n. By the assumption on n, Left wins as first player on n-y, and using the induction hypothesis, he also wins as first player on n -y + d + x. Therefore, Left wins as second player on n + d + x. • Right plays y ∈ S R , with y > n. Now Left answers by playing x. This leads to the position (n -y) + d, with (n -y) + d > p by assumption on d, and n-y +d < d by assumption on y. Since n-y +d < d, Right can no longer play his move d, and the outcome of G d on n -y + d is the same as the outcome of G on this position. Since n -y + d > p Left wins playing second on this position. Right plays d, then Left answers by playing x, leading to the position n on which Left wins as second player by assumption.

Corollary 13 .

 13 There are sets S L and S R with |S L | = 2 and |S R | arbitrarily large such that (S L , S R ) is SD for Left .Remark 14. The condition on d ≥ p + max(S R ∪ {x 2 -x 1 }) in Theorem 11 is optimal. Indeed, take S L = {c, c + 1} and S R = {1}. As seen in the proof of Proposition 8, the game (S L , S R ) is SD for Left, with preperiod the Froebenius number of {c + 1, c + 2}, which is p = c 2 + 2c -1 = c(c + 1) -1. Thus, by Theorem 11, the game ({c, c + 1}, {1, d}) with d > c(c + 1) is also SD for Left. But, as proved in Example 5, this is not true for d = c(c + 1) since the game is then F.

Lemma 15 .

 15 Let S L = {1, . . . , k}, and |S R | = k. Then: 1. If S R = {c + 1, c + 2, . . . c + k} for some integer c, then Left weakly dominates if c > 0 and the game is impartial if c = 0, 2. otherwise, Left strongly dominates.

  Outcomes with S L = {a} and S R = {b} for first values 4.2. Case |S L | = 2 and |S R | = 1

1 .

 1 if r < c, then Left wins playing second, 2. if r ≥ g -c, then Left wins playing first, 3. if r ≥ c, then Right wins playing first, 4. if r < g -c, then Right wins playing second.

4 .

 4 Finally, if r < g -c, then Left playing first can move to a position n ′ equal to either n -a or n -b. Since a ≡ b ≡ -c mod g, in both cases, we have n ′ ≡ r + c mod g. Since c ≤ r + c < g, by the argument above, we know that Right playing first on n ′ wins. Consequently, Left playing first on n loses.

a = 4

 4 and k = 7 a = 7 and k = 2

Figure 1 :

 1 Figure 1: Properties of the outcome sequences for G = ({a, a + k}, {c, d}). The parameters a and k are fixed, and the pictures are obtained by varying the parameters c and d. The point at coordinate (c, d) is blue if the corresponding game is eventually L, red if it is eventually R, and green if there is a mixed period.

  2 , we denote by d(p, D) = min{d(p, p ′′ ), p ′′ ∈ D} the distance of the point p to the set D.

Theorem 26 .

 26 Let a, b, c and d be positive integers, let A = ⌈ a b-a ⌉ + 1. Assume that d((c, d), T a,A ) ≥ 2A(a + 2b), then the partizan subtraction game with S L = {a, b}, and S R = {c, d} is ultimately L.

SUPPORTED BY THE ANR-14-CE25-0006 PROJECT OF THE FRENCH NATIONAL RE-SEARCH AGENCY

Although not germane to this paper, Sylvester's solution is central to the strategy stealing argument that proves that naming a prime 5 or greater is a winning move in sylver coinage[START_REF] Berlekamp | Winning Ways for your Mathematical Plays[END_REF], chapter 18.


Da Chen
email: chenda@ceremade.dauphine.fr

Laurent D Cohen
email: cohen@ceremade.dauphine.fr

A New Dynamic Minimal Path Model for Tubular Structure Centerline Delineation

We propose a new dynamic Riemannian metric with adaptive anisotropy enhancement and with appearance feature coherence penalization. The appearance features are characterized by the orientation score maps. Unlike the static geodesic metrics which depend on local pointwise information, the dynamic metric can take into account the nonlocal feature coherence penalty in order to extract a desired structure from complicated background or from a vessel tree. We construct the metric using the information from two external reference points which are identified during the geodesic distance computation. Numerical experiments are performed in retinal vessels, including the independent results from the proposed dynamic metric itself and the comparison against existing minimal path models. The results show that the proposed metric indeed gets better performance than state-of-the-art geodesic metrics.

I. INTRODUCTION

The minimal path model [START_REF] Cohen | Global minimum for active contour models: A minimal path approach[END_REF] is a robust and efficient method for vessel extraction. In its basic formulation, a tubular structure can be naturally modelled as a minimal path. It seeks a globally optimal curve that minimizes the path length L(γ) = 1 0 P (γ(t)) γ (t) dt along a path γ with Lipschitz continuity, where s is the arc-length parameter of γ such that γ (s) ≡ 1 and P is a potential function with small values inside the tubular structure. The minimal path model is able to efficiently find the global optimality of the path length L through the solution to the Eikonal partial differential equation (PDE) thanks to the well-established numerical solvers like the fast marching methods [START_REF] Sethian | Fast marching methods[END_REF], [START_REF] Mirebeau | Anisotropic fast-marching on cartesian grids using lattice basis reduction[END_REF]. By designing suitable potentials P , the minimal path model can be applied to solve various vessel segmentation problems [START_REF] Peyré | Geodesic methods in computer vision and graphics[END_REF].

One of the key ingredients for the minimal path computation is the used geodesic metrics. In order to address various tubular structure segmentation problems, a series of geodesic metrics have been designed. The Li-Yezzi minimal path model [START_REF] Li | Vessels as 4-D curves: Global minimal 4-D paths to extract 3-D tubular surfaces and centerlines[END_REF] defined an isotropic Riemannian metric in a multi-scale space to solve the problem of simultaneously finding the vessel centerlines and boundaries. Benmansour and Cohen [START_REF] Benmansour | Tubular structure segmentation based on minimal path method and anisotropic enhancement[END_REF] generalized the Li-Yezzi model to the anisotropic Riemannian case, where the vessel orientations were also used to mitigate the shortcuts problem. Péchaud et al. [START_REF] Péchaud | Extraction of tubular structures over an orientation domain[END_REF] added an abstract orientation dimension to the multi-scale space, which provides an orientation-lifted way to use the tubular orientation information. The elastica geodesic metrics [START_REF] Chen | Global minimum for a Finsler elastica minimal path approach[END_REF] and the Reeds-Sheep metrics [START_REF] Bekkers | A PDE approach to data-driven sub-Riemannian geodesics in SE (2)[END_REF], [START_REF] Duits | Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis[END_REF] can be used to minimize the path length with second-order regularization term such as the curvatures. These metrics have beed successfully applied to retinal imaging. In [START_REF] Liao | Progressive minimal path method for segmentation of 2D and 3D line structures[END_REF], a new minimal path extraction method in conjunction with a fast marching front frozen scheme was proposed. The path features like curvatures are estimated through the truncated geodesics from the front points, which will be frozen if their path features do not satisfy the prescribed criteria. The idea of using truncated geodesics to estimate the features are also used in this paper. In order to reduce the user intervention, the keypoints methods [START_REF] Benmansour | Fast object segmentation by growing minimal paths from a single point on 2D or 3D images[END_REF]- [START_REF] Chen | Vessel tree extraction using radius-lifted keypoints searching scheme and anisotropic fast marching method[END_REF] iteratively add new source points in the course of geodesic distance computation. The approaches listed above are not exhaustive and other interesting methods relevant to minimal path-based tubularity segmentation include [START_REF] Ulen | Shortest paths with higher-order regularization[END_REF], [START_REF] Chen | Curve-like structure extraction using minimal path propagation with backtracking[END_REF].

In this paper, we propose a new dynamic geodesic metric for tubular centerline delineation. The main contribution lies at the construction of a metric with adaptive anisotropy enhancement and feature coherence penalty in a dynamic manner. The computation of the dynamic metric is carried out during the fast marching fronts propagation in conjunction with a truncated geodesics tracking scheme. The new dynamic metric is able to reduce the risk of tracking incorrect tubular structures. In Fig. 1b, we show a typical short combination problem suffered by the anisotropic Riemannian metric [START_REF] Benmansour | Tubular structure segmentation based on minimal path method and anisotropic enhancement[END_REF]. In Fig. 1c, we illustrate the result from the proposed metric which avoids this problem.

The paper is organized as follows. In Section II, we briefly introduce the computation of the tubular features. In Sec-tion III, we introduce the construction method for the dynamic metric. The experimental results are presented in Section V.

II. LOCAL TUBULARITY DESCRIPTOR

We suppose that the gray levels inside the tubular structures are locally darker than the background. A tubular structure or a vessel can be described by a feature vector field and by a vesselness map. The feature vector field indicates the vessel orientation at each point and the vesselness map indicates the probability of a point belonging to a vessel. Both maps can be detected through any multi-scale steerable filters such as [START_REF] Law | Three dimensional curvilinear structure detection using optimally oriented flux[END_REF], [START_REF] Frangi | Multiscale vessel enhancement filtering[END_REF]. In this paper, we choose the optimally oriented flux (OOF) filter, as our vessel detector. It invokes a Gaussian filter G σ with variance σ and a characteristic function χ r of a disk with radius r

OF(x, r) := 1 r ∂ xx G σ ∂ xy G σ ∂ yx G σ ∂ y G σ * χ r (x) * I(x), (1)
where ∂ xy G σ is the second-order derivative of G σ and I : Ω → R is a gray level image. For each point x and scale r, the OOF response OF(x, r) is a 2 × 2 symmetric matrix with eigenvalues ˆ 1 (x, r) and ˆ 2 (x, r). Let qof (x, r) be the eigenvector corresponding to the eigenvalue ˆ 2 (x, r). Without loss of generality, we assume that ˆ 1 (x, r) ≤ ˆ 2 (x, r) and if x is inside a vessel one further has ˆ 1 (x, r) ≈ 0. At each point x, one can define an optimal scale

ζ(x) = arg max r ˆ 2 (x, r).
Let S 1 = [0, 2π) be an orientation space with periodic boundary condition and let g(θ) = (cos θ, sin θ) T be an unit vector associated to an angle θ ∈ S 1 . An orientation score (OS) map ψ os : Ω × S 1 → R can be computed by

ψ os (x, θ) = max{ g ⊥ (θ), OF(x, ζ(x))g ⊥ (θ) , 0}, (2)
with g ⊥ (θ) = (-sin θ, cos θ) T a vector orthogonal to g(θ).

A feature map q of is defined by

q of (x) = qof (x, ζ(x)). (3)

III. DYNAMIC METRIC WITH COHERENCE PENALIZATION AND ADAPTIVE ANISOTROPY ENHANCEMENT A. Potentially Asymmetric Orientation Score

We consider an oriented Gaussian kernel Q θ σ associated to θ ∈ S 1 which can be expressed for any x ∈ Ω by

Q θ σ (x) = exp - | g(θ), x | 2 2σ 2 1 - | g ⊥ (θ), x | 2 2σ 2 2
, where σ = (σ 1 , σ 2 ) with σ 1 and σ 2 (σ 1 σ 2 ) being the Gaussian variances along the directions g θ and g ⊥ θ , respectively. Here we further consider an asymmetric Gaussian kernel through a cutoff function δ θ : Ω → {0, 1}

δ θ (x) = 1, if ∇G σ1 (x), g(θ) ≥ 0 , 0, otherwise,
where

∇G σ1 = (∂ x G σ1 , ∂ y G σ1 )
T is the standard Euclidean gradient of the isotropic Gaussian kernel G σ1 with variance σ and 0 ∈ R + 0 is a sufficiently small constant. An asymmetric Gaussian kernel H θ σ over the domain Ω can be expressed by

H θ σ (x) = δ θ (x) Q θ σ (x).
A new potentially asymmetric OS map Ψ os for each fixed orientation θ ∈ S 1 is defined by

Ψ os (x, θ) = (H π+θ σ * ψ θ os )(x) Ω H π+θ σ (x) dx , ψ θ os (•) := ψ os (•, θ) ψ os ∞ , (4)
where * is a convolution operator.

B. Crossing-adaptive Tensor Field

In an image which involves tubular tree structures, there may exist a set of points belonging to different vessels. These points are crossing points, for which one needs more than one orientation vectors to describe the tubular anisotropic property.

In this case, it may increase the risk of obtaining incorrect geodesic tangents at these crossing points. A possible solution is to design a crossing-adaptive Riemannian metric, which should be weakly anisotropic (or approximately isotropic) at these crossing points but be strongly anisotropic at the other points inside the tubular tree. This can be done by taking into account the orientation score values at the crossing points to establish the relevant tensor field [START_REF] Franceschiello | A Neuromathematical model for geometrical optical illusions[END_REF]. In contrast to [START_REF] Franceschiello | A Neuromathematical model for geometrical optical illusions[END_REF] which uses the score values corresponding to all the orientations, in this section we only consider the score values with respect to locally optimal orientations. For this purpose, we first define a set M x involving locally optimal feature vectors in the sense of orientation score map. For each point x, the set M x of locally optimal feature vectors associated to Ψ os (x, •) can be defined by

M x = g(θ * ); Ψ os (x, θ * ) > Ψ os (x, θ), ∀θ ∈ N (θ * , ξ),
and

Ψ os (x, θ * ) > 1 2π 2π 0 Ψ os (x, θ) dθ ,
where N (θ * , ξ) is a neighbourhood of θ * ∈ S 1 with length of ξ. The characteristic function of the set M x is expressed as

C(x, θ) = 1, if g(θ) ∈ M x , 0,
otherwise.

Similar to M x , the set of locally optimal directions associated to ψ os (x, θ) is denoted by M x , ∀x ∈ Ω. Let I d be the 2 × 2 identity matrix. A tensor field T base can be constructed by

T base (x) = 2π 0 C(x, θ)Ψ os (x, θ)g(θ)g(θ) T dθ max 2π 0 C(x, θ)dθ, 1 + µ 0 I d , (5)
where µ 0 and 1 are sufficiently small positive constants. The matrix µ 0 I d ensures the non-singularity of the matrix T base (x), ∀x ∈ Ω.

The desired tensor field T os : Ω → S + 2 for the anisotropyadaptive Riemannian metric can be computed in terms of T base where α ∈ R + is a positive constant that controls the contrast ratio and T -1 base (x) is the inverse matrix of T base (x).

T os (x) = exp -α max θ∈S 1 ψ os (x, θ) T -1 base (x). (6)

C. Coherence-Penalized Dynamic Riemannian Metric

Let p : Ω → M x be a new tubular anisotropy feature map, which corresponds to an orientation map a : Ω → S 1 , where a(x) is defined being such that (cos(a(x)), sin(a(x))) T = p(x). At a crossing point x, the feature vector p(x) should be proportional to the centerline tangent of the target vessel at x. Let x, a x , b x ∈ Ω be three points belonging to the same tubular structure. The points a x and b x , which are named reference points, are supposed to be approximately located at the tubular centerline. In addition, we also suppose the point x is close to the reference point a x . In the following, we solve the problem for the computation of the coherence penalty at a point x providing its reference points a x and b x are known.

The computation criterion for the feature vector p(x) is based on the prior that p(a x ) and p(b x ) have been known. Since x and a x is close to each other, the measurement | p(x), p(a x ) | ≈ 1 should be held. We define a set M *

x ⊆ M x of the selected feature vectors by

M * x = {w * ; w * = arg max w∈Mx | w, p(a x ) |}.
Thus the feature vector p(x) can be identified by

p(x) := (cos θ * x , sin θ * x ) T , (7)
where the orientation θ x is computed by

θ * x := arg min θ:g(θ)∈M * x |Ψ os (x, θ) -Ψ os (a x , a(a x ))|.
For a crossing point x, each feature vector in M x characterizes the orientation that the tubular structure should have at x through the map a. The map p is constructed in a progressive way. For the source point s, the feature vector p(s) = (cos(a(s)), sin(a(s))) T is chosen being such that

a(s) = arg max θ Ψ os (s, θ)
The progressive procedure for the computation of p and a is is detailed in Section IV. Once the feature vector p(x) and the corresponding orientation a(x) at point x are detected, we can construct a coherence penalization term which is comprised of two components. The first component is a scalar field E os computed by the enhanced orientation score map Ψ os and the reference point b x such that for a point x ∈ Ω

E os (x) = exp λ |Ψ os (x, a(x)) -Ψ os (b x , a(b x ))| , ( 8
)
where λ is a positive constant. Now we can define a dynamic tensor field

T d : Ω → S + 2 for ∀x ∈ Ω by T d (x) := E os (x) (T os (x) + T aniso (x)) , (9)
where T aniso is defined by

T aniso (x) = µ p ⊥ (x) ⊗ p ⊥ (x), µ ∈ R + . (10)
We set µ = 10 through all the experiments.

IV. FAST MARCHING IMPLEMENTATION

The fast marching front visits all the grid points in Z 2 . It computes the geodesic distances in a monotonically increasing order from the source points, coupled with a course of label assignment [START_REF] Sethian | Fast marching methods[END_REF], [START_REF] Mirebeau | Anisotropic fast-marching on cartesian grids using lattice basis reduction[END_REF]. During the geodesic distance computation, each grid point is assigned a label which is either Far, Accepted or Trial. A basic point for the fast marching method is the stencil map S which defines the neighbourhood for each grid point. In order to deal with the anisotropic case, a complicated metric-dependent stencil construction method should be used [START_REF] Mirebeau | Anisotropic fast-marching on cartesian grids using lattice basis reduction[END_REF]. In this paper, we make use of state-ofthe-art fast marching method proposed by Mirebeau [START_REF] Mirebeau | Anisotropic fast-marching on cartesian grids using lattice basis reduction[END_REF] as our Eikonal solver, where the C++ codes can be downloaded from Anisotropic FM.

At the initialization step, all the source points are tagged as Trial while the remaining grid points in Z 2 are tagged as Far. In each distance update step, we seek a Trial point x min with the minimal geodesic distance. The point x min is immediately tagged as Accepted, from which one can back track a curve length-parameterized geodesic Cxmin joining x min to the source point, i.e., Cxmin (0) = x min . By this geodesic, we can determine two points a min and b min can be identified In order to estimate the geodesic distance U s (•)(x), we need to solve the following Hopf-Lax operator [START_REF] Mirebeau | Anisotropic fast-marching on cartesian grids using lattice basis reduction[END_REF]

a min = Cxmin (u 1 ), b min = Cxmin (u 2 ), (11)
U s (x) = min y∈∂S(x) y -x T d (x) + I S(x) U s (y) , (12)
where I S U s (y) is a distance value estimated by the piecewise linear interpolator I S(x) in the stencil S(x).

In contrast to the general fast marching method which starts the front propagation only from the source point s, here we adopt the partial fronts propagation style [START_REF] Deschamps | Fast extraction of minimal paths in 3D images and applications to virtual endoscopy[END_REF] which starts the propagation simultaneously from the source point s and the endpoint q. A saddle point x * is the first meeting point of the two fronts expanding from the respective points s and q. It can be defined by

x * = arg min x: Us(x)=Uq(x) U s (x), (13)
where U s and U q are the geodesic distance maps associated to the fixed points s and q. Based the maps U s and U q , we can define a new geodesic distance map U by

U(x) = min{U s (x), U q (x)}.
The procedure for the dynamic metrics-based partial fronts propagation can be found in Algorithm 1. We illustrate an example for this partial fronts propagation scheme in Fig. 3. Note that the fast marching front propagation will be terminated once the saddle point x * is detected. Note that the idea of using feature coherence penalization to construct dynamic metric during the geodesic distance propagation was also considered in [START_REF] Chen | Interactive retinal vessel centreline extraction and boundary delineation using anisotropic fast marching and intensities consistency[END_REF]. However, the method 1 A non-accepted point is a point tagged as Trial or Far.

Algorithm 1 PARTIAL FRONTS PROPAGATION SCHEME Output: The distance map U and the saddle point x * . Initialization:

• ∀x ∈ Z2 \{s, q}, set U(x) ← ∞ and set V(x) ← Far.

• ∀x ∈ {s, q}, set U(x) ← 0 and set V(x) ← Trial.

• ∀x ∈ {s, q}, set p(x) ← arg max θ Ψ os (x, θ).

1: while x min is not a saddle point do 2:

Find x min , the Trial point which minimizes U.

3:

Set V(x min ) ← Accepted.

4:

Find the reference points a and b.

5:

for All x n ∈ S * (x min ) and V(x n ) = Accepted do 6:

Set V(x n ) ← Trial. 1: Update the feature vector p(x n ) by a via Eq. ( 7). 2: Update T d (x n ) by the reference point b via Eq. ( 9). 3: Estimate the distance value U tem (x n ) by evaluating [START_REF] Benmansour | Fast object segmentation by growing minimal paths from a single point on 2D or 3D images[END_REF].

4: Set U s (x n ) ← min{U tem (x n ), U s (x n )}.
developed in this paper mainly differs to [START_REF] Chen | Interactive retinal vessel centreline extraction and boundary delineation using anisotropic fast marching and intensities consistency[END_REF] in two ways: (i) we take into account a new adaptive anisotropy tensor field T aniso (see Eq. ( 10)) to enhance the geodesics computation. (ii) the tubular appearance feature is built by the smoothed OS map instead of using the vesselness map 2 itself in [START_REF] Chen | Interactive retinal vessel centreline extraction and boundary delineation using anisotropic fast marching and intensities consistency[END_REF].

V. EXPERIMENTAL RESULTS

We compare our model to the anisotropic radius-lifted Riemannian (ARLR) metric [START_REF] Benmansour | Tubular structure segmentation based on minimal path method and anisotropic enhancement[END_REF] and the Finsler elastica (FE) metric [START_REF] Chen | Global minimum for a Finsler elastica minimal path approach[END_REF] on both synthetic and real images.

In Fig. 4, we compare the dynamic metric against the ARLR metric and the FE metric. Our goal is to extract a tubular structure with weak appearance features between the two points which are indicated by dots. Both the geodesics from the ARLR metric (Fig. 4b) and the FE metric (Fig. 4c) favour to pass through the way with stronger appearance, whereas the proposed method is able to delineate the desired structure, which can be seen from Fig. 4d.

In Fig. 5, we illustrate the minimal path extraction results derived from the ARLR metric, the FE metric and the proposed dynamic metric on retinal images, which are shown in columns 1 to 3, respectively. The user given points are indicated by dots. From column 1, we can observe the short branches combination problem suffered by the ARLR metric, where the extracted paths prefer to pass through vessel segments with strong appearance feature. In the first two rows of column 2, we can see the curvature-penalized geodesics pass by wrong vessel segments due to the complicated structures of the vessel network. In the third column, our model can get the desired results thanks to the feature coherence-penalized nature. We validate the proposed dynamic minimal path model on 45 retinal patches from the DRIVE dataset [START_REF]Ridge-based vessel segmentation in color images of the retina[END_REF]. Each patch includes a retinal artery vessel which is near a stronger retinal vein vessel or crosses it. Our goal is to extract the artery vessel between two user-provided points. The artery-vein (A-V) groundtruth for the DRIVE dataset can be found in [START_REF] Hu | Automated separation of binary overlapping trees in lowcontrast color retinal images[END_REF]. Let A be the set of the grid points inside the desired regions (such as the artery vessels) and let |A| ∈ R + 0 be the number of elements of the set A. In addition, we define a set Γ of grid points such that each grid point involved in Γ is passed by a continuous geodesic. Thus, a measure Θ ∈ [0, 1] can be simply defined by Θ = |Γ∩A|/|Γ|. For the DRIVE dataset, we provide two ways to construct the set A, where the first way is directly set A as the artery vessel map which can be identified from the A-V groundtruth. In this case, the measurement Θ evaluates the ability of reducing the risk of short branches combination problem for each geodesic metric. The second way is to skeletonise the artery regions (derived from the A-V groundtruth) via morphological operators. Following that we perform a dilation operation with radius = 1 on the artery vessel skeletons. Finally, the set A is obtained by identifying all the grid points which simultaneously belong to the dilated regions and the vessel groundtruth regions (including both artery and vein vessels). In this case, the measurement Θ is able to evaluate the alignment between the extracted geodesic and the desired vessel centerlines in a more restrict manner.

VI. CONCLUSION

In this paper, we propose a new dynamic Riemannian metric for geodesic computation with application to tubularity centerline delineation. The dynamic metric can benefit from the tubular appearance feature coherence property and adaptive anisotropy enhancement, by which we can extract a tubular structure with low variations of appearance features from an image with complicated tree structures. The tubular appearance features are estimated using the tool of orientation scores. The proposed dynamic Riemannian metric is constructed during the fast marching front propagation in terms of the respective reference points. The results show that our method indeed outperforms state-of-the-art minimal path methods.

Fig. 1 .

 1 Fig. 1. Short branches combination problem. a Original image with boundaries of target vessel. b Minimal path from the anisotropic Riemannian metric [6]. c Minimal path from the proposed dynamic metric.

Fig. 2 .

 2 Fig. 2. Left The red and blue arrows at point x 1 (resp. x 2 ) respectively indicate the elements involved in Mx 1 (resp. Mx 2 ) and Mx 1 (resp. Mx 2 ). Middle The red and blue curves respectively indicate the values of Ψos(x 1 , θ) and ψos(x 1 , θ). Black dots are the peak orientations. Right The red and blue curves respectively indicate the values of Ψos(x 2 , θ) and ψos(x 2 , θ).

Fig. 3 .

 3 Fig. 3. Partial fronts propagation scheme. The geodesic distance maps superimposed on the retinal patch. The black curves indicate the geodesics for which the endpoints are respectively s and q.

  n , U, V, p, a, b).

2

 2 UPDATEFRONTDISTANCE(x n , U s , p, a, b)

Fig. 4 .Fig. 5 .

 45 Fig. 4. Comparison results on a synthetic image. a A synthetic image which includes a tubular shape. b-d Minimal paths obtained via the ARLR metric, the FE metric and the proposed metric. The dots indicate the user-provided points.

TABLE I QUANTITATIVE

 I COMPARISONS OF DIFFERENT METRICS ON DRIVE.

	A	Θ	ARLR	FE	Dynamic
		Avg.	0.32	0.66	0.93
	A-V Groundtruth	Max. Min.	0.97 0.02	1.0 0.15	1.0 0.59
		Std.	0.21	0.29	0.08
		Avg.	0.28	0.51	0.77
	Dilated Skeleton	Max. Min.	0.95 0.02	0.91 0.14	0.95 0.33
		Std.	0.21	0.24	0.13

The vesselness map is defined as: maxr ρ(x, r).

ACKNOWLEDGMENT

The authors would like to thank the reviewers for their suggestions to improve the presentation of this paper. This research has been funded by Roche pharma (project AMD short) and by a grant from the French Agence Nationale de la Recherche ANR-16-RHUS-0004 (RHU TRT cSVD).


Uddam Chukmol

Aïcha-Nabila Benharkat

Youssef Amghar
email: youssef.amghar@insa-lyon.fr

Bringing socialized semantics into Web services based on user-centric collaborative tagging and usage experience

Keywords: Social Web service, user annotation, collaborative social semantics I

The semantics of Web services is often provided by suppliers and embedded physically inside the service descriptions expressed in WSDL. This type of annotation can be very costly and is generally performed by well-trained cognitive or knowledge engineers. In this research work, we aim at providing an alternative to the actual Semantic Web Service (SWS) technologies by bringing a community-based or social semantics into Web services. This semantics is created by users through collaborative tagging on the capabilities of Web services after testing or using them. We argue that this type of semantic annotation can be very pragmatic and facilitate the process of Web service discovery, composition or clustering assisted by users.

INTRODUCTION

Semantic Web community proposes numerous formalisms based on logics or ontologies to extend standard Web service description expressed in WSDL such as OWL-S [START_REF]OWL-S: Semantic Markup for Web Services[END_REF], WSMO [START_REF]Web Service Modeling Ontology (WSMO)[END_REF], WSDL-S [START_REF]Web Service Semantics -WSDL-S[END_REF], SAWSDL [START_REF]Semantic Annotations for WSDL and XML Schema[END_REF] or WSMO-Lite [START_REF]D11v0.2 WSMO-Lite[END_REF]. Semantic annotations based on these formalisms can be done at the service supplier sides only and may represent some cost and rigidity to them. In effect, modifying and maintaining ontologies are very complex and timeconsuming tasks and in order to master completely the annotation process, the suppliers must acquire sufficient expertise in cognitive or knowledge engineering. In addition to the heterogeneity of semantics representations that may provoke several interoperability issues, the absence of fully semantic supported Web service registries in business environment discourages even more the enterprises in adopting SWS at large scale [START_REF] Shi | Semantic Web Services: An Unfulfilled Promise[END_REF]. Besides, the SWS community itself reveals that there are still many challenges to convince practitioners to adopt their technologies [START_REF] Martin | Semantic Web Services, Part 1[END_REF] [START_REF] Martin | Semantic Web Services, Part 2[END_REF]. At the user sides, exploiting SWS technologies means at least a proficiency in description logics or knowledge engineering, which can be considered as a burden. Moreover, there are not many tools supporting these technologies that are robust and in a form that developers find attractive and easy to learn and use [START_REF] Martin | Semantic Web Services, Part 2[END_REF].

The recent emergence of Internet of Service [START_REF] Schroth | Web 2.0 and SOA: Converging Concepts Enabling the Internet of Services[END_REF][10] and the increasing number of public accessible Web services in the Internet [START_REF] Wu | Searching Services "on the Web": A Public Web Services Discovery Approach[END_REF] [START_REF] Hageman | [END_REF] [START_REF] Al-Masri | Discovering Web Services in Search Engines[END_REF] through portals or catalogs lead us to several other research issues. The main one that interests us is how to assist users at best in the discovery and composition of Web service in the aforementioned environment (publicly accessible Web services in the Internet). We are aware of the limit met in the keyword based service discovery systems due to the poor textual descriptions that can be extracted from WSDL descriptions of Web services [START_REF] Hageman | [END_REF]. We assume also that users who browse Web service portals in the Internet are not proficient enough in constructing discovery queries using description logics or SPARQL to exploit the semantic metadata embedded in the WSDL contents of Web services. Thus, it is interesting to provide them intuitive and easily approachable ways to discover, to compose or to classify Web services.

Inspired by the dynamics of Web 2.0, we encourage user communities to participate in sharing their perceptions on Web services by tagging collaboratively any Web service that they used or tested before. Only through real world testing and usage, a user can have a clear idea on how to comment or give feedback on a Web service. Service usage experience can be expressed as comments or feedbacks on several aspects of Web service that can be observed by users during its testing or usage. We are interested in bridging the gap between original description and real world usage of service.

In this research work, we propose a folksonomic annotation model allowing users to express their perception on service functionality (after testing or using them). The annotations issued from users form incrementally community-based semantics on annotated Web services. This semantic metadata can be viewed by other users of the system and can be used to assist them in the task of discovery, composition or clustering of services. We propose also a collaborative tagging system supporting the aforementioned annotation model and allowing collect and construct social semantics of Web services.

This paper is organized as follows. Section 2 discusses similar research works. Section 3 describes the annotation/tagging model followed by the supporting tagging system in section 4. Section 5 argues on some applicative usage scenarios of the annotation to prove the pragmatism of our approach. Finally we conclude and present some future directions of the proposal.

II. RELATED WORKS

To our knowledge, there are still few existing proposals that adhere to the idea of using community-based semantics of Web services. We choose some significant proposals that follow the concepts and try to point out their strengths and limits.

The earliest proposal to use tagging to represent the semantics of Web service is discussed in [START_REF] Meyer | Light-Weight Semantic Service Annotations Through Tagging[END_REF]. It is still a rudimentary approach by considering keywords provided by users and associated to Web services as sufficient to describe their semantics. It is a collaborative tagging process but there is no discussion on how to merge tags provided by different users to annotate a specific service. Later on, a similar approach follows the same tagging mechanism but improves the system with more complete tags management in terms of variety and aggregation [START_REF] Chukmol | Enhancing Web Service Discovery by Using Collaborative Tagging System[END_REF]. However, it shares with the previous one the same downside. Despite all, this concept of user-provided semantics of Web service is exploited in the real world situation in [START_REF] Papathanasiou | Combining Service Models, Semantic and Web 2.0 Technologies to Create a Rich Citizen Experience[END_REF] and [START_REF]seekda! -About seekda[END_REF] to help users in searching for services.

Some improvement of the concept has been made in [START_REF] Bouillet | A Folksonomy-Based Model of Web Services for Discovery and Automatic Composition[END_REF] by tagging only the input and output parts of Web services with the final goal to facilitate the discovery for composition process. However, the main drawback of the approach is that the original description of Web services is modified, which can be done only by the providers. Tags are then used to build a hierarchy with help from a machine learning approach, which requires a great quantity of annotated services and time. The discovery process using tags is based on this hierarchy. This idea of tag hierarchy is also picked up by [START_REF] Silva-Lepe | SOAlive Service Catalog: A Simplified Approach to Describing, Discovering and Composing Situational Enterprise Services[END_REF] with help from WordNet [START_REF]About WordNet -WordNet -About WordNet[END_REF] and Wikipedia [START_REF]Wikipedia, the free encyclopedia[END_REF] by exploiting their linguistic relations between terms. This hierarchy is also served to facilitate the discovery by tag. Nonetheless, both approaches ignore how tags are merged when provided by several users and associated to a service and still consider freeform tags as representative enough to reflect the service semantics.

In brief, there are common limits of the aforementioned proposals such as:

x Considering service semantics as global and taking freeform tags that are associated to the service as sufficient semantic expression of the service. This concept is still very vague because the semantics of service should be expressed in a more elaborated way by favoring more expression on the capability of the services x Several users can tag a service but their aggregations are usually ignored. In fact, in a collaborative tagging system tag weight or tag frequency is an important factor to assess the significance of the tagged object via that tag and x Tag ambiguity is often ignored. This issue can cause very weak ratio of precision and recall in the search of tagged objects by using tags. Our proposal attempts to provide some solutions to improve the aforementioned limits encountered in the existing approaches.

III. ANNOTATION/TAGGING MODEL

It is worth mentioning that we work with publicly accessible Web services that can be collected from various Web service portals or catalogs on the Internet. Therefore, users are not allowed to add services into the system. Only the service providers can modify the service collection. Users can only add metadata to annotate or tag the existing Web services in the collection. Generally, a public Web service can be discovered, tested, tagged or annotated (in our case) and used (e.g. in a composition). This cycle can be repeated as many times as possible and conducted by any user on any service. Thus, a public Web service can be present in various states of the aforementioned cycle (see Figure 1). At the user side, in order to get a full and clear idea on the functionality of a Web service, testing it is strongly recommended. Testing a service generally refers to testing the operations of the service by providing input data and observing output data. Therefore, at this state, the functionality of a Web service is qualified by its operations and for each of them what input and output is required (see the unit test interface of Seekda [START_REF]seekda! -About seekda[END_REF] and Directory of public SOAP Web services [START_REF]Directory of public SOAP Web Services[END_REF]).

However, a service can be employed differently with respect to usage context or user requirement (e.g. a weather forecast service can be used perfectly in either "holiday preparation" or "wedding party organization" context). Thus, operational and contextual information are necessary to fully describe the user perception on a Web service after a usage experience of the service.

In brief, given a Web service described by WSDL content, there can be several operations to test and for each operation there can be several input parameters to enter and output results to observe. Consequently, a tester can annotate a Web service at usage (describing the situation or context in which he/she uses the service), operation (describing different atomic functions of the service), input (describing what to offer as input when testing an operation) and output (describing the observable result after testing an operation) level.

Therefore, given a service, we can identify four types of taggable object that correspond to the four aforementioned levels (see Figure 2). We ignore the pre-condition and effect at operation level because a unit testing is done completely stateless and these aspects are hardly perceived by users. A user can annotated a Web service as efficient to be used in a certain context or situation, as providing several functions and each of them executes an action or as requiring some input data and providing certain output result.

The system allows collaborative participation of users in the tagging or annotation activities. In effect, a taggable object can be annotated by several users with different keywords and a user can annotate many taggable objects as well. Keywords from several users are used to construct tags and then feed the tag cloud that is associated to the corresponding taggable object (see Figure 3). The next section discusses in detail the tagging system and describes its core components. We attempt to illustrate the functionality of such system by presenting the abstract architecture of the system and its interactions with users.

IV. ANNOTATION/TAGGING SYSTEM

After choosing a Web service to tag, the identifier of the service (its invocation URL) is input to the system. The system parses the WSDL file (with help from WSDL Parser module -(see Figure 4)) corresponding to the description of Web service in order to display its interfaces, operations, inputs and outputs. This parsing process is needed to visualize the Web service as structurally perceived by the user, mentioned in Figure 2.

A WSDL file can offer x taggable objects with x=1+number of operations + number of inputs + number of outputs. An operation, input, output object is identified by the Web service identifier and its XPath path (including namespace) of the corresponding element in the WSDL file.

After the parsing, the system searches for the existing tag cloud that is associated to each taggable object and displays them to users. This can give the user some ideas of how the others perceive the service he/she is tagging. Partial tagging is completely allowed in order to diminish the user effort in interacting with the system; i.e. the user is not obliged to tag every single item of the Web service.

Then the user can proceed to the effective tagging by providing a list of keywords to be associated to a chosen object. Each keyword is delimited by "" and separated by ;. We recommend users to provide dictionary vocabularies instead of personalized terms as keywords. In effect, personalized terms (e.g. nyc for New York City, fb for Facebook, etc.) can represent an important source of littering tags for the global tag cloud, thereby affects the quality of search operations using tags.

Each keyword can be associated to a set of meanings proposed by the system. The user chooses a meaning that suits best his/her keyword to form a tag. In effect, there are several linguistic issues related to collaborative tagging systems mainly synonymy and polysemy [START_REF] Golder | The Structure of Collaborative Tagging Systems[END_REF]. We decide to treat only polysemous keywords in our system because it represents an important element judging the precision rate of discovery/search system based on tags. This issue goes against our initial objective that proposes to use collaborative tags to enhance Web service discovery, reuse and composition processes, where precision rate is important for the system performance.

As soon as the keywords are semantified and the tags are formed, they are aggregated with the existing ones, given a taggable object. We opt for bag-of-words aggregation method that consists of increasing the frequency of tags in the tag cloud. A recent research proves that tag frequency is significant to qualify the tagged object by the related tag because in most of the cases, tag distribution follows a power law [START_REF] Robu | Emergence of consensus and shared vocabularies in collaborative tagging systems[END_REF].

The result of the aggregation is another tag cloud combining the tags provided by the user and those associated to the tagged object before the tagging. Finally, the tagged object and its tag cloud are saved back into the system (see Figure 4).

In detail, given a Web service identifier (its invocation URL), the Tagged Web Serivce Collection can output the corresponding WSDL file using its Access Interface. All the existing tags associated with this Web service are output by the same interface also.

In this collection, we store different instances of our folksonomy represented by 3 relations (see Figure 5) such as User-Tag: given a user u and a tag t, this relation offers the list of objects tagged by t. For each object, it indicates also the number of times (weight or frequency) t is used by u to tag the object, Object-Tag: given an object o and a tag t, this relation offer the list of users employing t to tag o. For each user, it indicates number of times he/she has used t to tag o and User-Object: given a user u and an object o, this relation offers the list of tags used by u to tag o. For each tag, it indicates its frequency also. First, tagging an object consists of fetching input keywords from users and for each keyword, the system checks through Wikipedia [START_REF]Wikipedia, the free encyclopedia[END_REF] for its various meanings. This operation is called disambiguation of keyword. It is simply done by inquiring for the disambiguation pages of Wikipedia using some API such as [START_REF]JWPL[END_REF] and [START_REF]Wikipedia API -Wikipedia-Lab[END_REF]. Each disambiguation page corresponds to the meaning that users chose to qualify a keyword.

In effect, the choice for Wikipedia is because it is a collaboratively edited free encyclopedia that evolves with strong support from community and covers a large number of vocabularies. It is possible that users leave the meaning of a keyword as null if none of the meanings proposed by Wikipedia suits him/her.

Secondly, after the meanings are selected by users, the tags are formed; i.e. couples of keywords and meanings. These tags are then aggregated with the existing tag cloud associated to the tagged object. The aggregation of two tag t i <k i , m i > and t j <k j , m j > having respectively f i and f j as frequency is a bag of tags (tag cloud) containing t i if and only if t i and t j are identical (keyword k i =k j and meaning m i =m j ) with the new frequency that is equal to (f i +f j )(one tag only); else, t i and t j with their previous frequencies respectively (two tags). After associating the aggregated tag cloud to the tagged object, the system updates the Tagged Web Service Collection by updating its three relations mention before, respectively.

V. SOME APPLICATIVE USAGE SCENARIOS USING OUR ANNOTATION/TAGGING MODEL The fact that users can annotate Web services with their own tags implies more plentiful and community supported semantics. Beyond syntactic information, these semantics can enhance the discoverability, reusability and composability of Web services.

During the Web service discovery process at design time, our annotation can be used to help application developers in finding relevant capabilities of services. In this case, tags at Web service (usage context) and operation level are considered because they are significant to get the functional offer of the services. Web services can also be browsed via tags and that is more intuitive for developer to create his/her discovery query easily, quickly and efficiently. However, it is recommended that service user communities care enough participating in tagging Web services at the two aforementioned levels to make social semantics of the services emerge.

Web service composition can be assisted by users also. In this case, tags at input and output levels are more considered than those of usage context or operation level. When a user would like to have on-time effects or interventions on the composition of Web services, he/she can check the tag clouds at his/her disposal for atomic service that responds to his/her prompt need in order to create his/her composite Web service. The requirement formulation is easy as our tagging model favors the annotation on input and output level of Web services.

Tags themselves can be used to create user profile and propose the recommendation to help in the discovery and composition process. User profile may be constructed from tag sets offered by the user and be used in the filtering phase of the discovery process whereas recommendation can be used in the composition process to enhance the composability of the service. Moreover, our annotation can help in the user-oriented and semi-automatic Web service clustering or classification also. With the increasing number of tags at operation levels, we can employ different natural language processing techniques on these tags to classify the tagged Web services.

Despite all, there are several challenges to overcome in order to evaluate our annotation model. Our system demands user participation to populate the tag clouds and their volume are important to access the quality and performance of the model. This factor is common to other collaborative tagging system as mentioned in [START_REF] Robu | Emergence of consensus and shared vocabularies in collaborative tagging systems[END_REF] and [START_REF] Golder | The Structure of Collaborative Tagging Systems[END_REF]. Besides, it is even harder to conduct a comparative qualitative evaluation on our because of the weak number of existing semantic annotation models of the kind and their supporting systems.

VI. CONCLUSION AND FUTURE WORKS

In this paper, we have proposed an annotation model that is easy to use and issued from the user perception on the functionality of Web services after testing or using them. The annotation model covers four levels of Web services: usage context, operation, input and output. Elements extracted from WSDL descriptions of Web services corresponding to each level represent system taggable/annotatable objects.

Several users can tag/annotate several objects during his/her system use. The tagging allows users to provide a list of keywords associated to an object and the system proposes several meaning of the keywords before asking the taggers to validate the suitable meanings. Thus, a tag is represented by a name entity and a meaning that is richer and unambiguous comparing to traditional freeform tags. The disambiguation of name entities or keywords is based the disambiguation functions/pages of Wikipedia which is the largest community supported and evolving encyclopedia.

The frequency of tag or tag weight evolves through user tagging activities and is essential to qualify the significance or semantic of the tagged object via the keywords.

We propose some applicative usage scenarios in which our annotation model can contribute in enhancing the overall performance and facilitating user interventions. It is also important to note that our annotation model does not modify the original descriptions of Web services and it is very plausible to use this model with the ontology-based semantic annotations presented in section 1. Both approaches are complementary because ours is more focused on the emerging semantics from the user side and those presented in section 1 are more used at the service provider sides.

In our future work, we would like to extend our annotation model to cover other semantic aspects of Web services such as non-functional or behavioral characteristics and use or adapt it in RESTful service context. We aim also at making use of existing SWS annotations by lowering them into human readable keyword meanings and employ them in the keyword disambiguation phase. We further provide multiple meaning bases to users allowing them to enrich their tag meanings and offer users the possibilities to add tailored meaning to their tags if none of the ones proposed by the system suits.

Figure 1 .

 1 Figure 1. Web service annotation/tagging cycle

Figure 2 .

 2 Figure 2. Web service annotation/tagging level

Figure 3 .

 3 Figure 3. An instance of folksonomy structure The annotations from a user on a service can be viewed by other users of the system in order to insure the community-based collaborative criterion. Therefore, we can define our annotation model as a folksonomy F (O × T × U) where O, T and U are distinct sets and U: represents the set of users subscribed to the system and capable of annotating and tagging the Web service collection provided by the system, O: represents the set of objects that can be tagged (taggable object) by users. Each object can be a Web service (service usage context or

Figure 4 .

 4 Figure 4. User-System modules interaction while tagging WSDL Parser parses the description WSDL of the service to tag by proposing a structure of taggable objects. Users can then choose some objects to tag.

Figure 5 .

 5 Figure 5. Taggable object -Tag -User relations