Luigi De

Jean Louet
email: louet@ceremade.dauphine.fr

J L Ceremade

A STUDY OF THE DUAL PROBLEM OF THE ONE-DIMENSIONAL L ∞ -OPTIMAL TRANSPORT PROBLEM WITH APPLICATIONS

Keywords: Mathematics Subject Classification. 49Q20, 49K30, 49J45 Monge-Kantorovich problem, optimal transport problem, cyclical monotonicity

. We construct a couple of Kantorovich potentials which is non trivial in the best possible way. More precisely, we build a potential which is non constant around any point that the restrictable, minimizing plan moves at maximal distance. As an application, we show that the set of points which are displaced at maximal distance by a "locally optimal" transport plan is shared by all the other optimal transport plans, and we describe the general structure of all the one-dimensional optimal transport plans.

Introduction

Given two probability measures µ, ν on R d , the infinite Wasserstein distance between µ and ν is defined as W ∞ (µ, ν) := min γ∈Π(µ,ν) γess.sup

R d ×R d |x -y|, (1.1)
where Π(µ, ν) denotes the set of positive measures on R d whose first and second marginals are µ, ν respectively. This distance is the natural limit as p → ∞ of the more common Kantorovich-Wasserstein distances W p . Problem (1.1) above was first studied in [START_REF] Champion | The ∞-Wasserstein distance: local solutions and existence of optimal transport maps[END_REF] where it was observed that, in spite of its proximity with the W p distances, it presents several peculiarities. The two most striking phenomena are the lack of linearity or even convexity of (1.1) with respect to γ (in fact the functional γ → yx L ∞ γ (R 2d ) is only level-convex), and the non-uniqueness of the minimizer: indeed, one may guess that, from any optimal plan γ, any small perturbation of γ around a point (x, y) which is not moved at maximal distance will provide a new and different optimal transport plan. It is therefore necessary to find a suitable notion of local solution of (1.1). The following definition, introduced in [START_REF] Champion | The ∞-Wasserstein distance: local solutions and existence of optimal transport maps[END_REF], turned out to be the right one. Definition 1.1. A transport plan γ ∈ Π(µ, ν) is a restrictable solution of (1.1) if any positive and nonzero Borel measure γ ′ on R 2d that is majorized by γ is a solution to the problem inf

λ∈Π(µ ′ ,ν ′ ) λ -ess.sup R d ×R d |y -x|,
where µ ′ = (π 1 ) # γ ′ and ν ′ = (π 2 ) # γ ′ .

It is likely that a small "local modification" of a restrictable solution will not be a restrictable solution anymore. From the analysis of the problem (1.1) as a limit of the classical optimal transport problem with cost c(x, y) = |y -x| p as p → +∞, it turns out that the notion of restrictable solution is equivalent to the one of infinite cyclical monotonicity of a transport plan, whose definition is the following: Definition 1.2. A transport plan γ ∈ Π(µ, ν) is ∞-cyclically-monotone (∞-cm in the paper) if, for all n ∈ N and (x 0 , y 0 ), . . . , (x n , y n ) ∈ spt(γ), it holds max

1≤i≤n {|x i -y i |} ≤ max 1≤i≤n {|x i -y i+1 |}, (1.2)
where, as usual, we set y n+1 = y 0 .

The infinite cyclical monotonicity is the L ∞ version of the c-cyclical monotonicity, which is a fundamental notion in the classical theory of optimal transportation.

The equivalence between the two definitions above is proven in [START_REF] Champion | The ∞-Wasserstein distance: local solutions and existence of optimal transport maps[END_REF], where it is also proven, under suitable assumptions, that ∞-cm transport plans are induced by maps (see Theorems 3.2 and 4.4 therein, and let us also mention [START_REF] Jylhä | The L ∞ optimal transport: infinite cyclical monotonicity and the existence of optimal transport maps[END_REF] where similar results are extended to more general cost functions). In fact, using the cyclical monotonicity to prove the existence of an optimal transport map was the first way to get around the absence of a satisfying duality theory for the problem (1.1). Indeed, as we said, the energy γ → yx L ∞ γ is non-linear, and not even convex, with respect to the transport plan γ, which makes difficult to guess a dual formulation of (1.1), and this is why this alternative method using cyclical monotonicity together with a regularity property of the transport plan has been introduced. Later on, similar "duality free" methods allowed to prove existence of optimal transport maps for many non-standard cases of cost functions, including the Monge's distance cost for arbitrary norms (see for example [START_REF] Champion | The Monge problem for strictly convex norms in R d[END_REF][START_REF] Champion | The Monge problem in R d[END_REF][START_REF] Jimenez | Optimal transportation for a quadratic cost with convex constraints and applications[END_REF][START_REF] Bertrand | Optimal transport with relativistic cost[END_REF]). However, looking for a (sort of) dual formulation of (1.1) is natural in order to try to find characterization of optimal transport plans: indeed, in the classical theory of optimal transportation, the duality method plays a crucial role not only in the proof of existence of an optimal transport map but also in the characterization of this map. Heuristically, the reasoning which leads to the characterization is the following: from the duality formula

inf c dγ : γ ∈ Π(µ, ν) = sup ϕ dµ + ψ dν : ϕ(x) + ψ(y) ≤ c(x, y) ,
one can deduce that, if γ and (ϕ, ψ) are respectively a minimizer and a maximizing pair for these problems, the condition ϕ ⊕ ψ ≤ c is saturated (in sense that equality holds) on the support of γ. Therefore, if c and ϕ are regular enough, one can deduce

∇ 1 c(x, y) = ∇ϕ(x) for γ-a.e. (x, y) ∈ (R d ) 2 .
If the cost function c is such that this relationship may be inverted, one concludes that an optimal transport maps exists and is characterized by ϕ (namely, it is exactly the map x → (∇ 1 c(x, •)) -1 (∇ϕ(x))). Following these arguments, Brenier [START_REF] Brenier | Décomposition polaire et réarrangement monotone des champs de vecteurs (in French)[END_REF][START_REF] Brenier | Polar factorization and monotone rearrangement of vector-valued functions[END_REF] proved the existence of an optimal map for the quadratic cost and that this map is induced by a convex potential; it must then be a solution of the Monge-Ampère equation, which serves as basis for a whole regularity theory of optimal transport maps, cf. [START_REF] Villani | Topics in optimal transportation[END_REF]Chapter 4]. Similar results have been generalized to a much larger class of cost functions, first for strictly convex costs with respect to the difference [START_REF] Gangbo | Optimal maps in Monge's mass transport problem[END_REF][START_REF] Gangbo | The geometry of optimal transportation[END_REF][START_REF] Caffarelli | Allocation maps with general cost functions[END_REF] and later on for those satisfying the so-called twist condition, see [START_REF] Fathi | Optimal transportation on non-compact manifolds[END_REF][START_REF] Champion | On the twist condition and c-monotone transport plans[END_REF]. These arguments cannot be reproduced for the cost functionals for which the existence of solutions (ϕ, ψ) is not known (see for instance [START_REF] Bertrand | Kantorovich potentials and continuity of total cost for relativistic cost functions[END_REF][START_REF] Louet | On the continuity of the total cost in the mass transport problem with relativistic cost functions[END_REF] for recent progresses in this direction in special cases) and even, for our L ∞ problem (1.1), the meaning of "dual formulation" is itself not clear. Yet, although the functional γ → yx L ∞ γ is not convex, it is still level-convex (in the sense that the level sets of the functional are convex sets and this, sometimes, goes under the name of quasi-convex). Then it is still possible to consider a (sort of) duality theory. This theory has been recently introduced and investigated by Barron, Bocea and Jensen in [START_REF] Barron | Duality for the L ∞ optimal transport problem[END_REF] where it is proven that the minimal value of (1.1) is equal to

inf λ≥0 sup λ + ϕ dµ + ψ dν : ϕ(x) + ψ(y) ≤ 0 whenever |y -x| ≤ λ , (1.3)
and that the infimum with respect to λ in

(1.3) is attained for λ = W ∞ (µ, ν) (see the next section for more details). It follows that W ∞ (µ, ν) is the smallest λ such that sup ϕ dµ + ψ dν : ϕ(x) + ψ(y) ≤ 0 whenever |y -x| ≤ λ = 0.
Unfortunately, the supremum with respect to (ϕ, ψ) always admits a trivial solution ϕ = ψ = 0. It is therefore important to look for the "most interesting solutions" of this dual problem, and to study what information can be obtained from them about the optimal plans for (1.1).

The aim of this paper is to provide, in the one-dimensional case, a solution of the dual problem (1.3) which is non constant as much as possible. More precisely, if (ϕ, ψ) is a solution of (1.3) for λ = W ∞ and γ is a fixed optimal transport plan for (1.1), one can at least formally notice that ϕ is locally constant around any point x which is sent by γ at smaller distance that W ∞ (see below a more precise statement in Prop. 2.2). In the present paper, we construct a pair (ϕ, ψ) of solutions of (1.3) (see Theorem 3.6) from a fixed infinite cyclically monotone transport plan γ, and such that ϕ is a BV function whose derivative is exactly supported on the set of points which are moved by γ at maximal distance: in this sense, our solution has a maximal set of variation. As an application, we will prove that there exists a set of points of the support of the source measure which are displaced at maximal distance by all the optimal transport plans for (1.3); in particular, this set is shared by all the infinitely cyclically monotone transport plans. Moreover, we prove that any optimal transport plan for (1.1) must exactly coincide with the infinitely cyclically monotone one on the set of points which are displaced at maximal distance. The proofs of both these results are based on the properties of the non trivial solution (ϕ, ψ) that we construct for the dual problem.

