P Legrand

J Lévy Véhel

LOCAL REGULARITY-BASED IMAGE DENOISING

We present an approach for image denoising based on the analysis of the local Hölder regularity. The method takes the point of view that denoising may be performed by increasing the Hölder regularity at each point. Under the assumption that the noise is additive and white, we show that our procedure is asymptotically minimax, provided the original signal belongs to a ball in some Besov space. Such a scheme is well adapted to the case where the image to be recovered is itself very irregular, e.g. nowhere differentiable with rapidly varying local regularity. The method is implemented through a wavelet analysis. We show an application to SAR image denoising where this technique yields good results compared to other algorithms.

INTRODUCTION

A large of number of techniques have been proposed for image denoising. The basic frame is as follows. One observes a image Y which is some combination F (X, B) of the signal of interest X and a "noise" B. Making various assumptions on the noise, the structure of X and the function F , one then tries to derive a method to obtain an estimate X of the original image which is optimal in some sense. Most commonly, B is assumed to be independent of X, and, in the simplest case, is taken to be white, Gaussian and centered. F usually amounts to convoluting X with a low pass filter and adding noise. Assumptions on X are almost always related to its regularity, e.g. X is supposed to be piecewise C n for some n ≥ 1. Techniques proposed in this setting resort to two domains: functional analysis and statistical theory. In particular, wavelet based approaches, developed in the last ten years, may be considered from both points of view [START_REF] Devore | Fast wavelet techniques for near optimal image processing[END_REF][START_REF] Donoho | De-noising by soft-thresholding[END_REF].

Our approach in this work is different from previous ones in several respects. First, we do not require that X belongs to a given global smoothness class but rather concentrate on its local regularity. More precisely, we view denoising as equivalent to increasing the Hölder function α Y (see section 2 for definitions) of the observations. Indeed, it is generally true that the local regularity of the noisy observations is smaller than the one of the original image, so that in any case, α X should be greater than αY . If the Hölder function of X happens to be known, it may serve as a target for the algorithm. If this is not the case, it can be estimated from Y provided sufficient information on F and B is available (e.g. independent additive noise of known law). More generally, the largest α X , the more regular the estimate will be, and the smoother it will look. We thus define our estimate X to be the image which minimizes the risk under the constraint that it has the desired Hölder function. Note that since the Hölder exponent is a local notion, this procedure is naturally adapted for images which have sudden changes in regularity, like discontinuities. In addition, this scheme is appropriate when one tries to process images for which it is important that the right regularity structure be recovered. An example of this situation is when denoising is to be followed by image segmentation based on textural information: Suppose we wish to differentiate highly textured zones (appearing for instance in MR or radar imaging) in a noisy image. Applying an denoising technique which assumes that the original image is, say, piecewise C 1 , will induce a loss of the information which is precisely the one needed for segmentation: The denoised image will not contain much texture, and cannot be used for segmentation. Our denoising technique is thus well suited to the case where the original signal X displays the following features:

• X is everywhere irregular.

• The regularity of X (as measured by its Hölder function) varies rapidly in space • The local regularity of X bears essential information for subsequent processing.

The remaining of this paper is organized as follows. Section 2 recalls some basic facts about Hölder regularity analysis, which is the basis of our approach. The denoising method is explained in section 3. Section 4 gives some theoretical results. Numerical experiments are displayed in section 5.

H ÖLDER REGULARITY ANALYSIS

A popular way of evaluating the regularity of an image is to consider a family of nested functional spaces, and to determine the ones it actually belongs to. A usual choice is to consider Hölder spaces, either in their local or pointwise version. To simplify notations, we deal with 1D signals, and we assume that our signals are nowhere differentiable. Generalization to differentiable signals simply requires to introduce polynomials in the definitions [START_REF] Meyer | Wavelets, Vibrations and Scalings[END_REF].

Definition 1 Pointwise Hölder exponent

Let α ∈ (0, 1), and

x 0 ∈ K ⊂ R. A function f : K → R is in C α x 0 if for all x in a neighbourhood of x0, |f (x) -f (x0)| ≤ c|x -x0| α (1)
where c is a constant. The pointwise Hölder exponent of f at x 0 , denoted α p f (x 0 ), is the supremum of the α for which (1) holds.

Let us now introduce the local Hölder exponent: Let α ∈ (0, 1), Ω ⊂ R. One says that f ∈ C α l (Ω) if:

∃ C : ∀x, y ∈ Ω : |f (x) -f (y)| |x -y| α ≤ C Let: α l (f, x 0 , ρ) = sup {α : f ∈ C α l (B (x 0 , ρ))} α l (f, x 0 , ρ) is non increasing as a function of ρ.
We are now in position to give the definition of the local Hölder exponent :

Definition 2 Let f be a continuous function. The local Hölder exponent of f at x 0 is the real number:

α l f (x 0 ) = lim ρ→0 α l (f, x 0 , ρ)
Since α p and α l are defined at each point, we may associate to f two functions x → α p f (x) and x → α l f (x) which are two different ways of measuring the evolution of its regularity.

These regularity characterizations are widely used in fractal analysis because they have direct interpretations both mathematically and in applications. It has been shown for instance that α p indeed corresponds to the auditive perception of smoothness for voice signals. Similarly, computing the Hölder exponents at each point of an image gives a good idea of its structure, as for instance its edges [START_REF] Véhel | Fractal Approaches in Signal Processing[END_REF]. More generally, in many applications, it is desirable to model, synthesize or process signals which are highly irregular, and for which the relevant information lies in the singularities more than in the amplitude. In such cases, the study of the Hölder functions is of obvious interest.

In [START_REF] Véhel | Multifractal Image Denoising[END_REF], a theoretical approach for signal denoising based on the use of the pointwise Hölder exponent and the associated multifractal spectrum was investigated. The work in [START_REF] Véhel | Signal enhancement based on Hölder regularity analysis[END_REF] proposes an approach similar to the one we explain below, but in a functional frame. We shall develop here a practical denoising technique in a statistical setting. More precisely, we will assume a definite model for the noise and its interaction with the image, and we shall derive the denoising procedure in a minimax frame.

IMAGE DENOISING

Let X denote the original image and Y the degraded observations. Our model supposes that Y = X + B with B a centered white Gaussian noise independent of X. The precise marginal law of B is however not important, and the computations below could be adapted with minor modifications to non-Gaussian cases. We seek a denoised version X of Y that meets the following constraints:

1. the risk E( X -X 2 ) is "small", 2. the Hölder function of X is prescribed.

