Laura Kallmeyer

Yannick Parmentier
email: parmenti@sfs.uni-tuebingen.de

On the relation between Multicomponent Tree Adjoining Grammars with Tree Tuples (TT-MCTAG) and Range Concatenation Grammars (RCG)

This paper investigates the relation between TT-MCTAG, a formalism used in computational linguistics, and RCG. RCGs are known to describe exactly the class PTIME; simple RCG even have been shown to be equivalent to linear context-free rewriting systems, i.e., to be mildly context-sensitive. TT-MCTAG has been proposed to model free word order languages. In general, it is NP-complete. In this paper, we will put an additional limitation on the derivations licensed in TT-MCTAG. We show that TT-MCTAG with this additional limitation can be transformed into equivalent simple RCGs. This result is interesting for theoretical reasons (since it shows that TT-MCTAG in this limited form is mildly context-sensitive) and, furthermore, even for practical reasons: We use the proposed transformation from TT-MCTAG to RCG in an actual parser that we have implemented.

Introduction

Tree Adjoining Grammars (TAG)

Tree Adjoining Grammar (TAG, [START_REF] Joshi | Tree-Adjoning Grammars[END_REF]) is a tree-rewriting formalism. A TAG consists of a finite set of trees (elementary trees). The nodes of these trees are labelled with nonterminals and terminals (terminals only label leaf nodes). Starting from the elementary trees, larger trees are derived by substitution (replacing a leaf with a new tree) and adjunction (replacing an internal node with a new tree). In case of an adjunction, the tree being adjoined has exactly one leaf that is marked as the foot node (marked with an asterisk). Such a tree is called an auxiliary tree. When adjoining it to a node n, in the resulting tree, the subtree with root n from the old tree is attached to the foot node of the auxiliary tree. Non-auxiliary elementary trees are called initial trees. A derivation starts with an initial tree. In a final derived tree, all leaves must have terminal labels. For a sample derivation see Fig. -N and T being disjoint finite sets, the nonterminals and terminals -I being a finite set of initial trees with nonterminals N and terminals T , and -A being a finite set of auxiliary trees with nonterminals N and terminals T .

The internal nodes in I ∪ A can be marked as OA (obligatory adjunction) and N A (null adjunction, i.e., no adjunction allowed).

Definition 2 (TAG derivation and tree language) Let G = I, A, N, T be a TAG. Let γ and γ ′ be finite trees.

-γ ⇒ γ ′ in G iff there is a node position p and a tree γ ′ 0 that is either elementary or derived from some elementary tree such that γ ′ = γ[p, γ ′ 0 ]. 1 * ⇒ is the reflexive transitive closure of ⇒. -The tree language of G is L T (G) := {γ | α * ⇒ γ for some α ∈ I, all leaves in γ have terminal labels and there are no remaining OA nodes in γ}. The string language L(G) contains all yields of trees from the tree language.

TAG derivations are represented by derivation trees (unordered trees) that record the history of how the elementary trees are put together. A derived tree is the result of carrying out the substitutions and adjunctions, i.e., the derivation tree describes uniquely the derived tree. Each edge in a derivation tree stands for an adjunction or a substitution. The edges are labelled with Gorn addresses. 2 E.g., the derivation tree in Fig. 1 indicates that the elementary tree for John is substituted for the node at address 1 and always is adjoined at node address 2 (the fact that the former is an adjunction, the latter a substitution can be inferred from the fact that the node at address 1 is a leaf that is no foot node while the node at address 2 is an internal node).

Definition 3 (TAG derivation tree) Let G = I, A, N, T be a TAG. Let γ be a tree derived as follows in G:

γ = γ 0 [p 1 , γ 1 ] . . . [p k , γ k ]
where γ 0 is an instance of an elementary tree and the substitutions/adjunctions of the γ 1 , . . . , γ k are all the substitutions/adjunctions to γ 0 that are performed to derive γ.

1 For trees γ, γ1, . . . , γn and pairwise different node positions p1, . . . , pn in γ, γ[p1, γ1] . . . [pn, γn] denotes the result of subsequently substituting/adjoining the γ1, . . . , γn to the nodes in γ with addresses p1, . . . , pn respectively. 2 The root address is ǫ, and the jth child of a node with address p has address pj.

Then the corresponding derivation tree has a root labelled with γ 0 that has k daugthers. The edges from γ 0 to these daughters are labelled with p 1 , . . . , p k , and the daughters are the derivation trees for the derivations of γ 1 , . . . , γ k .

Range Concatenation Grammars (RCG)

This section defines RCGs [START_REF] Boullier | On TAG Parsing[END_REF][START_REF] Boullier | Range Concatenation Grammars[END_REF]. 3Definition 4 (Range Concatenation Grammar) A Range Concatenation Grammar is a tuple G = N, T, V, S, P such that -N is a finite sets of predicates, each with a fixed arity; -T and V are disjoint alphabets of terminals and of variables; -S ∈ N is the start predicate, a predicate of arity 1; -P is a finite set of clauses A 0 (x 01 , . . . , x 0a0 ) → ǫ, or A 0 (x 01 , . . . , x 0a0 ) →

A 1 (x 11 , . . . , x 1a1 ) . . . A n (x n1 , . . . , x nan ) with n ≥ 1 and A i ∈ N, x ij ∈ (T ∪ V ) * and a i being the arity of A i .

An RCG with maximal predicate arity n is called an RCG of arity n.

When applying a clause with respect to a string w = t 1 . . . t n , the arguments of the predicates in the clause are instantiated with substrings of w, more precisely with the corresponding ranges. A range i, j with 0 ≤ i < j ≤ n corresponds to the substring between positions i and j, i.e., to the substring t i+1 . . . t j . If i = j, then i, j corresponds to the empty string ǫ. If i > j, then i, j is undefined.

Definition 5 For a given clause, an instantiation with respect to a string w = t

1 . . . t n consists of a function f : {t ′ | t ′ is an occurrence of some t ∈ T in the clause} ∪ V → { i, j | i ≤ j, i, j ∈ IN} such that
a) for all occurrences t ′ of a t ∈ T in the clause: f (t ′ ) := i, i + 1 for some i, 0 ≤ i < n such that t i = t, b) for all v ∈ V : f (v) = j, k for some 0 ≤ j ≤ k ≤ n, and c) if consecutive variables and occurrences of terminals in an argument in the clause are mapped to i 1 , j 1 , . . . , i k , j k for some k, then j m = i m+1 for 1 ≤ m < k. By definition, we then state that f maps the whole argument to i 1 , j k .

The derivation relation is defined as follows:

Definition 6 (RCG derivation and string language)

-For a predicate A of arity k, a clause A(. . .) → . . ., and ranges i 1 , j 1 , . . . , i k , j k with respect to a given w: if there is a instantiation of this clause with lefthand-side A( i 1 , j 1 , . . . , i k , j k ), then in one derivation step (. . . ⇒ . . .) A( i 1 , j 1 , . . . , i i , j k ) can be replaced with the right-hand side of this instantiation. * ⇒ is the reflexive transitive closure of ⇒.

-The language of an RCG G is L(G) = {w | S( 0, |w| ) * ⇒ ǫ with respect to w}.

For illustration, consider the RCG G = {S, A, B}, {a, b}, {X, Y, Z}, S, P with

P = {S(X Y Z) → A(X, Z) B(Y ), A(a X, a Y ) → A(X, Y ), B(b X) → B(X), A(ǫ, ǫ) → ǫ, B(ǫ) → ǫ}. L(G) = {a n b k a n | k, n ∈ IN}.
Take w = aabaa. The derivation starts with S( 0, 5 ). First we apply the following clause instantiation: 2 2,3 3,5 0,2 3,5 2,3

S(X Y Z) → A(X, Z) B(Y ) 0,
aa b aa aa aa b With this instantiation, S( 0, 5 ) ⇒ A( 0, 2 , 3, 5 )B( 2, 3 ). Then B(b X) → B(X) 2, 3 3, 3 3, 3 b ǫ ǫ and B(ǫ) → ǫ lead to A( 0, 2 , 3, 5 )B( 2, 3 ) ⇒ A( 0, 2 , 3, 5 )B( 3, 3 ) ⇒ A( 0, 2 , 3, 5 ). A(a X a Y ) → A(X, Y ) 0, 1 1, 2 3, 4 4, 5 1, 2 4, 5 a a a a a a leads to A( 0, 2 , 3, 5 ) ⇒ A( 1, 2 , 4, 5 ). Then A(a X a Y ) → A(X, Y ) 1, 2 2, 2 4, 5 5, 5 2, 2 5, 5 a ǫ a ǫ ǫ ǫ and A(ǫ, ǫ) → ǫ lead to A( 1, 2 , 4, 5 ) ⇒ A( 2, 2 , 5, 5 ) ⇒ ǫ
An RCG is called non-combinatorial if each of the arguments in the righthand sides of the productions are single variables. It is called linear if no variable appears more than once in the left-hand sides of the productions and no variable appears more than once in the right-hand side of the productions. It is called non-erasing if for each production, each variable occurring in the left-hand side occurs also in the right-hand side and vice versa. An RCG is called simple if it is non-combinatorial, linear and non-erasing. Simple RCGs and linear contextfree rewriting systems (LCFRS, Weir 1988) are equivalent (see Boullier 1998b). Consequently, simple RCG's are mildly context-sensitive [START_REF] Joshi | An introduction to Tree Adjoining Grammars[END_REF].

From TAG to RCG

Now let us sketch the general idea of the transformation from TAG to RCG (see Boullier 1998a): The RCG contains predicates α (X) and β (L, R) for initial and auxiliary trees respectively. X covers the yield of α and all trees added to α, while L and R cover those parts of the yield of β (including all trees added to β) that are to the left and the right of the foot node of β. The clauses in the RCG reduce the argument(s) of these predicates by identifying those parts that come from the elementary tree α/β itself and those parts that come from one of the elementary trees added by substitution or adjunction. A sample TAG with an equivalent RCG is shown in Fig. 2.

TAG: α1 SNA a S F ǫ α2 F d α3 F e β S b S * NA c Equivalent RCG: S(X) → α1 (X) | α2 (X) | α3 (X)
(every word in the language is the yield of an α ∈ I)

α1 (aF ) → α2 (F ) | α3 (F )
(the yield of α1 can consist of the terminal a followed by the yield of the tree that substitutes into the F node)

α1 (aB1B2F ) → β (B1, B2) α2 (F ) | β (B1, B2) α3 (F ) (or β adjoins to S in α;
then the yield of α1 is a followed by the part of the yield of β left of the foot node followed by the part of the yield of β right of the foot node followed by the yield of the tree that substitutes into F )