The potentials we construct only carry informations on the points which are moved at maximal distance by all the optimal plans. This fact is not surprising: indeed, as we said, the points which are moved at non-maximal distance by a transport plan are in some sense "not relevant", since the plan can be modified on a small region around such a point without loosing the optimality. It is then natural that the characterizations provided by this dual formulation only impacts the region where modifications could alter the optimality of a transport plans. In other words, the "zone where ϕ carries some information" (i.e. the zone where ϕ is not locally constant) is exactly the "minimal set of maximal displacement of optimal plans", so that our result is nearly optimal in that sense.

Acknowledgements. The research of the first author is part of the project 2010-A2TFX2 Calcolo delle Variazioni funded by the Italian Ministry of Research, and has been partially financed by the Fondi di ricerca di ateneo of the University of Pisa. The second author acknowledges the support of PGMO project MACRO, funded by EDF and Fondation Mathématique Jacques Hadamard, and of the Laboratoire Ypatia des Sciences Mathématiques (LYSM). He also acknowledges the hospitality of Universities of Pisa and of Florence during several research visits where part of this work has been done.

Notations and the dual problem

In this section, we quickly collect all the notations and known facts of measure theory and optimal transportation that we will use throughout the paper.

Let X and Y be two Polish spaces, and µ, ν be two positive measures on X, Y whose total masses are finite and equal. We denote Π(µ, ν) the set of transport plans from µ to ν, that is, the set of positive measures on X × Y satisfying for any Borel sets A ⊂ X and B ⊂ Y, γ(A × Y ) = µ(A) and γ(X × B) = ν(B); recall that this constraint can be reformulated as

for any (u, v) ∈ C b (X) × C b (Y ), u(x) dγ(x, y) = u dµ and v(y) dγ(x, y) = v dν.
In our settings, X = Y = R d (and d = 1 along almost the whole paper) and the "primal" problem that we consider is the minimization of the supremal functional (1.1) above. We will denote by O ∞ (µ, ν) the set of its minimizers. The definition of an infinitely cyclically monotone transport plan has been recalled in the introduction, see Definition 1.2. We will use by simplicity the abbreviation "∞-cm plan"; recall that, from [8, Theorems 3.2 and 4.4], we know that at least one such plan exists provided µ, ν are both compactly supported in R d , and that these plans are exactly those which are restrictable solutions of (1.1), in sense given by Definition 1.1.

The following "dual problem" was introduced in Theorem 2.3 and Remark 2.4 of [START_REF] Barron | Duality for the L ∞ optimal transport problem[END_REF].

Theorem 2.1 (Duality formula for the L ∞ -optimal transport problem). Let µ, ν ∈ P(R d ) be compactly supported. For any λ > 0, denote by U λ the set of couples (ϕ, ψ) ∈

L 1 µ × L 1 ν such that, for µ-a.e.
x and ν-a.e. y, the inequality ϕ(x) + ψ(y) ≤ 0 holds whenever |y -x| ≤ λ. Then,

W ∞ (µ, ν) = inf λ≥0 sup λ + ϕ dµ + ψ dν : (ϕ, ψ) ∈ U λ ,
and the infimum with respect to λ is attained for λ = W ∞ (µ, ν).

For shorter notations we introduce λ C := W ∞ (µ, ν) where C stands for critical. As a consequence

max ϕ dµ + ψ dν : (ϕ, ψ) ∈ U λ C = 0 (2.1)
and we observe that, given an optimal transport plan γ for the primal problem (1.1), a pair (ϕ, ψ) is optimal for the dual problem (2.1) if and only if the equality ϕ(x)+ψ(y) = 0 holds for γ-a.e. (x, y). Such functions ϕ, ψ will be then called Kantorovich potentials.

We notice that among the maximizers for problem (2.1) above there are always ϕ ≡ 0 and ψ ≡ 0. The duality conditions impose a strong constraint on the variability of the Kantorovich potentials which make difficult to find non trivial couples. We explain this in the next Proposition.

Proposition 2.2. Let (ϕ, ψ) ∈ L 1 µ ×L 1 ν be Kantorovich potentials and let γ be an optimal transport plan. Then µ is concentrated on a set L such that if x ∈ L has the property max

(x,y)∈spt(γ) |x -y| = λ < λ C , (2.2)
then there exists ε > 0 such that ϕ is constant in B(x, ε) ∩ L

Proof. First we observe that since the distance is continuous and spt(γ) is closed, there exists ε > 0 such that for every x ∈ B(x, ε)

max (x,y)∈spt(γ) |x -y| < λ + λ C -λ 2 < λ C .

Denote by D

c := {(x, y) ∈ R d × R d | |x -y| ≤ λ C }, and let N µ and N ν be such that µ(N µ ) = ν(N ν ) = 0 and ϕ(x) + ψ(y) ≤ 0 on D c \ (N µ × R d ∪ R d × N ν ).
Denote by Γ the set on which γ is concentrated and such that

ϕ(x) + ψ(y) = 0 for all (x, y) ∈ Γ. Finally let Γ := Γ \ (N µ × R d ∪ R d × N ν ).
We will prove that L = π 1 ( Γ) has the desired property.

We prove that if x ∈ L is such that max

(x,y)∈spt(γ) |x -y| = λ < λ C then for all x ∈ B(x, λ C -λ) ∩ L ϕ(x) ≤ ϕ(x), i.e.
x is a local maximum for ϕ on the set L which has full µ-measure. Since x ∈ L there exists y such that (x, y) ∈ Γ (so

x ∈ N µ nor y ∈ N ν ). Let x ∈ L ∩ B(x, λ C -λ), we have |x -y| ≤ λ C and again x ∈ N µ and y ∈ N ν it follows that ϕ(x) + ψ(y) ≤ 0 and then ϕ(x) ≤ -ψ(y) = ϕ(x).
If, in the first step of the proof, we choose ε < λ Cλ 4 and we take x ∈ B(x, ε) ∩ L, by symmetry, we also have

ϕ(x) ≤ ϕ(x)
which concludes the proof.

Construction of non-trivial potentials

In this section, we construct, in the one-dimensional case, a couple of Kantorovich potentials (ϕ, ψ) which are not locally constant on the largest possible set. Our assumptions on the data are that µ, ν are two probability measures on R with compact support and without atoms.

We will use the following notations:

• as before, we denote by λ C the optimal value of the problem (1.1), and by O ∞ the set of optimizers; • for any γ ∈ O ∞ , we introduce the sets