If α X is known, we choose α X = α X . In some situations, α X is not known but can be estimated from Y (see [START_REF] Legrand | Statistical denoising of irregular signals[END_REF]). Otherwise, we just set α X = αY + δ, where δ is a user-defined positive function, so that the regularity of X will be everywhere larger than the one of the observations. Two problems must be solved in order to obtain X. First, we need a procedure that computes the Hölder function of a signal from discrete observations. Second, we need to be able to manipulate the data so as to impose a specific regularity.

Both these aims may be reached through a wavelet analysis. Indeed, under some assumptions, one may estimate and control the Hölder regularity via wavelet coefficients. More precisely, let {ψ j,k } j,k be an orthonormal wavelet basis, where as usual j denotes scale and k position, and assumes that ψ is regular enough and has sufficiently many vanishing moments. For ease of notation, we shall explain the method in one dimension (generalization to images is straightforward). Let X n = (x n 1 , . . . x n 2 n ) denote a regular sampling over the 2 n points (t n 1 , . . . t n 2 n ) of the original signal. Let (c j,k ) denote the wavelet coefficients of X, (d j,k ) denote the coefficients of Y , and (ĉ j,k ) denote the coefficients of X. From our noise model, and since we use orthonormal wavelets, we have:

d j,k = c j,k + σ √ 2 n z j,k
, where σ is the standard deviation of the noise B and z j,k are iid Gaussian variables with unit variance.

For p = 1 . . . 2 n , we consider the point i = t n p and the wavelet coefficients which are located "above" it, i.e. d j,k(j,i) with k(j, i) = (i -1)/(2 n+1-j ) + 1. In general, estimating the Hölder exponents at a given i from the wavelet coefficients is not an easy task, because one needs to take into account all the coefficients in a neighbourhood of i. In this work, we shall assume that our signals verify α l (i) = α p (i) at all i. The implications of such an assumption are discussed in [?]. One then has:

α l (i) = α p (i) = - 1 2 + liminf j→∞ log(|d j, (i-1)/(2 n+1-j ) +1| ) -j (2)
The equality above means that when the local and pointwise Hölder exponents at i coincide, we may compute their common value by looking only at the wavelet coefficients above i. In the sequel, we shall denote the common value by α(i). To simplify the exposition, we assume in addition that the liminf in ( 2) is a limit (the more general case may be handled with techniques presented in [START_REF] Legrand | Signal processing with Fra-cLab[END_REF]). When this is the case, the Hölder exponent may be estimated through a linear regression of the logarithm of the wavelet coefficients above i with respect to scale.

We may now formulate our denoising scheme as follows: For a given set of observations Y = (Y 1 , . . . , Y 2 n ) and a target Hölder function α, find X such that the risk R = E(|| X -X|| 2 ) is minimum and the regression of the logarithm of the wavelet coefficients of X above any point i w.r.t. scale is -(α(i) + 1 2 ). Note that we must adjust the wavelet coefficients in a global way. Indeed, each coefficient at scale j subsumes information about roughly 2 n-j points. Thus we cannot consider each point i sequentially and modify the wavelet coefficients above it to obtain the right regularity, because point i + 1, which shares many coefficients with i, requires different modifications. The right way to control the regularity is to write the regression constraints simultaneously for all points. This yields a system which is linear in the logarithm of the coefficients:

M L = A
where M is a (2 n , 2 n+1 -1) matrix of rank 2 n , and

L = (log |ĉ1,1|, log |ĉ2,1|, log |ĉ2,2|, . . . log |ĉn,2n |), A = - n(n -1)(n + 1) 12 α(1) + 1 2 , . . . , α(2 n ) + 1 2
Since we use an orthonormal wavelet basis, the requirements on the (ĉ j,k ) may finally be written as:

minimize: R = E( j,k (ĉ j,k -c j,k ) 2 )
subject to:

∀ i = 1 . . . 2 n , n j=1 sjlog(|ĉ j, (i-1)/(2 n+1-j ) +1 |) = -Mn(α(i) + 1 2 ) (3)
where the coefficients

s j = j -n+1 2 , M n = n(n-1)(n+1)
12 and equation (3) are deduced form the requirement that the linear re-gression of the wavelet coefficients of X above position i should equal -(α(i) + 1 2 ). Searching the most general solution to the program above is not an easy task. We consider instead in this paper the following special case: We impose that, for all (j, k),

ĉj,k = B j d j,k (4)
where the multipliers B j are real numbers belonging to the interval (0, 1]. The main motivation for the restriction on the form of the ĉj,k is of course that it leads to a simple solution. The choice of the range of the B j parallels an idea at work in classical denoising by wavelet shrinkage, namely that we seek to reduce the variance of the estimator by decreasing the absolute value of the coefficients. Now, by definition:

n j=1 s j log(|d j, (i-1)2 j+1-n |) = -M n (α Y (i) + 1 2 ) (5)
Subtracting ( 5) to (3) and using (4), we get:

∀i = 1, . . . , 2 n , n j=1 s j log(B j ) = M n (α Y (i) -α(i))
Thus the ansatz (4) imposes that the desired increase in regularity is uniform along the path, i.e. δ(i) = δ = constant. This restriction can be weakened by a classical block technique. Our problem now reads: minimize: R = E(

j,k (Bjd j,k -c j,k ) 2 )
subject to:

n j=1 s j log(B j ) = β and 0 < B j ≤ 1
where β = M n (α Y (i) -α(i)). The risk is computed as follows:

R = E j,k Bj(c j,k + σ √ 2 n z j,k ) -c j,k 2 = j,k c 2 j,k (1 -Bj) 2 + B 2 j σ 2 2 n = j e 2 j (1 -Bj) 2 + σ 2 j 2 j-n B 2 j
where e 2 j = k (c j,k ) 2 is the energy of X at scale j.

The constrained minimization has a unique solution

B * = (B * 1 , . . . , B * n ).
The values are classically found using a Lagrange multiplier. One gets:

B * j = 1± √ ∆ 2 a j with ∆ = 1- λ2 β+1 (j-n-1
2 ) a j e 2 j and a j = e 2 j e 2 j +2 j-n σ 2 . Here, λ is the Lagrange multiplier. No closed form exist for λ. It is obtained through a numerical procedure (see [START_REF] Legrand | Statistical denoising of irregular signals[END_REF] for more details).

It is interesting to compare our scheme with the soft-thresholding policy. Recall that soft-thresholding replaces the noisy coefficient d j,k by e j,k = sgn(d j,k )(|d j,k | -λ)+, where λ is a threshold that depends, among other things, on n and the type of noise. Denoting β j = -log(B j ), we see that in our case:

log(|ĉ j,k |) = log(|d j,k |) -β j , with sgn(ĉ j,k ) = sgn(d j,k )
The regularity based enhancement is thus a kind of shrinkage on the logarithm of the wavelet coefficients, and the restriction (4) may be interpreted as a requirement that the threshold must depend only on scale and not on position.