β (B1b, cB2) → β (B1, B2)

TT-MCTAG

For a range of linguistic phenomena, multicomponent TAG (MCTAG, [START_REF] Weir | Characterizing mildly context-sensitive grammar formalisms[END_REF] have been proposed as a TAG extension. The motivation it the desire to split the contribution of a single lexical item (e.g., a verb and its arguments) into several elementary trees. An MCTAG consists of sets of elementary trees, socalled multicomponents. If a multicomponent is used in a derivation, all its members must be used.

Definition 7 (MCTAG) A multicomponent TAG (MCTAG) is a tuple G = I, A, N, T, A where G T AG := I, A, N, T is a TAG, and A is a partition of I ∪ A, the set of elementary tree sets.

The particular type of MCTAG we are concerned with is Tree-Tuple MCTAG with Shared Nodes (TT-MCTAG, Lichte 2007). TT-MCTAG were introduced to deal with free word order phenomena in languages such as German. An example is (1) where the argument es of reparieren precedes the argument der Mechaniker of verspricht and is therefore not adjacent to the predicate it depends on:

(1) ... dass es der Mechaniker zu reparieren verspricht ... that it the mechanic to repair promises '... that the mechanic promises to repair it'

A TT-MCTAG is slightly different from standard MCTAG since the elementary tree sets contain two parts: 1. one lexicalized tree γ, marked as the unique head tree, and 2. a set of auxiliary trees, the argument trees. Such a pair is called a tree tuple. During derivation, the argument trees must either adjoin directly to their head tree or they must be linked by a chain of adjunctions at root nodes to a tree that attaches to the head tree. In other words, in the corresponding TAG derivation tree, the head tree must dominate the auxiliary trees such that all positions on the path between them, except the first one, must be ǫ. This captures the notion of adjunction under node sharing from [START_REF] Kallmeyer | Tree-local Multicomponent Tree Adjoining Grammars with Shared Nodes[END_REF]. 4Definition 8 (TT-MCTAG) Let G = I, A, N, T, A be an MCTAG. G is a TT-MCTAG iff 1. every Γ ∈ A has the form {γ, β 1 , . . . , β n } where γ contains at least one leaf with a terminal label, the head tree, and β 1 , . . . , β n are auxiliary trees, the argument trees. We write such a set as a tuple γ, {β 1 , . . . , β n } . 2. A derivation tree D for some t ∈ L( I, A, N, T ) is licensed as a TAG derivation tree in G iff D satisfies the following conditions (MC) ("multicomponent condition") and (SN-TTL) ("tree-tuple locality with shared nodes"): (a) (MC) There are k pairwise disjoint instances Γ 1 , . . . , Γ k of elementary tree sets from A for some k ≥ 1 such that k i=1 Γ i is the set of node labels in D. (b) (SN-TTL) for all nodes n 0 , n 1 , . . . , n m , m > 1, in D with labels from the same elementary tree tuple such that n 0 is labelled by the head tree: for all 1 ≤ i ≤ m: either n 0 , n i ∈ P D5 or there are n i,1 , . . . , n i,k with auxiliary tree labels such that n i = n i,k , n 0 , n i,1 ∈ P D and for 1 ≤ j ≤ k -1: n i,j , n i,j+1 ∈ P D where this edge is labelled with ǫ.

Fig. 3 shows a TT-MCTAG derivation for (1). Here, the NP nom auxiliary tree adjoins directly to verspricht (its head) while the NP acc tree adjoins to the root of a tree that adjoins to the root of a tree that adjoins to reparieren.

In the general case, the recognition problem for TT-MCTAG is NP-hard [START_REF] Søgaard | The complexity of linguistically motivated extensions of tree-adjoining grammar[END_REF]). In the following, we define a limitation for TT-MCTAG based on a suggestion from [START_REF] Søgaard | The complexity of linguistically motivated extensions of tree-adjoining grammar[END_REF]: TT-MCTAG are of rank k if, at any time during the derivation, at most k argument trees depending on higher head trees in the derivation tree are still waiting for adjunction.

Definition 9 (k-TT-MCTAG) Let G = I, A, N, T, A be a TT-MCTAG. G is of rank k (or a k-TT-MCTAG for short) iff for each derivation tree D licenced in G, the following holds: (TT-k) There are no nodes n, h 0 , . . . , h k , a 0 , . . . , a k in D such that the label of a i is an argument tree of the label of h i and h i , n , n, a i ∈ P + D for 0 ≤ i ≤ k.

3 From k-TT-MCTAG to RCG

We construct equivalent simple RCGs for k-TT-MCTAG in a way similar to the RCG construction for TAG. There are predicates γ for the elementary trees (not the tree sets) that characterize the contribution of γ. Recall that each TT-MCTAG is a TAG, a TT-MCTAG derivation is a derivation in the underlying TAG. (This is how we defined TT-MCTAG.) Consequently, we can construct the RCG for the underlying TAG, enrich the predicates in a way that allows to keep track of the "still to adjoin" argument trees and constrain thereby further the RCG clauses. In this case, the yield of a predicate corresponding to a tree γ contains not only γ and its arguments but also arguments of predicates that are higher in the derivation tree and that are adjoined below γ via node sharing. 6Our construction leads to an RCG of arity 2 with complex predicate names. In order to keep the number of necessary predicates finite, the limit k is crucial.

A predicate γ must encode the set of argument trees that depend on higher head trees and that still need to be adjoined. We call this set the list of pending arguments (LPA). These trees need to either adjoin to the root or be passed to the LPA of the root-adjoining tree. The LPA is a multiset since we allow for several occurrences of a single tree.

In order to reduce the number of clauses, we distinguish between tree clauses (predicates γ... ) and branching clauses (predicates adj... and sub... ) following [START_REF] Boullier | On TAG Parsing[END_REF]. We therefore have three kinds of predicates:

1. γ, LP A with LP A being the list of pending arguments coming from higher trees (not arguments of γ). This predicate has arity 2 if γ is an auxiliary tree, arity 1 otherwise.

γ, LP A -clauses distribute the variables for the yields of the trees that substitute or adjoin into γ among corresponding adj and sub predicates. Furthermore, they pass the LP A to the root-position adj predicate and distribute the arguments of γ among the LPAs of all adj predicates. 2. adj, γ, dot, LP A as intermediate predicates (of arity 2). Here, LPA contains a) the list of higher args if dot = ǫ, and b) arguments of γ. We assume as a condition that it contains only trees that can be adjoined to dot in γ. adj, γ, dot, LP A -clauses adjoin a γ ′ to the dot in γ. If γ ′ ∈ LP A, then the new predicate receives LP A \ {γ ′ }. Othwerwise, γ ′ must be a head and LP A is passed unchanged. 3. sub, γ, dot as intermediate predicates (arity 1).

sub, γ, dot -clauses aubstitute a γ ′ into dot in γ.

More precisely, the construction goes as follows:

We define the decoration string σ γ of an elementary tree γ as in Boullier (1999): each internal node has two variables L and R and each substitution node has one variable X (L and R represent right and left parts of the yield of the adjoined tree and X represents the yield of a substituted tree). In a top-down-left-to-right traversal the left variables are collected during the topdown traversal, the terminals and variables of substitution nodes are collected while visiting the leaves and the right variables are collected during bottom-up traversal. Furthermore, while visiting a foot node, a separating "," is inserted. The string obtained in this way is the decoration string.

1. We add a start predicate S and clauses S(X) → α, ∅ (X) for all initial trees α. 2. Let γ be a tree, σ its decoration string. Let L p , R p be the left and right symbols in σ for the node at position p if this is no substitution node. Let X p be the symbol for the node at position p if this is a substitution node. We assume that p 1 , . . . , p k are the possible adjunction sites, p k+1 , . . . , p l the substitution sites in γ. Then the RCG contains all clauses γ, LP A (σ) → adj, γ, p 1 , LP A p1 (L p1 , R p1 ) . . . adj, γ, p k , LP A p k (L p k , R p k ) sub, γ, p k+1 (X p k+1 ) . . . sub, γ, p l (X p l ) such that -If LP A = ∅, then ǫ ∈ {p 1 , . . . , p k } and LP A ⊆ LP A ǫ , and

-k i=0 LP A pi = LP A ∪ Γ (γ)
where Γ (γ) is the set of arguments of γ or (if γ is an argument itself), the empty set. 3. For all predicates adj, γ, dot, LP A the RCG contains all clauses adj, γ, dot, LP A (L, R) → γ ′ , LP A ′ (L, R) such that γ ′ can be adjoined at position dot in γ and

-either γ ′ ∈ LP A and LP A ′ = LP A \ {γ ′ }, -or γ ′ / ∈ LP A, γ ′ is a head (i.
e., a head tree), and LP A ′ = LP A. 4. For all predicates adj, γ, dot, ∅ where dot in γ is no OA-node, the RCG contains a clause adj, γ, dot, ∅ (ǫ, ǫ) → ǫ. 5. For all predicates sub, γ, dot and all γ ′ that can be substituted into position dot in γ the RCG contains a clause sub, γ, dot (X) → γ ′ , ∅ (X).

As an example consider the TT-MCTAG from Fig. 4. For this TT-MCTAG we obtain (amongst others) the following RCG clauses:

-α v , ∅ (L v 0 R) → adj, α v , ǫ, ∅ (L, R)
(only one adjunction at the root, address ǫ)

-adj, α v , ǫ, ∅ (L, R) → β v1 , ∅ (L, R) | β v2 , ∅ (L, R) (β v1 or β v2 might be adjoined at ǫ in α v , LPA (here empty) is passed) -β v1 , ∅ (L v 1 , R) → adj, β v1 , ǫ, {β n1 } (L, R) (in β v1
, there is only one adjuntion site, address ǫ; the argument is passed to the new LPA)

-adj, β v1 , ǫ, {β n1 } (L, R) → β n1 , ∅ (L, R) | β v1 , {β n1 } (L, R) | β v2 , {β n1 } (L, R) (either β n1
is adjoined and removed from the LPA or another tree (β v1 or β v2 ) is adjoined; in this case, the LPA remains)

-β v1 , {β n1 } (L v 1 , R) → adj, β v1 , ǫ, {β n1 , β n1 } (L, R)
(again, only one adjunction in β v1 ; the argument β n1 is added to the LPA) -β n1 , ∅ (L N, R) → adj, β n1 , ǫ, ∅ (L, R) sub, β n1 , 1, (N ) (adjunction to root and substitution to 1 in β n1 ) -adj, β n1 , ǫ, ∅ (ǫ, ǫ) → ǫ (adjunction at root of β n1 not obligatory as long as LPA is empty) -sub, β n1 , 1, (N ) → α n1 , ∅ (N ) (substitution of α n1 at address 1) -α n1 , ∅ (n 1 ) → ǫ (no adjunctions or substitutions at α n1 ) . . .