M + γ := {(x, y) ∈ spt(γ) : y -x = λ C } , M - γ := {(x, y) ∈ spt(γ) : y -x = -λ C } , M γ := M + γ ∪ M - γ and M + γ = π 1 (M + γ ), M - γ = π 1 (M - γ ), M γ = π 1 (M γ )
, where π 1 is the projection on the first variable (π 1 (x, y) = x for any (x, y) ∈ R 2 ). We notice that M + γ , M - γ are, respectively, the sets of points which are moved by γ at maximal distance to the right or to the left. We will then call M γ the Maximal displacement set of γ. We also observe that M + γ , M - γ , M γ and M + γ , M - γ , M γ are compact subsets of R 2 and R respectively; moreover, the sets M + γ and M - γ are never simultaneously empty (and so is not M γ ). Remark 3.1. Let A ⊂ R be a compact set a point x ∈ A will be called right-extreme point of A (resp. left-extreme point of A) if there exists δ > 0 such that the interval ]x, x + δ[ (resp. ]xδ, x[) does not intersect A. We notice that since A is closed, the set R \ A may be written as

R \ A = i ]a i , b i [
where the union is taken on an at most countable set of indexes i. In particular, the left-extreme and right-extreme points are all part of the a i , b i , so that such points are at most countably many: since µ and ν have no atoms, the sets of left-extreme or right-extreme points of any closed set have always zero mass for µ, ν.

3.1.

Properties of the maximal displacement set of ∞-cm plans. In this paragraph, we fix an ∞-cm plan γ. Actually, in the one-dimensional context, it can be proven that such a γ is necessarily induced by a monotone map T , in sense that γ = (id × T ) # µ where T is non-decreasing and T # µ = ν and that such a map T is unique up to µ-negligible sets, see [START_REF] Santambrogio | Optimal transport for applied mathematicians[END_REF]Chapter 2]; the support of γ is then exactly the set of points x, lim t→x t<x

T (t) : x ∈ spt µ x, lim t→x t>x T (t) : x ∈ spt µ
for a well-chosen representative of T . However, since the only property that we really use is the formula (1.2) itself, we will not enter into more details concerning the characterization of spt γ.

We can then prove some additional properties of the maximal displacement set.

Lemma 3.2. For any x ∈ M + γ , the intersection ]x, x + 2λ C [∩M - γ is empty. Similarly, if x ∈ M - γ , then ]x -2λ C , x[∩M + γ = ∅. Proof.
We give a proof of the first case, being the second analogous. Assume by contradiction that there exists some z ∈ M - γ such that x < z < x + 2λ C . Both (z, zλ C ) and (x, x + λ C ) belong to the support of γ, so that the ∞-cm property implies

λ C = max |(z -λ C ) -z|, |(x + λ C ) -x| ≤ max |(z -λ C ) -x|, |(x + λ C ) -z| . (3.1)
On the other hand, the fact that x < z < x + 2λ C implies immediately that the righthandside in (3.1) is smaller than λ C and this is a contradiction.

Lemma 3.3. The set M + γ ∩ M - γ is finite.
Proof. Since M + γ ∩ M - γ is included in the support of µ, which is bounded, it is sufficient to prove that all of its points are isolated, and this is true since, by Lemma 3.2, above, if

x ∈ M + γ ∩ M - γ , then (M + γ ∩ M - γ )∩]x, x + 2λ C [= ∅ and (M + γ ∩ M - γ )∩]x -2λ C , x[= ∅. 3.2.
Construction of a non-trivial potential. In this paragraph, starting from an ∞-cm optimal transport plan γ, we introduce a couple (ϕ, ψ) of non-trivial solutions of the dual problem (2.1). The couple enjoys the property that the points around which ϕ is not locally constant are exactly those that γ moves at maximal distance i.e. those of M γ . We will need the following lemma of measure theory. Lemma 3.4. There exists two positive measures ρ + , ρ -on R, having finite mass and such that, denoting by ρ = ρ +ρ -, the following properties are satisfied:

(i) spt ρ + = M + γ , spt ρ -= M - γ and spt ρ = M γ ; (ii) for any point x of M +
γ which is a left-extreme or a right-extreme of M + γ , we have ρ({x}) > 0.

Proof. By lemma 3.3, the set M + γ ∩M - γ is finite, we denote by {z 1 , . . . , z N } the (possibly empty) set of its elements. We also select two at most countable (and also possibly empty) families (x i ) i , (y j ) j of points of M + γ \ M - γ , and of M - γ \ M + γ which are dense in M + γ \ M - γ and M - γ \ M + γ respectively. Moreover, by Remark 3.1, the left-isolated (resp. right-isolated) points of M + γ are at most countably many, so we can assume that all of them are part of the family (x i ) i or (z k ) k . It is then straightforward to check that the measures

ρ + := i 2 -i δ x i + N k=1
δ z k and ρ -:= Theorem 3.6. The functions ϕ r and ψ r defined above satisfy the following properties:

(i) ϕ r has bounded variation (in particular, it has a left-limit and a right-limit at any point) and is right-continuous; (ii) the support of (ϕ ′ r ) -is exactly M + γ , and the support of

ϕ ′ r is exactly M γ ; (iii) for any point x ∈ M + γ which is left-isolated or right-isolated in M + γ , we have lim x→x x<x ϕ(x) > ϕ r (x);
(iv) the couple (ϕ r , ψ r ) is a Kantorovich potential, i.e. a maximizer of (2.1).

In some sense, Property (ii) of Theorem 3.6 means that the potential ϕ r is "optimal with respect to γ": indeed, Prop. 2.2 suggests that, for any potential ϕ having bounded variation, the support of ϕ ′ should not be larger than M γ , as ϕ should be locally constant anywhere else. Moreover, we will that the smallest possible M γ among the optimal plans γ is actually achieved by the ∞-cm transport plans (cf. Th. 4.2 below).

Proof of Theorem 3.6. By definition ϕ r is the cumulative distribution function of the measure -ρ, then it is a BV function whose distributional derivative is the measure -ρ; this and the definition of ρ classically imply the properties (i) and (ii). As for (iii), let x be an isolated point of M + γ . Then, for any

x < x, ϕ r (x) -ϕ r (x) = -ρ(]x, x]) = -ρ({x}) -ρ(]x, x[).
By Property (ii) of Lemma 3.4 we have ρ({x}) > 0 while the other term in the last equality vanishes as x → x, which proves (iii).

It remains to show that (ϕ r , ψ r ) is a pair of Kantorovich potentials. First of all, from the definition of ψ r , it follows that for any (x, y) ∈ R 2 with |y -x| ≤ λ C , ϕ r (x) + ψ r (y) ≤ 0. This proves that (ϕ r , ψ r ) is an admissible couple for the dual problem. We moreover claim that ϕ r (x) + ψ r (ȳ) = 0 for γ-a.e. (x, y);

(3.2)
more precisely, we will prove that, if (x, ȳ) ∈ spt µ × spt ν is such that (3.2) does not hold, then either x belongs to an at most countable subset of spt µ or ȳ belongs to an at most countable subset of spt ν. This will be enough to prove (iv) since it implies that ϕ r dµ + ψ r dν = (ϕ r (x) + ψ r (y)) dγ(x, y) = 0, so that (ϕ r , ψ r ) is optimal. Let (x, ȳ) be a point of spt(γ) such that ϕ r (x) + ψ r (ȳ) < 0. Then:

-ϕ r (x) > ψ r (ȳ) = inf -ϕ r (x) : x ∈ [ȳ -λ C , ȳ + λ C ] .
We deduce that there exists z ∈ [ȳλ C , ȳ + λ C ] such that ϕ r (z) > ϕ r (x), and we distinguish the cases z < x and z > x.

First case: z < x. In this case, the definition of z reads

ϕ r (x) -ϕ r (z) = -ρ(]z, x]) < 0.
In particular, there exists z ′ ∈]z, x] which belongs to M + γ , so that (z

′ , z ′ + λ C ) ∈ spt(γ). Then, notice that max |ȳ -x|, |(z ′ + λ C ) -z ′ |} = λ C (3.3) and consider max |ȳ -z ′ |, |(z ′ + λ C ) -x|}. (3.4)
By the cyclical monotonicity of γ, the max in (3.4) must be at least λ C too, meaning that either |ȳz ′ | or |(z ′ + λ C ) -x| is larger or equal to λ C . Now:

• From the fact that z ′ ∈ (z, x] and that z, x ∈ [ȳλ C , ȳ + λ C ], we have

-λ C < z ′ -ȳ ≤ x -ȳ ≤ λ C .
Therefore, the inequality |ȳz ′ | ≥ λ C is only possible if z ′ = x = ȳ + λ C . This implies that x belongs to M + γ ∩ M - γ , which is finite by Lemma 3.3. • On the other hand, using again that z

′ ∈]z, x] and z, x ∈ [ȳ -λ C , ȳ + λ C ], we observe -λ C ≤ ȳ -x < z ′ + λ C -x ≤ λ C . The inequality |(z ′ + λ C ) -x| ≥ λ C can then only hold if x = z ′ .
In this case, both (x, ȳ) and (x, x + λ C ) belong to the support of γ. As a consequence of ∞-cm condition, for every (x, y ′ ) ∈ spt γ with ȳ < y ′ < x + λ C it must hold x = x (in fact, if x < x the couples (x, y ′ ) and (x, ȳ) would violate the condition while if x < x the bad couples would be (x, y ′ ) and (x, x + λ C )). It follows that

0 = µ({x}) = γ({x} × R) ≥ γ({x}×]ȳ, x + λ C [) = γ(R×]ȳ, x + λ C [) = ν(]ȳ, x + λ C [).
Then ȳ is a right-isolated point of spt ν which, as discussed in Remark 3.1, are at most countably many.

Second case: z > x. This case is treated in a very similar way as the previous one. First of all, we start by deducing from the inequality ϕ r (z) > ϕ r (x) that there exists z ′ ∈ (x, z] such that (z ′ , z ′λ C ) ∈ spt(γ). Then, by the ∞-cm condition,

λ C = max |ȳ -x|, |(z ′ -λ C ) -z ′ | ≤ max |ȳ -z ′ |, |(z ′ -λ C ) -x|}, (3.5) so that either |ȳ -z ′ | or |z ′ -λ C -x| is at least equal to λ C . On the other hand, the fact that z ′ ∈ (x, z] with ȳ -λ C ≤ x ≤ z ≤ ȳ + λ C enforces -λ C < z ′ -λ C -x ≤ ȳ -x ≤ λ C . (3.6) and -λ C < z ′ -ȳ ≤ λ C (3.7)
Therefore, the condition (3.5) is only satisfied in the two following cases:

• there is equality in the two last inequalities of (3.6): in this case, we have simultaneously z ′ = ȳ +λ C and x = ȳ -λ C . Therefore, (ȳ -λ C , ȳ) and (ȳ +λ C , ȳ) both belong to the support of γ: this means that ȳ ∈ M + γ ∩ M - γ , where γ is the "symmetric plan" of γ, that is γ = τ # γ with τ (x, y) = (y, x).

The transport plan γ (which belongs to Π(ν, µ)) being itself ∞-cm , Lemma 3.3 also applies, yielding finiteness of M + γ ∩M - γ . Therefore, the equality case in (3.6) is only possible for a finite number of ȳ.

• If there is equality in the last inequality of (3.7), we deduce that both (x, ȳ) and (ȳ + λ C , ȳ) belong to the support of γ, with x < ȳ + λ C . As in the previous case, we conclude that x is a boundary point of one of the connected components of R \ (spt µ), which are at most countably many thanks to Remark 3.1, concluding the proof of (iv).

Application: existence of a minimal set of maximal displacements

In this section, we will use the pair of Kantorovich potentials provided by Theorem 3.6 to get some informations on general optimal transport plans for (1.1) (not necessarily ∞-cm ). Since any optimal plan γ is concentrated on the set (x, y) ∈ R 2 : ϕ r (x) + ψ r (y) = 0 and |y -x| ≤ λ C , it is natural to start by collecting some properties of this set. This is the goal of the following proposition: roughly speaking, it suggests that, if x belongs to M + γ , its only possible "image" by an optimal transport plan γ is x + λ C . Proposition 4.1. For any x, denote by

