Patrick Solé

Michel Planat

Extreme values of the Dedekind Ψ function

Keywords: 11N56, 11A25, 11M06 Dedekind Ψ function, Euler totient function, Mertens formula, Nicolas bound, Primorial numbers

Let Ψ(n) := n p|n (1 + 1 p ) denote the Dedekind Ψ function. Define, for n ≥ 3, the ratio R(n) := Ψ(n) n log log n . We prove unconditionally that R(n) < e γ for n ≥ 31. Let N n = 2 • • • p n be the primorial of order n. We prove that the statement R(N n ) > e γ ζ(2) for n ≥ 3 is equivalent to the Riemann Hypothesis.

I. INTRODUCTION

The Dedekind Ψ function is an arithmetic multiplicative function defined for every integer n > 0 by

Ψ(n) := n p|n (1 + 1 p ).
It occurs naturally in questions pertaining to dimension of spaces of modular forms [START_REF] Csirik | On the genera of X0(N )[END_REF] and to the commutation of operators in quantum physics [START_REF] Planat | Pauli graphs when the Hilbert space dimension contains a square: why the Dedekind psi function ?[END_REF]. It is related to the sum of divisor function

σ(n) = d|n d by the inequalities Ψ(n) ≤ σ(n),
and the fact that they coincide for n squarefree. It is also related to Euler ϕ function by the inequalities

n 2 > ϕ(n)Ψ(n) > n 2 ζ(2)
derived in Proposition 5 below.

In view of the studies of large values of σ [START_REF] Robin | Grandes valeurs de la fonction somme des diviseurs et hypothèse de Riemann[END_REF] and of low values of ϕ [START_REF]Jean-Louis Petites valeurs de la fonction d'Euler[END_REF], it is natural to study both the large and low values of Ψ. To that end, we define the ratio R(n

) := Ψ(n)
n log log n . The motivation for this strange quantity is the asymptotics of Proposition 3. We prove unconditionally that R(n) < e γ , for n ≥ 31 in Corollary 2. Note that this bound would follow also from the Robin inequality σ(n) ≤ e γ n log log n for n ≥ 5041 under Riemann Hypothesis (RH) [START_REF] Robin | Grandes valeurs de la fonction somme des diviseurs et hypothèse de Riemann[END_REF], since Ψ(n) ≤ σ(n). In the direction of lower bounds, we prove that the statement R(N n ) > e γ ζ(2) for n ≥ 3 is equivalent to RH, where N n = 2 • • • p n is the primorial of order n. The proof relies on Nicolas's work on the Euler totient function [START_REF]Jean-Louis Petites valeurs de la fonction d'Euler[END_REF].

Telecom ParisTech, 46 rue Barrault, 75634 Paris Cedex 13, France. Institut FEMTO-ST, CNRS, 32 Avenue de l'Observatoire, F-25044 Besanc ¸on, France II. REDUCTION TO PRIMORIAL NUMBERS Define the primorial number N n of index n as the product of the first n primes

N n = n k=1 p k , so that N 1 = 2, N 2 = 6,
• • • and so on. As in [START_REF]Jean-Louis Petites valeurs de la fonction d'Euler[END_REF], the primorial numbers play the role here of superabundant numbers in [START_REF] Robin | Grandes valeurs de la fonction somme des diviseurs et hypothèse de Riemann[END_REF]. They are champion numbers (ie left to right maxima) of the function x → Ψ(x)/x :

Ψ(m) m < Ψ(n) n for any m < n, (1)
We give a proof of this fact, which was observed in [START_REF] Planat | Riemann hypothesis from the Dedekind psi function[END_REF].

Proposition 1: The primorial numbers N n are exactly the champion numbers of the function x → Ψ(x)/x.

Proof: The proof is by induction on n. The induction hypothesis H n is that the statement is true up to N n . It is clear that H 2 is true. Let N n ≤ m < N n+1 be a generic integer. The number m has at most n distinct prime factors. This, in combination with the observation that 1 + 1/x is monotonically decreasing as a function of x, shows that

Ψ(m)/m ≤ Ψ(N n )/N n . Further Ψ(N n )/N n < Ψ(N n+1 )/N n+1 . The proof of H n+1 follows.
In this section we reduce the maximization of R(n) over all integers n to the maximization over primorials.

Proposition 2: Let n be an integer ≥ 2. For any m in the range

N n ≤ m < N n+1 one has R(m) ≤ R(N n ).
Proof: Like in the preceding proof we have

Ψ(m)/m ≤ Ψ(N n )/N n
Since 0 < log log 6 < log log N n ≤ log log m, the result follows.

III. Ψ AT PRIMORIAL NUMBERS We begin with an easy application of Mertens formula [START_REF] Hardy | An introduction to the theory of numbers[END_REF]Th. 429

]. Proposition 3: We have, as n → ∞ lim R(N n ) = e γ ζ(2) ≈ 1.08. Proof: Writing 1 + 1/p = (1 -1/p 2 )/(1 -1/p) in the definition of Ψ(n) we can combine the Eulerian product for ζ(2) with Mertens formula p≤x (1 -1/p) -1 ∼ e γ log(x) to obtain Ψ(N n ) N n ∼ e γ ζ(2) log(p n ),
Now the Prime Number Theorem [3, Th. 6, Th. 420] states that x ∼ θ(x) for x large. where θ(x) stands for Chebyshev's first summatory function:

θ(x) = p≤x log p.
This shows that, taking x = p n we have

p n ∼ θ(p n ) = log(N n ).
The result follows. This motivates the search for explicit upper bounds on R(N n ) of the form e γ ζ(2) (1+o(1)). In that direction we have the following bound.

Proposition 4: For n large enough to have p n ≥ 20000, that is n ≥ 2263, we have

Ψ(N n ) N n ≤ exp(γ + 2/p n ) ζ(2) (log log N n + 1.125 log p n )
So, armed with this bound, we derive a bound of the form R(N n ) < e γ for n ≥ A, with A a constant.

Corollary 1: For n ≥ 4, we have R(N n ) < e γ = 1.78 • • • Proof: For p n ≥ 20000, we use the preceding proposition. We need to check that

exp(2/p n )(1 + 1.125 log(p n ) log log(N n ) ) ≤ ζ(2).
Since the LHS is a decreasing function of n it is enough to check this inequality for the first n such that p n ≥ 20000. For 5 ≤ p n ≤ 20000, that is 3 ≤ n ≤ 2262 we simply compute R(N n ), and check that it is < e γ .

We can extend this Corollary to all integers > 30 by using the reduction of preceding section, combined with some numerical calculations for 30 < n ≤ N 4 .

Corollary 2: For n > 30, we have R(n) < e γ .

We prepare for the proof of the preceding Proposition by a pair of Lemmas. First an upper bound on a partial Eulerian product from [8, (3.30)

p.70].

Lemma 1: For x ≥ 2, we have

p≤x (1 -1/p) -1 ≤ e γ (log x + 1 log x )
Next an upper bound on the tail of the Eulerian product for ζ(2). Lemma 2: For n ≥ 2 we have

p>pn (1 -1/p 2 ) -1 ≤ exp(2/p n )
Proof: Use Lemma 6.4 in [START_REF] Choie | Patrick On Robin's criterion for the Riemann hypothesis[END_REF] with x = p n and t = 2. We are now ready for the proof of Proposition 4.

Proof:

Write Ψ(N n ) N n = n k=1 1 -1/p k 2 1 -1/p k
and use both lemmas to derive

Ψ(N n ) N n ≤ exp(γ + 2/p n ) ζ(2) (log p n + 1 log p n ).
Now we get rid of the first log in the RHS by the bound of [7, p.206]

log(p n ) < log log N n + 0.125 log p n .
The result follows.