Take the input word n

1 n 2 n 1 v 2 v 1 v 1 v 0 .
The RCG derivation goes as follows:

S(n 1 n 2 n 1 v 2 v 1 v 1 v 0 ) ⇒ α v , ∅ (n 1 n 2 n 1 v 2 v 1 v 1 v 0 ) ⇒ adj, α v , ǫ, ∅ (n 1 n 2 n 1 v 2 v 1 v 1 , ǫ) (adjunction at ǫ, v0 is scanned) ⇒ β v1 , ∅ (n 1 n 2 n 1 v 2 v 1 v 1 , ǫ) (βv 1 is adjoined) ⇒ adj, β v1 , 0, {β n1 } (n 1 n 2 n 1 v 2 v 1 , ǫ)
(adj. at ǫ, v1 scanned,

βn 1 put into LPA) ⇒ β v1 , {β n1 } (n 1 n 2 n 1 v 2 v 1 , ǫ) (βv 1 is adjoined) ⇒ adj, β v1 , 0, {β n1 , β n1 } (n 1 n 2 n 1 v 2 , ǫ)
(adj. at ǫ, v1 scanned,

βn 1 put into LPA) ⇒ β v2 , {β n1 , β n1 } (n 1 n 2 n 1 v 2 , ǫ) (βv 2 is adjoined) ⇒ adj, β v2 , ǫ, {β n2 , β n1 , β n1 } (n 1 n 2 n 1 , ǫ) (adj. at ǫ, v2 scanned, βn 2 put into LPA) ⇒ β n1 , {β n2 , β n1 } (n 1 n 2 n 1 , ǫ) (βn 1 from LPA adjoined)
⇒ adj, β n1 , 0, {β n2 , β n1 } (n 1 n 2 , ǫ) sub, β n1 , 1, (n 1 )

(adj. at ǫ,)

(subst. at 1) ⇒ adj, β n1 , 0, {β n2 , β n1 } (n 1 n 2 , ǫ) α n1 , ∅ (n 1 ) (subst. of αn 1 ) ⇒ adj, β n1 , 0, {β n2 , β n1 } (n 1 n 2 , ǫ) ǫ (n1 scanned) ⇒ β n2 , {β n1 } (n 1 n 2 , ǫ) (βn 2 from LPA adjoined) ⇒ adj, β n2 , 0, {β n1 } (n 1 , ǫ) sub, β n2 , 1, (n 2 ) (adj. at ǫ, subst. at 1) ⇒ adj, β n2 , 0, {β n1 } (n 1 , ǫ) α n2 , ∅ (n 2 ) (subst. of αn 2 ) ⇒ adj, β n2 , 0, {β n1 } (n 1 , ǫ) ǫ (n2 scanned) ⇒ β n1 , ∅ (n 1 , ǫ) (βn 1 from LPA adjoined) * ⇒ adj, β n1 , 0, ∅ (ǫ, ǫ) α n1 , ∅ (n 1 ) (subst. of αn 1 ) * ⇒ ǫ (scanning of n1)
This example requires LPAs of maximal cardinality 3, i.e., a 3-TT-MCTAG. Note that with this construction, the grouping into tree sets gets lost. E.g., in our example, we do not know which of the n 1 came with which of the v 1 . However, in our parser we construct the RCG only for the TT-MCTAG of a given input sentence and if the same terminal occurs more than once in the input sentence, we use different occurences of the correponding tree tuples.7 This way, we avoid using the same elementary tree twice and the grouping can be inferred from the tuple identifiers encoded in the names of the trees.

With the above construction the following can be shown:

Theorem 1. For each k-TT-MCTAG G there is a simple RCG G ′ with L(G) = L(G ′ ).
As a corollary, we obtain that the string languages of k-TT-MCTAG are mildly context-sensitive.

To prove the theorem, we introduce TT-RCG derivation trees:

Definition 10 (TT-RCG derivation tree) Let G ′ be an RCG constructed from a k-TT-MCTAG as above. A tree D G ′ with node and edge labels is a TT-RCG derivation tree for G ′ iff -each node in D G ′ is labeled with a predicate name γ, LP A and with a sequence of one or (if γ is an auxiliary tree) two w ∈ T * . -if the root predicate is γ, LP A , then there is a clause S → γ, LP A ; -if there is a node with predicate γ, LP A and with l daughters with predicates γ i , LP A ′ i and edge labels dot i (1 ≤ i ≤ l), then there is a γ, LP A -clause with adj... and sub... predicates on the righthand side as described in the construction such that • for all adjunction sites p in γ, p / ∈ {dot i | 1 ≤ i ≤ l}: LP A p = ∅, L p , R p = ǫ and there is a clause adj, γ, p, ∅ (ǫ, ǫ) → ǫ • for all adjunction sites p = dot i in γ (for some i, 1 ≤ i ≤ l): there is a clause adj, γ, dot i , LP A p (L, R) → γ i , LP A ′ i (L, R) • for all substitution sites p = dot i in γ (for some i, 1 ≤ i ≤ l): LP A ′ i = ∅ and there is a clause sub, γ, dot i (X) → γ i , ∅ (X) -if a node with label γ, LP A and w or w 1 , w 2 (if γ auxiliary) does not have a daughter, there is a clause γ, LP A (w) → ǫ or γ, LP A (w 1 , w 2 ) → ǫ respectively. -the sequences of strings for a mother node are computed from the daughters such that for at least one word w, the clauses leading from the mother to the daughters can be instantiated successfully.

Furthermore, we call a TAG derivation tree whose nodes are equipped with the yields of the derivation trees they root (one component for initial trees, two components for auxilary trees) and the set of arguments they dominate that actually depend on higher head trees a decorated TAG derivation tree.

Once these structures are defined, we can prove the correspondence between the decorated TAG derivation trees licensed in the k-TT-MCTAG G and the TT-RCG derivation trees of the RCG G ′ . More precisely, we show that for each decorated TAG derivation tree in G, there is an isomorphic TT-RCG derivation tree in G ′ and vice versa. We can show this by an induction on the height of the subtree rooted by a node. (Due to space limitations, we omit the proof here.)

Conclusion

This paper has investigated the relation between two grammar formalisms, TT-MCTAG and RCG. TT-MCTAG is a tree rewriting formalism that allows to adequately model the free word order in certain languages, e.g., German. RCG, on the other hand, is known to have nice formal properties: RCGs in general are polynomially parsable, simple RCGs are even mildly context-sensitive. Furthermore, parsing algorithms for simple RCGs are already available.

In this paper, we have shown how to construct for a given TT-MCTAG with a certain limitation (a so-called k-TT-MCTAG) an equivalent simple RCG. As a formal result, we obtain that the class of string languages generated by k-TT-MCTAG is contained in the class of languages generated by simple RCGs. In particular, k-TT-MCTAG are mildly context-sensitive.

As a practical result, we can use this transformation from k-TT-MCTAG to simple RCG for a 2-step k-TT-MCTAG parser that, in a first step, does the transformation and, in a second step, parses with the RCG obtained from the first step. As we have seen from the correspondence between the two derivation structures, the derivation tree of the k-TT-MCTAG can be retrieved from the RCG parse tree in a straightforward way. We have implemented this within a project that develops a TAG-based grammar for German along with a parser for this grammar.8

1 .Fig. 1 .

 11 Fig. 1. TAG derivation for John always laughs

  Fig. 2. A sample TAG and an equivalent RCG

  Fig. 4. TT-MCTAG

Since throughout the paper, we use only posisitive RCGs, whenever we say "RCG", we actually mean "positive RCG".

The intuition is that if a tree γ ′ adjoins to some γ, its root in the resulting derived tree somehow belongs both to γ and γ ′ , it is shared by them. A further tree β adjoining to this node can then be considered as adjoining to γ, not only to γ ′ as in standard TAG. Note that we assume that foot nodes do not allow adjunctions, otherwise node sharing would also apply to them.

For a tree γ, Pγ is the parent relation on the nodes, i.e., x, y ∈ Pγ iff x is the mother of y.

An alternative possibility would be to consider only γ and its arguments as the yield of γ. An argument of a higher head adjoining below γ would then interrupt the contribution of γ. This construction is more complex than the one we choose here.

We distinguish them via the position of the terminal in the input.

See http://www.sfb441.uni-tuebingen.de/emmy/tulipa.


Ikram Bouras
email: ikram.bouras@lirmm.fr

Rosa Figueiredo
email: rosa.figueiredo@univ-avignon.fr

Michael Poss
email: michael.poss@lirmm.fr

Fen Zhou
email: fen.zhou@univ-avignon.fr

A Bi-level Approach

Keywords: Energy-aware engineering, Bi-level programming, Multi-path, Cutting plane, Branch-and-Cut

In recent years, green networking has attracted a lot of attention from device manufacturers and Internet Service Providers (ISP) to reduce energy consumption. In the literature, energy-aware traffic engineering problem is proposed to minimize the total energy consumption by switching off unused network devices (routers and links) while guaranteeing full network connectivity.

In this work, we are interested in the problem of energy-aware Traffic Engineering while using multi-path routing (ETE-MPR) to minimize link capacity utilization in ISP backbone networks. To this end, we propose a bi-level optimization model where the upper level represents the energy management function, and the lower level refers to the deployed multi-path routing protocol. Then, we reformulate it as a one-level MILP replacing the second level problem by different sets of optimality conditions. We further use these formulations to solve the problem with classical branch-and-bound, cutting plane, and branchand-cut algorithms. The computational experiments are performed on real instances to compare the proposed algorithms and to evaluate the efficiency of our model against the existing single-path and multi-objective approaches.

Minimizing Energy and Link Utilization in ISP Backbone Networks with multi-path Routing

Introduction

As we are entering the era of Internet of Everything, the number of devices connected to the IP networks will increase by one and a half times the global population (8 billion) by 2022, says the latest Cisco Visual Networking Index (VNI) [START_REF]CISCO Visual Networking Index[END_REF]. Consequently, the monthly global IP traffic will be 77 exabytes by 2022, and the annual traffic will reach almost one zettabyte [START_REF]CISCO Visual Networking Index[END_REF]. With the tremendous growth of Internet traffic, the network energy consumption is inherently growing fast with a rate of 10% per year, which exceeded 350 TWh and represented 1.8% of the worldwide electricity consumption in 2012 [START_REF] Lambert | Worldwide electricity consumption of communication networks[END_REF]. It is even reported that communication networks will consume as much as 51% of the global electricity in the worst-case by 2030, if its energy efficiency is not improved enough [START_REF] Andrae | On global electricity usage of communication technology: Trends to 2030[END_REF]. Thus, the problem of energy efficiency is becoming critical for communication networks nowadays.