B r (x) := y ∈ [x -λ C , x + λ C ] : ϕ r (x) + ψ r (y) = 0 . Let x ∈ M + γ . Then, for any x such that x ≤ x < x + 2λ C , we have B r (x) ⊆ [x + λ C , x + λ C ]. In particular, the set B r (x) is reduced to {x + λ C }.
Proof. Let us fix x ∈ M + γ and select x ∈ [x, x + 2λ C [. By definition, all the elements of B r (x) are at most equal to x + λ C , thus we only have to prove that B r (x) does not contain any y which is smaller than x + λ C . Consider then y with xλ C ≤ y < x + λ C , and let us prove that the equality ϕ r (x) + ψ r (y) = 0 can not hold. We observe that, by Lemma 3.2, if x > x then ρ -(]x, x]) = 0, so that

ϕ r (x) ≥ ϕ r (x) (4.1)
which is of course also true when x = x. On the other hand, by definition of ψ r and since [y

-λ C , x[⊂ [y -λ C , y + λ C ],
we also have

ψ r (y) ≤ inf -ϕ r (z) : y -λ C ≤ z < x . (4.2)
From (4.1) and ( 4.2), it is clear that proving that

∃z ∈ [y -λ C , x[, ϕ r (z) > ϕ r (x) (4.3)
would be enough to conclude that ψ r (y) < -ϕ r (x). We prove (4.3) by separating two cases.

• First case: x is a left-isolated point of M + γ . In this case, Property (iii) of Theorem 3.6 ensures lim

z→x z<x ϕ r (z) > ϕ r (x)
which is clearly enough to find the desired z.

• Second case: x is not a left-isolated point of M + γ . Let us select some x ∈]x - λ C , x[∩M +
γ . By applying Lemma 3.2 to x, we know that ]x, x] ∩ M - γ = ∅. From this fact and since x is a left-cluster point of M + γ , we deduce ρ + (]x, x]) > 0 and ρ -(]x, x]) = 0 which implies ϕ r (x) > ϕ r (x), as expected.

We are now able to state the next main result of this paper, which in particular asserts the existence of a "minimal set of maximal displacements", which is shared by all the optimal transport plans: Theorem 4.2. Let γ, γ ∈ O ∞ be optimal transport plans and assume that γ satisfies the ∞-cm -condition. Then

M + γ ⊆ M + γ and M - γ ⊆ M - γ .
In other words, there are two compact sets M + and M -which are "minimal sets of maximal displacement for optimal plans", in sense that, for any optimal plan γ,

M + ⊆ M + γ and M -⊆ M - γ
with equality if γ is an ∞-cm plan (and in particular, all the ∞-cm plans have same set of maximal displacements).

Proof. First we consider some consequences of Prop. 4.1 for γ.

Step I. For any x ∈ M + γ , the quarter of plane Q := [x, +∞) × (-∞, x + λ C ] has zero mass for γ. To prove this result, we first observe that, by the optimality of γ and of (ϕ r , ψ r ) it follows that γ is concentrated on the set B := (x, y) ∈ R 2 : |y -x| ≤ λ C and ϕ r (x) + ψ r (y) = 0 which can be written as (x, y) : y ∈ B r (x) . Now, for x ≥ x and y ∈ B r (x) we have:

• if x < x + 2λ C , then Prop. 4.1 ensures that y ≥ x + λ C ; • if x ≥ x + 2λ C , the same holds since |y -x| ≤ λ C .
This exactly means that B has no intersection with the interior of the quarter of plane Q, which has therefore zero mass for γ; since moreover the lines {x} × R and R × {x + λ C } have also zero mass for γ (because µ and ν are non atomic), the Step I is proven.

Step II: if there exists

x ∈ M + γ \ M + γ , then such an x satisfies µ([x, x + δ]) = ν([x + λ C -δ, x + λ C ]) = 0 for δ > 0 small enough.
Let x be such a point; since x / ∈ M + γ , we can select δ > 0 such that the square with side-length 2δ and centered in the point (x, x + λ C ) has zero γ-measure. Without loss of generality we may also assume that 0 < δ < λ C . Since µ is the first marginal of γ, we then have

µ([x, x + δ]) = γ([x, x + δ] × R). Since x ∈ M + γ the result of Step I applies and gives γ([x, x + δ] × (-∞, x + λ C ]) = 0, so that γ([x, x + δ] × R) = γ([x, x + δ] × [x + λ C , +∞)).
Moreover, since γ is an optimal transport plan, we have |y -x| ≤ λ C for γ-a.e. (x, y); in particular, for γ-a.e. (x, y) with x ≤ x + δ, we have y

≤ x + δ + λ C . Consequently, γ([x, x + δ] × [x + λ C , +∞)) = γ([x, x + δ] × [x + λ C , x + λ C + δ]),
which is zero since, by assumption on x and δ, the square [xδ, x + δ] × [x + λ Cδ, x + λ C + δ] has zero mass for γ. The three last equalities imply that µ([x, x + δ]) = 0. The proof of the other equality is similar, and may be described as follows:

ν([x + λ C -δ, x + λ C ]) = γ(R × [x + λ C -δ, x + λ C ]) since ν = (π 2 ) # γ = γ((-∞, x] × [x + λ C -δ, x + λ C ]) by Step I = γ([x -δ, x] × [x + λ C -δ, x + λ C ]) since |y -x| ≤ λ C γ-a.e.
= 0 by assumption.

Step III: M + γ ⊂ M + γ . By contradiction, assume that there exists x ∈ M + γ which does not belong to M + γ . Since γ is concentrated on the half-space (x,

y) ∈ R 2 : y ≤ x+λ C , we notice that γ([x -δ, x] × [x + λ C , x + λ C + δ]) = 0
because, in this square, only the point (x, x + λ C ) satisfies |y -x| ≤ λ C and γ has no atom (because µ and ν don't). From this property, and from the fact that γ gives no mass to any horizontal or vertical line, it follows

γ([x -δ, x + δ] × [x + λ C -δ, x + λ C + δ]) = γ([x, x + δ] × [x + λ C -δ, x + λ C + δ]) + γ([x -δ, x] × [x + λ C -δ, x + λ C ]). (4.4)
But, from the result of Step II, it follows that

γ([x, x + δ] × [x + λ C ± δ]) ≤ γ([x, x + δ] × R) = µ([x, x + δ]) = 0 and that, similarly, γ([x -δ, x] × [x -λ C -δ, x -λ C ]
) is zero. The equality (4.4) therefore implies that the open square with side-length 2δ and with center (x, x + λ C ) has zero mass for γ, which gives the desired contradiction and concludes Step III.

Step IV: M - γ ⊂ M - γ . Consider the "opposite transport plans" γ neg := χ # γ γ neg := χ # γ where χ(x, y) = (-x, -y).

It is clear that γ neg , γ neg have same marginals which are atomless and compactly supported (they are dµ(-x) and dν(-y)), have same maximal displacement which is still equal to λ C and that γ neg is still an ∞-cm plan, and that

x ∈ M + γ neg ⇐⇒ (-x) ∈ M - γ and x ∈ M + γneg ⇐⇒ (-x) ∈ M - γ .
We can then apply the result if Steps I-III to the plans γ neg and γ neg , which concludes the proof.

We conclude this paper with a description of the general structure of an optimal transport plans for (1.1). This result is very similar to the one obtained in [START_REF] Marino | The entropic regularization of the Monge problem on the real line[END_REF]Prop. 3.1] in the L 1 context. The optimal plans are constrained to coincide with the graph of the translation of ±λ C on the critical regions M ± γ while on any maximal interval I ⊂ R\M γ , they are free to "fill" the whole region {|y -x| ≤ λ C }∩(I ×I ±λ C ) provided the marginal constraint is satisfied.

In order to make precise this description, let us introduce some additional notations. Let a < b be the lower and upper bounds of spt µ and c < d be those of spt ν. We then set, for each i,

c i =    c if a i = a, a i + λ C if a i ∈ M + γ and a i = a, a i -λ C if a i ∈ M - γ , a i / ∈ M +
γ and a i = a and similarly

d i =    d if b i = b, b i -λ C if b i ∈ M - γ and b i = b, b i + λ C if b i ∈ M + γ , b i / ∈ M - γ and b i = b.
Roughly speaking, each c i (resp. d i ) is "the image" of a i (resp. b i ) by the infinitely cyclically monotone transport plan γ. In particular, they satisfy the following property. Proof. Fix i = j ∈ I; assume for instance that a i < b i ≤ a j < b j . It is then enough to prove that d i ≤ c j . From the definition of d i , c j , it turns out that the only case we need to treat is

d i = b i + λ C and c j = a j -λ C .
This case corresponds to to

a j = a, a j ∈ M - γ \ M + γ , b i = b, ∈ M + γ \ M - γ
and in particular implies that b i < a j (otherwise these equal points would belong to

M + γ ∩ M - γ ).
From the fact that the points (b i , b i + λ C ) and (a j , a jλ C ) both belong to the support of the ∞-cm plan γ, we then deduce

|b i + λ C -a j | ≥ λ C . (4.5)
Assume now that d i > c j , i.e. that b i + λ C > a jλ C . Then, since moreover b ia j > 0, we deduce that the inequality (4.5) does not hold, a contradiction.

As for the second point, let i ∈ I, consider ȳ ∈ (c i , d i ) and let us prove that x := ȳ-λ C does not belong to M + γ . By definition of (a i , b i ), this is clearly true if a i < x < b i , thus we only need to consider the cases x ≤ a i and x ≥ b i .