IV. LOWER BOUNDS We reduce first to Euler's ϕ function. Proposition 5: For n ≥ 2 we have

n 2 > ϕ(n)Ψ(n) > n 2 ζ(2)
Proof: The first inequality follows at once upon writing

ϕ(n)Ψ(n) n 2 = p|n (1 -1/p 2 ),
a product of finitely many terms < 1. Notice for the second inequality that

ϕ(n)Ψ(n) n 2 = p|n (1 -1/p 2 ) > p (1 -1/p 2 ),
an infinite product that is the inverse of the Eulerian product for ζ(2).

Theorem 1: [START_REF] Csirik | On the genera of X0(N )[END_REF] . We need to show that there exists an x 0 ≥ 3 such that g(x 0 ) > 1 or equivalently log g(x 0 ) > 0. Using once again the identity 1 -1/p 2 = (1 -1/p)(1 + 1/p), and [1, Lemma 6.4], we obtain, upon writing

Under RH the ratio R(N n ) is > e γ ζ(2) for n ≥ 3. If RH
(1 + 1/p) -1 , Observing that log θ(p n ) = log log N n , we see that g(p n ) < 1 is equivalent to R(N n ) > e γ ζ (
-log ζ(2) = p≤x log(1 -1/p 2 ) + p>x log(1 -1/p 2 ), the bound log g(x) ≥ log f (x) -2/x,
where f is the function introduced in [4, Theorem 3], that is f (x) := e γ log θ(x) p≤x (1 -1/p).

We know by [START_REF]Jean-Louis Petites valeurs de la fonction d'Euler[END_REF]Theorem 3 (c)] that, if RH is false, there is a 0 < b < 1 such that lim sup x -b f (x) > 0 and hence lim sup log f (x) >> log x. Since 2/x = o(log x), the result follows.

V. CONCLUSION In this note we have derived upper and lower bounds on the Dedekind Ψ function. We show unconditionally that the function Ψ(n) satisfies the Robin inequality. Since ψ(n) ≤ σ(n) this could be proved under RH [START_REF] Robin | Grandes valeurs de la fonction somme des diviseurs et hypothèse de Riemann[END_REF] or by referring to [START_REF] Choie | Patrick On Robin's criterion for the Riemann hypothesis[END_REF]. Of special interest is Conjecture 1 which is shown here to be equivalent to RH. We hope this new RH criterion will stimulate research on the Dedekind Ψ function.

  is false, this is still true for infinitely many n.

	Proof:
	Follows by Proposition 5, combined with [4, Theorem 2].
	In view of this result and of numerical experiments the natural conjecture is
	Conjecture 1: For all n ≥ 3 we have R(N n ) > e γ ζ(2) . The main result of this note is the following.
	Theorem 2: Conjecture 1 is equivalent to RH.
	Proof: If RH is true we refer to the first statement of Theorem 1. If RH is false we consider the
	function	g(x) :=	e γ ζ(2)	log θ(x)	p≤x

Acknowledgements:

The authors thank Fabio Anselmi, Pieter Moree, and Jean-Louis Nicolas for helpful discussions.


Lisa Chauvet

Patrick Guillaumont

Aid, Volatility and Growth Again When Aid Volatility Matters and When it Does Not

In previous papers we have argued that aid is likely to mitigate the negative effects of external shocks on economic growth (i.e. that aid is more effective in countries which are more vulnerable to external shocks). Recently an important debate has emerged about the possible negative effects of aid volatility itself. However, the cushioning effect of aid may involve some volatility in aid flows, which then is not necessarily negative for growth. In this paper we examine to what extent the time profile of aid disbursements may contribute to an increase or a decrease of aid effectiveness. We first show that aid, even if volatile, is not clearly as pro-cyclical as often argued, and, even if pro-cyclical, is not necessarily destabilizing. We measure aid volatility by several methods and assess pro-cyclicality of aid with respect to exports, thus departing from previous literature, which usually assess pro-cyclicality of aid with respect to national income or fiscal receipts. The stabilizing/destabilizing nature of aid is measured by the difference in the volatility of exports and the volatility of the aid plus exports flows. Then, in order to take into account the diversity of shocks to which aid can respond, we consider the effect of aid on income volatility and again find that aid is making growth more stable, while its volatility reduces this effect. We finally evidence through growth regressions that the higher effectiveness of aid in vulnerable countries is to a large extent due to its stabilizing effect.

Introduction

While a rising concern was perceptible about the problems raised by volatility, several recent papers, followed by more official documents and political declarations, have underlined the problem induced by aid volatility (Bulir and Hamann, 2001, 2003[START_REF] Raddatz | Are External Shocks Responsible for the Instability of Output in Low-Income Countries? World Bank Policy Research Working Paper 3680[END_REF][START_REF] Benn | Improving the dynamics of aid[END_REF]Fielding and Mavrotas 2005;[START_REF] Lensink | Aid Instability as a Measure of Uncertainty and the Positive Impact of Aid on Growth[END_REF][START_REF] Pallage | Foreign Aid and the Business Cycle[END_REF][START_REF] Rand | Business Cycles in Developing Countries : Are They Different[END_REF]IMF and World Bank, 2005): if aid is volatile, it may contribute to macroeconomic instability, then be itself a factor of vulnerability. This concern has been reinforced by the prospect of an acceleration of disbursements in order to achieve the Millennium Development Goals. It may be particularly relevant for African countries, which are highly vulnerable and where the prospects of aid increase mainly apply.

However, in the context of the aid effectiveness debate, we have argued in two previous papers [START_REF] Patrick | Aid and Performance: A Reassessment[END_REF][START_REF] Lisa | Aid and Growth Revisited: Policy, Economic Vulnerability and Political Instability[END_REF]) that aid is likely to cushion the negative effects of external shocks on economic growth (i.e. that aid is more effective in countries that are more vulnerable to external shocks). Aid volatility prosecution may thus be misplaced if aid has a compensatory profile: in that case aid volatility, rather than a problem, would be a solution. Indeed, any cushioning effect of aid involves some volatility in aid flows: if aid is to mitigate trade and climatic shocks, then aid will obviously be volatile.

This kind of aid volatility should not have a negative impact on growth, since it is likely to protect the growth process of the developing countries vulnerable to external shocks. This is why volatility of aid is not so much prosecuted than its unpredictability and its pro-cyclicality. Unpredictability of aid is supposed to be harmful, but is difficult to assess. Its assessment would need a forecasting model of aid at the recipient level, where the predicted level would depend among other factors on the kind of aid delivered and on the shocks likely to occur. Pro-cyclicality is easier to measure. It has been essentially assessed with respect to national income or fiscal revenue. Here we analyse the pro or contra-cyclicality of aid mainly with respect to exports, because exports volatility, which results to a large extent from commodity price shocks, is more likely to be exogeneous than national income or fiscal revenue volatility. However pro-cyclicality may not be the most relevant concept to assess the economic consequences of aid volatility, what we intend to do with regard to growth. This is why in this paper we design another concept, which is the stabilizing impact of aid, here measured with respect to exports.

Section 2 assesses the concepts of aid volatility, pro-cyclicality, and stabilizing impact.

Referring to the evolution of exports of goods and services, we argue that aid is not as procyclical as it is often asserted. We measure the stabilizing character of aid with the difference between the volatility of exports and the volatility of exports plus aid. Using this indicator, we argue that a pro-cyclical aid can still be stabilizing, and that there may be cases where aid is contra-cyclical and destabilizing, depending on the relative volatility of aid with respect to exports.

Since the instability of exports is not the only kind of exogeneous shocks faced by low income countries, section 3 studies the stabilizing or destabilizing character of aid in a broader perspective. It examines through panel data the impact of aid on the volatility of income: controlling for the traditional variables of income volatility (including exports instability) we find that the level of aid has a stabilizing impact, while its volatility has a destabilizing impact.