To reduce energy consumption, green networking has attracted a lot of attention from device manufacturers and Internet Service Providers (ISP). To this end, many technologies and approaches have been proposed by the networking community to cut the carbon footprint of the ISP backbone networks [START_REF] Addis | Energy management through optimized routing and device powering for greener communication networks[END_REF][START_REF] Amaldi | Energy-aware traffic engineering with elastic demands and MMF bandwidth allocation[END_REF][START_REF] Bolla | Energy efficiency in the future internet: A survey of existing approaches and trends in energy-aware fixed network infrastructures[END_REF][START_REF] Chiaraviglio | Minimizing isp network energy cost: Formulation and solutions[END_REF][START_REF] Dabaghi | A survey on green routing protocols using sleepscheduling in wired networks[END_REF][START_REF] Gupta | Greening of the internet[END_REF]. Among them, one promising solution is the energy management of network elements including routers and communication links [START_REF] Addis | Energy management through optimized routing and device powering for greener communication networks[END_REF][START_REF] Amaldi | Energy-aware traffic engineering with elastic demands and MMF bandwidth allocation[END_REF][START_REF] Chiaraviglio | Minimizing isp network energy cost: Formulation and solutions[END_REF][START_REF] Cianfrani | An OSPF-Integrated Routing Strategy for QoS-Aware Energy Saving in IP Backbone Networks[END_REF]. In fact, network resources like processing power and memory are oversized in communication networks nowadays, which results in a low utilization of 30-40% in low traffic periods [START_REF] Dabaghi | A survey on green routing protocols using sleepscheduling in wired networks[END_REF]. As a result, important energy savings can be obtained by switching into the sleeping mode the network elements which are not used for the data delivery during a certain period. Following this idea, authors in [START_REF] Chiaraviglio | Minimizing isp network energy cost: Formulation and solutions[END_REF] tried to minimize the total energy consumption by switching off unused network devices while guaranteeing full network connectivity. In [START_REF] Amaldi | Energy-aware traffic engineering with elastic demands and MMF bandwidth allocation[END_REF], the authors studied the energy-aware traffic engineering problem subject to elastic traffic and max-min fair bandwidth allocation. The work in [START_REF] Addis | Energy management through optimized routing and device powering for greener communication networks[END_REF] is focused on the energy minimization strategy that selectively switches off devices according to the traffic level. The authors of [START_REF] Cianfrani | An OSPF-Integrated Routing Strategy for QoS-Aware Energy Saving in IP Backbone Networks[END_REF] proposed an OSPF-integrated routing strategy for QoS-aware energy saving in backbone networks.

However, all the work mentioned above only considered the single-path routing (using protocols like Routing Information Protocol (RIP) or Open Shortest Path First (OSPF) protocol) for the energy-aware traffic engineering [START_REF] Addis | Energy management through optimized routing and device powering for greener communication networks[END_REF][START_REF] Amaldi | Energy-aware traffic engineering with elastic demands and MMF bandwidth allocation[END_REF][START_REF] Chiaraviglio | Minimizing isp network energy cost: Formulation and solutions[END_REF][START_REF] Cianfrani | An OSPF-Integrated Routing Strategy for QoS-Aware Energy Saving in IP Backbone Networks[END_REF], where only one path is used per communication request to deliver data from its source node to its destination. The single-path routing strategy may lead to a high blocking probability when some network links are congested during the period of high traffic load. In light of this, multi-path routing has been investigated [START_REF] Banner | Multipath routing algorithms for congestion minimization[END_REF][START_REF] Chen | A multipath routing mechanism in optical networks with extremely high bandwidth requests[END_REF][START_REF] Chiesa | Traffic engineering with equal-cost-multipath: An algorithmic perspective[END_REF][START_REF] Singh | A survey on internet multipath routing and provisioning[END_REF][START_REF] Li | Multipath transmission for the internet: A survey[END_REF][START_REF] Liu | Multipath routing from a traffic engineering perspective: How beneficial is it?[END_REF][START_REF] Zhang | Load balancing in ip networks using generalized destination-based multipath routing[END_REF].

Recent works show that Internet-wide multi-path routing is feasible and very attractive: First, utilizing diverse paths through multi-path routing en-ables to reduce blocking probability by load balancing, which permits to improve both the utilization efficiency of network bandwidth and the transmission reliability. Second, a higher Quality of Service (QoS) and Quality of Experience (QoE) can be obtained [START_REF] Lee | A survey of multipath routing for traffic engineering[END_REF][START_REF] Li | Multipath transmission for the internet: A survey[END_REF][START_REF] Singh | A survey on internet multipath routing and provisioning[END_REF]. Thus, many multi-path routing protocols and algorithms have been proposed, for instance, generalized destination-based multi-path routing [START_REF] Zhang | Load balancing in ip networks using generalized destination-based multipath routing[END_REF], equal-cost multi-path routing [START_REF] Chiesa | Traffic engineering with equal-cost-multipath: An algorithmic perspective[END_REF] and minimum routing cost multi-path routing [START_REF] Liu | Multipath routing from a traffic engineering perspective: How beneficial is it?[END_REF]. In general, there are two main variants of multi-path routing, whose optimization goal is either to minimize the network congestion ratio through load balancing [START_REF] Banner | Multipath routing algorithms for congestion minimization[END_REF][START_REF] He | Achieving near-optimal traffic engineering in hybrid software defined networks[END_REF][START_REF] Merindol | Improving load balancing with multipath routing[END_REF][START_REF] Zhang | Load balancing in ip networks using generalized destination-based multipath routing[END_REF], or to minimize the total routing cost of traffic flows on all paths [START_REF] Chen | A multipath routing mechanism in optical networks with extremely high bandwidth requests[END_REF][START_REF] Chiesa | Traffic engineering with equal-cost-multipath: An algorithmic perspective[END_REF][START_REF] Liu | Multipath routing from a traffic engineering perspective: How beneficial is it?[END_REF].

In this paper, we deal with the problem of energy-aware traffic engineering while using multi-path routing to minimize link capacity utilization in ISP backbone networks. We suppose the network control plane disposes of several key functions like energy management, routing, and signaling. To achieve energy-efficient, we suppose that the energy management function and the deployed routing protocol work independently. On the one hand, to improve the energy efficiency, the energy management function of the ISP network tends to minimize the network energy consumption by putting on sleep unused network devices according to the actual traffic demands. On the other hand, the network operator should also assure that the deployed routing protocol is able to provide all the traffic demands in the link capacity constraint. We assume that the multi-path routing protocol minimizing total link capacity utilization (a simple version of total routing cost of all traffic flows on paths) [START_REF] Liu | Multipath routing from a traffic engineering perspective: How beneficial is it?[END_REF][START_REF] Chen | A multipath routing mechanism in optical networks with extremely high bandwidth requests[END_REF][START_REF] Chiesa | Traffic engineering with equal-cost-multipath: An algorithmic perspective[END_REF] is used by the ISP network operator. However, the energy consumption and link capacity utilization cannot be optimized simultaneously, and an equilibrium should be achieved for the two control plane functions. Different from the literature, we propose a bi-level formulation for this green network optimization problem instead of the traditional single-level one [START_REF] Addis | Energy management through optimized routing and device powering for greener communication networks[END_REF].

Our bi-level formulation is motivated by the following two reasons. First, from the point of view of the ISP network operator, it is difficult to tune the weights of two network resources (i.e., energy consumption and link capacity utilization) so as to find a good trade-off. In contrast, our formulation enables to find an equilibrium between the two network resources utilization, which is transparent for the ISP network operator. Second, instead of developing new energy-aware routing protocols, we can take advantage of the existing work by deploying directly the proposed multi-path routing protocols in [START_REF] Liu | Multipath routing from a traffic engineering perspective: How beneficial is it?[END_REF][START_REF] Chen | A multipath routing mechanism in optical networks with extremely high bandwidth requests[END_REF][START_REF] Chiesa | Traffic engineering with equal-cost-multipath: An algorithmic perspective[END_REF], which minimize the total link capacity utilization. In our bi-level model, the upper level represents the energy management function aiming at cutting the total network energy consumption. The lower level refers to the deployed multi-path routing protocol, whose objective is to reduce the total link capacity utilization.

The novelties and contributions of this work can be summarized as follows:

-We study the problem of minimizing the network energy consumption while using multi-path routing to reduce link capacity utilization. To the best of our knowledge, it is the first time that this problem is investigated.

-From the perspective of optimization techniques, we formulate the studied problem as a bi-level optimization for the first time. To solve it, the bi-level formulation is then transformed into a one-level optimization using KKT conditions, minimum flow inequalities or residual network optimality conditions. A cutting plane and branch-and-cut methods are further proposed to solve the problem to optimality.

The rest of this paper is organized as follows. The energy-aware traffic engineering problem is presented in Section 2 and its bi-level formulation is given in Section 3. Then, in the same section, we reformulate the problem as a one-level MILP formulation by using different optimality conditions. In Section 4, several algorithms based on the MILP formulations are proposed to solve the studied problem. To verify the proposed models and solutions, numerical simulations have been conducted in Section 5. Finally, Section 6 concludes this paper.

Problem definition and notation

We consider an ISP backbone network (Figure 1) with slow dynamics, where the traffic demand is supposed to be relatively stable during a period of time. With the help of intelligent network management like Software Defined Networking (SDN), the control plane of the ISP network disposes of key functions like energy management and routing. This kind of network management permits us to change the state of network devices and engineer the traffic in a centralized way. To correctly model the energy consumption of a router, we should get familiar with its architecture. We consider the widely used router architecture, which consists of a chassis and a set of line cards [START_REF] Addis | Energy management through optimized routing and device powering for greener communication networks[END_REF][START_REF] Amaldi | Energy-aware traffic engineering with elastic demands and MMF bandwidth allocation[END_REF]. The chassis is used to provide computation and switching functionalities. One example can be chassis Junifer M10i. Line cards are usually used to provide communication interfaces and network processing. To achieve power savings, the router elements (chassis and line cards) can be powered on and off by the control plane energy management function. Once activated, the chassis has a constant energy consumption independent from the amount of traffic passing through the router. It should be noted that the chassis can only be put into sleep when all of its line cards are OFF. To satisfy heterogeneous traffic, a router can be plugged with different kinds of line cards, which result in distinct energy efficiencies. For instance, we have line cards like Gigabit-Eth (2Gbps), Fast-Eth 12 ports (2.4Gbps), SONET /SDH OC-48c (5Gbps), among others, whose capacity and hourly power consumption are listed in [START_REF] Addis | Energy management through optimized routing and device powering for greener communication networks[END_REF][START_REF] Amaldi | Energy-aware traffic engineering with elastic demands and MMF bandwidth allocation[END_REF]. However, a communication link must be connected to the same type of line cards available on the two ending routers. Thus, each communication link is accordingly associated with a capacity and an energy-efficiency factor, which depends on the types of line cards used. For energy savings, only a subset of line cards are powered on to assure just enough bandwidth for the carried traffic while the rest will be put to sleep. For simplicity reasons, we thus assume the energy consumption on communication links is proportional to its carried traffic rate. Fig. 2: The graph representation of the ISP network (Figure 1).