Assume first that x ≤ a i . If this is an equality, this implies a i ∈ M + γ thus c i = a i + λ C (this is also true in this case a i = a ∈ M + γ ): since ȳ = x + λ C = a i + λ C > c i , this is impossible. If now the inequality x ≤ a i is strict, then one has x = ȳλ C < a i and c i < ȳ from which we deduce c iλ C < a i . In particular, we are in the cases "a i = a" or "a i ∈ M - γ \ M + γ " of the definition of c i . If a i = a, the inequality x < a i leads to x / ∈ spt µ so that x / ∈ M + γ , as expected; if now

a i ∈ M - γ \ M + γ , then from Lemma 3.2, we deduce (a i -2λ C , a i ) ∩ M + γ = ∅. Since x < a i , c i < ȳ, c i = a i -λ C and ȳ = x+ λ C , it is easy to see that x ∈ (a i -2λ C , a i ), so that it cannot belong to M + γ . In the case x ≥ b i we have x ≥ b i , x = ȳ -λ C and ȳ < d i from which we deduce d i > b i + λ C . But from the definition of d i , we can see that (b i , d i ) must belong to the support of γ so that d i ≤ b i + λ C , which is a contradiction.
The last part of Lemma 4.3, namely the fact that ȳ + λ C never belongs to M - γ for any ȳ ∈ (c i , d i ), can be proven in a very similar way.

Having at hand the last notations and the result of Lemma 4.3, we can now state the structural result which characterizes all the one-dimensional optimal plans for (1.1). Theorem 4.4. For each i, denote by

µ i := µ⌊[a i , b i ] and ν i = ν⌊[c i , d i ].
Then, for each i, µ i and ν i have same total mass. Moreover, the optimal plans γ for the problem (1.1) are exactly those which can be written as

γ = (id × (id + λ C )) # (µ⌊M + γ ) + (id × (id -λ C )) # (µ⌊M - γ ) + i γ i (4.6)
where, for each i, γ i is a transport plan from µ i to ν i such that |y -x| ≤ λ C for γ ia.e. (x, y).

Proof. Let γ ∈ O ∞ (µ, ν), we will prove that it satisfies (4.6). Again we divide the proof in several steps.

Step I: the measure γ⌊

(M + γ × R) (resp. γ⌊(M - γ × R)) is concentrated on the line {y = x + λ C } (resp. {y = x -λ C }). Let (x, ȳ) be such that for any ε > 0, γ ([x -ε, x + ε] ∩ M + γ ) × [ȳ ± ε] > 0
, we prove that, for γ-a.e. such (x, ȳ), ȳ is necessarily equal to x + λ C . Assume by contradiction that ȳ < x+ λ C (the converse inequality can not hold since γ ∈ O ∞ (µ, ν)); without loss of generality, we may assume that x is not a left-isolated point of M + γ , since such points are countably many. Select then x ∈ M + γ such that 0 < xx < (x + λ C )ȳ.

Since x ∈ M + γ by Th. 4.2 implies that γ([x, +∞) × (-∞, x + λ C ]) = 0.

In particular, for ε > 0 such that xε > x and ȳ < (x + λ C )ε, we obtain γ([xε, x + ε] × [ȳε, y + ε]) = 0, in contradiction withthe starting point. This proves that γ⌊(M + γ × R) is concentrated on the line {y = x + λ C }; the same for γ⌊(M - γ × R) can then be obtained by considering the "opposite transport plans" γ neg , γ neg , as in Step IV of the proof of Theorem 4.2.

Step II: for any i, the plan γ⌊( By definition of c i , this is obvious if a i = a; moreover, in the case c i = a iλ C , we have for γ-a.e. (x, y) with x ≥ a i :

y ≥ x -λ C ≥ a i -λ C = c i .
Then we need to look at the case c i = a i + λ C , which corresponds to a i ∈ M + γ , and this, again, follows from the first step of Th. 4.2.

To conclude we have to prove that Step III: conclusion. Let us define γ -:= γ⌊(M - γ × R), γ + := γ⌊(M + γ × R) and γ i := γ⌊([a i , b i ] × R) for each i. It is clear that γ = γ -+ γ + + i γ i , and that γ -, γ + have µ⌊M - γ , µ⌊M + γ as respective first marginal. Moreover, Step I proves that γ -(resp. γ + ) is the transport plan induced by idλ C (resp. id + λ C ). Therefore, it remains to prove that, for each i, γ i has µ i , ν i as marginals. Let us then fix i ∈ I; again the fact that (π 1 ) # γ i = µ i for each i is a direct consequence of the definition of γ i . Moreover, γ i is dominated by γ and, by Step II, is concentrated on (a i , b i ) × (c i , d i ): therefore

(π 2 ) # γ i ≤ (π 2 ) # γ ⌊(c i , d i ) = ν i .
Assume now that this last inequality is strict: in other words, there exists a Borel set B ⊂ (c i , d i ) such that γ i (R × B) < ν(B). By Lemma 4. Adding all of these equalities, we obtain γ(R × B) < ν(B), which is impossible since γ ∈ Π(µ, ν). This proves that any optimal plan satisfies (4.6). In particular, this implies that µ i and ν i have same total mass for any i, and that

µ⌊M + γ + µ⌊M - γ + i µ i = µ, ν⌊(M + γ + λ C ) + ν⌊(M - γ -λ C ) + i ν i = ν.
For any plan satisfying (4.6) and belonging to Π(µ, ν), the confinement betwen the two lines y = x + λ C and y = xλ C inplies the optimality, concluding the proof.

j 2 -

 2 j δ y j + N k=1 2δ z k satisfy the required property. Define, now, a candidate pair of Kantorovich potentials. Definition 3.5. For x, y ∈ R, we define ϕ r (x) := -ρ((-∞, x]) and ψ r (y) := infϕ r (x) : x ∈ [yλ C , y + λ C ] .

  We can then write ]a, b[\M γ = i∈I ]a i , b i [ where I is an at most countable set and, for each i, ]a i , b i [ is a maximal open interval fully included in ]a, b[\M γ . In particular, all the points a i , b i belong to M γ ∪ {a, b}.

Lemma 4 . 3 .

 43 The intervals ]c i , d i [, i ∈ I, are mutually disjoint. Moreover, for any i, M + γ + λ C and M - γλ C have also empty intersection with ]c i , d i [.

  [a i , b i ] × R) is concentrated on [a i , b i ] × [c i , d i ]. Let i ∈ I, first we prove that γ⌊([a i , +∞) × R) is concentrated on [a i , +∞) × [c i , +∞).(4.7)

  γ⌊((-∞, bi ] × R) is concentrated on (-∞, b i ] × (-∞, d i ]. (4.8) This is again obvious in the cases b i = b and d i = b i + λ C , we thus have only to consider the case d i = b iλ C , which enforces b i ∈ M - γ . Again, it suffices to consider the negative transport plans γ neg , γ neg : observing then that -b i ∈ M + γ neg , we apply Prop. 4.1 to γ neg , γ neg to deduce γ neg ([-b i , +∞) × (-∞, -d i ]) = 0 which proves (4.8).

3 ,

 3 B does not meet any (c j , d j ) with j = i and neither meetsM + γ + λ C , M - γλ C . Therefore the result of Step I also implies γ -(R × B) = γ + (R × B) = γ j (R × B) = 0 for any j = i.


Jin Li

Dechen Zhan
email: dechen@hit.edu.cn

Lanshun Nie

Xiaofei Xu
email: xiaofei@hit.edu.cn

A Construction Approach of Model Transformation Rules Based on Rough Set Theory

Keywords: Model transformation, Model transformation rules, Rough set theory

Model transformation rules are the central part of model transformation. Many model transformation approaches provide some mechanisms to construct transformation rules in industrial and academic research. However, transformation rules are typically created manually in these approaches. As far as we know, there are no complete solutions that construct transformation rules automatically. In this paper, we propose a rough set based approach to construct transformation rules semi-automatically. Construction approach of rough set is improved in order to support the transformations between different meta-models, then the corresponding algorithm to construct transformation rules is presented. We also provide the measurement indicators of transformation rules to support selecting proper rules from many rules which meet transformation requirement. Three kinds of experiments for problems with distinct complexity and size are given for the validation of the proposed method.

Introduction

Model-driven architecture (MDA) is an approach for the development of software systems. Model transformation is a core part of MDA and plays an indispensable role in many different application domains, for instance, to generate code from models, to derive higher-level models from legacy models, to support model driven interoperability, or to compose service models for enterprise interoperability.

However, model transformation involves many repetitive difficulties. Model transformation consists of transformation rules which describe how a set of elements of the source model are transformed into a set of elements of the target model through transformation relationships [START_REF] Kleppe | MDA Explained: The Model Driven Architecture: Practice and Promise[END_REF]. With increasing in number and size of models, the relationships implicated among models reflect gradually more and more uncertainty, incompleteness and inconsistency, etc. Therefore, the efficient design of transformation rules has become a major challenge to model transformation.

A lot of researchers in both academic and industry study on how to implement model transformation and construct transformation rules. For example, model transformation has been well achieved especially in database domain [START_REF] Agrawal | Quest Synthetic Data Generator[END_REF].Usually there are two kinds of approaches for constructing transformation rules. One is that domain experts and model transformation designers capture mapping relationships between source and target metamodel elements, then define transformation rules based on these mapping relationships. It depends on domain experts and model transformation designers to not only understand the knowledge of modeling and model transformation, but also discover the semantic relationships among source and target models, especially implicit relationships. The other is that matching relationships can be discovered from a set of input meta-models through data mining methods [START_REF] Han | Data Mining: Concepts and Techniques[END_REF], and then transformation rules are designed according to these matching relationships [START_REF] Varró | Model transformation by example[END_REF]. It gives enough attention to meta-model transformations, however complex and uncertain relationships among source and target models are difficult to derive and selection from rules set is also a challengeable task.