In section 4, coming back to the stabilizing impact of aid with respect to exports, we use this indicator in growth regressions. We can explain that the higher aid effectiveness in vulnerable countries is due to a large extent to its stabilizing effect: exogeneous trade shocks have a negative impact on growth and aid mitigates this impact. Finally, section 5, presents the main conclusions of the paper.

Contra-cyclicality, volatility and stabilizing character of aid with regard to exports

The contra-cyclical character of aid can be measured by the correlation between the "cycle" of aid (i.e. the deviation from its trend) and the "cycle" of the aggregate to which aid is compared. Thus contra-cyclicality is always related to the choice of a reference aggregate and of a trend measurement.

Contra-cyclical aid: with reference to which aggregate?

Previous literature has so far assessed contra-cyclicality of aid with respect to national income (e.g. [START_REF] Pallage | Foreign Aid and the Business Cycle[END_REF] or fiscal receipts (e.g. Bulir and Hamann, 2001, 2003[START_REF] Raddatz | Are External Shocks Responsible for the Instability of Output in Low-Income Countries? World Bank Policy Research Working Paper 3680[END_REF]. Here we compare aid cycles to that of exports of goods and services.1 This can be justified on two grounds. First, as far as we are concerned by macroeconomic vulnerability to external shocks, better is to compare aid with the aggregate the most likely to be affected by exogeneous shocks. Many low income developing countries hugely suffer from export price shocks which can directly be assessed through the instability of exports. Second, national income and fiscal revenues are more likely to be influenced by aid disbursements than exports. Exceptions are countries suffering from Dutch disease, which however generally occurs with some delay. Anyway if Dutch disease effects were to occur immediately and symmetrically, aid volatility would be to some extent stabilizing: aid increase, leading to a real exchange rate appreciation, would induce a slow down of exports, and conversely.

Cycles: how are they measured?

Several alternative methodologies are available to analyse the cyclical characteristics and the volatility of aid and exports. Following Bulir and Hamann (2001, 2003[START_REF] Raddatz | Are External Shocks Responsible for the Instability of Output in Low-Income Countries? World Bank Policy Research Working Paper 3680[END_REF], [START_REF] Pallage | Foreign Aid and the Business Cycle[END_REF] and [START_REF] Rand | Business Cycles in Developing Countries : Are They Different[END_REF], an H-P filter [START_REF] Hodrick | Postwar U.S. Business Cycles: An Empirical Investigation[END_REF] can be used to extract the trend and cycle components of aid and of the reference flow, here exports. The H-P filter decomposes a series, t

x , (where t x is the logarithm of the observed series t X ) in a cycle, c t x , and a trend, g t x , by minimising the following function:

( ) ( ) ( ) 2 2 1 1 g g g g g t t t t t t t t x x x x x x λ + -   - + - - -   ∑ ∑
, where λ is the smoothing parameter of g t x . The choice of the value of λ depends on the frequency of observations. On annual data, [START_REF] Pallage | Foreign Aid and the Business Cycle[END_REF] use λ equals 100, while Bulir and Hamann (2001) use λ equals 7. The study of [START_REF] Ravn | On Adjusting the Hodrick-Prescott Filter for the Frequency of Observations[END_REF] shows that on annual data, λ should be of the order of 6.25 so we follow Bulir and Hamann (2001) and choose λ equals 7. The pro or contra-cyclical character of aid is measured by the correlation between the cycle of aid and that of exports over a given time period. 2 The volatilities of aid and exports are measured by the respective standard errors of their cycles.

Another way of measuring trend and cycles, more frequently used for the analysis of export instability, is to perform an econometric estimate of the trend. This method was used by [START_REF] Lensink | Aid Instability as a Measure of Uncertainty and the Positive Impact of Aid on Growth[END_REF] to measure aid volatility. Due to the uncertainty about the deterministic or stochastic nature of this trend, it is convenient to estimate an equation of the following form:

case of the poorest and highly aid-dependent countries. In emerging economies the issue is less the procyclicality of aid than of capital flows (underlined by Kaminsky et al., 2003).

1 2 3 1 t t t x time x α α α ε - = + + + .
The predicted value, t x ) , is the trend component, while the residual, t ε , is the cycle component. As previously, contra-cyclicality is measured by the correlation of the cycles of aid and exports. The respective volatilities of aid and exports are measured by the standard errors of the residuals. The trend is here estimated on the whole period under consideration (so called global adjustment).

We shall use alternatively these two measures of volatility to check the robustness of our results. Both aid and exports are measured in absolute terms, in constant dollars (100=2000). Aid and exports data are from the World Development Indicators [START_REF] Wdi | World Development Indicators 2006[END_REF].

Is aid really pro-cyclical?

Previous studies on aid volatility conclude that more often than contra-cyclical, aid is pro-cyclical, at best not correlated with the cycles of national income or fiscal revenues (Bulir and Hamann, 2001, 2003[START_REF] Raddatz | Are External Shocks Responsible for the Instability of Output in Low-Income Countries? World Bank Policy Research Working Paper 3680[END_REF][START_REF] Pallage | Foreign Aid and the Business Cycle[END_REF]: for instance Bulir and Hamann (2001) find that aid is modestly pro-cyclical with correlation coefficients mainly concentrated on the right of zero and with only a small number of countries with contra-cyclical aid.

Referring to exports, Table 1 (with cycles measured with respect to a global adjustment) gives a slightly different picture.

Table 1 suggests that for the whole sample of developing countries, during the seventies and eighties, aid was indeed slightly more pro-cyclical than contra-cyclical with respect to export (11 or 12 significantly positive correlation and 6 significantly negative correlations). In the nineties (whatever the subset of countries) two evolutions are worth mentioning: (1) the 2 Our dataset for growth estimations is on five-year averages from 1970-74 to 1995-99. The correlations of total number of significant cases decreases; (2) the number of negative cases converges towards the number of positive cases. In subgroups of countries (Africa, Low Income Countries, Least Developed Countries), the same pattern applies, except that in the seventies the average correlation is negative. In brackets: number of cases significant at 10%.

What does make aid stabilizing or not?

Pro or contra-cyclicality is indeed an important parameter. But it is not the only relevant one to determine whether aid inflows are stabilizing or destabilizing. Pro-cyclical aid can still be stabilizing if its volatility is lower than that of exports. On the reverse there may be cases where aid is contra-cyclical and destabilizing, when its volatility is significantly higher than that of exports, in a proportion depending on the relative level of aid and exports.

Overall, the stabilizing character of aid with respect to export volatility is a function both of cycles are measured on six to eight years: five years of the sub-period and one to three years before. aid contra-cyclicality and of its relative volatility with respect to exports, as well as of the relative trend levels of aid and exports.

What is the real picture? To assess the stabilizing character of aid we build an index which is the difference between the volatility of exports and the volatility of aid plus exports:

Stabilizing character of aid = Volatility of (X) -Volatility of (X + A).

If the difference is positive, aid is considered as stabilizing; if it is negative, aid is seen as destabilizing (with regard to exports). Figure 1 represents the pro-cyclical character of aid versus its stabilizing character over 1970-1999 (volatilities are measured by the global adjustment method). We have 239 observations, corresponding to the 102 contra-cyclical versus 137 pro-cyclical cases (significant or not). Over the102 cases of contra-cyclical aid, still 20 appear to be associated with a negative stabilizing indicator, due to high aid volatility and aid levels. On the other hand, pro-cyclical aid is most often associated with a positive stabilizing indicator: over the 137 cases of pro-cyclical aid only 49 correspond to a destabilizing aid (one third), leaving a majority of seemingly "paradoxical" cases (88) where aid is both pro-cyclical and stabilizing. Thus the cases where aid appears to be stabilizing represent 71% of the observations and they correspond to an aid as often pro-cyclical (88 cases) as contra-cyclical (82 cases).

To summarize, aid volatility is a matter of concern only if it is destabilizing, which occurs in a minority of cases, more likely when it is pro-cyclical rather than contra-cyclical.

The stabilizing character of aid is also a function of the volatility and of the level of aid compared to that of the flow of reference, here exports. Although aid is pro-cyclical in a slight majority of cases (57%), most of them being statistically unsignificant, it is still likely to be stabilizing in a clearer majority of cases (71%). The stabilizing character of aid with respect to exports basically depends on three characteristics of aid, its contra/pro-cyclicality, its relative volatility and its relative trend level, all the three with respect to exports.

Broader perspective: the impact of aid on growth volatility

In order to assess the extent to which the stabilizing character of aid influences growth, we will need to focus on a major but specific source of shocks, namely exports volatility. However, developing countries are facing other kinds of shocks (in particular climatic instability) and aid may have a dampening effect also with regard to them. It is possible to aggregate several kinds of shocks in an index of vulnerability, such as the UN economic vulnerability index (EVI) (see [START_REF] Guillaumont | Macro Vulnerability in Low-Income Countries and Aid Responses[END_REF], or in an appropriate index as we have done earlier [START_REF] Patrick | Aid and Performance: A Reassessment[END_REF][START_REF] Lisa | Aid and Growth Revisited: Policy, Economic Vulnerability and Political Instability[END_REF], in order to test, through a multiplicative variable, the hypothesis of a higher aid effectiveness in more vulnerable countries. But it is more difficult to assess aid contra-cyclicality or stabilizing character with respect to several shock variables, introduced both additively and multiplicatively; and it is not very meaningful to consider the contra-cyclicality and stabilizing character of aid with respect to each of them separately. In this section, we propose a synthetic way to assess whether aid has been stabilizing or destabilizing: we examine to what extent income volatility has been influenced by the average level of aid inflow and the level of its volatility.

Traditional factors of income growth volatility

There are few papers on the determinants of growth volatility. Some are focused on policy factors [START_REF] Easterly | Shaken and Stirred: Explaining Growth Volatility[END_REF], some try to split up structural and policy factors (Combes et al., 2000), others to split up internal and external factors [START_REF] Raddatz | Are External Shocks Responsible for the Instability of Output in Low-Income Countries? World Bank Policy Research Working Paper 3680[END_REF].

Some papers rely on cross-country or panel regressions (the first two quoted above), others on time series for each country and try to measure factors explaining a conditional variance (Raddatz). None of the cross-country or panel regressions (to our knowledge) consider what has been the impact of aid. Only time-series studies try to assess the impact of aid shocks among several kinds of shocks on the forecast error of income per capita, as well as the reaction of aid to several kinds of shocks. Anyway they did not measure the impact of the aid average level and volatility on multi-year income volatility, what we now try to do.

The previous studies of the factors of aid volatility give information on what should be the appropriate control variables in any estimation of the effect of aid on income volatility, under the condition that they are not themselves affected by aid.

When aid dampens growth volatility

We estimate an equation where income volatility is a function of aid to GDP ratio and aid volatility. The level of aid is likely to have a stabilizing impact, consistently to what has been found with regard to exports volatility. Aid volatility may have a positive or a negative impact, according to its level and pro or contra-cyclicality with respect to the various kinds of shocks that affect income volatility. We control for initial income, and lagged income volatility as well as export to GDP ratio and the volatility of exports which are likely to be major factors of income volatility in developing countries. Aid and export volatilities are weighted by their levels.

, 1 , 5

X GDP X GDP Vol X ODA GDP ODA GDP Vol A α α α α α α ε - - = + + + + + +
In Table 2 are presented the results of the estimations of the income volatility equation. Lagged income volatility, initial income, aid ratio and aid volatility are instrumented. We use two estimation methods, implying different sets of instruments. First, we use the generalized method of moments. Lagged income volatility and initial income are instrumented using twice-lagged income volatility and initial income. Instruments used for aid are those of [START_REF] Tavares | Does Foreign Aid Corrupt?[END_REF] i.e. the total budget of aid of the five major donors weighted by distance variables: cultural distance (same language, same religion) and geographical distance (distance from Brussels, Tokyo and Washington). This list of instruments is supplemented with the average growth rate of the two major donors of each receiving country.

We also use the application of the GMM method proposed by [START_REF] Arellano | Some Tests of Specification for Panel Data: Monte Carlo Evidence and an Application to Employment Equations[END_REF] in which first-differenced equations are instrumented by lagged level variables. We assume that income volatility, initial income, aid and aid volatility are predetermined and instrument them using their lags from t-1 to t-3. In column ( 1) and ( 2) we measure volatility from a global adjustment, and test the robustness in column (3) using the H-P method.

All regressions support the view that export volatility is a highly significant factor of the volatility of income. When significant (regression ( 2)), the level of exports has also a positive effect on income volatility: economies more open to trade are also more prone to external shocks. The level of aid is negative, and significant in column ( 1) and (3), while aid volatility is significantly positive in all regressions. It seems that aid volatility contributes to overall income volatility whereas the level of aid tends to dampen it. The debate initiated by the influential paper of [START_REF] Burnside | Aid, Policies and Growth[END_REF][START_REF] Burnside | Aid, Policies and Growth[END_REF] has at least made clear that aid effectiveness is likely to depend on specific features of the recipient country. The feature focused on by Burnside and Dollar was the quality of economic policy and institutions. The debate on the Burnside and Dollar thesis has been mainly related to the robustness of their econometric results [START_REF] Hansen | Aid and growth regressions[END_REF] and to the consistency of their relying hypotheses. In two previous papers [START_REF] Patrick | Aid and Performance: A Reassessment[END_REF][START_REF] Lisa | Aid and Growth Revisited: Policy, Economic Vulnerability and Political Instability[END_REF] we have argued that a major factor conditioning aid effectiveness in recipient countries was the economic vulnerability they face. In vulnerable countries foreign support has a high marginal productivity in avoiding collapses when shocks occur or long standing recessions afterwards; it is expected to smooth public expenditures and to lower the risk of fiscal deficit. Consequently the marginal contribution of aid to growth of recipient countries is expected to be higher in developing countries exposed to external shocks. This effect of vulnerability on aid effectiveness was captured in a growth regression by a multiplicative explanatory variable (aid to GDP ratio x vulnerability indicator) which was significantly positive. The measure of the vulnerability variable was not the same in the two papers. Only the 2001 paper used a concept of vulnerability close to that used for LDCs identification, including (small) population size, exports instability and agricultural production instability. The 2004 paper used a narrower concept, limited to exports instability and (negative) terms of trade trend. 3,4,5 For the purpose of our present analysis we use an even narrower concept of vulnerability; that is we focus on that part of vulnerability due to external trade shocks, as captured by exports instability. We do so because we intend to analyse aid effectiveness with respect to its contra-cyclicality and to its stabilizing impact and consequently need a reference aggregate (exports) to which we can compare aid cycles.

The second step of our econometric analysis of aid effectiveness consists in estimating a baseline model of the form: ). As in the previous section, we use both GMM and Difference-GMM estimators. Lagged income and aid (as well as aid interacted with exports volatility) are instrumented. According to the estimation method, we use the two sets of instruments presented in section 3.

, 1 5 2 , 3 , 4 , , , . / . x
The first two columns of Table 3 present the estimation of the baseline model. They show that the significantly negative impact of exports volatility can be mitigated by aid, since aid interacted with the volatility of exports is significantly positive.

The export stabilizing impact of aid and growth

The last step of our analysis is to assess the impact on growth of the stabilizing character of aid. Columns (3) to (5) of Table 3 present these results. They show that when the stabilizing character of aid is introduced into the baseline model it is significantly positive, while aid interacted with exports volatility loses its significance in two out of three regressions.

Let's recall that the stabilizing impact of aid with respect to exports depends on: (i) the relative level of aid; (ii) a contra-cyclical pattern; (iii) the relative volatility compared to exports. These three components of the stabilizing character of aid can compensate or reinforce each other. In regressions (1) and (2) only the stabilizing impact of the level of aid was captured through the multiplicative term. In regressions (3) to (5) all three components are captured through the indicator of "stabilizing character". This indicator seems in regressions ( 4) and ( 5) to capture all the dampening effect of aid. Regression (3) suggests that there may be a stabilizing impact of the level aid, distinct from the overall stabilizing impact which is also determined by the time profile of aid (contra-cyclicality and relative volatility).

Conclusion

Somewhat diverging from the current concern about aid volatility, this paper argues that aid has a stabilizing impact first with respect to exports volatility, second and more generally as a dampening factor of income volatility. Aid volatility may lower and possibly cancel this effect when it is pro-cyclical with regard to exogeneous shocks, and even, but more hardly, when it is contra-cyclical and very high compared to other sources of shocks.

Even if it is pro-cyclical aid is stabilizing with respect to exports, if its volatility is lower than that of exports. And when it is contra-cyclical, it is stabilizing only as far as its volatility does not exceed a certain threshold.

It has not indeed been possible in this paper to examine how aid can contribute to the average long term growth by mitigating the negative impact of the growth volatility evidenced in the literature [START_REF] Ramey | Cross Country Evidence on the Link Between Volatility and Growth[END_REF][START_REF] Hnatkovska | Volatility and Growth[END_REF][START_REF] Guillaumont | Macro Vulnerability in Low-Income Countries and Aid Responses[END_REF]. Testing this effect would imply to move from a medium term (adopted in this paper) to a long term framework.

Figure 1 -

 1 Figure 1 -Pro-cyclical versus stabilizing aid, 1970-1999, ten-year averages.

Table 1

 1

	-Is aid pro or contra-cyclical?
			1970-79 1980-89 1990-99
	Developing Countries Average	0.015	0.110	0.015
		Number of positive correlation	39 [12] 52 [11] 46 [5]
		Number of negative correlation 31 [6] 27 [6] 44 [5]
	Sub-Saharan Africa	Average	-0.031	0.234	0.061
		Number of positive correlation	16 [8] 26 [9] 21 [2]
		Number of negative correlation 15 [3] 7 [1] 18 [2]
	LICs	Average	-0.020	0.189	0.025
		Number of positive correlation	19 [7] 29 [6] 23 [3]
		Number of negative correlation 17 [3] 8 [1] 21 [3]
	LDCs	Average	-0.006	0.209	0.023
		Number of positive correlation	14 [6] 21 [5] 17 [2]
		Number of negative correlation 11 [2] 5 [1] 17 [2]

  .

	i t Volatility of y	i t Volatility of y	y	i t			i t	i t	i t
		/	i t		/	i t	x .	i t	i t

Table 2 -

 2 Income volatility estimation, 5-year averages, 1970Income volatility estimation, 5-year averages, -1999. .

	Volatility from global adjustment	HP
	GMM	DIFF-GMM	GMM
	(1)	(2)	(3)

  /

	i t y	=	α	t y	-	+	α	Exports volatility	i t	+	α	i t ODA GDP	+	α	i t Exports volatility ODA GDP i t	+	ε	i t
	where y i,t is the logarithm of real income per capita (PWT 6.1) of country i ( 1... i =	N	) in
	period t ( 1... t T =

Table 3 -

 3 Growth equations, 5-year averages, 1970Growth equations, 5-year averages, -1999. .

			Instability from global adjustment	HP
		GMM	DIFF-GMM	GMM	DIFF-GMM	GMM
		(1)	(2)	(3)	(4)	(5)
	Ln income p.c, t-5	0.942	0.690	0.985	0.611	0.947
		(42.90)*** (10.16)***	(34.32)*** (7.40)***	(41.84)***
	Volatility of X	-0.003	-0.0001	-0.020	-0.0063	-1.575
		(2.59)**	(1.11)	(3.25)*** (1.75)*	(2.56)**
	Aid / GDP	-2.382	-0.521	-1.587	-0.262	-1.527
		(4.15)***	(2.16)**	(2.35)**	(1.15)	(3.37)***
	Volatility of X x Aid / GDP 0.085	0.011	0.088	0.010	3.472
		(2.75)***	(1.85)*	(2.79)*** (1.12)	(0.79)
	Stabilizing character of aid			0.019	0.006	3.147
				(2.83)*** (1.76)*	(1.67)*
	Constant	0.659		0.527		0.556
		(3.53)***		(2.51)**		(2.69)***
	Observations	445	389	445	389	291
	Number of countries	91	94	91	94	72
	R-squared	0.96		0.95		0.96
	Hansen p-value	0.21	0.17	0.99	0.24	0.45
	Anderson p-value	0.00		0.14		0.00
	AR (1) p-value		0.01		0.00
	AR (2) p-value		0.32		0.32
	Instruments		47		54
	All regressions include time dummies. Robust t statistics in parentheses; * significant at 10%; ** significant at
	5%; *** significant at 1%

Here we consider as a reference flow exports of goods and services, but not international capital flows, the volatility of which may exacerbate the consequences of trade shocks in middle income countries, as studied in the case of Chile (Cabalerro,

2002): extending the reference flow to capital movements seems less relevant in the

Were also taken into account the impact on aid effectiveness of : (i) political instability (negative effect), (ii) present economic policy (positive effect) ; and (iii) previous economic policy (negative effect, due to the possible effect of aid on policy improvement from a "bad" initial situation).

Another paper by[START_REF] Collier | Ouverture sur l'extérieur et instabilité des taux de croissance[END_REF] also evidenced the role of aid as a factor mitigating export price shocks considered on a year by year basis, defined from a forecasting model, and retained only if they were on the tail of the distribution; although this model did not allow to measure the long term effect of instability on growth, it made a useful distinction between the effect of a change of aid, found to lower the negative effect of a negative shock, and the effect of aid level itself, found to increase the positive effect of a positive shock.

A good survey of these papers is given by[START_REF] Mcgillivray | Aid Effectiveness and Selectivity: Integrating Multiple Objectives into Aid Allocations[END_REF]. Moreover,[START_REF] Roodman | The Anarchy of Numbers : Aid, Development, and Cross-country Empirics, Center for Global Development[END_REF] presents a thorough assessment of the econometric robustness of various papers, confirming the relative robustness of our 2001 results (the 2004 paper is not analyzed). These are found to be more robust than those by Collier and Dehn, themselves more robust (for the effect of aid change) than those of Burnside and Dollar, but less robust than the results of Hansen and Tarp, who do not address the vulnerability issue.


Zeina Azmeh
email: azmeh@lirmm.fr

Marianne Huchard
email: huchard@lirmm.fr

Nizar Messai
email: messai@loria.fr

Chouki Tibermacine
email: tibermacin@lirmm.fr

Christelle Urtado
email: christelle.urtado@mines-ales.fr

Sylvain Vauttier
email: sylvain.vauttier@mines-ales.fr

Many-Valued Concept Lattices for Backing Composite Web Services

A Web service is a software functionality accessible through the network. Web services are intended to be composed to realize domainspecific applications. Achieving a required functionality by a service composition necessitates the discovery of a collection of Web services out of the enormous service space. Each service from this service space must be examined to verify its functionality, which makes the discovery task neither efficient nor practical. Moreover, when a service in a composition becomes unavailable or functionally broken, the whole composition may become broken too. Therefore, a functionally equivalent service must be discovered, in order to replace the broken service, thus spending more time and effort. In this paper, we propose an approach that facilitates the discovery of a web service and the identification of its candidate substitutes. We use many-valued concept lattices to classify web services, depending on the similarity estimated between their operations. This classification enables the identification of a needed web service as well as its possible alternatives. Thus, a Web service composition can be achieved more easily and can be supported with backup services, to recover the functionality of a broken service.

Introduction

A Web service is a software functionality accessible through the network. It exposes its functionality to the external world by an abstract interface expressed by Web Service Description Language, WSDL 4 . A WSDL interface is a uniform mechanism for describing a service's available operations, parameters, data types, and access protocols.

According to the functionalities described by the WSDL interfaces, web services can be assembled to serve a particular function, solve a specific problem, or deliver a particular solution. They represent the building blocks for creating composite applications. When creating a composite application, each selected web service must fulfil a part of the application's functionality. Therefore, each service's WSDL must be analyzed to verify its provided operations, and so to decide whether to select the service or not. Due to the big number of web services that exist on the web nowadays, the task of finding an appropriate service to use becomes hard and time-consuming. After identifying the needed services, they can be assembled together in order to form the functionality of the aimed composite application. This application will be functional as long as each of its composing services is functional, but once one of its services breaks, the part of the application represented by this service will break too, causing a total or partial dysfunctionality to the application. The obvious solution in this case, will be to search for another web service to replace the broken one and recover the missing functionality. Thus, the task of finding an appropriate web service to use has to be repeated every time a service breaks and has to be replaced by an equivalent one.

In this paper, we propose an approach for web service browsing, in order to facilitate the discovery of a web service and the identification of its candidate backups. We use the formal concept analysis (FCA), a mathematical formalism that permits the identification of groups of objects having common attributes. We adopted FCA in a number of our previous work [START_REF] Arévalo | Fca-based service classification to dynamically build efficient software component directories[END_REF][START_REF] Arévalo | Precalculating component interface compatibility using fca[END_REF]. Using FCA, we construct web service lattices according to their functionality domain, depending on the similarity estimated between their operations.

Our generated service lattices represent a browsing mechanism that facilitates the discovery of a needed service, along with a set of possible backup services.

The rest of the paper is organized as follows: Section 2 defines the problem statement. In Section 3, we give a quick overview about formal concept analysis with its basic definitions. In Section 4, we explain our approach along with examples and formal definitions. In Section 5, we demonstrate a case study to explain the use of our approach. In Section 6, we list and discuss the related work. Finally, in Section 7, we conclude our paper and briefly give some of our perspectives.

Problem Statement

Web services face several challenging issues coming from several factors. Since, they are offered by various providers, remotely accessed, and sometimes provided for free, there is no guarantee of a continuous execution. An available functioning web service may crash and become unavailable at any time, which necessitates finding an equivalent one to replace it. Unfortunately, this can be hard to achieve since there is a lack of WSDL organizing facilities, especially after the deficiency of the UDDI5 registries: "UDDI did not achieve its goal of becoming the registry for all Web Services metadata and did not become useful in a majority of Web Services interactions over the Web" [START_REF] Newcomer | Understanding SOA with Web Services (Independent Technology Guides)[END_REF].

Thus, a mechanism for finding service backups becomes indispensable, especially when a service represents a part of a composite application.

Let's take the two following services: a currency converter service and a calculation service. The currency converter service offers an operation that returns the exchange rate between two entered currencies. The calculation service offers several operations for calculation, one of them return the multiplication of two entered numbers. We will link the exchange rate operation with the multiplication operation in order to build a composite service of the two mentioned service, we will call it the composite currency service. This new composite service will give us a converted amount from a currency to another. Fig. 1 shows us an overview of this composite service. In the composition of Fig. 1, if the service Calc crashes, for example, a service offering a multiplication operation equivalent to mul() must be searched and discovered. Thus to recover the missing functionality, and ensure the continuity of the composition.

In the following sections, we illustrate some background definitions about FCA in order to describe the classification of Web services into concept lattices.

FCA Overview

In our approach, we use the FCA formalism in order to construct a classification of web services. FCA is a mathematical theory that permits the identification of groups of objects having common attributes [START_REF] Ganter | Formal Concept Analysis[END_REF]. FCA takes as input a given data set represented as a formal context and produces the set of all the formal concepts which form a concept lattice. A formal context is denoted by K = (G, M, I) where G is a set of objects, M is a set of attributes, and I is a binary relation between G and M (I ⊆ G × M ). (g, m) ∈ I denotes the fact that object g ∈ G is in relation through I with attribute m ∈ M (also read as g has m). We adapt the FCA for web services, by considering that the set of objects represent web services and the set of attributes represent operations. In this way, a formal context of web services and operations becomes K = (W, O, I), where:

W = {ws i | 1 ≤ i ≤ |W| ∧ |W| > 1}
is the set of web services, we suppose that it must contain more than one web service. Each service offers a set of one or more operations, and the union of all of the sets of operations offered by the services forms the total set of operations:

ws i = {op ij | 1 ≤ i ≤ |W| ∧ 1 ≤ j ≤ |ws i |} O = i≤|W| i≥1
ws i (ws, op) ∈ I denotes the fact that the service ws ∈ W provides the operation op ∈ O (also read as ws has op). Table 1 shows an example of a formal context (W, O, I) where W = {ws 1 , ws 2 , ws3} and O = {op 1 , op 2 , op 3 , op 4 , op 5 }.

Table 1. A formal context for W × O. op1 op2 op3 op4 op5 ws1 × × × ws2 × × × ws3 × × × × Having a set of web services X ⊆ W, X = {op ∈ O | ∀ ws ∈ X : (ws, op) ∈ I}
is the set of common operations. In the same way, having the set of operations

Y ⊆ O, Y = {ws ∈ W | ∀ op ∈ Y : (ws, op) ∈ I}
is the set of common web services. In our example, ({ws 1 , ws 3 }) = {op 1 , op 2 , op 4 } and ({op 3 }) = {ws 2 , ws 3 }.

A concept is a pair of sets (X, Y ) where X ⊆ W is called the extent, Y ⊆ O is called the intent, and Y = (X) , X = (Y ) . Meaning that, a concept is a maximal collection of services offering similar operations. The set of all concepts is denoted by B(W, O, I).

In our example, ({ws 1 , ws 3 }, {op 1 , op 2 , op 4 }) is a concept while ({op 3 }, {ws 2 , ws 3 }) is not. In fact, while ({op

3 }) = {ws 2 , ws 3 }, ({ws 2 , ws 3 }) = {op 2 , op 3 }. A con- cept (X1, Y 1) is a subconcept of a concept (X2, Y 2) if X1 ⊆ X2, which imposes a partial order relation on B(W, O, I) expressed as (X1, Y 1) ≤ (X2, Y 2).
The partial order relation ≤ can be used to build a structure, which is called a concept lattice. A concept lattice defines a hierarchical representation of services and operations, in which a certain concept inherits all the extents (services) of its descendants and all the intents (operations) of its ascendants. Fig. 2 illustrates the lattice built for the context shown in table 1, we notice that upper labels are the reduced intent sets (operations) and bottom labels are the reduced extent sets (services). In this lattice we can reveal the relationships between the present services, some of them are the following:

-ws 1 , ws 2 and ws 3 offer the operation {op 2 }, thus, they can replace each other for this operation -ws 1 and ws 3 offer the operations {op 1 , op 2 , op 4 } -ws 3 can replace ws 1 since it offers all of its operations in addition to op 3 -ws 2 and ws 3 offer together the operations {op 2 , op 3 } -ws 2 can replace ws 1 for the operation op 2

Classifying Web Services into Concept Lattices

In this section, we explain our approach using some basic formal definitions, along with an illustrative example. For clarity sake, we illustrate our approach using an imaginary set of Web services for performing calculations. Each service from this set is parsed by a WSDL parser to extract its signatures. The set of services with their signatures are given unique identifiers, as listed in table 2.

Next, a similarity measure must be chosen, and the operations signatures extracted from the WSDL files will be used by this similarity measure, according to its input format. Several similarity measures for web services exist in the Table 2. A set of calculation services with their operations. literature. They evaluate the similarity according to the syntactic and semantic levels, such like [START_REF] Dong | Similarity search for web services[END_REF][START_REF] Stroulia | Structural and semantic matching for assessing webservice similarity[END_REF][START_REF] Kokash | A comparison of web service interface similarity measures[END_REF]. The similarity measure is applied on pairs of operations provided by different services. We do not consider the similarity between operations provided by the same service, because when a service becomes dysfunctional, all of its operations become dysfunctional too. The similarity is assessed in the form of values in the range [0,1]. If two operations are sufficiently similar, the similarity value will approach 1, or else it will approach 0. A similarity measure (Sim) can be defined as follows:

Services Id Operations Id

Sim : O × O → [0, 1] ∀ op ij ∈ O =⇒ Sim(op ij , op ij ) = 1 (an operation with itself) ∀ op ij , op ik ∈ O =⇒ Sim(op ij , op ik ) = 0 (operations in the same service) ∀ op ij , op nm ∈ O =⇒ Sim(op ij , op nm ) ∈ [0, 1]
(operations in different services)

The calculated similarity values can be presented by a symmetric square matrix that we will call SimM at, as shown in table 3 6 . This matrix is of size n = |O|, and its diagonal elements are all equal to 1, since we consider that the similarity of an operation with itself is equal to 1 as declared above.

From the similarity matrix SimM at, we can extract several binary contexts, by specifying threshold values θ ∈]0, 1]. Thus, the values of SimM at that are greater or equal to the chosen threshold θ are scaled to 1, while other values are scaled to 0. The binary context that corresponds to θ = 0.75 is shown in table 4, we call it SimCxt.

The SimCxt context is a triple (O, O, RSim θ ), where RSim θ is a binary relation indicating whether an operation is similar to another operation or not.

(op ij , op nm ) ∈ RSim θ ⇐⇒ Sim(op ij , op nm ) ≥ θ
We use the SimCxt context to generate a lattice of operations, B(O, O, RSim θ ). This lattice helps in discovering groups of similar operations, which are used

op11 op12 op21 op31 op32 op33 op34 op11 x x x op12 x x op21 x x x x op31 x x op32 x x op33 x op34 x x x
later on to construct the services lattice.

In the resulting operation lattice, groups of mutually similar operations can be identified by the concepts having equal extent and intent sets. We call such concepts as square concepts, because they form square gatherings on the binary context matrix. We define a group G op of mutually similar operations Op Sim as:

G op = {Op Sim | (Op Sim , Op Sim ) ∈ B(O, O, RSim θ )}
The notion of square concepts can be better recognized by performing a mutual column-line interchange in the SimCxt, the resulting interchanged context is shown in table 5.

Table 5. The interchanged (SimCxt) context.

op11 op34 op21 op31 op12 op32 op33 op11 x x x op34 x x x op21 x x x x op31 x x op12 x x op32 x x op33
x

From the lattice in Fig. 3 as from the interchanged context in table 5, we can identify the groups of similar operations, and they are the following:

-{op 11 , op 34 , op 21 } -{op 21 , op 31 } -{op 12 , op 32 } -{op 33 } Fig. 3. The generated lattice for (SimCxt) shown in table 4.

The groups of similar operations, denoted as G, are used to define the final binary context. This context is a triple (W, G, R), in which the relation R indicates whether or not a service offers the functionality represented by the corresponding group of similar operations.

We will represent each group of operations by an identifier that corresponds to the indices of the operations. The new context is shown in table 6: From the

Lattice interpretation

From the final generated lattice, shown in Fig. 4, we can notice the following:

-ws 1 , ws 2 , and ws 3 offer the functionality denoted by [START_REF] Ganter | Formal Concept Analysis[END_REF]34,[START_REF] Stroulia | Structural and semantic matching for assessing webservice similarity[END_REF], so they can replace each other for this specific functionality -ws 3 can replace ws 1 and ws 2 , and it offers an additional functionality (33)

We can also infer immediately which services offer a specific functionality (denoted by a specific label), by regarding the indices in the label.

Case Study

In this section, we demonstrate the use of the service lattices for the construction of composite web services and supporting them with backup services. We return to the example of the composite currency service, described in Section 2. We use BPEL 7 to orchestrate the two services by their operations, as shown in Fig. 1. We use many-valued contexts of similarity values as explained previously, in order to build two service lattices, a lattice for currency exchange services, and a lattice for calculation services. We retrieved a set of services8 for currency conversion as shown in table 7 and for calculations as shown in table 8. We limit the number of services in this example, in order to simplify it and clearly explain the idea of lattice use.

We choose manually a value for similarity threshold in order to get a binary context. Then we obtain two lattices corresponding to each set of services. The two lattices are shown in the right side of Fig. 5. We can use the service lattices to build our composite service as well as to support it with backup services. We select operation op 11 (CR:11) from the service s1 for exchange rate (currency lattice), and operation op 13 (mul:13) from service s1 for multiplication (calculation lattice). From the lattices in Fig. 5, we can extract some backup services for our composite service. For example, we used operation op 11 from service s1, this operation has 3 equivalents: op 21 , op 31 and op 51 appearing clearly in the lattice. This means that if service s1 breaks down, we can replace it by the services s2, s3 or s5. Moreover, if we go down in the lattice, we get the set of services that cover the used operations and offer other operations, like service s5 and service s3. In the same way, we can extract the backup services for the calculation service s1 that we are using. According to the calculation services lattice, the service s1 as a whole set of operations cannot be replaced by any service. But, regarding the multiplication functionality, op 13 (mul:13), it can be replaced by the operations op 33 , op 43 , op 52 , op 63 , which are offered by the services s3, s4, s5, s6 respectively.

The service lattices present the table of services in an organized way, which reveals the relations between the services. We can verify the correctness of the lattice by verifying the data in the table. The chosen threshold value determines the necessity of human intervention, when it is small, the precision becomes lesser, then a service's substitutes may need few adaptations in order to replace a service. For example, while doing our experiments, we had an operation for rate exchange that takes an additional date parameter. For a specific threshold value, lesser than 1, we got this operation grouped with the other operations, which do not have a date parameter. We need to do a little adaptation, in order to use this operation, which can be putting a default value like today's date.

Multiply(A,B) op52
OperationAdd(A,B) op53
Subtract(A,B) op54 Calculate ws6 Add(dbl1,dbl2) op61 Divide(dbl1,dbl2) op62 Multiply(dbl1,dbl2) op63
Subtract(dbl1,dbl2) op64

Related Work

Several works have been proposed for web service classification, in order to facilitate browsing, discovery and selection. A quick overview of some of the works can be obtained from [START_REF] Brockmans | Service-finder deliverable d4.1. research report about current state of the art of matchmaking algorithms[END_REF][START_REF] Lausen | Survey of current means to discover web services[END_REF]. Below, we describe a selection of works, classified according to their adapted techniques.

Using formal concept analysis (FCA)

In [START_REF] Aversano | Using concept lattices to support service selection[END_REF], Aversano et al. classify web services using FCA as a means for WSDL browsing. Their formal contexts are composed according to three levels, service level, operation level and type level, together with keywords. These keywords are identified from the WSDL files by applying vector space metrics with the help of WordNet to discover the synonyms. The resulting service lattice represents an indexing of web services, it highlights the relationships between the services and permits the identification of different categorizations of a certain service. In [START_REF] Bruno | An approach to support web service classification and annotation[END_REF], Bruno et al. also use keywords extracted from services' interfaces together with FCA to build a web services lattice. They analyze the extracted words, process them using WordNet and other IR techniques. Then, they classify them into vectors using support vector machines (SVM). The obtained vectors categorize the services into domains, then service lattices can be obtained for each category using FCA.

In Peng et al. [START_REF] Peng | Concept-based retrieval of alternate web services[END_REF], similarity values are calculated for service operations, and depending on a chosen threshold, a service lattice is built.

Using machine learning

Many approaches adapt techniques from machine learning field, in order to discover and group similar services. In [START_REF] Crasso | Awsc: An approach to web service classification based on machine learning techniques[END_REF][START_REF] Heßand | Learning to attach semantic metadata to web services[END_REF], service classifiers are defined depending on sets of previously categorized services. Then the resulting classifiers are used to deduce the relevant categories for new given services. In case there were no predefined categories, unsupervised clustering is used. In [START_REF] Ma | Efficiently finding web services using a clustering semantic approach[END_REF], CPLSA approach is defined that reduces a services set then clusters it into semantically related groups.

Using service matching

In [START_REF] Lu | Web service search: Who, when, what, and how[END_REF], a web service broker is designed relying on approximate signature matching using XML schema matching. It can recommend services to programmers in order to compose them. In [START_REF] Günay | Structural and semantic similarity metrics for web service matchmaking[END_REF], a service request and a service are represented as two finite state machines then they are compared using various heuristics to find structural similarities between them. In [START_REF] Dong | Similarity search for web services[END_REF], the Woogle web service search engine is presented, which takes the needed operation as input and searches for all the services that include an operation similar to the requested one. In [START_REF] Bouillet | A folksonomy-based model of web services for discovery and automatic composition[END_REF], tags coming from folksonomies are used to discover and compose services.

Using vector space model techniques

The vector space model is used for service retrieval in several existing works as in [START_REF] Platzer | A vector space search engine for web services[END_REF][START_REF] Wang | Semantic structure matching for assessing web service similarity[END_REF][START_REF] Crasso | Query by example for web services[END_REF]. Terms are extracted from every WSDL file and the vectors are built for each service. A query vector is also built, and similarity is calculated between the service vectors and the query vector. This model is sometimes enhanced by using WordNet, structure matching algorithms to ameliorate the similarity scores as in [START_REF] Wang | Semantic structure matching for assessing web service similarity[END_REF], or by partitioning the space into subspaces to reduce the searching space as in [START_REF] Crasso | Query by example for web services[END_REF].

Discussion on the related work

In FCA approaches based on keywords, similar operations can't be determined and thus, web service substitutes can't be identified either. In our approach, we use the lattice based on keywords as a preliminary index together with operation similarity measuring, in order to generate our concept lattices. We have proposed several uses of the generated lattices, as for service discovery, selection and supporting service compositions with backup services. One of our main contributions is the idea of supporting the continuity of service compositions.

A service lattice is an organization of services that reveals the relations between them according to the operations provided in common. It offers a structure of navigation that enables better discovery and browsing than in structures such as lists and sets in other approaches (described in subsections 6.2, 6.3 and 6.4). New services can be classified in existing lattices by incremental algorithms for lattice generation. Thus, there is no need to regenerate the whole lattice, if a new service is to be added. A query represents a new concept in the lattice, and the services that offer the minimum required functionality represent the concepts that are closest to the query concept, while further situated services offer extra functionalities. In the lattice, when selecting a service, a sub-lattice that is descendant from this service can be extracted. This sub-lattice contains the possible backups that can replace this service to ensure a recovered functionality.

Conclusion

In this paper, we proposed an approach based on formal concept analysis (FCA) for building web service lattices according to functionality domains. We make use of similarity measures for web services to form our formal contexts in order to build the lattices according to threshold values. A web service lattice reveals the invisible relations between web services in a certain domain, showing the services that are able to replace other ones. Thus, facilitating service browsing, selecting and identifying possible substitutions. We explained how to exploit the resulting lattices to build orchestrations of web services and supporting them with backup services.

The quality of our generated lattices depends on the chosen similarity measure and the similarity threshold. The more accurate the measure is, the more precise the obtained lattice is. The chosen values of threshold will give us a variation of lattices, and they reflect the level of the required adaptations. Thus, a high value of threshold means similar services with a low number of required adaptations.

Our work in progress is to enrich the service lattices with quality of service (QoS) aspects, in order to enable an automatic selection of a service that respond to a requested level of QoS. We are also working on the dynamic substitution of a web service by one of its backups, to ensure a continuous functionality of a service orchestration.

Fig. 1 .

 1 Fig. 1. The composite currency service.

Fig. 2 .

 2 Fig. 2. The service lattice for the context in table1.

  Calculator1 ws1 add(a,b) op11 sub(a,b) op12 Calculator2 ws2 add(a,b,c) op21 Calculator3 ws3 add(a,b,c,d) op31 sub(a,b,c) op32 mult(a,b) op33 add(a,b,c) op34

Fig. 4 .

 4 Fig. 4. The final service lattice with possible backups.

  CalculatorService ws4 add(y,x) op41 divide(denominator,numerator) op42 multiply(y,x) op43 subtract(y,x) op44 CalcService ws5 Divide(A,B) op51

Fig. 5 .

 5 Fig. 5. The composite currency service, supported by backups from the service lattices.

Table 3 .

 3 The similarity matrix (SimM at).

Table 4 .

 4 The binary context (SimCxt) for θ = 0.75.

Table 6 .

 6 The final services × groups context.

		(11,34,21) (21,31) (12,32) (33)
	ws1	x		x
	ws2	x	x
	ws3	x	x	x	x
	final binary context, we can generate the corresponding service lattice, which is
	shown in Fig 4.

Table 7 .

 7 The set of currency converter services.

	Services	Id	Operations	Id
	CurrencyConverter	ws1	GetConversionRate(fromCurrency,toCurrency)	op11
	CurrencyConvertor	ws2	ConversionRate(FromCurrency,ToCurrency)	op21
	DOTSCurrencyExchange ws3	GetExchangeRate(ConvertFromCurrency,ConvertToCurrency)	op31
			ConvertCurrency(Amount,ConvertFromCurrency,ConvertToCurrency) op32
			GetCountryCurrency(Country)	op33
	CurrencyRates	ws4	GetRate(CurrencyCode)	op41
			GetConversion(FromCurrencyCode,ToCurrencyCode)	op42
	RadixxFlights	ws5	GetExchange(FromCurrency,ToCurrency)	op51
			ConvertCurrency(Amount,FromCurrency,ToCurrency)	op52
	rates	ws6	Convert(CurrencyFrom,CurrencyTo,ValueFrom)	op61
	Conversion	ws7	CelciusToFahrenheit(fCelsius)	op71
			FahrenheitToCelcius(fFahrenheit)	op72
			Currency(fValue,sFrom,sTo)	op73
	CurConvert	ws8	GetCurrencySign(CountryName)	op81
			ConvertCurrency(FromCountry,ToCountry,Amount)	op82
	ConverterService	ws9	Convert(sourceCurrency,targetCurrency,value)	op91

Table 8 .

 8 The set of calculation services.

http://www.w3.org/TR/wsdl

http://www.uddi.org/pubs/uddi v3.htm

We can calculate the similarity values using any Web services similarity measure.Here we used a string distance measuring method, since similarity measuring is not the main objective of this paper

http://docs.oasis-open.org/wsbpel/2.0/wsbpel-v2.0.html

The services are obtained from the Seekda web service search engine, http://www.seekda.com