THEORETICAL RESULTS

In order to obtain convergence results, we need to assume that X has some regularity. A convenient frame is provided by the Besov spaces B α p,∞ (see for instance [START_REF] Donoho | De-noising by soft-thresholding[END_REF] for an account on Besov spaces).

Proposition 1 Assume that X ∈ B α p,∞ , with p ∈ [2, ∞], α > 1 p . Then the Hölder based denoising is asymptotically minimax, i.e.

R = O(2 -n 2α 2α+1 )
when n → ∞ See [START_REF] Legrand | Statistical denoising of irregular signals[END_REF] for a proof.

NUMERICAL EXPERIMENTS

Our examples deal with synthetic aperture radar (SAR) images. A huge literature has been devoted to the difficult problem of enhancing these images, where the noise, called speckle, is non Gaussian, correlated and multiplicative. A fine analysis of the physics of the speckle suggests that it follows a K distribution [START_REF] Oliver | Information from SAR images[END_REF]. Classical techniques specifically designed for SAR image denoising include geometric filtering and Kuan filtering. Wavelet shrinkage methods have also been adapted to this case [START_REF] Gagnon | Speckle noise reduction of airborne SAR images with symetric Daubechies wavelets[END_REF]. SAR imaging of natural landscapes is a good test for our technique, since the original signal is itself irregular. Although the noise is not additive, it is interesting to see how the Hölder based denoising performs on such data. We display on figure 1 an original image along with its denoising using a) Kuan filtering, b) classical wavelet hard-thresholding, and c) the algorithm developed in this paper. Figure 2 shows a Hölder based denoising on another SAR image.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Original SAR image (top left), Kuan median filtering (top right), wavelet shrinkage (bottom left), local regularity based method (bottom right).


Local regularity-based interpolation

Pierrick Legrand, Jacques Lévy Véhel Projet Fractales, IRCCyN 1 Rue de la Noé, B.P. , 44000 Nantes, France {Pierrick.Legrand, Jacques.Levy-Vehel}@irccyn.ec-nantes.fr

Description of the work and motivation

A ubiquitous problem in signal processing is to obtain data sampled with the best possible resolution. At the acquisition step, the resolution is limited by various factors such as the physical properties of the captors or the cost. It is therefore desirable to seek methods which would allow to increase the resolution after acquisition. This is useful for instance in medical imaging or target recognition. In some applications, one dispose of several low resolution overlapping signals [START_REF] Baker | Super-resolution: Reconstruction of Recognition[END_REF]. In more general situations, a single signal is available for superresolution. Interpolation then requires that the available data be supplemented by some a priori information. Two types of methods have been explored: In the first, "class-based" one, the signal is assumed to belong to some class, with conditions expressed mainly in the time or frequency domain [START_REF] Donoho | Maximum Entropy and the Nearly Balck Object[END_REF][START_REF] Kueh | Non-linear Approximation Theory on Finite Group[END_REF][START_REF] Youla | Image restoration by the method of convex projections: Part I -theory[END_REF]. This puts constraints on the interpolation, which is usually obtained as the minimum of a cost-function. The second type of approaches hypothesizes that the information needed to improve the resolution is local and is present in a class of similar signals [START_REF] Candocia | Superresolutions of images based on local correlations[END_REF][START_REF] Freeman | Example-Based Super-Resolution[END_REF]. This type of approach could be called "contextual". Both "class-based" and "contextual" approaches use a "model" for interpolation: The "class-based model" is that the signal belongs to an abstract class characterized by a certain mathematical property. The "contextual model" is that the signal will behave locally under a change of resolution in way "similar" to other signals in a given set, for which a high resolution version is known. Both types of techniques have some drawbacks. Roughly speaking, class-based methods generally lead to overly smooth signals, while contextual-based ones, on the contrary, tend to generate spurious details.

Our motivation is to find a way to interpolate in such a way that smooth regions as well as irregular ones (e.g. sharp edges) remain so after zooming. We interpret this as the constraint that interpolation should preserve the local regularity. We measure this regularity through a notion of Hölder exponent. Hölder exponents have been shown to correspond to an intuitive notion of regularity in both images and 1D signals [START_REF] Véhel | Fractal Approaches in Signal Processing[END_REF]. In order to control the interpolation and obtain a simple implementation, we need to make some assumptions on the signal, to the effect that (a) this Hölder exponent can be easily estimated from wavelet coefficients (b) the exponent allows to predict the finer scales coefficients. Technically, this requires that the signal is not oscillatory. Our scheme allows to control both the reconstruction error and the regularity of the interpolated signal, i.e. the visual appearance of the added information.

The method

The method is best understood in terms of wavelet coefficients: Let X denoted the input signal and let d j,k be its wavelet coefficients, where, as usual, j corresponds to scale and k to location. Roughly speaking, if a signal has regularity α at point t, then its wavelet coefficient d j,k(j,t) "above" t are bounded by C2 -jα for some constant C: ∀j = 1 . . . n, |d j,k(j,t) | ≤ C2 -jα . The exponent α corresponds to an intuitive notion of regularity: A large α translates in a smooth signal, while α ∈ (0, 1) means that the signal is continuous and non differentiable at t. If the signal is discontinuous at t but bounded, then α = 0. Now if we are willing to conserve the regularity, we should prescribe the wavelet coefficient above t at the superresolved scale n + 1 in such a way that

|d n+1,k(n+1,t) | ≤ C2 -(n+1)α .
For concreteness, let us explain schematically how our method would act on a uniform region and on a step edge. On a uniform region, all the wavelet coefficients are close to zero. The bound on the wavelet coefficients then holds with arbitrarily large α, since 0 ≤ C2 -jα for all α > 0. As a consequence, the predicted coefficient d n+1,k will be zero, since it must satisfy the same inequality: Smooth regions will remain smooth, because no detail will be added. On the other hand, above a step edge, the wavelet coefficients d j,k do not decay in scale. This imply that α = 0. The predicted coefficient d n+1,k will then be of the same order as d n,k . As a consequence, the local regularity of the interpolated image will be again equal to 0 at this point, and the edge will not be blurred.

Our approach has similarities with both class-based and contextual methods. As in class-based methods, we do not rely on information learnt from a database, and require that the signal belongs to a definite class. A distinctive feature is that our class is based on local features. The similarity with contextual approaches is that the information is learnt from the image instead of being a priori, as in class-based ones. Also, this information is local in space and scale, and is versatile enough to handle a wide variety of situations.