We introduce rough set [START_REF] Pawlak | Rough sets rudiments[END_REF][START_REF] Liyun | An Approach for Attribute Reduction and Rule Generation Based on Rough Set Theory[END_REF][START_REF] Swiniarski | Rough set methods in feature selection and recognition[END_REF] into the construction process of transformation rules. In doing so, we try to discover both explicit and implicit matching relationships and specify transformation rules. Then we also provide measurement indicator for selecting the proper transformation rules [START_REF] Øhrn | Discernibility and rough sets in medicine: tools and applications[END_REF]. The rest of this paper is structured as follows. In Sect. 2, we propose the motivating example which will be used throughout the paper. Section 3 provides the core concepts and main algorithms and illustrates the construction process of the example. Section 4 designs three kinds of experiments in order to respectively analyze three quantities' influence on transformation rules. Sect. 5 presents related work. Finally, Sect. 6 concludes the paper and further work.

Motivating Example

As the transformation from UML class diagram to relation database model is very common in the field of software system development, in this section, we introduce an example, entitled UCD2RDM, to construct transformation rules which describe how UML class diagram is transformed into relational database model. Both source and target metamodels are illustrated in Fig. We define a source model conforming to UML class diagram and a target model conforming to relational database model. Both models describe the relationships among teachers, students and courses of some educational institution.

The class Teacher can teach one or more courses (Course). The class Student can select one or more courses (Course). According to the teacher's title information, Teacher has a subclass (Professor). Student has also a subclass (Master). Only the class Professor can supervise the master (Master). The model of the educational institution is shown in Fig. 2.

UML Class Model

Relational database Model [START_REF] Pawlak | Rough sets and Boolean reasoning[END_REF]. This paper extends rough set theory to construct transformation rules with three major improvements. Firstly, we present more precisely domain using source and target metamodels in order to discover the mapping among source and target metamodels. Secondly, we redefine the traditional property set to get a new property set that has two kinds of properties: composed by source metamodels and decision properties composed by target metamodels. Finally, we extend the decision table and other correlative concepts. The work will help discover and construct transformation rules.

Basic Concept

For the convenience of description, we introduce some related definitions of model transformation [START_REF] Zhang Tian | MDA Based Design Patterns Modeling and Model Transformation[END_REF]. We also extend some basic notions of rough set theory (i.e. decision tables and decision function) that will be useful in this paper. Definition 3.1 (Directed-role graph): A directed-role graph is defined as

RG = (L, ⊗, ⊕) . (1)
M=(RG, γ, ξ) . ( 2
)
Where RG=(L, ⊗, ⊕) is a directed-role graph; γ is also a directed-role graph, and it can be denoted as RG γ =(L γ , ⊗ γ , ⊕ γ ); each L has a mapping function ξ: L→L γ , and ξ describes all of elements, such as node, relation, role and domain, come from the finite symbol set of RG γ .

Definition 3.3 (Metamodel):

Given two model M 1 =(RG 1 , γ 1 , ξ 1 ),M 2 =(RG 2 , γ 2 , ξ 2 ). if γ 1 =M 2 , that is RG γ =(L γ , ⊗ γ , ⊕ γ )=(RG 2 , γ 2 , ξ 2 ) then M 2 is called the metamodel of M 1 , which denotes M 1 :M 2 .

Definition 3.4 (Model match): A model match is defined as

MMatch= Match ({sm}:MM s ,{tm}:MM t ) .

(

) 3
MMatch builds the relationships between the source{sm} and target{tm} metamodels Definition 3.5 (Model transformation): A model transformation is defined as

MT=∪Match ({sm}:MM s ,{tm}:MM t ) . ( 4
)
MT is a process in which elements of source models are transformed into elements of target models according to MMatch.

Definition 3.6 (Model transformation rule): A model transformation rule is defined as

MTR={sm}:MM s → {tm}:MM t . (5)
If the conditions of the source metamodel are satisfied, the conditions of the target metamodel would be deduced.

Because model transformation language ATL provides simply structure, we use it to describe transformation rules.

Definition 3.7 (Decision table of transformation rules): A decision table of transformation rules is defined as