We consider the ISP backbone network modeled by the bi-directed graph G(V, A) (Figure 2), where V is the set of routers and A represents the set of communication links. Since the backbone networks are bi-directed and for modelling the activation link constraints (Section 3), we define the set of (undirected) edges associate to A as E = {{i, j} : (i, j) ∈ A or (j, i) ∈ A}.

Let C ij ≥ 0 denotes the capacity of the link (i, j) ∈ A defined by the line cards on routers i and j, and K be the set of traffic demands. Demand k ∈ K must send a volume of φ k from node o(k) to node d(k).We denote by P i the energy consumption of the chassis in router i, and we use g ij = g ji to denote the energy efficiency of the line cards connecting the link (i, j) ∈ A.

The energy-aware traffic engineering with multi-path routing problem (ETE-MPR) problem consists of selecting a set of routers (nodes) and links (edges) to be activated with minimum energy consumption. Assuming that each traffic demand uses a multi-path flow minimizing the total link capacity utilization.

Mathematical formulations

In this section, we will introduce four different formulations for the ETE-MPR problem. We start by a bi-level integer programming model in Subsection 3.1, then, the model will be transformed into three one-level MILP formulations (Subsections 3.2, 3.3 and 3.4). For comparison purposes, Subsection 3.5 will be devoted to present the unsplittable flow version of the energy-aware traffic problem.

Bi-level formulation

The problem is naturally cast as a bi-level optimization problem where the upper level represents the energy management function, and the lower level refers to the deployed multi-path routing protocol. For each i ∈ V and e(i, j) = {i, j} ∈ E, we introduce the binary variables z i and y e that represent the power status (ON/OFF) of router i and link e = {i, j}, respectively. Furthermore, for each k ∈ K and (i, j) ∈ A let the continuous positive variable x k ij be the flow on (i, j) of demand k.

The problem belongs to the class of NP-hard problems and can be modeled as a bi-level mixed integer programming problem, as follows:

min i∈V P i z i + (i,j)∈A k∈K g ij x k ij (1a) s.t. z i ∈ {0, 1} , ∀i ∈ V, (1b)
y e ≥ z i + z j -1, ∀e = {i, j} ∈ E, (1c)
y e ≤ z i , ∀e = {i, j} ∈ E, (1d)
y e ≤ z j , ∀e = {i, j} ∈ E, (1e)
min

k∈K (i,j)∈A x k ij (1f) s.t. (i,j)∈δ + (i) x k ij - (i,j)∈δ -(i) x k ji = b k i , ∀i ∈ V, ∀k ∈ K, (1g) k∈K x k ij ≤ C ij y e(i,j) , ∀(i, j) ∈ A, (1h) x k ij ≥ 0, ∀(i, j) ∈ A, ∀k ∈ K. (1i)
where:

b k i =      φ k , if i = o(k), -φ k , if i = d(k), 0, otherwise.
The upper-level objective function (1a) aims to minimize the energy consumption of routers and links, while the objective of the second level problem is to minimize the total link capacity utilization (1f). Constraints (1c)-(1e) ensure that a link (i, j) is activated only if the two routers i and j are switched ON. Constraints (1g) and (1h) define the classical flow and capacity constraints, respectively. While (1i) requires the variables x k ij to be non-negative.

One level formulation

The problem can be reformulated as a one-level integer programming problem by replacing the second level problem by the associated optimality conditions. Following the classical reformulation used in [START_REF] Bouras | On two new formulations for the fixed charge network design problem with shortest path constraints[END_REF][START_REF] Mauttone | A tabu search approach to solve a network design problem with user-optimal flows[END_REF][START_REF] Erkut | Solving the hazmat transport network design problem[END_REF], among others, we can apply the fundamental theorem of duality and complementarity slackness conditions [START_REF] Bazaraa | Linear programming and network flows[END_REF] to replace the follower problem:

min i∈V P i z i + (i,j)∈A k∈K g ij x k ij s.t. (1b) -(1e), (i,j)∈δ + (i) x k ij - (i,j)∈δ -(i) x k ji = b k i , ∀i ∈ V, ∀k ∈ K, (2a)
(C ij y e(i,j) - k∈K x k ij )W ij = 0, ∀(i, j) ∈ A, ∀k ∈ K, (2b)
(1 + π k i -π k j + W ij )x k ij = 0, ∀(i, j) ∈ A, ∀k ∈ K, (2c) 1 + π k i -π k j + W ij ≥ 0, ∀(i, j) ∈ A, ∀k ∈ K, ( 2d
) k∈K x k ij ≤ C ij y e(i,j) , ∀(i, j) ∈ A, (2e)
W ij ≥ 0, ∀(i, j) ∈ A, (2f)
π k i ∈ R, ∀i ∈ V, ∀k ∈ K, (2g)
x k ij ≥ 0, ∀(i, j) ∈ A, ∀k ∈ K. (2h)
This formulation contains non-linear constraints (2b) and (2c). We can linearize them using the big-M method by adding a new binary variable for each constraint. After this modification, we obtain a one-level mixed integer programming reformulation for (1), as follows:

min i∈V P i z i + (i,j)∈A k∈K g ij x k ij s.t. (1b) -(1e), (2d) -(2h) (i,j)∈δ + (i) x k ij - (i,j)∈δ -(i) x k ji = b k i , ∀i ∈ V, ∀k ∈ K, (3a)
C ij y ee(i,j) - k∈K x k ij ≤ M η ij , ∀(i, j) ∈ A, (3b)
M η ij + W ij ≤ M, ∀(i, j) ∈ A, (3c) 1
+ π k i -π k j + W ij ≤ M µ k ij , ∀(i, j) ∈ A, ∀k ∈ K, (3d)
M µ k ij + x k ij ≤ M, ∀(i, j) ∈ A, ∀k ∈ K, (3e)
η ij ∈ {0, 1} , ∀(i, j) ∈ A, (3f)
µ k ij ∈ {0, 1} , ∀(i, j) ∈ A, ∀k ∈ K. ( 3g
)
where M is a precomputed large number. Unlike the other constraints, where the value of M cannot be bounded, in constraint (3b) M can be replaced by a lower bound M = C ij for each (i, j) ∈ A.

BILP formulation based on flow constraints

We propose an alternative one level formulation to the problem where the second level problem is replaced by a set of constraints eliminating unfeasible flows. Let us denote by F the set of all feasible flows defined as:

F = {F = (x, y, z) : (1b) -(1e), (1g) -(1i)} For each F ∈ F, we also define C(F ) = k∈K (i,j)∈A
x k ij as the total capacity link utilization of a flow F and G(F ) = {e ∈ E : y e = 1} as the associated set of activated edges.

The flow F = (x, y, z) is bi-level unfeasible if there exists a solution F = (x , y, z) ∈ F such that:

C(F ) < C(F ).
Hence, the bi-level problem can be reformulated as:

min i∈V P i z i + (i,j)∈A k∈K g ij x k ij s.t. (1b) -(1e) (i,j)∈δ + (i) x k ij - (i,j)∈δ -(i) x k ji = b k i , ∀i ∈ V, ∀k ∈ K, (4a)
k∈K (i,j)∈A

x k ij ≤ C(F ) + (|G(F )| - e∈G(F ) ye)M, ∀F ∈ F , ( 4b
) k∈K x k ij ≤ C ij y e(i,j) , ∀(i, j) ∈ A, (4c)
x k ij ≥ 0, ∀(i, j) ∈ A, ∀k ∈ K. ( 4d
)
Constraint (4b) is in charge of eliminating all bi-level unfeasible flows F on the set of activated links {e = {i, j} ∈ E : y e = 1}. Again, M is a precomputed large number. The above formulation contains a polynomial number of variables and an exponential number of constraints.

Residual network optimality conditions

We can remark that the follower problem is a particular case of the minimum cost flow problem where the cost of each arc is equal to 1. In this subsection, we propose to reformulate this problem by using a set of optimality conditions for the min-cost flow problems defined on the residual network.

We start by giving the definition of the residual network and the associated optimality conditions. Let x k = (x k ij ) (i,j)∈A ∈ R |A| be the flow between the origin-destination pair of demand k ∈ K. Notice that x = (x k ) kı,K ∈ R |A|×|K| .

Definition 1 (Residual network)

The residual network associated to x k is the graph denoted by G k (x) = (V, A k (x)) and defined by the set of activated and unsaturated arcs A k (x). This set of arcs is defined as the union of the two following sets:

A k+ (x) = (i, j) ∈ A : 0 < k ∈K x k ij < C ij , x k ji = 0 A k-(x) = (i, j) ∈ A : x k ji > 0 .
Each arc of G k (x) is associated with a residual cost c k defined as: (c) The residual network of (3a).

c k ij = 1, if (i, j) ∈ A k+ , -1, if (i, j) ∈ A k-.
s

1 2 d 3 1 -1 -1 -1 1 -1 1 -1 (d)
The residual network of (3b).

Fig. 3: Example of an unfeasible (feasible) flow violating (satisfying) negative cycle conditions. All link capacities are equal to 2 with Φ = 3 to be sent from s to d.

Theorem 1 (Residual network optimality ([2], chapter 9)) A feasible flow x k of a demand k is optimal if and only if the network G(x k ) has no negative cycles. This condition is equivalent to:

c k ij + Π k i -Π k j ≥ 0, ∀(i, j) ∈ G(x k ), ∀k ∈ K. ( 5a
)
To illustrate, let us consider the example in Figure 3. We suppose that the capacity of each link is equal to 2 and we have a demand with φ = 3 to be sent from the node s to d. Figure 3 represents two solutions (3a) and (3b) and the associated residual networks (3c) and (3d), respectively. The solution in Figure (3a) is unfeasible because the associated residual network contains a negative cycle: s-3-d-2-1-s (resp,(3b) is feasible because (3d) contains no negative cycle).