Let X denote the original signal, and X n = (x n 1 , . . . x n 2 n ) its regular sampling over the 2 n points (t n 1 , . . . t n 2 n ). Let ψ denote a wavelet such that the set {ψ j,k } j,k forms an orthonormal basis of L 2 . Let d j,k be the wavelet coefficients of X.

For p = 1 . . . 2 n , we consider the point t = t n p and the wavelet coefficients which are located "above" it, i.e. d j,k(j,t) with k(j, t) = ⌊(t -1)/(2 n+1-j )⌋ + 1. Let α n (t) denote the slope of the liminf regression (see [START_REF] Legrand | Signal Processing with FracLab Preprint[END_REF] for an account on liminf regressions) of the vector (log(d 1,k(1,t) , . . . d n,k(n,t) ) versus (-1, . . . , -n).

When n tends to infinity, α n (t) tends to liminf

log d n,k(n,t)
-n

. This number has been considered in the literature [START_REF] Meyer | Wavelets, Vibrations and Scalings[END_REF] under the name of weak scaling exponent, denoted β w . It is a measure of the local regularity in the following sense. The weak scaling exponent of the signal X at t 0 is defined as: β w = sup{s : ∃n, X (-n) ∈ C s+n t0 } where X (-l) denotes a primitive of order l of X and C s t0 is the usual pointwise Hölder space at t 0 . When the local Hölder exponent α l and the pointwise Hölder exponent α p of X at t coincide, then β w is also equal to their common value. See [START_REF] Véhel | Seuret The 2-microlocal formalism[END_REF] for more on this topic. In the following we will always assume that this is the case. In other words, we consider that our signals belong to the class S defined as follows:

S = {X ∈ L 2 (IR), ∀t ∈ IR, α p (t) = α l (t)}
The class S may appear somewhat abstract to the reader. Here are a few clues. S contains all C ∞ signals and all signals of the type n∈I N |t -t n | γn , with t n ∈ IR, γ n ∈ IR + . Many everywhere irregular signals are also in S, such as the continuous nowhere differentiable Weierstrass function n∈I N 2 -nh sin(2 n t), h ∈ (0, 1). On the other hand, "chirp" signals as |t| γ sin(1/|t| β ), γ > 0, β > 0 do not belong to S. For X in S, at each point t, the "largest" coefficients are located above t in the following sense. Take any sequence d j,k of coefficients such that k2 -j tends to t. Then, if X belongs to S,

liminf j→∞ log |d j,k | -j ≥ liminf j→∞ log |d j,k(j,t) | -j (1)
Such signals are called "non-oscillatory" in the literature. To perform the interpolation, we compute above each point t the regression of the wavelet coefficients vs scale (figure 1). The parameters of the regression allow to build the extrapolated coefficient. These coefficients in turn determine the "superresolved" signal. For a sampled signal X n , we denote Xn the signal interpolated on infinitely many levels.

Regularity and Asymptotic properties

Proposition 1 Let X be in C η for some η > 0. Then, for all ε > 0, there exists N such that for all n > N , all p and all t ∈ (t n p , t n p+1 ), α Xn p (t) = α Xn l (t) ∈ [β -ε, β + ε], where β = min(β w (t n l ), β w (t n l+1 )).

Proposition 2 Let X belong to S, and assume X ∈ C α . Then, ∀ε > 0, ∃N :

n > N ⇒ ||X-Xn || 2 = O(2 -n(α-ε) ). In addition, ||X-Xn || B s p,q = O(2 -n(α-s-ε) ) for all s < α -ε.

Numerical experiments

We provide experiments on a step edge (figure 2), a generalized Weierstrass function (figure 3), and a real-world signal, namely a road profile (figure 4). In each case, we compare our method with a simple linear interpolation.

Figure 1 :

 1 Figure 1: Regression above a point of the signal. We find scales in abscissa and the log of the wavelet coefficients in ordinate. The extrapolated coefficient is the rightmost point.

Figure 2 :

 2 Figure 2: Interpolation of a step edge (32 points to 1024 points). Notice how the edge is not blurred with the Hölder based interpolation.

Figure 3 :

 3 Figure 3: Generalized Weierstrass ( n∈I N 2 -nt sin(2 n t)) with zooms and comparison with linear interpolation. Notice how the Hölder based method preserves the irregular as well as regular parts of the signal. In the zoomed figures the Hölder based interpolation is the dashed one.


Zeina Azmeh
email: azmeh@lirmm.fr

Fady Hamoui
email: hamoui@lirmm.fr

Marianne Huchard
email: huchard@lirmm.fr

Nizar Messai
email: nizar.messai@ecp.fr

Chouki Tibermacine
email: tibermacin@lirmm.fr

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

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

Backing Composite Web Services Using Formal Concept Analysis

Keywords: Web service classification, Formal Concept Analysis (FCA), service composition, service backups

A Web service is a software functionality accessible through the network. Web services are intended to be composed into coarser-grained applications. Achieving a required composite functionality requires the discovery of a collection of Web services out of the enormous service space. Each service must be examined to verify its provided functionality, making the selection task neither efficient nor practical. Moreover, when a service in a composition becomes unavailable, the whole composition may become functionally broken. Therefore, an equivalent service must be retrieved to replace the broken one, thus spending more time and effort. In this paper, we propose an approach for Web service classification based on FCA, using their operations estimated similarities. The generated lattices make the identification of candidate substitutes to a given service straightforward. Thus, service compositions can be achieved more easily and with backup services, so as to easily recover the functionality of a broken service.

Introduction

A Web service is a software functionality accessible through the network. It exposes its functionalities to the external world by an abstract interface expressed in Web Service Description Language (WSDL) [START_REF]Web Services Description Language (WSDL) 1.1[END_REF]. A WSDL interface is an XML-based document that describes a service's available operations, parameters, data types, and access protocols.

Web services represent the building blocks for creating composite applications. When creating a composite application, each selected Web service must fulfill 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. Then, after identifying the needed services, they can be assembled together in order to meet the desired functionality of the whole composite application.

The task of finding an appropriate service to use is hard and time-consuming, because of the large number of existing Web services nowadays. This may become even harder knowing that Web services are not guaranteed to have a continuous execution. This is due to their dynamic nature, being offered by various providers, remotely accessed, and having different quality of service (QoS) levels. Therefore, an available functioning Web service may crash and become unavailable at any time, which requires finding an equivalent one to replace it, in order to maintain the application functionality.

The real challenge lies in the fact that there is a lack of WSDL management facilities, especially after the deficiency of UDDI [2], which was originally proposed as a core Web service registry standard: "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 organizing and indexing Web services is significantly required. This leads us to our proposition for Web service classification, which is based on Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis[END_REF].

In our proposed approach, we consider the objects to be Web services and the attributes to be the operations offered by these services. We construct Web service lattices using many-valued contexts of similarity values calculated for each pair of operations. The generated service lattices provide us with browsing and navigation capabilities. This allows the retrieval of more general to more specific sets of services [START_REF] Godin | Méthodes de classification conceptuelle basées sur les treillis de Galois et applications[END_REF][START_REF] Carpineto | A lattice conceptual clustering system and its application to browsing retrieval[END_REF]. More general sets have lesser common operations while more specific sets have more common operations. Therefore, applying FCA to Web services provides us with a retrieval mechanism, which facilitates both selection of Web services and identification of their possible substitutes. Accordingly, it helps building composite applications as well as supporting them with backup services.

The rest of the paper is organized as follows: Section 2 defines how we adapt FCA to web services. Section 3 explains our approach along with examples and formal definitions. Section 4 demonstrates a case study using real web services. Section 5 lists and discusses the related work. Finally, Section 6 concludes the paper and describes some of our perspectives.

An FCA-Based Approach for Web Service Classification

In our approach, we use FCA [START_REF] Ganter | Formal Concept Analysis[END_REF] in order to construct a classification of Web services. We consider that the objects are Web services and the attributes are operations. In this way, a formal context of Web services and operations becomes K = (W, O, I), where:

W = {ws i | 1 ≤ i ≤ n W , n 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 all of the services forms the total set of operations:

ws i = {op i j | 1 ≤ i ≤ n W , 1 ≤ j ≤ n ws i } O = i=n 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 = {Calc 1 ,Calc 2 ,Calc 3 } and O = {add, sub, mul, div, pow}. A concept, for example ({Calc 1 ,Calc 2 }, {add, sub, pow}), is thus a maximal collection of services offering similar operations. The concept lattice defines a hierarchical organization of services and operations, in which a certain concept inherits all the extents (services) of its descendants (subconcepts) and all the intents (operations) of its ascendants (super-concepts). Fig. 1 illustrates the lattice built for the context shown in Table 1, using the ConExp tool [START_REF]The Concept Explorer[END_REF].

add sub mul div pow Calc 1 × × × Calc 2 × × × × Calc 3 × × ×
From the lattice in Fig. 1, we can reveal the relationships between the presented services. We list some of them as follows:

-Calc 1 , Calc 2 and Calc 3 offer the operation {add}. Thus, they can replace each other for this operation; -Calc 1 and Calc 2 offer the operations {add, sub, pow}; -Calc 2 can replace Calc 1 since it offers all of its operations in addition to div; -Calc 2 and Calc 3 offer together the operations {add, div}.

Using binary contexts to classify Web services by their operations reflects two cases: the service either offers a given operation or not. Substitution can only be handled when services offer strictly identical operations which is not the case for real Web services. This is why we need to introduce the notion of operation similarity and use many-valued contexts of similarity values, as in the following section.

Using Many-Valued Contexts

Web services in a certain business domain may offer similar operations. In order to classify these services by their operations using FCA, we need to calculate the operation similarity and to use many-valued contexts. We explain our approach using the set of services illustrated in Table 1. For clarity, we use only the first 3 operations of each service. We use the actual operations 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 applied on pairs of operation signatures extracted from the WSDL files. There are several similarity measures for Web services that evaluate similarity according to syntax and semantics, such as [START_REF] Dong | Similarity search for web services[END_REF][START_REF] Stroulia | Structural and semantic matching for assessing web-service similarity[END_REF][START_REF] Kokash | A comparison of web service interface similarity measures[END_REF]. 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, otherwise it will approach 0. The similarity measure is applied on pairs of operations provided by distinct services. We do not evaluate similarity between distinct operations provided by the same service (we suppose that it is equal to 0), because when a service becomes dysfunctional, all of its operations become dysfunctional too.

A similarity measure Sim : O × O → [0, 1] can be defined as follows:

∀ op i j ∈ O =⇒ Sim(op i j , op i j ) = 1 (an operation with itself) ∀ op i j , op ik ∈ O, j = k =⇒ Sim(op i j , op ik ) = 0 (operations in the same service)

∀ op i j , op nm ∈ O, i = n =⇒ Sim(op i j , op nm ) ∈ [0, 1] (operations in different services)
The calculated similarity values can be presented by a symmetric square matrix that we will call SimMat, as shown in Table 3. This matrix is of size n = |O|, and its diagonal elements are all equal to 1 (similarity of an operation with itself).

From the similarity matrix SimMat, we can extract several binary contexts, by specifying threshold values θ ∈]0, 1]. Thus, the values of SimMat 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 i j , op nm ) ∈ RSim θ ⇐⇒ Sim(op i j , op nm ) ≥ θ
We use the SimCxt context to generate a lattice of operations (Fig. 2), B(O, O, RSim θ ). This lattice helps in discovering groups of similar operations, which are used later on to construct the service 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 square concepts [START_REF] Azmeh | Many-Valued Concept Lattices for Backing Composite Web Services[END_REF], 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. shown in Table 4.