RT = (M, V, Γ) . ( 6
Γ : M × γ M → V is a determine function, γ M =γ SM ∪γ TM is

, :

γ

SM SM SM mm s mm V V SM V γ ∈ = Γ × →  . ( 7
)
For ∀mm∈γ TM , tm∈TM, then has

γ γ γ , : γ TM TM TM TM mm T mm V V TM V ∈ = Γ × →  . ( 8
)
In decision table decision properties can be unique or not. When some condition properties are satisfied, decisions, operations and actions in decision properties will be executed.

Definition 3.8 (Indiscernibility relation): Let RT=(M, V, Γ) be a decision table, and

B⊆γ SM . Then an indiscernibility relation ∆ B is generated from B and SM with the form

∆ B = {(w 1 ,w 2 ) ∈ SM×SM : Γ (w 1 ,smm) = Γ (w 2 ,smm), ∀smm ∈ B} (9) if (w 1 ,w 2 ) ∈ ∆ B ,
δ B : SM → ρ( Vγ TM ) δ B (w) = { i : ∃w' ∈ SM s.t. w∆ B w', t(w) = i, 1≤ i ≤ r(γ TM ) } . ( 10
)
Where ρ( Vγ TM ) denotes the power set of Vγ TM , and t(w) denotes the value of model element w in the decision property set γ TM .

Definition 3.10 (Indiscernible decision table):

Let RT=(M, V, Γ) be a decision

(δ B ) = { ∀(p, q)∈ SM×SM, then δ B (p) = δ B (q) } . Where RT is called the indiscernible decision table; SM/θ(γ SM )={W 1 , W 2 ,…,W n }, W i (i=1,2,…,n) is the equivalence class of the condition property and i=1 to n; TM/θ(γ TM )={X 1 , X 2 , X m },X j (j=1,2,…,m)
(3) set B'∈B, if B' is independent and ∆' B =∆ B , B' is one of simplified set of B.

Definition 3.12 (Decision matrix of transformation rules):

Let RT= (M, V, Γ) be a decision table, then a decision matrix CM(RT) is defined as

CM(RT) = (m ij ) n×n . ( 11
)
Where

SM/θ(γ SM )={W 1 ,W 2 ,…,W n }, τ(W i ) is the value of the equivalence class W i in the set of condition properties; m ij = { τ ⊆ γ SM : τ(W i ) ≠τ(W j ) 且 δ B (W i ) ≠ δ B (W j ) }
Decision matrix of transformation rules is a symmetric matrix, namely CM(RT) is an upper triangular matrix. (  )

ij kj il i j smm m k i smm m l i smm m B smm smm smm ∈ < ∈ < ∈ = = ∧ ∧ ∨ ∨ ∧ ∨ ∧ . ( 12
)
Where i=1 to n, and let B i be minimal disjunctive normal form (DNF) according to the idempotent rule a∧a=a, the absorption rule a∧(a∨b)=a, and the distributive rule a ∧(b∨c)=(a∧b)∨(a∧c). Decision matrix of transformation rules describes the relationships between equivalence classes(SM/θ(γ SM )) and decision classes(SM/θ(γ TM )). These relationships can be presented using the form W i →X j . W i , called as the precondition of transformation rules, is the minimal disjunctive normal form. X j , called as the decision of transformation rules, is the elements of the target metamodel. We use three measurement indicators [START_REF] Pawlak | Rough set approach to multi-attribute decision analysis[END_REF], i.e. support, accuracy and coverage, in rough set theory to evaluate transformation rules. Support, denoted as support (W j ∧X i ), means the number of objects which satisfy both X i and W j in decision table. Accuracy, denoted as accuracy (W i →X j )=support(W i ∧X j )/support(W i ), is the confidence of the decision of transformation rules. Coverage, denoted as coverage (W i →X j )=support(W i ∧X j )/ support(X j ), means the applicability of transformation rules.

Algorithm for Transformation Rules

In this section, we present a construction algorithm, entitled rsCRT, based on the generation algorithm of rough set theory using UCD2RDM in Sect. 2. There are four sub-algorithms in rsCRT. The main construction process of transformation rules is the following:

(1) Firstly, decision

[] TM/θ(γ TM )={X 1 ,X 2 ,…,X n },SM/θ(γ SM )={W 1 ,W 2 ,…,W m }; for(i=1 to |SM/θ(γ TM )|){W i = SM/θ(γ TM )[i]; for(j=1 to |TM/θ(γ TM )|){X j = TM/θ(γ TM )[j]; if(ξ S (RG S (W i ))∈X j ){ X j .add(RG S (W i )); Support(W i ,X j )=|W i ∩X j |;//support SI(W i ,X j )=|W i ∩X j |/|W i |;//accuracy CI(W i ,X j )=|W i ∩X j |/|X i |;//coverage } } String[][] m ij ={smm∈γ S :smm(X i )≠smm(X j )&Γ(X i ,ξ S (RG S (X i )) = Γ(X j ,ξ S (RG S (X j )} CM(model_tran_rule_dec_table)=(m ij ) n×n ;
In Sub-algorithm 3, the decision class SM/∆γ TM is defined as following:

X 1 = Teacher∪Professor∪Course∪Student∪Master∪ Teaching∪Selecting∪Supervising X 2 = TID∪CID∪SID∪TName∪CName∪SName X 3 = title∪tutor We apply this algorithm and obtain the decision matrix. The result is shown in

We apply Sub-algorithm 3 and get the transformation rules, as shown in Table 3. The transformation rules can be selected according to their measurement indicators, for example, we can select the rule through coverage. The highest coverage of the rule between Class and Table is 0.25, and the coverage of the rule between Relation and Table is 0.30, and the coverage of the rule between Property and Column is 0.27. The three kinds of transformation rules described using ATL are shown in Fig. 3. Note that according to the inclusion relationship between Class and Property, like Table and Column, the rule between Property and Column is consisted in the rule Class2Table and Relationship2Table.

These sub-algorithms are central components of rsCRT, so they determine the time complexity of rsCRT. Sub-algorithm 1 is used to generate the decision table through searching elements of the source and target model according to the mapping relationships, so the decision table is created in O(N 2 ), and N is equivalent of max{|{⊗(r)}|,|⊕(n,u,r)|}; in Sub-algorithm 2, the decision table is detected through searching itself. The number of cycles is equal to the record number of items in the decision table, so the compatibility problem is solved in O(N 2 ); the number of the decisional class(|TM/θ(γ TM )|) is less than the number of the equivalence class (|SM/θ(γ TM )|), and the number of the equal class is less than the number of the decision table in Sub-algorithm 3, so the decision matrix is built in O(N 2 ); in Sub-algorithm 4, the number of transformation rules is equal to the number of the equivalence class, so these transformation rules are constructed in O(N 2 ). Although the same rules are merged in Sub-algorithm 4, the number of cycles is not more than |SM/θ(γ TM )| 2 . Therefore the time complexity of rsCRT is O(N 2 ), and N=max{|{⊗(r)}|, |⊕(n,u,r)|}.

Experiment

To validate the proposed approach, we designed three kinds of experiments in order to respectively analyze three quantities' influence on transformation rules (i.e. Class2Table, Relationship2Table and Property2Column), i.e. the sample's number, the number of the source metamodels and the property reduction. In each experiment, seven intervals of the sample's number are investigated. They are [0, 50], (50,100], (100, 150], (150, 200],…,(300, 350]. For each interval, 350 instances which are randomly generated are executed and averages of the three measure indicators are calculated. Java is used for programming in all of simulation.

MTR 1 Class is transformed into

Experiment 2 Number of the source metamodels

In order to verify whether the detailed information of the source and target metamodels affects the construction and measurement of transformation rules, we expand the role elements of UCD2RDM, such as sou, tar and child. The result of the measurement indicators is shown in Fig. 5.

Experiment 3 Property reduction

The property reduction plays an important role in rough set theory. this experiment, the condition properties, such as the property c, are reduced to observe the change of the average Coverage The result is shown in Fig. 6.

The first experiment demonstrates that the more the number of the mapping relationships is, the larger the average of the measurement indicators of the transformation rules is. For instance, the average Coverage of Class2Table varies from 0.2500 to 0.6072. In the second experiment, the more the number of the source metamodels is, the larger the average of the measurement indicators of the transformation rules is, in particular Relationship2Table and Property2Column. The third experiment denotes the average of the measure indicators become large when some properties whose values fluctuate are eliminated. For example, the average Coverage of Property2Column increases observably after eliminating property c in the source metamodels.

Related Work

Shane [START_REF] Shane | Combining generative and graph transformation techniques for model transformation: An effective alliance?[END_REF] presents a transformation language based on graph transformation and defines transformation rules through a group of production rule, while Karsai [START_REF] Karsai | Graph transformations in OMG's model-driven architecture[END_REF] proposes another transformation language to describe the mapping between the source model into target model using the theory of graph transformation and graph rewriting. Dhamanka [START_REF] Dhamanka | iMAP: discovering complex semantic matches between database schemas[END_REF] proposes an approach to create complex links in the beginning of a mapping. However, the complex mapping should be divided into smaller parts to produce transformation rules. David [START_REF] David | A relational approach to defining transformations in a metamodel[END_REF] gives emphasis to use set and relational algebra to describe transformation rules. The definition of relation is too strict to expand the set of transformation rules. So the coverage of the method is not widely. The solution in [START_REF] Miller | The Clio Project: Managing heterogeneity[END_REF] provides a mechanism which name is Clio to produce transformations based on a set of relationships. Clio has a shortage that the definition of the relationships is not extended, so creating complex kinds of model transformation has become a challenge. Similarity Flooding has evolved in [START_REF] Melnik | Generic Model Management: Concepts and Algorithms[END_REF] to define transformation rules for difference metamodels. The major work gives an algorithm which is the basis of metamodel matching transformations. Design Pattern [START_REF] Zhang Tian | MDA Based Design Patterns Modeling and Model Transformation[END_REF] is one of the first solutions to integrate modeling units to generate transformation rules. It can discover the relation between the source and target models. It is not adapted to match elements in metamodel-level, so it can not support the production of more complex mappings.

The work from [START_REF] Didont | Towards the efficient development of model transformations using model weaving and matching transformations[END_REF] uses matching transformations and weaving models to semiautomate the development of model transformation. The weaving model can be used to discover and save the different kinds of relationships among metamodels. Our approach can not only construct transformation rules but also evaluate these transformation rules. In a paper of Zoltán [START_REF] Balogh | Model Transformation by Example Using Inductive Logic Programming[END_REF], their approach is applied to derive transformation rules on the basis of the prototype of the source and target models using the inference logic method. Wimmer [START_REF] Wimmer | Towards model transformation generation by-example[END_REF] use an object-based idea to derive ATL rules for model transformation. Because both approaches use mappings between terminal models to construct transformation rules, the rules will have the influence of the size of terminal models.

The INTEROP [START_REF] Panetto | INTEROP NoE: Interoperability Research for Networked Enterprises Applications and Software[END_REF] approach is generally used to solve the transformations from and to the enterprise model level and usage of ontologies. In paper [START_REF] Bauer | A Model-Driven Approach to Designing Cross-Enterprise Business Processes[END_REF], starting from the ATHENA interoperability architecture, Bernhard Bauer presents a methodical approach to transform ARIS into UML and BPDM. However, the source and target models are conforming to UML2 and the approach doesn't support the other metamodels.

Conclusions and Future Work

In this paper we use rough set to semi-automate the production of transformation rules and present an approach to construct transformation rules. The approach supports the matching of different metamodels. Transformation rules constructed by our approach are accompanied by measurement indicators supporting selection of transformation rules.

We analyzed the construction theory of rough set from several aspects related to the complexity of transformation rules. Firstly, we have improved the construction approach of rough set to support the mapping between different metamodels. Secondly, we have presented the algorithm rsCRT to construct transformation rules. We provided the measurement indicators of transformation rules according to rough set. These indicators consist of support, accuracy and coverage.

To validate the construction approach, we designed three kinds of experiments in order to respectively analyze three quantities' influence on transformation rules, i.e. the sample's number, the number of the source metamodels and the property reduction. The result denote that the more the number of the mapping relationships and the source metamodels is, the larger the average of the measurement indicators of the transformation rules is, and the average of the measure indicators become large when some properties whose values fluctuate are eliminated. Future work is to optimist transformation rules constructed through our approach transformation. For this reason, we plan to analysis the transformation rules and compose some transformation rules to improve the efficiency of model transformation.

Fig. 1 .

 1 Fig. 1. Source and target metamodels of UCD2RDM.

Fig. 2 .

 2 Fig. 2. Source and target models of UCD2RDM. In Fig. 2, there are three kinds of transformation rules which are used to transform elements of UML class diagram into elements of relational database model. -The first rule describes how to transform Class intoTable through the mapping between the properties of Class and the columns of Table; -The second rule expresses the correspondence between Relation and Table. It consists of the matching relationships between the Relation's name and the Table's name, and the mapping relationship between the crucial properties of Relation and the foreign column of Table; -The last rule presents the mapping relationships between the identity property of Class and the important column of Table.

  the finite element set of the source and target metamodel, and Γ determines the metamodel element of each model element. For ∀mm∈γ SM , sm∈SM, then has SM γ γ

  then w 1 and w 2 are called as the indiscernibility relation of B. Indiscernibility relation is the main concept of rough set theory. The source model is divided into the equivalence class according to indiscernibility relation, which is denoted as SM/∆ B . Definition 3.9 (Indiscernibility relation of the decision value): Let RT=(M, V, Γ) be a decision table, and B⊆γ SM . Then an indiscernibility relation of the decision value ∆ B is generated from B and RT with the form

Definition 3 . 13 (

 313 Decision function of transformation rules): Let CM(RT) = (m ij ) n×n be a decision matrix, a decision function of the condition equivalence class is defined as ( )

Fig. 3 . 4 .Experiment 1

 341 Fig. 3. Transformation rules of the example. Fig. 4. Comparisons of the number of samples. Experiment 1 Number of samples The average Coverage (Class2Table, Relationship2Table, and Property2Column) is shown in Fig. 4. The average Coverage of Class2Table varies from 0.5489 to 0.6072, and the average Coverage of Relationship2Table rises from 0.4619 to 0.4928 and the average Coverage of Property2Column increases from 0.5243 to 0.5522.

Fig. 5 .

 5 Fig. 5. Comparisons of the number of source metamodels.

Fig. 6 .

 6 Fig. 6. Comparisons of the property reduction.

  Each Class has zero or more Properties. The type of each Property can be defined by builtin type or another Class. The relation among Classes is specified by Relationship. Relationship can be extended to describe the more concrete relations, for example Association, Composition, Aggregation, Generalization and Dependency, etc. Relational database model is composed of Table, FKey and Column. A Table contains one or more Column, and zero or more FKey. An FKey is also a Column.

1. UML class diagram consists primarily of Class, Relationship and Property.

Table ; -

 ; Table through the mapping between the properties of Class and the columns of The second rule expresses the correspondence between Relation and Table. It consists of the matching relationships between the Relation's name and the Table's name, and the mapping relationship between the crucial properties of Relation and the foreign column of Table; -The last rule presents the mapping relationships between the identity property of Class and the important column of Table.

3 Rough Set and Discovered Rule Based on Rough Set 3.1 Rough Set Theory

	Rough set theory is a mathematical tool to deal with vagueness and uncertainty. It has
	capability to effectively analyze uncertain, incomplete and inconsistent data, discover
	dependent and implicit relations, and construct mapping rules [10]. The process of
	constructing rule in rough set is composed of three steps. The first step is to classify
	the data according to the equivalence relations. The second step is to format the data
	in order to generate the decision table. The last step is to calculate the data belong to
	the decision table and construct the mapping rules

Definition 3.11 (Property reduction): Let

  is the decision class of transformation rules and j=1 to m. RT=(M, V, Γ) be a decision table, and B⊆γ SM , smm j ∈B (1) if ∆ B =∆ B -{smm j } is true, the metamodel smm j is redundancy to the set B, else smm j is necessary to B; (2) if all properties of B are necessary, B is independent;

Table 1 .

 1 table is generated by Def. 6. Its construction algorithm is shown in Sub-algorithm 1; (2) After generating the decision table, the compatibility of the decision table should be detected according to Def. 8. If the decision table is incompatible, it should be redesigned through indistinguishable function δ B defined by Def. 9.The specific detection and operation is written in Sub-algorithm 2; (3) Before building the decision matrix, the decision table should be rewritten according to equivalence class and decision class. The decision matrix is built according to Sub-algorithm 3; (4) Finally, the decision function B i , established based on the decision matrix, is converted into minimal disjunctive normal form to construct transformation rules. The rules with the same source and target metamodels are merged and calculated their measure indicators. The creation algorithm of transformation rules is written in Sub-algorithm 4.In Sub-algorithm 1, to reduce decision table of UCD2RDM, we use n to describe the node of source metamodel (i.e. Class,Relationship,Propery), and r to denote the relation of source metamodel (i.e. Association,Inheritance,Composition), and u to present the node's role participated in the relation, such as attr, type and parent etc, and c to indicate the number of the role, and t to reveal the elements of target metamodel(i.e. Table,Fkey and Column). Decision table of transformation rules. We apply Sub-algorithm 2 in UCD2RDM and get the incompatible information which is shown as follows: δ The result is shown in the right part of Table 1 (i.e. condition property and decision property).

	Sub-algorithm 1. Generating Decision Table
	Input: MS=(RGS,γS,ξS),MT=(RGT,γT,ξT)
	Output: model_tran_rule_dec_table
	model_tran_rule_dec_table(schema)={n,r,u,c,t};
	List queryRelList,queryUseList,queryCarList;
	void queryRUCList(String tempNodeInstance){
	for(m=1 to |{⊗(r)}|)
	if(⊗(r)[m].n==tempNodeInstance){
	queryRelList.add(⊗(r)[m].r);
	for(n=1 to |⊕(n,u,r)|)
	if(⊕(n,u,r)[n].n==tempNodeInstance)&
	⊕(n,u,r)[n].u==⊗(r)[m].u)&
	⊕(n,u,r)[n].r==⊗(r)[m].r))
	queryCarList.add(⊗(r)[m].u);} }
	for(i=1 to |RG S (L)|){
	meta_model_Element=ξ S (RGS(L i ));
	queryRUCList(meta_model_Element);
	Value=queryNodeSchemaValue(meta_model_Element);
	for(j =1 to queryRelList.length()){
	rValue=queryRelSchemaValue(queryRelList[j]);
	uValue=queryUseSchemaValue(queryUseList[j]);
	cValue=queryCarSchemaValue(queryCarList[j]);
	model_tran_rule_dec_table.add(row)=({nValue,
	rValue, uValue, cValue, ξ T (RGT(tempNodeInstance }); }
	}

i .n==row j .n&row i .r==row j .r & row i .u==row j .u&row i .c==row j .c){ if(row i .t<>row j .t){ row i .t=row i .t+row j .t ; row j .t=row i .t;} } B

(TID)= δ B (TName)={1,2},that is |δ B (TID)|=| δ B (TName)|≠1 similarly,δ B (CID)= δ B (CTName)= δ B (SID)= δ B (SName)=={1,2}

So the decision table should be redesigned through Sub-algorithm 2.

Table 2 .

 2 The equivalence class W 10 is defined by Def.3.10 and def.3.11 based on the results of incompatibility.

	Sub-algorithm 4. Constructing Transformation Rules Set
	Input: the decision matrix CM
	Output: {MTR}
	List rulefirstList, rulelastList, ruleList;
	for(i=1 to CM.col.length){
	row i = model_tran_rule_dec_table(row)[i];
	String rulefirst, rulelast;//save a rule
	for(j=1 to i)
	if(i==j)
	for(k=i to CM.row.length)
		rulefirst= rulefirst∧m[i][k];
	else
	for(k=1 to i)
		rulefirst= rulefirst∧m[k][i];
	rulelast= rulelast∨row i .t;
	rulefirstList.add(disformat(rulefirst));
	rulelastList.add(rulelast); }
	for(i=1 to rulefirstList.length)
	for(j=i+1 to rulefirstList.length){
	if(rulefirstList[i]==rulefirstList[j])
		if(rulelastList[i]<>rulelastList[j])
	rulelastList[i]=rulelastList[i]∨rulelastList[j];
	rule=rulefirstList[i]→rulelastList[i];
	rule.SI=	rulefirstList[i].SI+	rulefirstList[j].SI;
	rule.CI= rulefirstList[i].CI+ rulefirstList[j].CI;
	ruleList.add(rule);
	rulefirstList.del[j];
	rulelastList.del[j]; }
	ruleset_rulepara(schema)={rule,rule.SI,rule.CI};
	for(m=1 to ruleList.length){
	MTRuleSet.add(row)[m]=({ruleList[m].rule,

Table 3 .

 3 Set of transformation rules and measurement indicator.

	order	transformation rules	support accuracy	coverage
	1	(n,0)∧(r,0) → (t,0)	5	1.00	(1.0,0.25)
	2	(n,0)∧(c,1) → (t,0)	2	1.00	(1.0,0.10)
	3	(r,1)∧(c,3) → (t,0)	1	1.00	(1.0,0.05)
	4	(n,0)∧(r,1) → (t,0)	1	1.00	(1.0,0.05)
	5	(r,1)∧(c,3) → (t,0)	1	1.00	(1.0,0.05)
	6	(n,0)∧(r,1)∧(u,6) → (t,0)	1	1.00	(1.0,0.05)
	7	(n,1)∧(r,0) → (t,0)∨(t,2)	6	1.00	(1.0,0.30) (1.0,0.55)
	8	(n,1)∧(c,3) → (t,0)∨(t,2)	6	1.00	(1.0,0.30) (1.0,0.55)
	9	(n,1)∧(r,1) → (t,0)	4	0.50,0.50	(1.0,0.

Table fkey 

 fkey source.sou.attrs column  source.sou.attrs fkey  source.tar.attrs column  source.tar.attrs }

	Table
	rule Class2Table{
	from source: CDM!Class
	to	target: RDM!Table
		column  source.attrs
		fkey  source.attrs	}
	MTR 2 Relation is transformed
	into Table
	rule Relationship2Table{
	from source: CDM!Relationship)
	to	target: RDM!

Table 2 .

 2 Decision matrix of transformation rules.

													measure
	decision class	Equiva lence class	decision matrix of transformation rules X1 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 X2 X3	transformation rules precondition decision	ment indicator (SI,CI)
		W1	ruc	r	c		r	n	nrc	nruc nruc (n,0)∧(r,0)	(t,0)	(1.0,0.10)
		W2	ruc	uc	ruc	ruc	uc	nru c	nu	nruc nru	(u,0), (n,0)∧(c,1)	(t,0)	(1.0,0.10)
		W3		r	c		r	n	nrc	nruc nruc (n,0)∧(r,0)	(t,0)	(1.0,0.10)
		W4			rc	r		nr	nc	nruc nruc	(r,1)∧(c,3), (n,0)∧(r,0)∧(u,6)	(t,0)	(1.0,0.05)
	X1	W5				c	rc	nc	nrc	nru	nruc (n,0)∧(r,0)	(t,0)	(1.0,0.05)
		W6					r	n	nrc	nruc nruc (n,0)∧(r,1)	(t,0)	(1.0,0.05)
		W7						nr	nc	nruc nruc	(r,1)∧(c,3), (n,0)∧(r,1)∧(u,6)	(t,0)	(1.0,0.05)
		W8							rc	nruc nruc	(n,1)∧(r,0), (n,1)∧(c,3)	(t,0)∨ (t,2)	(1.0,0.30) (1.0,0.55)
												(n,1)∧(r,1),
		W9								nruc nru	(n,1)∧(c,1),	(t,0)	(1.0,0.20)
												(u,6)∧(c,1)
	X2	W10									uc	(u,2)	(t,1)∨ (t,2)	(1.0,1.00) (1.0,0.27)
	X3	W11										(u,1)	(t,2)	(1.0,0.18)

Acknowledgments

. Research works in this paper are partial supported by the National Natural Science Foundation of China (60773064), the National High-Tech Research and Development Program of China (2009AA04Z153, 2008GG1000401028).