We can model the residual network associated with a demand k by using binary variables µ k+ ij , µ k- ij , and the additional variables ν ij for each (i, j) ∈ A.

Proposition 1 Let µ ∈ {0, 1} 2×|A|×|K| , ν ∈ {0, 1} |A| be a solution of:

C ij - k ∈K x k ij ≤ C ij ν ij , ∀(i, j) ∈ A, (6a)
µ k+ ij + µ k- ij ≤ y e(i,j) , ∀(i, j) ∈ A, (6b)
µ k- ij ≤ x k ji ∀(i, j) ∈ A, (6c)
C ji µ k- ij ≥ x k ji ∀(i, j) ∈ A, (6d)
C ij µ k+ ij ≤ C ij - k ∈K x k ij ∀(i, j) ∈ A, (6e)
µ k+ ij ≥ y e -µ k- ij + ν ij -1 ∀(i, j) ∈ A, (6f)
µ k+ ij , µ k- ij ∈ {0, 1} ∀(i, j) ∈ A, (6g)
ν ij ∈ {0, 1} ∀(i, j) ∈ A. (6h) 1. For each (i, j) ∈ A, ν ij = 1 if: k∈K x k ij < C ij . 2. Arc (i, j) ∈ A k-(x) iff: µ k- ij = 1. 3. Arc (i, j) ∈ A k+ (x) iff: µ k+ ij = 1.
Proof We see that the set of constraints (6a)-(6h) is decomposable by arc. Hence, consider an arc (i, j) ∈ A.

1. is guaranteed by constraints (6a). 2. is guaranteed by constraints (6c) and (6d):

-(i, j) / ∈ A k-⇒ x k ji = 0 (6c) = = ⇒ µ k- ij = 0. -(i, j) ∈ A k-⇒ x k ji > 0 (6d) = = ⇒ µ k- ij = 1.

is guaranteed by constraints (6a)-(6f):

-(i, j) ∈ A k+ (6a),(6c)

= ====== ⇒ µ k- ij = 0 and ν ii = 1

(6f) = = ⇒ µ k+ ij = 1. -(i, j) / ∈ A k+ Definition 1 = ====== ⇒          C ij - k∈K x k ij = 0 (6e) = = ⇒ µ k+ ij = 0, or x k ji > 0 (6c),(6f) = ==== ⇒ µ k+ ij = 0.
Hence, for any solution to (6), arc (i, j)

∈ A k+ (x) (resp. (i, j) ∈ A k-(x)) if µ k+ ij = 1 (resp. µ k- ij = 1).
Using Theorem 1 and Proposition 1, the ETE-MPR problem can be reformulated with the residual network optimality conditions.

min i∈V P i z i + (i,j)∈A k∈K g ij x k ij s.t. (1b) -(1e), (6a) -(6h), (i,j)∈δ + (i) x k ij - (i,j)∈δ -(i) x k ji = b k i , ∀i ∈ V, ∀k ∈ K, ( 7a
) k∈K x k ij ≤ C ij y e(i,j) , ∀(i, j) ∈ A, (7b) 1 + π k i -π k j ≥ M (µ k+ ij -1) ∀(i, j) ∈ A, ∀k ∈ K (7c) -1 + π k i -π k j ≥ M (µ k- ij -1) ∀(i, j) ∈ A, ∀k ∈ K (7d) x k ij ≥ 0, ∀(i, j) ∈ A, ∀k ∈ K. ( 7e
)
Constraints (7c) and (7d) eliminate negative cycles in the residual network associated to each flow x k , for all k ∈ K. Since these constraints represent optimality condition (5a) associated to our problem.

Single path routing

Section 5 presents a comparison of the multi-path routing model with the existing single-path model. Thus, in this subsection, we describe the bi-level problem of minimizing energy and link utilization while using a single path protocol OSPF. The single-path routing problem consists of finding a single shortest path for each demand k ∈ K from its source node o(k) to the destination node d(k). This problem can be formulated as:

min i∈V P i z i + (i,j)∈A k∈K g ij φ k x k ij s.t. (1b) -(1e), min k∈K (i,j)∈A x k ij (8a) s.t. (i,j)∈δ + (i) x k ij - (i,j)∈δ -(i) x k ji = b k i , ∀i ∈ V, ∀k ∈ K, (8b) k∈K φ k x k ij ≤ C ij y e(i,j) , ∀(i, j) ∈ A, (8c)
x k ij ∈ {0, 1}, ∀(i, j) ∈ A, ∀k ∈ K, ( 8d
)
where:

b k i =      1, if i = o(k), -1, if i = d(k), 0,
otherwise.

x k ∈ {0, 1} |A| represents here the path for demand k. Then, the flow in each arc (i, j) ∈ A will be given by φ k x k ij in this single-path routing model. The follower problem is now an integer linear program. Thus, the KKT optimality conditions cannot be applied here. We propose to formulate the single-path routing problem as a one level BILP program with flow elimination constraints as:

min i∈V P i z i + (i,j)∈A k∈K g ij φ k x k ij s.t. (1b) -(1e), (i,j)∈δ + (i) x k ij - (i,j)∈δ -(i) x k ji = b k i , ∀i ∈ V, ∀k ∈ K, ( 9a
) k∈K φ k x k ij ≤ C ij y e(i,j) , ∀(i, j) ∈ A, ( 9b
)
k∈K (i,j)∈A x k ij ≤ C(P ) + (|E(P )| - e∈E(P ) ye)M, ∀P ∈ P, (9c)
x k ij ∈ {0, 1}, ∀(i, j) ∈ A, ∀k ∈ K. ( 9d
)
where, P is the set of all feasible solutions P = (x * , y * , z * ), and E(P ) is the set of activated arcs on P defined by E(P ) = {e ∈ E : y * = 1}. In (9c), C(P ) represents the total cost of P , and M is a precomputed large number that can be replaced by k∈K Φ k . The single-path routing problem is studied in [START_REF] Bouras | On two new formulations for the fixed charge network design problem with shortest path constraints[END_REF] without capacity constraints, in this paper, the bi-level problem is reformulated using the constraint (9c) which gave good results comparing the other proposed reformulations.

Algorithms

In Subsections 3.2, 3.3, and 3.4, we presented three different formulations for ETE-MPR the problem. Formulations (3) and ( 7) are compact ones, while formulation (4) may have an exponential number of constraints. In this section, first, we focus on presenting different exact methods to deal with the problem formulations (Subsections 4.1, 4.2 and 4.3). Then, we present how formulation (8) will be solved (Subsection 4.4).

Compact formulations

The first way to solve the problem is to feed the one level models based on KKT (3) and residual network optimality conditions [START_REF] Bolla | Energy efficiency in the future internet: A survey of existing approaches and trends in energy-aware fixed network infrastructures[END_REF] to an ILP solver with default parameters. Let KKT and RN denote the solution methods obtained, respectively.

Cutting plane algorithm

In this subsection, we discuss how to solve our problem with a cutting plane (CP-FC) algorithm based on the MILP formulation (4). This algorithm is described in the following:

1. Let P be the first level problem minimizing the sum of the energy consumption and the arc utilization:

min i∈V P i z i + (i,j)∈A k∈K g ij x k ij s.t. (1b) -(1e), (1g) -(1i).
2. Solve P and let F * = (z * , y * , x * ) be the solution obtained.

3. Let N * be the subnetwork defined by the set of activated routers (z * , y * ), and solve the second level problem (minimization of the link capacity utilization) in N * . Let x be the flow obtained and F = (z * , y * , x ). 4. If C(F ) = C(F ), then the solution (z * , y * , x * ) is optimal, stop. Otherwise, add the inequality (4b) associated with the solution F * as a new constraint to P in order to cut the unfeasible solution (z * , y * , x * ). 5. Go to step 2. The procedure described above is repeated until the optimal solution is found.

Branch-and-cut algorithm

The one-level formulation (4) can also be used to solve the ETE-MPR problem by a branch-and-cut (B&C-FC) algorithm.

The main idea of the algorithm used here is to solve the first level problem (without taking in consideration the minimization of the total traffic) by a branch-and-bound procedure and to add valid inequalities (4b) at each integral node of branch-and-bound tree violating the min-cost flow constraints. Once an integral node of the branch-and-bound tree is reached, i.e. a node where an integer solution has been found, if an inequality (4b) is violated, it is added to the problem through callbacks. In the sequence, the algorithm continues the search for an integer optimal solution satisfying all flow constraints. The algorithm stops when there are no more nodes to evaluate, i.e., all the required missing flow constraints (4b) were generated.

The difference between this algorithm and the iterative cutting plane algorithm presented in Subsection 4.2 lies in solving a unique MILP while one MILP is solved from scratch at each iteration of the algorithm previous presented.

Single path routing

The single-path routing is a generalization of the fixed charge network design problem with shortest path constraints (FCNDP-SCP) studied in [START_REF] Bouras | On two new formulations for the fixed charge network design problem with shortest path constraints[END_REF]. Because of the capacity constraints added to the problem, the algorithms proposed in [START_REF] Bouras | On two new formulations for the fixed charge network design problem with shortest path constraints[END_REF] are no longer applicable.

One of the ways to solve it is to use the iterative cutting plane algorithm presented in Subsection 4.2. The only difference is that we now solve the first level problem of ( 8), and we cut a path violating shortest path requirement in each iteration by adding valid inequalities (9c).

Numerical results

In this section, we present two different experiments. First, we compare in Subsection 5.2 the CPU time of the algorithms presented in subsections 4.1-4.3 to obtain optimal solutions. Then, in order to compare our multi-path bi-level model with the existing single-path model, numerical evaluations are performed to compare the improvement on values of optimal solutions in Subsection 5.3.

All algorithms are implemented in Julia 0.6.0, and the problems are solved using Gurobi 7.5.1 with default parameters and a time limit of 3600s. Simulations were performed on an Intel(R)core TM i7-6500M CPU@2.50 2.60GHz computer with 8 GB of RAM.

Instances set