From the lattice in Fig. 2 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 } that we label [START_REF] Azmeh | Many-Valued Concept Lattices for Backing Composite Web Services[END_REF][START_REF] Azmeh | SylvainVauttier: Using concept lattices to support web service compositions with backup services[END_REF][START_REF] Huchard | Galois lattice as a framework to specify building class hierarchies algorithms[END_REF]; -{op 21 , op 31 } labelled (21, 31); -{op 12 , op 32 } labelled (12, 32); -{op 33 } labelled [START_REF] Peng | Concept-based retrieval of alternate web services[END_REF].

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 use the labels representing the groups of operations to build the final context, which is shown in Table 6. Using this context, we generate the corresponding service lattice that is shown in Fig. 3. From the final generated service lattice, shown in Fig. 3, we can notice the following:

ws 1 × × ws 2 × × ws 3 × × × ×
ws 1 , ws 2 , and ws 3 offer the functionality denoted by [START_REF] Azmeh | Many-Valued Concept Lattices for Backing Composite Web Services[END_REF][START_REF] Azmeh | SylvainVauttier: Using concept lattices to support web service compositions with backup services[END_REF][START_REF] Huchard | Galois lattice as a framework to specify building class hierarchies algorithms[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 [START_REF] Peng | Concept-based retrieval of alternate web services[END_REF].

We can also infer immediately which services offer a specific functionality (denoted by a specific label), by considering the indices in the label. For example, the label [START_REF] Azmeh | Many-Valued Concept Lattices for Backing Composite Web Services[END_REF][START_REF] Azmeh | SylvainVauttier: Using concept lattices to support web service compositions with backup services[END_REF][START_REF] Huchard | Galois lattice as a framework to specify building class hierarchies algorithms[END_REF] makes it possible to directly deduce that (11) is provided by ws 1 , (34) by ws 3 and (21) by ws 2 .

Case Study

In this section, we demonstrate the use of service lattices for both building composite Web services and supporting them with backup services in a real world context.

We consider the example of a composite service for currency conversion, composed of two Web services: a currency converter service Currency and a calculation service Calculator. The Currency service offers an operation that returns the exchange rate between two entered currencies: getRate(fromCurr,toCurr). The Calculator service offers an operation that calculates the multiplication of two entered numbers: mul(a,b). We compose these two operations in order to build the composite currency service that converts a given amount from one currency to another. We describe a service composition using the Business Process Execution Language (BPEL) [START_REF]Web Services Business Process Execution Language Version 2[END_REF]. We use the BPEL editor of NetBeans IDE [START_REF]NetBeans IDE[END_REF] to design and describe the specified CompositeCurrencyService as shown in Fig. 4.

We used the Seekda [START_REF]Seekda Web Services Search Engine[END_REF] and Service-Finder [START_REF]Service-Finder Web Services Search Engine[END_REF] Web service search engines to search for the needed services. We describe this case study on two parts: first we illustrate the use of the approach, then we validate it.

Using the Approach

We use a set of services for currency conversion shown in Table 7 and another set for calculation 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. For dealing with this illustration, we assess manually the similarity for the obtained services' operations of each set (an automatic approach is described later in the paper). This is achieved by comparing operation signatures (operation names, parameter names and types). Using the operations lattice and its square concepts, we identify the following groups of mutually similar operations for the currency services in These extracted groups of similar operations lead to a binary context for each set of services as shown in Tables 9 and10.

ws 1 × × × × × ws 2 × × × ws 3 × × × × ws 4 × × × × ws 5 × × × × ws 6 × × × ×
We generate the two corresponding lattices as shown in the right side of Fig. 5. We can exploit these service lattices to build our composite service as well as to support it with backup services. Thus, we decide to select operation op 11 : (CR : 11) from service ws 1 for exchange rate (currency lattice), and operation op 13 : (mul : 13) from service ws 1 for multiplication (calculation lattice). From these lattices (Fig. 5), we can also extract some backup services for our composite service according to the selected operations. For example, we used operation op 11 : (CR : 11) from service ws 1 , which has 3 equivalent operations: op 21 : (CR : 21), op 31 : (CR : 31) and op 51 : (CR : 51) appearing clearly in the lattice. This means that if service ws 1 breaks down, we can replace it by any of the services ws 2 (equivalent to ws 1 being in the same concept), ws 3 or ws 5 (services introduced in subconcepts).

Moreover, if we go down in the lattice, we get the set of services that provide the operations used together with extra operations, like service ws 5 and service ws 3 . They can help if the composite service evolves and needs other operations. In the same way, we can extract the backup services for the calculation service ws 1 that we are using. According to the calculation service lattice, service ws 1 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 operations op 33 : (mul : 33), op 43 : (mul : 43), op 52 : (mul : 52), and op 63 : (mul : 63), which are offered by services ws 3 , ws 4 , ws 5 , and ws 6 respectively. This gives us a replacement possibility in case of unavailability of ws 1 in the framework of the composite currency service.

Validation

In this section, we validate our approach using the entire number of retrieved Calculator and Currency services 4 . We queried Service -Finder to collect service endpoints (addresses), then we downloaded the corresponding WSDL interfaces via Seekda. For the Calculator service, we searched using multiply as keyword. This returned a set W S1 of 29 services, among which we found one unrelated service.

For the Currency service, we used a combination of the following keywords exchange, rate, currency, converter. After eliminating the repeated services, we found a set of 81 services. From this set, we also eliminated the services that we were unable to parse. This resulted in a set W S2 of 64 services.

We parsed each service of the two sets (WSDL parser 5 ), to extract its operation signatures. The set W S1 has a total of 142 operations, while W S2 has 935 operations.

In order to calculate the SimMat (explained in Section 3) for both sets of services, we make use of Jaro -Winkler [START_REF] Cohen | A comparison of string distance metrics for name-matching tasks[END_REF] similarity measure, to assess the similarity between the extracted signatures according to each set. This metric gave convenient similarity values that were calculated efficiently, compared to another tested technique that used a combination of syntactic and semantic metrics. After a number of experiments, we found that a relatively pertinent similarity value starts from 80%. By applying this threshold on the SimMat, we obtained the binary SimCxt corresponding to each set.

We tried to compute the lattices corresponding to each SimCxt using Galicia [17]. The lattices could not be generated due an "out of memory" error (on a machine with limited resources). Therefore, we computed the Galois Sub Hierarchy (GSH), (order induced by attribute and object concepts). Using GSH, we obtained a suborder of 155 concepts for SimCxt (142 × 142) and another suborder of 1724 concepts for SimCxt (935 × 935). The second suborder may be reduced depending on the functionality filtering techniques.

Hereby, we restrict our analysis on W S1 regarding the limited paper space. From the GSH calculated for SimCxt (142 × 142), we extracted 65 square concepts. Among these 65 square concepts, we had 13 non-trivial concepts and 52 concepts reduced to one operation. Each square concept represents a functionality, for example: c82 represents the multiply functionality. It contains {op15.2, op18.3, op2.3, op6.3, op8.2}, which are mutually substitutable operations for calculating the multiplication of two numbers.

Afterwards, we constructed the lattice of services (as objects) and these square concepts (as attributes). The generated lattice is shown in Fig. 6, and contains 21 concepts. By regarding the right half of the lattice, we can notice services that can be entirely replaced by other ones. For example: if we consider ws15, it contains the multiply functionality (being a subconcept of c82). This service can be replaced by three other services: ws18, ws6 and ws2.

Related Work

Software engineering research has long benefitted from using FCA-based techniques in various ways, as attested by [START_REF] Tilley | A survey of formal concept analysis support for software engineering activities[END_REF] which indexes and classifies 42 such scientific papers published between 1992 and 2003 using FCA. These works go from early development phases (requirement engineering) to late ones (maintenance or legacy system analysis). Many have focused on refactoring and reingineering, especially in object-oriented languages [START_REF] Godin | Building and maintaining analysis-level class hierarchies using galois lattices[END_REF][START_REF] Snelting | Understanding class hierarchies using concept analysis[END_REF][START_REF] Huchard | Galois lattice as a framework to specify building class hierarchies algorithms[END_REF][START_REF] Godin | Formal concept analysis-based class hierarchy design in objectoriented software development[END_REF]. Although our approach can be used and understood as a Web service refactoring method (since operations are factorized in the lattice), this paper chooses to focus on the classification of Web services inside backup service libraries. Among the works that ambition to browse or request software libraries using FCA, some rely mainly on syntax [START_REF] Aboud | Automated architectural component classification using concept lattices[END_REF][START_REF] Arévalo | FCA-based service classification to dynamically build efficient software component directories[END_REF], extending type theory [START_REF] Liskov | Keynote address -data abstraction and hierarchy[END_REF] to recent paradigms (Componentbased development or SOA). Others have studied the use of FCA [START_REF] Lindig | Concept-based component retrieval[END_REF] to structure keyword-based indexes that enable to browse software libraries [START_REF] Fischer | Specification-based browsing of software component libraries[END_REF][START_REF] Sigonneau | Indexation multiple et automatisée de composants logiciels[END_REF]. In the literature, we can find several works that more specifically focus on Web service classification and selection. A quick overview can be obtained from [START_REF] Brockmans | Service-finder deliverable d4.1[END_REF][START_REF] Lausen | Survey of current means to discover web services[END_REF]. In sections 5.1 and 5.2 we list a selection of works based respectively on FCA and on other techniques. Then we discuss comparatively our contribution in Section 5.3.

Approaches Based on FCA

In [START_REF] Aversano | Using concept lattices to support service selection[END_REF], Web services are classified using FCA to facilitate WSDL browsing. The 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], FCA is used together with keywords extracted from services' interfaces to build a Web services lattice. The extracted words are processed using WordNet and other IR techniques, and are classified into vectors using support vector machines (SVM). The obtained vectors categorize the services into domains, and service lattices are obtained for each category using FCA.

In [START_REF] Peng | Concept-based retrieval of alternate web services[END_REF][START_REF] Azmeh | SylvainVauttier: Using concept lattices to support web service compositions with backup services[END_REF], pairs of similar operations, depending on a chosen threshold, are merged together and the services are described by a representative operation of the pair in order to build the service lattice. They do not approach the issue that in a set of operations, op 1 can be similar to op 2 and op 2 similar to op 3 but op 1 might be not similar to op 3 because similarity is in general not a transitive operation. We solve this issue using an intermediate operation lattice based on the SimCxt to merge the maximal sets of mutually similar operations. Our mining of mutually similar operations is another application of the use of tolerance relations jointly with FCA, as is also done in [START_REF] Kaytoue | Embedding tolerance relations in formal concept analysis: an application in information fusion[END_REF].

Approaches Based on Other Techniques

Many approaches use machine learning techniques, 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ß | Learning to attach semantic metadata to web services[END_REF], service classifiers are defined depending on sets of previously categorized services. The resulting classifiers are then used to deduce relevant categories for new services. In case there are no predefined categories, unsupervised clustering is used. In [START_REF] Ma | Efficiently finding web services using a clustering semantic approach[END_REF], the CPLSA approach is defined that reduces a service set then clusters it into semantically related groups.

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 folksonomybased model of web services for discovery and automatic composition[END_REF], tags coming from folksonomies are used to discover and compose services.

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 vectors are built for describing 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 similarity scores as in [START_REF] Wang | Semantic structure matching for assessing web service similarity[END_REF], or by partitioning the search space into smaller subspaces as in [START_REF] Crasso | Query by example for web services[END_REF].