Our computational experiments have been carried out on different network topologies provided by [START_REF] Orlowski | SNDlib 1.0-Survivable Network Design Library[END_REF] and depicted in Figure 4: Abilene (4a), Polska (4b), and Geant (4c) networks. The capacity of line cards and the energy consumption of each chassis are randomly chosen from the three cases in Table First, we compare the different algorithms presented in subsections 4.1-4.3 with respect to solution times. The obtained results are reported in Tables 3,4 and 5. These tables present for each instance, the CPU time in seconds spent by the different algorithms to get the optimal solutions. The symbol in the tables of results "-" means that the algorithm was not able to find the optimal solution in the time limit of 3600s for the considered instance. The results show that the iterative cutting plane and branch-and-cut algorithms are close in terms of CPU time and outperform significantly the compact formulations. Also, We can remark, comparing the different tables, that the Geant instance (Figure (4c)) is more difficult than the other instances in terms of CPU time. If we consider, for instance, the cutting plane algorithm, the CPU time average to find the optimal solutions for Geant instance is more than 200 times the CPU time of Abilene network and 100 times the CPU time of Polska network. Furthermore, for all instances, we observe that the first scenarios 1, 2, and 3 are easier than the last ones 4 and 5 according to the running time of all algorithms. These results can be explained by the difference in the size and the number of demands in each scenario and instance.

Furthermore, the residual network formulation is faster than the formulation based on KKT conditions.

Single path routing vs multi-path routing

We compared our multi-path model with the single-path approach (where each demand uses one path). Tables 6 and7 summarize the obtained results. For each instance, we compare the first and the second level optimal solution obtained under the two settings: single and multi-path routing. We can easily remark that using the multi-path leads to lower network energy consumption (the first level objective function) for 9/15 instances. This is because in the single-path approach, we need to activate more routers and links in the case of insufficient link capacity, unlike the multi-path where the flow can be distributed. In addition, and for the same reason, in 7/15 instances, the total traffic (the second level problem) is reduced. To conclude, Table 8 reports the percentage of the reduction of energy consumption (First level objective) and capacity link utilization (Second level objective) when we use the multi-path approach. It is clear that, in the worst case, the two models give the same solution. Lastly, the quantity of the energy and the capacity of links saved even if the average the obtained gaps are small. Considering for example, the third instance of Geant network, the percentage of the energy reduced is small (10.30%), but, it represents more than 13000 (unity of energy).

Instances

Conclusion

In this paper, we have studied the problem of Energy-aware Traffic Engineering using a multi-path routing protocol (ETE-MPR) to minimize link capacity utilization in ISP backbone networks. To formulate the problem, we proposed a new bi-level optimization model where the objective of the upper-level problem Table 8: Percentage of the reduction on the first and the second level objectives using the multi-path model.

is to activate network devices minimizing the energy consumption, and the lower level represents a multi-path routing protocol. Then, we presented two one-level MILP formulations, respectively, based on complementarity slackness optimality and on residual network conditions and a BILP formulation using unfeasible flow elimination constraint.

The obtained results show that the iterative cutting plane and branchand-cut algorithms are close in terms of CPU time and outperform the compact formulations. Furthermore, the residual network formulation obtained the optimal solution in CPU time faster than the formulation based on KKT conditions.

Fig. 1 :

 1 Fig. 1: ISP model architecture.

Fig. 4 :

 4 Fig. 4: Examined network topologies: (a) Abilene (b) Polska (c) Geant [24].

Table 1 :

 1 1 (Table 1[START_REF] Amaldi | Energy-aware traffic engineering with elastic demands and MMF bandwidth allocation[END_REF]). Router chassis and cards Five different instances are generated for each network topology. Let |V e | be the number of nodes selected to be origin or destination point, and |K| is the number of demands. Network instances are summarized in Table2.The demand between each origin-destination pair is randomly generated in [100, 700] Mgbs.

		Chassis Features
	Case	device	capacity	hourly power consumption
	1	Gigabit-Eth 1 port	2 Gbps	7.3 W
	2	Fast-Eth 12 ports	2.4 Gbps	18.6 W
	3	Gigabit-Eth 4 ports	8 Gbps	31 W
	4	SONET /SDH OC-48c	5 Gbps	41.4 W

Table 2 :

 2 Network topologies used.

	5.2 Solution times
	Instances	KKT	RN	CP-FC B&C-FC
	1	0.08	0.08	0.03	0.34
	2	0.35	0.94	0.09	0.06
	3	2.31	3.47	0.10	0.07
	4	6.84	6.11	0.10	0.11
	5	19.19 10.12	0.12	0.11
	Average	5.76	4.14	0.09	0.14

Table 3 :

 3 Comparison of CPU time on Abilene network.

Table 4 :

 4 Comparison of CPU time on Geant network.

Table 5 :

 5 Comparison of CPU time on Polska network.

		Abilene network	Geant network	Polska network
	Instances	multi-path single path	multi-path single path	multi-path single path
	1	21531.7	21531.7	20856.8	20856.8	33900.4	33900.4
	2	97076.9	97076.9	35949.8	35949.8	67535.8	67535.8
	3	199014.3	199512.3	118786.9	132426.9	104429.8	107261.8
	4	200820.3	204881.3	220255.3	223851.4	176674.7	181298.7
	5	220454.3	224991.3	200819.3	203373.3	290679.3	291752.3
	Average	147779.5	149598.7	119333.62	123291.64	134644	136349.8

Table 6 :

 6 Comparison of the first level solution of the multi-path and the singlepath approaches.

		Abilene network	Geant network	Polska network
	Instances	multi-path single path	multi-path single path	multi-path single path
	1	4908	4908	6423	6423	7848	7848
	2	21791	21791	13018	13018	14410	14410
	3	39572	39771	31941	32396	26346	26346
	4	40642	42176	49948	51548	36688	36688
	5	44003	45892	50105	50450	56448	56459
	Average	30183.2	30907.6	30287	30767	28348	28350.2

Table 7 :

 7 Comparison of the second level solution of the multi-path and the single-path approaches.


David Zarzoso

Diego Del-Castillo-Negrete

Anomalous losses of energetic particles in fusion plasmas

come

Anomalous losses of energetic particles in fusion plasmas

David Zarzoso

Aix-Marseille Université, CNRS, PIIM, UMR 7345 Marseille, France. *

Diego del-Castillo-Negrete

Oak Ridge National Laboratory, Oak Ridge, Tennessee 37831-8071, USA (Dated: September 10, 2019)

The confinement of energetic particles (EP) in nuclear fusion devices is studied in the presence of an oscillating electrostatic potential and an axi-symmetric magnetic equilibrium. Despite the poloidal and toroidal symmetries, radial transport is observed. The transport leads to an algebraic decaying loss time, which is at odds with diffusive transport that predicts a faster exponential decay. A dynamical explanation of the observed anomalous loss time decay is presented. It is shown that transport is characterized by Lévy flights that lead to super-diffusive poloidal transport and asymmetric non-Gaussian (Lévy) probability distribution functions of displacements. The anomalous scaling exponents are shown to be consistent with the Continuous Time Random Walk (CTRW) theory. The results imply that EP might efficiently slowed down by the thermal population before leaving the system. Also, the asymmetric transport can potentially lead to a net torque.

Energetic particles (EP) are ubiquitous in both laboratory and astrophysical plasmas. They exhibit energies much larger than the thermal energy of the bulk plasma. In laboratory devices, the confinement can be ensured by the superposition of toroidal and poloidal magnetic fields forming nested toroidal flux surfaces where particles are supposed to remain, which is the principle of the tokamak. However, due to the curvature of the magnetic field lines, the trajectories of particles depart from the magnetic flux surfaces. This departure (called magnetic drift) is more pronounced when the energy of particles increases. Therefore, the magnetic drift of EP can be intense enough so that their trajectories intercept the wall even with circular concentric magnetic surfaces, leading to losses and limiting the performance of the machine. In addition, the presence of a substantial population of EP leads to gradients of the distribution function in phase space, which may result in instabilities called energetic particle modes (EPM) (see e.g. [1][2][3][4] and Refs. therein). EPM tend to increase the transport of EP, reducing inevitably the tokamak performance. It is well-established that EP, such as α particles, must be sufficiently well confined in order to transfer their energy to the bulk plasma and achieve the steady-state production of nuclear reactions or to ensure the current drive efficiency [5][6][START_REF] Pinches | Plasma physics and controlled fusion[END_REF]. Therefore, determining whether EP will remain enough time confined in the presence of EPM to be slowed-down by the thermal population is of prime importance for future fusion devices like ITER. In the presence of perturbations driven by EP, phase-space zonal flow structures can be generated, similarly to those driven by drift-wave turbulence [8]. Because of the importance that zonal structures play in the performance of tokamaks, it is essential to determine their impact on the EP transport. For this purpose, we focus our analysis on a special class of EPM called energetic geodesic acoustic modes (EGAMs), dominated by a zonal structure oscillating at the acoustic frequency [9][10][11][12][13]. This case exhibits additional interest because EGAMs are axisymmetric and therefore were initially believed not to play a significant role in the radial transport of particles. Nonetheless, there is experimental and numerical evidence that losses can occur in the presence of these axi-symmetric large scale modes [10,14]. It was in particular shown that most of these losses are due to chaotic transport in phase-space [15]. So far, no systematic studies of the confinement time of EP and the nature of the transport in the presence of such zonal structures have been conducted. For this purpose, statistical analyses can be performed to uncover the underlying physics of the induced EP losses. Although we focus on EGAMs, the analysis and results can be extended without any loss of generality to situations where zonal structures are generated by small amplitude perturbations.

To have meaningful statistics, a very large number of test particles during sufficiently long simulations is required. Due to computational restrictions, we replace the EGAM potential obtained from expensive direct simulations by an analytical model containing the main physics. This strategy is the most favorable in terms of CPU time, since no interpolation of the field is required. In addition, it allows us to simulate trajectories on time scales comparable with the experimental measurements. A zonal structure can be modeled as φ (r, t) ≈ φ 00 (r) cos (ωt), and based on previous simulations [16], the radial dependence is approximated as φ 00 (r) = φ 00 1 -tanh r-r0 δr , where φ 00 is the value of the potential at r = r 0 and δr controls the width of the mode. We solve the equations of motion of guidingcentres in toroidal geometry [17]

dx i dt = v b * s • ∇x i + v E • ∇x i + v D • ∇x i (1a) m s dv dt = -µb * s •∇B-eZ s b * s •∇J 0 φ+ m s v B v E •∇B (1b)
where x i is the i th contravariant component of the coordinate x (x 1 ≡ r in the radial direction, x 2 ≡ θ in the poloidal direction and x 3 ≡ ϕ in the toroidal direction), v is the parallel component of the velocity along the magnetic field lines, v E is the E × B drift, v D is the magnetic drift, µ is the magnetic moment, which is an invariant within the present model, m s is the mass of particles, e is the elementary charge, Z s is the atomic number, B is the magnitude of the magnetic field, J 0 is the gyro-average operator and b