Discussion

In FCA approaches based on keywords, similar operations can not be determined and thus, Web service substitutes can not be identified either. In our approach, we generate an intermediary lattice to group mutually similar operations. Thus, sets of equivalent operations appear in each concept of the final lattice. This serves for several purposes such as service retrieval, selection and support for service compositions with backup services. Indeed, one of our main contributions is the idea of supporting the continuity of service compositions. 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.

A service lattice is a structure that reveals relations between services according to the operations provided in common. It offers a navigation facility that enables better discovery and browsing than in structures such as lists and sets used in the other approaches. New services can be classified in existing lattices using incremental lattice generation algorithms. Thus, there is no need to regenerate the whole lattice. Moreover, our approach can be tuned to have similarity thresholds set to consider finer-grained to coarser-grained comparisons. Indeed, the threshold values set during the process set the sizes of the sieves used to keep similar operations. These thresholds are set empirically. They condition the number of candidate backups our approach will discover. If there are too much candidate services, selection might as well be harder (only very similar services should be kept): the threshold can be raised. If there are few services proposed as backups, the threshold can be lowered. Backup candidates will be more dissimilar, probably requiring some little manual adaptations, but such setting would find backup possibilities where others would not. Finally, systematically calculating lattices for several threshold values might provide an interesting zoom-in / zoom-out capability that would provide several finer to coarser-grained classifications as in [START_REF] Messai | Using domain knowledge to guide lattice-based complex data exploration[END_REF].

Conclusion and Future Work

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 [START_REF] Dong | Similarity search for web services[END_REF][START_REF] Stroulia | Structural and semantic matching for assessing web-service similarity[END_REF][START_REF] Kokash | A comparison of web service interface similarity measures[END_REF] 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 responds 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. Besides, the construction of a composite web service could benefit from Relational Concept Analysis [START_REF] Huchard | Relational concept discovery in structured datasets[END_REF]. Several context families could be considered that would encode relations between operations, operations and services, or services in the composition.

Another challenge is the dynamic update of the classification. As algorithms exist that incrementally build lattices, we believe adding services might be possible without reconsidering the whole calculus. When the disappearance of services is concerned, dismissing the indexing information immediately might not be a good idea as services might be frequently unavailable for temporary periods of time (as a crashed web server reboots, for instance). More observation still is necessary for us to evaluate if disappearances should be handled as immediate removals (or, maybe, as lazy removals, based on their being unavailable for too long). This dynamic aspect is an interesting field for future research.

  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, ({Calc 1 ,Calc 2 }) = {add, sub, pow} and ({div}) = {Calc 2 ,Calc 3 }.

  [START_REF] Azmeh | Many-Valued Concept Lattices for Backing Composite Web Services[END_REF][START_REF] Azmeh | SylvainVauttier: Using concept lattices to support web service compositions with backup services[END_REF][START_REF] Huchard | Galois lattice as a framework to specify building class hierarchies algorithms[END_REF] (21,31) (12,32)[START_REF] Peng | Concept-based retrieval of alternate web services[END_REF]

Fig. 3 :

 3 Fig. 3: The final service lattice with possible backups.

Fig. 4 :

 4 Fig. 4: The composite currency service.

Fig. 5 :

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

Fig. 6 :

 6 Fig. 6: The lattice corresponding to the Calculator services set.

Table 1 :

 1

A formal context for W × O Fig. 1: The service lattice for the context in

Table 1

 1