* s = B B * ,s + msv eZsB * ,s B ∇×B with B * ,s = B + ms eZs v b•∇×b
, where b is the unit vector along the magnetic field. We use a simplified magnetic equilibrium characterised by circular concentric flux surfaces. To further reduce the computational time, due to the axisymmetry of the electrostatic potential, the equation for the toroidal angle does not need to be integrated to determine the radial transport. Axysimmetry also implies the conservation of the toroidal canonical angular momentum P ϕ = -eZ s ψ + m s Rv ϕ = constant, where v ϕ is the toroidal velocity, R is the major radius and ψ is the poloidal flux, which is written for circular flux surfaces in terms of the safety factor q, the amplitude of the magnetic field at the magnetic axis B 0 and the radial position r as ψ = B 0 r 0 r q(r ) dr . The conservation of P ϕ allows us to obtain the parallel velocity v without integrating equation (1b). Finally, for a large scale zonal structure the gyro-average is not expected to play a major role. Therefore, we make the simplification J 0 • φ = φ. This numerical scheme reduces the number of differential equations to integrate and ensures the conservation of the toroidal canonical momentum within machine precision.

We assume that the minor radius of the tokamak (a) and the thermal ion Larmor radius (ρ th ) are such that ρ = 1/150, with ρ = ρ th /a. This reduced model is applied to calculate the exit time of an ensemble of counter-passing EP, characteristic of NBI heating. For this purpose, we follow ∼ 4 • 10 5 deuterium tracers initialised at the position r = 0.4a, θ = 0, ϕ = 0, with energy E ≈ 20E th and magnetic moment such that µB 0 /T i = 14. These particles are confined in the absence of any perturbation. We use Gysela normalizations [17], but one can recover the units by choosing parameters for standard tokamaks. For instance, with T i ≈ 4 keV and B 0 ≈ 2 T, one gets a ≈ 0.67 m. Using the amplitude of the EGAM in nonlinear Gysela simulations, and using the electron temperature T e ≈ 3 keV, the amplitude of the radial electric field is E r,0 ≈ 14 kV • m -1 . Despite the simple structure of φ, its time dependence leads to radial transport and losses. The probability distribution function (PDF) of the exit time, P exit , is plotted in Fig. 1 in log -log scale, showing an algebraic decay P exit ∼ t -µe , in contrast with the exponential decay one would expect from a diffusive transport [START_REF] Gardiner | Handbook of stochastic methods[END_REF]. For the parameters chosen here, the tail of the PDF is developed from 1 -100 ms, which is of the order of, or greater than, the slowing-down time. In other words, these EP will remain sufficiently well confined to transfer their energy to the thermal population.

To understand why this algebraic decay occurs, we focus on the region responsible for the chaotic transport of particles, i.e. the stochastic layer separating the passing and trapped particles. The black dots in Fig. 2 represent the Poincaré map of the unperturbed trajectories for passing and trapped particles. The dashed blue lines with arrows indicate the direction of the trajectories of the particles contained in each region. Therefore, injected counter-passing particles rotate in the clockwise direction. When they become trapped and eventually copassing, they rotate in the anti-clockwise direction. This occurs in the outer region of the tokamak, where particles can intercept the wall and be lost. The red region represents the Poincaré map of particles located on the separatrix in the presence of an oscillating radial electric field. It is clearly observed that the separatrix is transformed into a chaotic area connecting the inner and outer parts of the tokamak. This separation between inner and outer regions is done strictly speaking in the radial direction. Since the radial region that the particle explores when going from one region to another is necessarily bounded by the minor radius of the tokamak, the statistics might be meaningless when focusing on the radial excursion of particles. However, due to the conservation of P ϕ , the radial position is intrinsically linked to the parallel velocity, which is in turn linked to the time derivative of the poloidal angle. In other words, when the counterpassing particle is confined in the core of the tokamak the poloidal angle decreases, and when the particle becomes co-passing in the outer region the poloidal angle increases. Contrary to the behaviour of the radial position, the poloidal angle that the particle explores can be arbitrarily large. Therefore, the statistical analysis of the FIG. 2: Poincaré map of unperturbed trajectories (black lines) and particles initialised on the separatrix in the presence of an EGAM (red dots). The direction of rotation of particles is represented by dashed blue lines. poloidal excursion can be easily done with the possibility to be connected to the radial excursion.

For this purpose, we follow during 10 7 cyclotron periods an ensemble of 10 5 EP initialised with E ≈ 20E th in the chaotic region. The nature of the transport can be analysed using the variance of the poloidal displacement, defined as σ 2 θ (t) = (∆θ (t) -∆θ (t) ) 2 , where ∆θ (t) = θ (t) -θ (0) is the poloidal displacement and the brackets • • • represent ensemble average. When the variance exhibits algebraic growth in time, i.e. σ 2 θ (t) ∼ t γ , the transport can be classified as: (i) sub-diffusive, if γ < 1, (ii) diffusive, if γ = 1, (iii) super-diffusive, if 1 < γ < 2, and (iv) ballistic, if γ = 2. The super-and sub-diffusive regimes correspond to anomalous diffusion. In Fig. 3 we represent by open red symbols the time trace (in log -log scale) of the variance of the poloidal displacement as measured from our simulations. The solid red line represents the linear fit in log -log scale. For comparison, we also show the ballistic (dotted-dashed black line) and diffusive (dotted blue line) scalings. Our simulation is bounded by both processes, with γ ≈ 1.64, meaning that transport is super-diffusive.

We interpret the observed super-diffusive transport in the framework of the Continuous Time Random Walk (CTRW) model. The CTRW extends the standard Brownian random walk (which underlies diffusive transport) by allowing non-Gaussian jump distributions and/or non-Markovian waiting time distributions [START_REF] Montroll | [END_REF]. Of particular interest to this work is the case of Lévy flights which are jumps with diverging second moments. The existence of flights in the transport of EP is evident in Fig. 4 that shows the poloidal displacement of two tracers. It is observed that the particles stochastically alternate between being trapped in the magnetic well (with no net poloidal displacement) and passing in the co-rotating or counter-rotating directions. It is interesting to point out the close conceptual analogy of this problem with the study of passive tracers in fluids in the presence of vortices (responsible for the trapping) and zonal shear flows (responsible for the flights) [20].

Coming back to Fig. 2, when an EP becomes trapped it is lost if the wall of the tokamak intercepts the chaotic region, which is the case here since a = 150ρ th . The exit time of a counter-passing particle is related to the time a particle spends moving towards negative poloidal angles, since the particle remains in the inner region of the tokamak. Accordingly, the probability distribution function (PDF) of the exit time, P exit , corresponds to the PDF of the negative flights of duration t, P - flight . To verify this connection, Fig. 5 shows the PDF of negative (top) and positive (bottom) flights of duration t. As expected, the PDF of negative flights exhibits an algebraic decay, P - flight ∼ t -µ f , with µ f ≈ µ e , where as shown in Fig. 1 P exit ∼ t -µe . The PDF of positive flights decays faster, following an exponential scaling (P - flight ∼ e -λt ). This finding has a physical impact in terms of radial transport: a counter-passing particle spends, probabilistically speaking, more time in the inner region than a co-passing particle in the outer region. This leads to an asymmetrically poloidal (and therefore radial) transport in the presence of the chaotic separatrix. Note that, because µ f < 3, the second moment of the PDF of negative flights diverges,

∞ 0 t 2 P - flight dt → ∞.
That is, the negative flights are Lévy flights which invalidates the use of the central limit theorem as it is customary done in the Brownian random walk model of diffusive transport. On the other hand, within the CTRW, superdiffusive behavior, γ > 1, is a natural consequence of the existence of Lévy flights, µ f < 3. In particular, according to CTRW theory γ = 2/(µ f -1) which for the numerically determined exponent µ f ≈ 2.2 predicts γ = 1.66, a value very close to the numerically observed γ ≈ 1.64.

Figure 6 shows the PDF of the total (summed) poloidal displacements at different times as function of the similarity variable χ = (∆θ -∆θ ) /t γ/2 . The collapse of the rescaled PDFs at different times provides numerical evidence that poloidal transport exhibits self-similar dynamics with anomalous exponent γ which, consistent with the CTRW model, is equal to the numerically deter- mined super-diffusive exponent γ ≈ 1.64. Formally, the observed self-similar evolution implies P ∆θ = t -γ/2 F (χ) where F is an asymmetric scaling function which, according to the CTRW, should exhibit an algebraic decay of the χ < 0 tail of form F ∼ χ -(α -+1) with α -= µ f -1, a results fully consistent with the numerically obtained values µ f ≈ 2.2 and α -≈ 1.2. For the χ > 0 tail, within the CTRW, the exponential decay of P + f light implies, consistent with the numerical results, α + > 2.

To conclude, we have provided numerical evidence of anomalous exit times statistics of EP in the presence of an oscillating radial electric field in axi-symmetric tokamak magnetic equilibria. The observed algebraic decay is in sharp contrast with the expected exponential exit time in the case of radial diffusive transport. We have shown that the anomalous loss time decay is the result of Lévy flights that lead to super-diffusive poloidal transport and an asymmetric non-Gaussian (Lévy) PDF of displacements. These results can have an important impact on the confinement time of EP needed to achieve sustained fusion in burning plasmas, in addition to the potential generation of a toroidal net torque resulting from the poloidal asymmetry of the particle displacements. Fractional diffusion results from the continuum (fluid) limit of the (kinetic) CTRW model, see e.g. [21,22]. Accordingly, the observed self-similar dynamics of the PDF of poloidal displacements, along with the consistency of the numerically determined anomalous exponents µ e , γ, µ f , α -and α + with the CTRW predictions, opens the possibility to describe EP transport using non-local transport models based on fractional derivatives [23]. This is a problem that will be addressed in a forthcoming publication.

D.dCN was sponsored by the Oak Ridge National Laboratory, managed by UT-Battelle, LLC, for the US Department of Energy under Contract No. DE-AC05-00OR22725

4 FIG. 1 :

 41 FIG.1: Probability distribution function (PDF) of the exit time for counter-passing EP initialised at r = 0.4a, θ = 0, ϕ = 0, with E = 20E th and µB 0 /T i = 14. The dashed line shows a linear fit, with µ e = 2.5.

FIG. 3 :FIG. 4 :

 34 FIG. 3: Time dependence of the variance of the poloidal displacement.

FIG. 5 :

 5 FIG. 5: PDF of negative (top) and positive (bottom)flight events of duration t.

FIG. 6 :

 6 FIG.6: Rescaled PDF of poloidal displacements at different times: ω c t = 9 • 10 6 (dashed magenta), ω c t = 9.5 • 10 6 (dotted red) and ω c t = 10 7 (solid black). The dotted-dashed grey line corresponds to a Gaussian PDF. The insets represent the log-log plots of the tails, showing the asymmetric algebraic decays.