Table 2

 2

	: A set of calculation services with their operations
	Services Id Operations Id
	Calc 1 ws 1 add(a,b) op 11
	sub(a,b) op 12
	Calc 2 ws 2 add(a,b,c) op 21
	Calc 3 ws 3 add(a,b,c,d) op 31
	sub(a,b,c) op 32
	mult(a,b) op 33
	add(a,b,c) op 34

Table 3 :

 3 The similarity matrix (SimMat). op 11 op 12 op 21 op 31 op 32 op 33 op 34

	op 11 1	0 0.75 0.5 0	0	1
	op 12 0	1	0	0 0.75 0	0
	op 21 0.75 0	1 0.75 0	0 0.75
	op 31 0.5 0 0.75 1	0	0	0
	op 32 0 0.75 0	0	1	0	0
	op 33 0	0	0	0	0	1	0
	op 34 1	0 0.75 0	0	0	1

Table 4 :

 4 The context (SimCxt) for θ = 0.75. op 11 op 12 op 21 op 31 op 32 op 33 op 34

	op 11 ×	×	×
	op 12	×	×
	op 21 ×	× ×	×
	op 31	× ×
	op 32	×	×
	op 33		×
	op 34 ×	×	×

Table 5 :

 5 The interchanged (SimCxt) context. op 11 op 34 op 21 op 31 op 12 op 32 op 33 op 11 × × × op 34 × × ×

	op 21 × × ×	×
	op 31	× ×
	op 12		× ×
	op 32		× ×
	op 33

× Fig. 2: The generated lattice for (SimCxt)

Table 6 :

 6

The final services × groups context.

Table 7 :

 7 The set of currency converter services.

	Services	Id	Operations	Id
	CurrencyConverter	ws 1	GetConversionRate(fromCurrency,toCurrency)	op 11
	CurrencyConvertor	ws 2	ConversionRate(FromCurrency,ToCurrency)	op 21
	DOTSCurrencyExchange ws 3	GetExchangeRate(ConvertFromCurrency,ConvertToCurrency)	op 31
			ConvertCurrency(Amount,ConvertFromCurrency,ConvertToCurrency) op 32
			GetCountryCurrency(Country)	op 33
	CurrencyRates	ws 4	GetRate(CurrencyCode)	op 41
			GetConversion(FromCurrencyCode,ToCurrencyCode)	op 42
	RadixxFlights	ws 5	GetExchange(FromCurrency,ToCurrency)	op 51
			ConvertCurrency(Amount,FromCurrency,ToCurrency)	op 52
	rates	ws 6	Convert(CurrencyFrom,CurrencyTo,ValueFrom)	op 61
	Conversion	ws 7	CelciusToFahrenheit(fCelsius)	op 71
			FahrenheitToCelcius(fFahrenheit)	op 72
			Currency(fValue,sFrom,sTo)	op 73
	CurConvert	ws 8	GetCurrencySign(CountryName)	op 81
			ConvertCurrency(FromCountry,ToCountry,Amount)	op 82
	ConverterService	ws 9	Convert(sourceCurrency,targetCurrency,value)	op 91

Table 8 :

 8 The set of calculation services.

	Services	Id	Operations	Id
	Calc	ws 1	add(a,b)	op 11
			div(a,b)	op 12
			mul(a,b)	op 13
			pow(b,a)	op 14
			sub(a,b)	op 15
	Service	ws 2	add(a,b)	op 21
			sqrt(a)	op 22
			sub(a,b)	op 23
	MathService ws 3	Add(A,B)	op 31
			Divide(A,B)	op 32
			Multiply(A,B)	op 33
			Subtract(A,B)	op 34
	CalculatorService ws 4	add(y,x)	op 41
			divide(denominator,numerator) op 42
			multiply(y,x)	op 43
			subtract(y,x)	op 44
	CalcService	ws 5	Divide(A,B)	op 51
			Multiply(A,B)	op 52
			OperationAdd(A,B)	op 53
			Subtract(A,B)	op 54
	Calculate	ws 6	Add(dbl1,dbl2)	op 61
			Divide(dbl1,dbl2)	op 62
			Multiply(dbl1,dbl2)	op 63
			Subtract(dbl1,dbl2)	op 64

Table 7 :

 7 -{op 11 ,op 21 ,op 31 ,op 51 } that we label (CR : 11, 21, 31, 51); -{op 32 ,op 42 ,op 52 ,op 61 ,op 73 ,op 82 ,op 91 } labelled (CC : 32, 42, 52, 61, 73, 82, 91); -{op 33 ,op 81 } labelled (CS : 33, 81); -{op 41 } labelled (R : 41); -{op 72 } labelled (FC : 72); -{op 71 } labelled (CF : 71). We extract also the groups of mutually similar operations for the calculation services in Table 8, and they are as follows: -{op 15 ,op 23 ,op 34 ,op 44 ,op 54 ,op 64 } labelled (sub : 15, 23, 34, 44, 54, 64); -{op 11 ,op 21 ,op 31 ,op 41 ,op 53 ,op 61 } labelled (add : 11, 21, 31, 41, 53, 61); -{op 13 ,op 33 ,op 43 ,op 52 ,op 63 } labelled (mul : 13, 33, 43, 52, 63); -{op 12 ,op 32 ,op 42 ,op 51 ,op 62 } labelled (div : 12, 32, 42, 51, 62); -{op 14 } labelled (pow : 14); -{op 22 } labelled (sqrt : 22).

Table 9 :

 9 The formal context corresponding to the currency converter services.

		(CR:11,21,31,51) (CC:32,42,52,61,73,82,91) (CS:33,81) (R:41) (FC:72) (CF:71)
	ws 1	×
	ws 2	×	×
	ws 3	×	×	×
	ws 4		×	×
	ws 5	×	×
	ws 6		×
	ws 7		×	×	×
	ws 8		×	×
	ws 9		×

Table 10 :

 10 The formal context corresponding to the calculator services.

(sub:

[START_REF]Service-Finder Web Services Search Engine[END_REF][START_REF] Aboud | Automated architectural component classification using concept lattices[END_REF][START_REF] Azmeh | SylvainVauttier: Using concept lattices to support web service compositions with backup services[END_REF][START_REF] Crasso | Query by example for web services[END_REF]54,64)

(add:11,21,31,41,53,61) (mul:13,33,43,52,63) (div:12,32,42,51,62) (pow:14) (sqrt:22)

Retrieved services: http://www.lirmm.fr/∼azmeh/icfca11/CaseStudy.html

Available online: http://www.lirmm.fr/∼azmeh/tools/WsdlParser.html

Acknowldegements Authors would like to thank anonymous reviewers for their relevant comments that helped to clarify and enrich our paper.