Marius Bozga
email: marius.bozga@imag.fr

Jean-Claude Fernandez
email: jean-claude.fernandez@imag.fr

Lucian Ghirvu
email: lucian.ghirvu@imag.fr

State Space Reduction based on Live Variables Analysis

Keywords: model checking, state space reduction, bisimulation, asynchronous communication, live variables analysis

The intrinsic complexity of most protocol speci cations in particular, and of asynchronous systems in general, lead us to study combinations of static analysis with classical model-checking techniques as a way to enhance the performances of automated validation tools. The goal of this paper is to point out that an equivalence on our model derived from the information on live variables is stronger than the strong bisimulation. This equivalence, further called live bisimulation, exploits the unused dead values stored either in variables or in queue contents and allow to simplify the state space with a rather important factor. Furthermore, this reduction comes almost for free and is always possible to directly generate the quotient model without generating the initial one.

Introduction

Formal Description Techniques such as lotos 16] or sdl [START_REF]Speci cation and Description Language[END_REF]] are now at the base of a technology for the speci cation and the validation of telecommunication systems. This is due not only to the fact that these formalisms are promoted by itu and other international standardization bodies but also to the availability of mature commercial tools, mainly for editing, code generation and testing.

Alternatively, we have been developing for more than ten years a set of tools dedicated to the design and validation of critical systems and based on the model checking paradigm [START_REF] Queille | Speci cation and Veri cation of Concurrent Programs in CESAR[END_REF][START_REF] Clarke | Automatic Veri cation of Finite State Concurrent Systems Using Temporal Logic Speci cations: A Practical Approach[END_REF]. One of them is the model checker aldebaran 7] maintained and distributed in collaboration with the vasy team of inria Rhône-Alpes as part of the cadp toolset 11]. Another one is the test sequence generator tgv 13], built upon cadp and jointly developed with the pampa project of irisa.

The central problem arising in the context of model based validation and implicitly for the above mentioned tools is the well known state explosion problem. To deal with it, we begin more recently to investigate alternative program representations and more important, ways to adapt techniques issued from other advanced domains such as compiler design and optimization in the context of model checking. In this respect, we developed if 5] which is an intermediate program representation based on asynchronously communicating timed automata. if was designed on one hand to be able to represent signi cant subsets of sdl and lotos and on the other hand to support the application of static analysis techniques used in compiler optimization [START_REF] Aho | Compilers: Principles, Techniques and Tools[END_REF][START_REF] Muchnick | Advanced Compiler Design Implementation[END_REF]. In particular, a translation from sdl into if is already implemented using the sdl/api interface provided by the industrial tool Objectgeode to its sdl compiler.

In general, model checkers and in particular aldebaran and tgv are based on the central notion of bisimulation 20]. In fact, either in the veri cation process or in the test generation process there is usually a step of minimization modulo strong bisimulation. This lead us to consider static analysis techniques for if programs in the context of bisimulation equivalences.

The main goal of this paper is to point out that an equivalence on our model derived from the information on live variables is stronger than the strong bisimulation. This equivalence, further called live bisimulation, exploits the unused dead values stored either in variables or in queue contents and allow to simplify the state space with a rather important factor. Furthermore, this reduction comes almost for free and is always possible to directly generate the quotient model without generating the initial one.

The idea of using static analysis to improve model checking was already being investigated in di erent particular contexts. For instance, in 10] was proposed a method to reduce the number of clocks in timed automata using live clocks and clocks equality analysis. [START_REF] Kurshan | Static Partial Order Reduction[END_REF] was given a method which combines partial order reductions and static analysis of independent actions for sdl programs. An important work was done to nd e cient representations of possible innite queue contents and to exploit the static control structure when performing reachability analysis 4, 1]. However, at the best of our knowledge we are the rst to make use of live variables to simplify the state space, including queue contents, of asynchronous systems with queue-based communication.

The paper is structured as follows. Section 2 presents the underlying model which is parallel processes asynchronous communicating via queues. Section 3 brie y remember the notion of live variables and some basic properties about them. In section 4 we introduce the live equivalence relation on states and show that is a bisimulation. An e cient way to identify live equivalent states using a canonical form is then presented in section 5. Finally, in section 6 we discuss the general utility of introduced equivalences in the context of model-checking. Some practical results obtained on a small example are given in section 7.

The model 2.1 Syntax

We consider systems consisting of asynchronous parallel composition of a number of processes that communicate through parameterized signal passing via a set of unbounded fo queues and operate on a set of shared variables. Formally, a system is a tuple:

P ::= (S; X; C; n Q i=1 p i )
where S is the set of signals, X is the set of variables, C is the set of queues and fp i g i=1;n are processes. Processes perform actions on queues and variables.

They are described by terms of a simpli ed value-passing process algebra with the following syntax: p ::= nil j :p j p + p j Z(e) This syntax contains the usual operators from process algebra: nil denotes the empty process, :p denotes p pre xed with action , p 1 + p 2 is the nondeterministic choice between p 1 and p 2 , and nally Z(e) stands for recursion with the value passing of the expression e. To give a semantics for terms we assume also the existence of a set of declarations: Z(y) / def p for each name Z which occurs in terms. Note that in our algebra such declaration binds the occurrences of the variable y inside p to Z, therefore y is considered a parameter of the de nition of Z. The actions are simple guarded commands de ned by the following syntax: ::= b ] 1 1 ::= x := e j c!s(e) j c?s(x)

where b ] with b a boolean expression denotes the guard, x := e denotes an assignment of the variable x to the expression e, c!s(e) denotes the output to the queue c of the signal s with parameter the expression e and nally, c?s(x) denotes the input from the queue c of the signal s and store of its parameter in the variable x.

Semantics

We give the semantics of systems in terms of labeled transition systems. We proceed in two steps: we start with the interpretation of the control part only, then we give the interpretation of control combined with data, i.e. queues contents and variables.

The control semantics is described by the following rules which give a way to build the control graph of the system, from the parallel composition of processes. The states in this graph are tuples of terms n Q i=1 p i , and the transitions are labeled by actions, as follows: ? :p ?!p p ?!p 0 p + q ?!p 0 q ?!q 0 p + q ?!q 0 p e=y] ?!p 0 Z(y) / def p Z(e) ?!p 0 p j ?!p 0 j p i = p 0 i 8i 6

= j n Q i=1 p i ?! n Q i=1 p 0 i
Note that, in this paper we restrict our attention to systems where the control graph is nite, that is if it contains only a nite number of states and transitions.

In order to interpret the data part we assume the existence of the universal domain D which contains the values of variables and signal parameters. We suppose that the boolean values ftrue; falseg and also the special unde ned ?

value are contained in D. We de ne variable contexts as being total mappings : X ! D which associate to each variable x a value v from the domain. We extend these mappings to expressions in the usual way. We de ne queue contexts as being also total mappings : C ! (S D) which associates to each queue c a sequence (s 1 ; v 1 ); :::; (s k ; v k ) of messages, that is pairs (s; v) noted also by s(v), where s is a signal and v is the carried parameter value. We assume also the existence of some special unde ned message . The empty sequence is noted with .

The semantics of a system is now completed by the following rules which give a way to build a labeled transition system based on the control graph. States of this system are triples of the form ( ; ; p), where is a variable context, is a queue context and p is a control state. Transitions are either internal and labeled with , when derived from assignments or signal inputs, either visible and labeled with c!s(v) when derived from signal outputs:

p b] x:=e ?! p 0 (b) = true (e) = v ( ; ; p) ?!( v=x]; ; p 0 ) p b] c!s(e) ?! p 0 (b) = true (e) = v (c) = w ( ; ; p) c!s(v) ?! ( ; w:s(v)=c]; p 0 ) p b] c?s(x)
?! p 0 (b) = true (c) = s(v):w ( ; ; p) ?!( v=x]; w=c]; p 0 )

Live variables analysis

In this section we brie y remember the de nition of live variables and some general properties about them. We consider the sets of variables used and respectively de ned by some action . Intuitively, a variable is used either in the guards, in the right hand side of assignments or in outputs. A variable is de ned either in the left hand side of assignments or in inputs. Formally, the sets Use( ) and Def( ) are de ned as follows:

Use We consider now the set of live variables for some term p. Intuitively it is the smallest set of variables which might be used before they are rede ned when interpreting the term. Formally, the sets Live(p) are de ned as the least xpoint solution of the following equation system over sets of variables:

8 > > > > > > > > > > > > > > < > > > > > > > > > > > > > > : Live(nil) = ;
Live( :p) = Use( ) Live(p) n Def( )

Live(p + q) = Live(p) Live(q)
Live(Z(e)) = Live(p e=x]) where Z(y

) / def p Live( n Q i=1 p i ) = n S i=1
Live(p i )

An equivalent characterization for the sets of live variables based on the control graph transitions and some basic properties are given by the following lemma.

Lemma 1.

p 2 , 8 > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > : V p b] x:=e ?! p 0 1 p 0 2 V p b] c!s(e) ?! p 0 1 p 0 2 V p b] c?s(x) ?! p 0 8 > > > > > > > > > > > > < > > > > > > > > > > > > : 1 (c) = ^ 2 (c) = ^ 1 p 0 2 _ 1 (c) = s(v 1 ):w 1 ^ 2 (c) = s(v 2 ):w 2 (x 2 Live(p 0 ) ) v 1 = v 2 ) ^ 1 w 1 =c] p 0 2 w 2 =c] _ 1 (c) = s 1 (v 1 ):w 1 ^ 2 (c) = s 2 (v 2 ):w 2 ŝ1 6 = s ^s2 6 = s
If the control graph is nite, the existence of the greatest xpoint satisfying the equations above is ensured by the Tarski's xpoint theorem given the monotonicity with respect to the relation inclusion at each state. We de ne now the live equivalence live relation over global states: two states are equivalent if the control states are identical and both the variable context and the queue context are equivalent:

( 1 ; 1 ; p) live ( 2 ; 2 ; p) , 1 live p 2 ^ 1 live p 2

The next theorem gives the central result of the paper, that is, the live equivalence is also a bisimulation relation over the global states.

Theorem 1. The live equivalence live is a bisimulation.

Proof. By de nition, live is a bisimulation if and only if for all pairs ( 1 ; 1 ; p) live ( 2 ; 2 ; p) we have:

8( 1 ; 1 ; p) a ?!( 0 1 ; 0 1 ; p 0 ) ) 9( 2 ; 2 ; p) a ?!( 0 2 ; 0 2 ; p 0 ) ^( 0 1 ; 0 1 ; p) live ( 0 2 ; 0 2 ; p) 8( 2 ; 2 ; p) a ?!( 0 2 ; 0 2 ; p 0 ) ) 9( 1 ; 1 ; p) a ?!( 0 1 ; 0 1 ; p 0 ) ^( 0 1 ; 0 1 ; p) live ( 0 2 ; 0 2 ; p)

Let ( 1 ; 1 ; p) live ( 2 ; 2 ; p) and let p ?!p 0 . We distinguish three di erent cases, depending on the type of .

1. = b ] x := e 8i = 1; 2 i (e) = v i ; i (b) = true ) ( i ; i ; p) ?!( 0 i ; i ; p 0 );

0 i = i v i =x] 1 live p 2 ) 1 (b) = 2 (b); 1 (e) = 2 (e); 1 v 1 =x] live p 0 2 v 2 =x] 1 live p 2 ) 1 live p 0 2 2. = b ] c!s(e) 8i = 1; 2 i (c) = w i ; i (e) = v i ; i (b) = true ) ( i ; i ; p) c!s(vi) ?! ( i ; 0 i ; p 0 ); 0 i = i w i :s(v i )=c] 1 live p 2 ) 1 (b) = 2 (b); 1 (e) = 2 (e); 1 live p 0 rho 2 1 live p 2 ) 1 live p 0 2 ) 1 w 1 :s(v 1 )=c] live p 0 2 w 2 :s(v 2 )=c]
Note that the second implication comes from the more general property of queue content equivalence to be closed under output operations. That is, it can be proven inductively that, two equivalent queue contents at some state p, are still equivalent after adding the same message to the same queue in both of them.

3. = b ] c?s(x) 8i = 1; 2 i (c) = s(v i ):w i ; i (b) = true ) ( i ; i ; p) ?!( 0 i ; 0 i ; p 0 ); 0 i = i v i =x]; 0 i = i w i =c] 1 live p 2 ) v 1 = v 2 if x 2 Live(p 0 ); 1 w 1 =c] live p 0 2 w 2 =c] 1 live p 2 ) 1 (b) = 2 (b); 1 v 1 =x] live p 0 2 v 2 =x]
An immediate consequence of the previous theorem is the following one, stating that the live equivalence is stronger than the strong bisimulation.

Theorem 2. live strong .

Reset equivalence

We would like to have a more e cient way to check that two contexts are live equivalent than to directly check the de nition. Here we investigate the possibility to transform contexts into some canonical form preserving the live equivalence. One way to do this is using the family of Reset functions, de ned below. It is straightforward to prove that the live equivalence and the reset equivalence on variable contexts are identical, that is, the following lemma holds.

Lemma 2. 8p reset p = live p .

In order to de ne a similar Reset q function for queue contexts we start by introducing some auxiliary notations.

Let consider some xed queue c. We de ne the relation c?

?! over control states to include all the control transitions, except the ones labeled with inputs from the queue c. We note with c? =) its transitive and re exive closure and with Post c? (Q) = f p 0 j 9p 2 Q p c? =)p 0 g

Let consider = b ] c?s(x) to be some input action of signal s from queue c. We note p =)p 0 if it is possible to reach p 0 from p by a sequence ending with and which does not contain any other input from the queue c. We de ne also the post image function Post c?s =) over sets of control states, that is, it gives all the states which can be reached after consuming an s from the queue c. Formally, we have:

p b] c?s(x) =) p 0 , 9p 00 p c? =)p 00 ^p00 b] c?s(x) ?! p 0 Post c?s =) (Q) = f p 0 j 9p 2 Q p b] c?s(x) =) p 0 g

We de ne now the local reset function for the queue c given an initial nonempty set of control states Q. That is, given the content w of the queue c, this function basically rewrite it and forgot the signal parameters which statically are detected to be unused, when execution starts somewhere in Q. With denoting the unde ned message, the function is recursively de ned as follows:

reset(Q; c; ) = 8 < : if 8s Post c?s =) (Q) = ; otherwise reset(Q; c; s(v):w) = 8 > > > > > > > > > > < > > > > > > > > > > : if Post c?s =) (Q) = ; s(v):reset(Post c?s =) (Q); c; w) if 9p 2 Q; p b] c?s(x) =) p 0 ^x 2 Live(p 0 ) s(?):reset(Post c?s =) (Q); c; w) if 8p 2 Q; p b] c?s(x) =) p 0 ) x 6 2 Live(p 0 )
Some interesting properties about the local reset function are given by the following lemma.

Lemma 3. For any Q, c, w, w 1 , w 2 holds 1. reset(Q; c; w) = reset(Post c? =) (Q); c; w).

2. reset(Q; c; w 1 ) = reset(Q; c; w 2 ) ) 8Q 0 Q reset(Q 0 ; c; w 1 ) = reset(Q 0 ; c; w 2 ).

Proof. 1. The proof is immediate from the fact that for any set of control states Q, channel c and signal s we have:

Q Post c? =) (Q) Post c?s =) (Q) = Post c?s =) (Post c? =) (Q))
2. The proof can be done by induction on the maximal size of the sequences w 1 and w 2 .

We de ne the Reset q function and the reset equivalence on queue contexts using local reset functions de ned before, that is, for a given control state p we consider:

Reset q (p; ) = (c) = reset(fpg; c; (c)) 1 reset p 2 , Reset q (p; 1 ) = Reset q (p; 2 )
The following lemma gives the relation between the live equivalence and the reset equivalence on queue contexts. In general, the reset equivalence is stronger than the live equivalence. This is explained by the fact that local resets are based on a conservative assumption about other queues: the inputs from other queues are always considered enabled. However, in the special case when the input actions from a queue do not enable input actions from other queues, the live equivalence and the reset equivalence become identical. This can be formalized as follows.

For an input action, we note p =) p 0 if p 0 is reachable from p by a sequence ending with and which does not contain other inputs. We de ne now queue c to be reset-independent from queue c 0 if and only if : 8p; q; q 0 p b 0 ]c 0 ?s 0 (x 0 ) =) q; q b]c?s(x) =) q 0 ) 9p 0 p b]c?s(x) =) p 0 ; p 0 b 0 ]c 0 ?s 0 (x 0 ) =) q 0 ; x 2 Live(p 0 ) , x 2 Live(q 0 ) Lemma 4. 1. 8p reset p live p . 2. if the queues are reset-independent then 8p reset p = live p .

Proof. 1. The proof consist to check that the reset equivalences reset p satis es the xpoint equations de ning the live equivalence. This can be easily done given the results established by the previous lemma. Then because the live equivalences are the greatest xpoint is clear that reset p live p for all control states p. ?! p 0 and because the inputs are independent we can choose this sequence such that it doesn't contain inputs from other queues

) we obtain a contradiction with the de nition of the live equivalence hypothesis, that is 1 6 live p 2 3. ) contradiction with the live equivalence, as before. ii. s 1 = s 2 = s and v 1 6 = v 2 and 9p b] c?s(x) =) p 0 x 2 Live(p 0 ) ) contradiction with the live equivalence, as before. iii. s 1 = s 2 = s and v 1 = v 2 = v or 8p b] c?s(x) =) p 0 x 6 2 Live(p 0 ) ) reset(fpg; c; s 1 (v 1 ):w 1 ) = s(v):reset(Post c?s =) (fpg); c; w 1 ) reset(fpg; c; s 2 (v 2 ):w 2 ) = s(v):reset(Post c?s =) (fpg); c; w 2 ) and from the live equivalence hypothesis we have also that 8p 0 2 Post c?s =) (fpg) 1 w 1 =c] live p 0 2 w 2 =c] so we can inductively infer that either contradiction or reset(fpg; c; s 1 (v 1 ):w 1 ) = reset(fpg; c; s 2 (v 2 ):w 2 )

Finally, we de ne the reset equivalence over global states as follows:

( 1 ; 1 ; p) reset ( 2 ; 2 ; p) , 1 reset p 2 ^ 1 reset p 2

The link between the live and reset equivalence over global states is established by the following theorem.

Theorem 3.

1. reset live 2. if the queues are reset-independent then: reset = live Finally, note that sdl systems satisfy the independence hypothesis as they are composed from parallel processes, each one having its own unique input queue. Thus, performing a signal input in a process does not interfere with other possible inputs in other processes.

The reductions based on live or reset equivalence can be obtained with almost no cost and are fully orthogonal to other techniques applied in the context of model-checking validation to deal with the state-explosion problem.

The weak cost of the live equivalence reduction is due to the static analysis approach: live variables need to be computed once in the beginning with an algorithm operating on the control graph and then are used by primitives such as Reset which operate on states content and which have a linear complexity with respect to the size of the state (the number of variables plus the number of messages in the queues). In fact, in the context of exhaustive state space exploration algorithms such primitives can be viewed as having constant operation time, similar to operations like state copying or state comparison.

Live equivalence reduction can be combined with techniques ranging from the simplest model generation, with standard on the y veri cation methods and even with more sophisticated partial order or symbolic techniques.

Enumerative simulation is at the basis of most of the veri cation algorithms. It is always possible to directly generate the quotient graph with respect to live or reset equivalences, thus preserving all the observable behaviors, without constructing the initial one. This can be easily done for instance by considering every time a new state is generated its canonical form given by Reset. Reset equivalent states will be automatically identi ed as equals and explored once by the generation algorithm.

On the y veri cation techniques such as 12] rely on enumerative depth rst traversals of the model state space and the meantime evaluation of the property (e.g, temporal logic formula, observer automaton, test purpose). In this case too, the property can be directly evaluated on the reduced graph, if it is not explicitly dependent on state variables or queue contents but only on the observable actions of the system (e.g, outputs). Note that, if such dependencies exist, they can be normally removed by introducing auxiliary observable actions and by modifying the property accordingly.

Partial order techniques 15] reduce the state space by avoiding to explore interleaving of independent actions. Clearly, the live equivalence reduction can be further considered when new states are encountered, as before.

In the symbolic model checking context 19] the information on live variables can be used to simplify the BDDs representing the transition relation and the sets of states. In fact, dead variables for a given control state provide non-trivial don't care conditions which can be exploited either directly to simplify any nal or intermediate result, or even better, to improve primitives like successors or predecessor computation on symbolic representations.

In particular, live equivalence reduction can also be applied at each step of the minimal model generation algorithm 14] which involves the (backward) computation of predecessor states. This must be very important as the predecessor computation usually gives a lot of spurious unreachable states and which might be equivalent w.r.t. the live equivalence.

Example

We illustrate the potential reduction obtained using the live equivalence on a small example. We consider two simple processes communicating through a queue as shown in gure 1. The rst process only send arbitrarily request and switch messages. It is described by Z dummy and the following equation:

Z dummy / def (in!switch + in!request( )):Z dummy
The second process is more interesting. It has two functioning modes, a normal one and a fault one. Basically, it inputs requests from the in queue and delivers them, when normal, and looses them otherwise. The mode changes from normal to fault (and backward) when input a switch signal. Formally, we consider this process described by Z normal and the following equations: We can easily check that the variable x is live only at the deliver state. Thus, the value of x must not be used to distinguish between states when somewhere else that deliver. Furthermore, it can be seen that when at the fault state, the parameters of the incoming requests are not live too. That is, request signals are only consumed, without using the carried values. It can be seen also that signals of the out queue are never consumed so we don't distinguish states which di ers on the out content. Such cases are all captured by the live equivalence as de ned in section 4.

Figure 2 shows the reduction obtained for this example with respect to two parameters: m, the size of the domain of x and n, the maximal allowed size of queue in. The continuous lines give the real number of states and the dotted lines give the number of states obtained after considering live equivalence reduction and please notice that an logarithmic scale was used for the number-of-states axis. Also, to better illustrate the reduction obtained, note that for instance when m = 6 and n = 5 the initial number of states is 352944 and it is reduced at 89824, so with a factor up to 75%. The essence of this work is to show that the live variable analysis de ne an equivalence stronger than bisimulation equivalence. This allow to simplify the state space exploiting the information on unused dead values stored either in the variables or in the queue contents. This idea was already experimented to the industrial case study SSCOP 6] where we have obtained impressive reductions of the state space up to 200 times.

In the context of model-based validation, the main interest of static analysis is to reduce the state space, which is crucial in practice to deal with complex speci cations. Model checking and automatic test generation for conformance testing are based on the same algorithmic techniques: given a speci cation and a property, they compute, in the rst case the validity of the property and, in the second case, the test case with respect to either the speci cation and the property. We are currently developing if 5], a toolbox for a high level representation of programs, especially for telecommunication speci cation languages. In this toolbox, static analysis is intensively used in the earlier stages of validation in order to reduce the memory costs of the next ones.

This lead us to consider two classes of analysis: property independent analysis: (such as live variable analysis or constant propagation) without regarding any particular property, the analysis is implemented by a module which takes as input and output a intermediate program, property dependent analysis: the analysis takes into account some information extracted from the property or from the environment and propagate them over the static control structure of the program (such as uncontrollable variables abstraction 9]).

We envisage to experiment more sophisticated analysis, such as constraints propagation in the context of symbolic test generation. We also want to exploit a connection with the tool invest 3], which computes abstractions and invariants on a set of guarded commands.

  := e vars(b) vars(e) fxg b ] c!s(e) vars(b) vars(e) ; b ] c?s(x) vars(b) fxg

  function de ned over sets of control states, formally: p c? ?!p 0 , 9 6 = b ] c?s(x) p ?!p 0 Post c? =)

1. 1

 1 (c) = ; 2 (c) = ) reset(fpg; c; 1 (c)) = reset(fpg; c; 2 (c)) 2. 1 (c) = ; 2 (c) = s 2 (v 2 ):w 2 (a) 8s Post c?s =) (fpg) = ; ) reset(fpg; c; 1 (c)) = reset(fpg; c; 2 (c)) = (b) 9s Post c?s =) (fpg) 6 = ; ) 9p = p 0 c?s ?!p 1 c?s ?!::: c?s ?!p n b] c?s(x)

  1 (c) = s 1 (v 1 ):w 1 ; 2 (c) = s 2 (v 2 ):w 2 (a) Post c?s 1 =) (fpg) = ;; Post c?s 2 =) (fpg) = ; ) reset(fpg; c; 1 (c)) = reset(fpg; c; 2 (c)) = (b) Post c?s 1 =) (fpg) 6 = ;; Post c?s 2 =) (fpg) = ; ) contradiction with the live equivalence, as before. (c) Post c?s 1 =) (fpg) 6 = ;; Post c?s 2 =) (fpg) 6 = ; i. s 1 6 = s 2

Fig. 1 .

 1 Fig. 1. The example

Fig. 2 .

 2 Fig. 2. Live equivalence reduction

  We consider similar equivalence relations de ned for queue contexts. Intuitively two queue contexts are equivalent if and only if they enable the same sequences of transitions and if for each enabled input the parameter values are identical if the receiving variable is live at the next state. Formally, we de ne the queue context equivalences live p to be the greatest xpoint solution of the following equation system where for each state p we have:

	First, we consider the variable context equivalence relation induced by the set of live variables: two variable contexts are equivalent if and only if the values assigned to each one of the live variables are pairwise identical. Formally, for each state p we de ne the variable context equivalence live p as follows: 1 live p 2 , 8x 2 Live(p) 1 (x) = 2 (x)
	1
	1. Live(p) = 2. p ?!p 0 ) Use( ) Live(p) S Use( ) Live(p 0 ) n Def( ). p ?!p 0 Live(p 0 ) n Def( ) Live(p):
	Proof. 1. Structural induction over term structure. 2. Immediate from 1.

  The Reset v function on variable contexts basically sets the value of the dead variables to the xed unde ned ? value, depending on the current control state p. A reset equivalence can be de ned over variable contexts as follows: two

	Reset v (p; ) = 1 reset p 2 , Reset v (p; 1 ) = Reset v (p; 2 ) (x) = (x) if x 2 Live(p) ? otherwise
	contexts are reset equivalent if they give the same result when reseted. Formally, we have:

  Z normal / def in?request(x):Z deliver + in?switch:Z fault Z deliver / def out!request(x):Z normal Z fault / def in?request(x):Z fault + in?switch:Z normal

			in?request(x)
	in!request(*)	normal	deliver
	in	in?switch	out!request(x)	out
	dummy	in?switch
		fault
	in!switch		in?request(x)

Let 1 live p 2 and the queue c xed. We will prove inductively that reset(fpg; c; 1 (c)) = reset(fpg; c; 2 (c)). We distinguish the following cases:

This work was partially supported by R egion Rhône Alpes ? ? ? VERIMAG is


Piotr Biler
email: piotr.biler@math.uni.wroc.pl

AND Grzegorz Karch
email: grzegorz.karch@math.uni.wroc.pl

Régis Égis Monneau
email: monneau@cermics.enpc.fr

Nonlinear diffusion of dislocation density and self-similar solutions

Keywords: . 2000 Mathematics Subject Classification. 35K, 35S, 35B40, 70 One-dimensional nonlinear pseudodifferential equation, viscosity solutions, self-similar solutions, stability

We study a nonlinear pseudodifferential equation describing the dynamics of dislocations in crystals. The long time asymptotics of solutions is described by the self-similar profiles.

Introduction

Dislocation dynamics. Dislocations are line defects in crystals whose typical length is ∼ 10 -6 m and their thickness is ∼ 10 -9 m.

When the material is submitted to shear stresses, these lines can move in the crystallographic planes and this dynamics can be observed using electron microscopy. The elementary mechanisms at the origin of the deformation of monocrystals are rather well understood, however, many questions concerning the plastic behavior of materials containing a high density of defects are still open. Hence, in recent years, new physical theories describing the collective behavior of dislocations have been developed and numerical simulations of dislocations have been performed. We refer the reader to the recent publications [START_REF] Alvarez | Dislocation dynamics: short time existence and uniqueness of the solution[END_REF][START_REF] Imbert | Homogenization of first order equations, with (u/ε)periodic Hamiltonians. Part II: application to dislocations dynamics[END_REF] for the comprehensive references about modeling of dislocation dynamics.

One possible (simplified) model of the dislocation dynamics is given by the system of ODEs (1.1) ẏi = F -V 0 (y i ) -j∈{1,...,N }\{i} V (y i -y j ) for i = 1, ..., N,

where F is a given constant force, V 0 is a given potential and V is a potential of two-body interactions. One can think of y i as the position of dislocation straight lines. In this model, dislocations can be of two types, + or -, depending on the sign of their Burgers vector (see the book by Hirth and Lothe [START_REF] Hirth | Theory of Dislocations[END_REF] for a physical definition of the Burgers vector). Self-similar solutions (i.e. solutions of the form y i (t) = g(t)Y i with constant Y i ) to system (1.1) with the particular potential V (z) = 1 z as well as their role in the asymptotic behavior of other solutions of (1.1) were studied by Head in [START_REF] Head | Dislocation group dynamics I. Similarity solutions od the n-body problem[END_REF][START_REF] Head | Dislocation group dynamics II. General solutions of the n-body problem[END_REF]. More recently, Forcadel et al. showed in [START_REF] Forcadel | Homogenization of the dislocation dynamics and of some particle systems with two-body interactions[END_REF]Th. 8.1] that, under suitable assumptions on V 0 and V in (1.1), the rescaled "cumulative distribution function"

(1.2) ρ ε (x, t) = ε - 1 2 + N i=1 H x -εy i t ε
(where H is the Heaviside function) satisfies (as a discontinuous viscosity solution) the following nonlocal eikonal equation

(1.3) ρ ε t (x, t) = c x ε + M ε ρ ε (•, t) ε (x) |ρ ε x (x, t)|
for (x, t) ∈ R × (0, +∞), with c(y) = V 0 (y) -F . Here, M ε is the nonlocal operator defined by

(1.4) M ε (U )(x) = R J(z) E U (x + εz) -U (x) dz,
where J(z) = V (z) on R \ {0} and E is the modification of the integer part: E(r) = k + 1/2 if k ≤ r < k + 1. Note that the nonlocal operator M ε describes the interactions between dislocation lines, hence, interactions are completely characterized by the kernel J.

Next, under the assumption that the kernel J is a sufficiently smooth, even, nonnegative function with the following behavior at infinity (1.5) J(z) = 1 |z| 2 for all |z| ≥ R 0 and for some R 0 > 0, the rescaled cumulative distribution function ρ ε , defined in (1.2), is proved to converge (cf. [START_REF] Forcadel | Homogenization of the dislocation dynamics and of some particle systems with two-body interactions[END_REF]Th. 2.5]) towards the unique solution of the corresponding initial value problem for nonlinear diffusion equation (1.6) u t = H(-Λu, u x ),

where the Hamiltonian H is a continuous function and Λ is a Lévy operator of order 1. It is defined for any function U ∈ C 2 b (R) and for r > 0 by the formula

(1.7) -ΛU (x) = C(1) R U (x + z) -U (x) -zU (x)1 {|z|≤r} 1 |z| 2 dz
with a constant C(1) > 0. Finally, in the particular case of c ≡ 0 in (1.3), we have H(L, p) = L|p| (cf. [START_REF] Forcadel | Homogenization of the dislocation dynamics and of some particle systems with two-body interactions[END_REF]Th. 2.6]) which allows us to rewrite equation (1.6) in the form (1.8) u t + |u x |Λu = 0.

One can show that the definition of Λ is independent of r > 0, hence, we fix r = 1. In fact, for suitably chosen C(1), Λ = Λ 1 = -∂ 2 /∂x 2 1/2 is the pseudodifferential operator defined in the Fourier variables by (Λ 1 w)(ξ) = |ξ| w(ξ) (cf. formulae (2.3) and (2.4) below). In this particular case, equation (1.8) is an integrated form of a model studied by Head [START_REF] Head | Dislocation group dynamics III. Similarity solutions of the continuum approximation[END_REF] for the selfdynamics of a dislocation density represented by u x . Indeed, denoting v = u x we may rewrite equation (1.8) as (1.9)

v t + (|v|Hv) x = 0,
where H is the Hilbert transform defined by (1.10) (Hv)(ξ) = -i sgn(ξ) v(ξ).

Let us recall two well known properties of this transform (cf. [START_REF] Stein | Singular Integrals and Differentiability Properties of Functions[END_REF])

(1.11)

Hv(x) = 1 π P.V. R v(y)
x -y dy and Λ 1 v = Hv x .

Head [START_REF] Head | Dislocation group dynamics III. Similarity solutions of the continuum approximation[END_REF] called (1.9) the equation of motion of the dislocation continuum and constructed an explicit self-similar solution. Numerical studies of solutions to this equation were performed in [START_REF] Deslippe | Dynamics scaling in a simple one-dimensional model of dislocation activity[END_REF].

Quasi-geostrophic equations. Let us recall completely different physical motivations which also lead to equation (1.9). The 2D quasi-geostrophic equations (QG), modeling the dynamics of the mixture of cold and hot air in a thin layer and the fronts between them, are of the form (1.12)

θ t + (u • ∇)θ = 0, u = ∇ ⊥ ψ, θ = -(-∆) 1/2 ψ
for x ∈ R 2 and t > 0, where ∇ ⊥ = (-∂ x 2 , ∂ x 1 ). Here, θ(x, t) represents the air temperature. Pioneering studies concerning a finite time blow up criterion of solutions to (1.12) are due to Constantin et al. [START_REF] Constantin | Formation of strong fronts in the 2-D quasigeostrophic thermal active scalar[END_REF]. Much earlier, Constantin et al. [START_REF] Constantin | A simple one-dimensional model for the three dimensional vorticity[END_REF] proposed a one-dimensional version of the QG model (1.12). To derive it, we first write system (1.12) in another equivalent form. From the second and third equation in (1.12) we have the representation

(1.13) u = -∇ ⊥ (-∆) -1/2 θ = -R ⊥ θ,
where we have used the notation R ⊥ θ = (-R 2 θ, R 1 θ), with the Riesz transforms defined by (see e.g. [START_REF] Stein | Singular Integrals and Differentiability Properties of Functions[END_REF])

R j (θ)(x, t) = 1 2π P.V. R 2 (x j -y j )θ(y, t) |x -y| 3 dy.
Using equation (1.13), we find that (1.12) can be transformed into

(1.14) θ t + div ((R ⊥ θ)θ) = 0, because div (R ⊥ θ) = 0.
To construct the 1D model, the authors of [START_REF] Constantin | A simple one-dimensional model for the three dimensional vorticity[END_REF] Obviously, for θ ≥ 0, both models (1.9) and (1.15) are identical. However, in the case of equation (1.15), it is possible to show that the complex valued function z(x, t) = Hθ(x, t) -iθ(x, t) satisfies the inviscid Burgers equation z t + zz x = 0. This property of solutions has been systematically used in [START_REF] Castro | Global existence, singularities and ill-posedness for a nonlocal flux[END_REF][START_REF] Chae | Finite time singularities in a 1D model of the quasi-geostrophic equation[END_REF] to study the existence, the regularity and the blow up in finite time of solutions to equation (1.15). We refer the reader to those publications for additional references concerning equation (1.15). Below, see Remarks 2.6, 2.10 and 7.7, we explain how our results on equation (1.9) and its generalizations contribute to the theory developed for model (1.15).

Organization of the paper. In the next section, we state the initial value problem considered in this paper and we formulate our main results. In Section 3, we construct explicitly the self-similar solution. In Section 4, we recall the necessary material about viscosity solutions, which will be used systematically in the remainder of the paper. In Section 5, we prove the uniqueness of the self-similar solution. Under the additional assumption that the solution is confined between its boundary values at infinity, we prove the stability of the self-similar solution, namely Theorem 2.5. In Section 6, we prove further decay properties of a solution with compact support. Applying these estimates, we finish the proof of Theorem 2.5 in the general case. In Section 7, we introduce an ε-regularized equation, for which we prove both the global existence of a smooth solution and the corresponding gradient estimates. Finally in Section 8, we deduce the gradient estimate in the limit case ε = 0, namely Theorem 2.7, using the corresponding estimates for the approximate ε-problem.

Main results

Motivated by physics described above, we study the following initial value problem for the nonlinear and nonlocal equation involving u = u(x, t)

u t = -|u x | Λ α u on R × (0, +∞), (2.1) u(x, 0) = u 0 (x) for x ∈ R, (2.2)
where the assumptions on the initial datum u 0 will be precised later. Here, for α ∈ (0, 2), Λ α = -∂ 2 /∂x 2 α/2 is the pseudodifferential operator defined via the Fourier transform

(2.3) (Λ α w)(ξ) = |ξ| α w(ξ).
Recall that the operator Λ α has the Lévy-Khintchine integral representation for every α ∈ (0, 2)

(2.4) -Λ α w(x) = C(α) R w(x + z) -w(x) -zw (x)1 {|z|≤1} dz |z| 1+α ,
where C(α) > 0 is a constant. This formula (discussed in, e.g., [START_REF] Droniou | Fractal first order partial differential equations[END_REF]Th. 1] for functions w in the Schwartz space) allows us to extend the definition of Λ α to functions which are bounded and sufficiently smooth, however, not necessarily decaying at infinity.

As we have already explained (cf. equation (1.8)), in the particular case α = 1, equation (2.1) is a mean field model that has been derived rigorously in [START_REF] Forcadel | Homogenization of the dislocation dynamics and of some particle systems with two-body interactions[END_REF] as the limit of a system of particles in interactions (cf. (1.1)) with forces V (z) = 1 z . Here, the density u x means the positive density |u x | of dislocations of type of the sign of u x . Moreover, the occurrence of the absolute value |u x | in the equation allows the vanishing of dislocation particles of the opposite sign. In the present paper, we study the general case α ∈ (0, 2) that could be seen as a mean field model of particles modeled by system (1.1) with repulsive interactions V (z) = 1 z α . Here, we would like also to keep in mind that (2.1) is the simplest nonlinear anomalous diffusion model (described by the Lévy operator Λ α ) which degenerates for u x = 0.

First note that equation (2.1) is invariant under the scaling (2.5) u λ (x, t) = u(λx, λ α+1 t)

for each λ > 0 which means that if u = u(x, t) is a solution to (2.1), then u λ = u λ (x, t) is so. Hence, our first goal is to construct self-similar solutions of equation (2.1), i.e. solutions which are invariant under the scaling (2.5). By a standard argument, any self-similar solution should have the following form (2.6) u α (x, t) = Φ α (y) with y = x t 1/(α+1) , where the self-similar profile Φ α has to satisfy the following equation

(2.7) -(α + 1) -1 y Φ α (y) = -(Λ α Φ α (y)) Φ α (y) for all y ∈ R.
In our first theorem, we construct solutions to equation (2.7).

Theorem 2.1 (Existence of self-similar profile). Let α ∈ (0, 2). There exists a nondecreasing function Φ α of the regularity C 1+α/2 at each point and analytic on the interval (-y α , y α ) for some y α > 0, which satisfies

Φ α = 0 on (-∞, -y α ), 1 on (y α , +∞),
and

(Λ α Φ α )(y) = y α + 1
for all y ∈ (-y α , y α ).

Remark 2.2. We can obtain the self-similar solutions corresponding to different boundary values at infinity, simply considering for any γ > 0 and b ∈ R the profiles γΦ α γ -1/(α+1) y + b which are also solutions of equation (2.7).

Remark 2.3. The fact that ∂ y Φ α has compact support reveals a finite velocity propagation of the support of the solution which is typical for solutions the porous medium equation, cf. Remark 2.8 below.

At least formally, the function Φ α is the solution of (2.7), and the selfsimilar function u α given by (2.6) is a solution of equation (2.1) with the initial datum being the Heaviside function

(2.8) u 0 (x) = H(x) = 0 if x < 0, 1 if x > 0.
In order to check that u α given by (2. In Theorem 2.4, the uniqueness holds in the sense that if u is another viscosity solution to (2.1), (2.8), then u = u α on (R × [0, +∞)) \ {(0, 0)}.

The self-similar solutions are not only unique, but are also stable in this framework of viscosity solutions, as the following result shows. Theorem 2.5 (Stability of the self-similar solution). Let α ∈ (0, 2). For any initial data u 0 ∈ BU C(R) satisfying

(2.9) lim x→-∞ u 0 (x) = 0 and lim x→+∞ u 0 (x) = 1,
let us consider the unique viscosity solution u = u(x, t) of (2.1)-(2.2) and, for each λ > 1, its rescaled version u λ = u λ (x, t) given by equation (2.5).

Then, for any compact set K ⊂ (R × [0, +∞)) \ {(0, 0)}, we have

(2.10) u λ (x, t) → Φ α x t 1/(α+1) in L ∞ (K) as λ → +∞.
We stress on the fact that Theorem 2.5 contains a result on the long time behaviour of solution because, first, choosing t = 1 in (2.10) and, next, substituting λ = t 1/(α+1) we obtain the convergence of u xt 1/(α+1) , t toward the self-similar profile Φ α (x).

On the other hand, convergence (2.10) can be seen as a stability result when we consider initial data which are perturbations of the Heaviside function. This is a nonstandard stability result in the framework of discontinuous viscosity solutions. It shows that the approach by viscosity solutions is a good one in the sense of Hadamard, even if we consider here initial conditions which are perturbations of the Heaviside function.

Remark 2.6. In the particular case of α = 1, the nonnegative function

U (x, t) = t -1/2 Φ 1 (xt -1/2
), with Φ 1 -the self-similar profile provided by Theorem 2.1, is the compactly supported self-similar solution of the Constantin-Lax-Majda equation (1.15). This function attracts other nonnegative solutions to (1.15) in the sense stated in Theorem 2.5.

Finally, we have the following result of independent interest.

Theorem 2.7 (Optimal decay estimates). Let α ∈ (0, 1]. For any initial condition u 0 ∈ BU C(R) such that u 0,x ∈ L 1 (R), the unique viscosity solution u of (2.1)-(2.2) satisfies u(•, t) ∞ ≤ u 0 ∞ and u x (•, t) ∞ ≤ u 0,x ∞ for any t > 0.
Moreover, for every p ∈ [1, +∞) we have

(2.11) u x (•, t) p ≤ C p,α u 0,x pα+1 p(α+1) 1 t - (p-1) p(α+1)
for any t > 0, with some constant C p,α > 0 depending only on p and α.

The decay given in (2.11) is optimal in the sense that the self-similar

solution satisfies (u α ) x (•, t) p = (Φ α ) y (•) p t - (p-1)
p(α+1) .

Remark 2.8. The equation satisfied by v = u x (2.12)

v t = -(|v|Λ α-1 Hv) x
(with the Hilbert transform H defined in (1.10)) can be treated as a nonlocal counterpart of the porous medium equation. Indeed, for α = 2 and for nonnegative v, equation (2.12) reduces to

v t = (vv x ) x = v 2 /2 xx .
As in the case of the porous medium equation (see e.g. [START_REF] Vázquez | Smoothing and Decay Estimates for Nonlinear Diffusion Equations[END_REF] and the references therein), estimates (2.11) show a regularizing effect created by the equation, even for the anomalous diffusion:

if v 0 ∈ L 1 (R) then v ∈ L p (R) for each p > 1.
Observe also that equation (2.12) has compactly supported self-similar

solution v(x, t) = t -1 α+1 Φ α x/t 1 α+1
, where the profile Φ α was constructed in Theorem 2.1. This function for α = 2 corresponds to the well known Barenblatt-Prattle solution of the porous medium equation.

Remark 2.9. As we have already mentioned, see Theorem 4.7 below, the initial value problem (2.1)-(2.2) has the unique global-in-time viscosity solution for any initial datum u 0 ∈ BU C(R). Under the additional assumption u 0,x ∈ L p (R), the corresponding solution satisfies u x (•, t) ∈ L p (R) for all t > 0. Indeed, this is an immediate consequence of the L p -inequalities stated in Remark 7.7 and of a limit argument analogous to that in Step 6 of the proof of Theorem 2.7.

Remark 2.10. For any positive, sufficiently regular and vanishing at infinity initial condition v 0 ∈ L 2 (R), the corresponding solution v = v(x, t) of the Constantin-Lax-Majda equation (1.15) is global-in-time and analytic, see [START_REF] Castro | Global existence, singularities and ill-posedness for a nonlocal flux[END_REF]Th. 2.1]. Since v = u x ≥ 0, this result holds true for solutions of problem (2.1)-(2.2) with α = 1. On the other hand, the blow up of v x (•, t) ∞ of nonpositive solutions to (1.15) was shown in [START_REF] Córdoba | Formation of singularities for a transport equation with nonlocal velocity[END_REF] (caution: one should replace θ by -θ in order to transform the model considered in [START_REF] Córdoba | Formation of singularities for a transport equation with nonlocal velocity[END_REF] into equation (1.15)). Moreover, the nonexistence of global-in-time solutions to the initial value problem for equation (1.15) has been always proved assuming that the initial datum is negative at some point, see [7, Th. 2.1 and Remark 2.3] and [START_REF] Castro | Global existence, singularities and ill-posedness for a nonlocal flux[END_REF]Th. 3.1 and 4.8]. Those arguments cannot be applied to equation (2.1) with α = 1 due to the factor |v| (= |u x |) in the nonlinearity.

Remark 2.11. For α ∈ (1, 2), we do not know how to define the product |u x | (Λ α u) in the sense of distributions, which is an obstacle for us to prove the result of Theorem 2.7 in this case, see Section 7. Note, however, that the inequalities from Theorem 2.7 are valid for α ∈ (1, 2] as well, provided the solution u = u(x, t) is sufficiently regular.

Construction of self-similar solutions

Proof of Theorem 2.1. The crucial role in the construction of the self-similar profile Φ α is played by the function

(3.1) v(x) = K(α) 1 -|x| 2 α/2 for |x| < 1, 0 for |x| ≥ 1, with K(α) = Γ(1/2) [2 α Γ(1 + α/2)Γ((1 + α)/2)] -1
. This function (together with its multidimensional counterparts) has an important probabilistic interpretation. Indeed, if {X(t)} t≥0 denotes the symmetric α-stable process in R of order α ∈ (0, 2] and if T = inf{t : |X(t)| > 1} is the first passage time of the process to the exterior of the segment {x : |x| ≤ 1}, Getoor [START_REF] Getoor | First passage times for symmetric stable processes in space[END_REF] proved that E x (T ) = v(x), where E x denotes the expectation under the condition X(0) = x.

In particular, it was computed in [15, Th. 5.2] using a purely analytical argument (based on definition (2.3) and on properties of the Fourier transform) that Λ α v ∈ L 1 (R) and

M (α) = K(α) 1 0 1 -|y| 2 α/2 dy = π 2 α (α + 1)Γ 1+α 2 2 .
Then, for any ϕ ∈ C ∞ c (R), we can introduce the following duality

Λ α u, ϕ = R u(y)(Λ α ϕ)(y) dy.
This defines Λ α u as a distribution, because we can check (using the Lévy-Khintchine formula (2.4)) that there exists a constant C > 0 such that

|(Λ α ϕ)(x)| ≤ C ϕ W 2,∞ (R) 1 + |x| 1+α .
If, moreover, supp ϕ ⊂ (-1, 1), it is easy to check using the properties of the

function v = v(x) that ∂ x (Λ α u), ϕ = -u, Λ α (∂ x ϕ) = -u, ∂ x (Λ α ϕ) = Λ α (∂ x u), ϕ = 1, ϕ ,
where the last inequality is a consequence of (3.2). From the symmetry of v, we deduce the antisymmetry of u, and then

(Λ α u)(-x) = -(Λ α u)(x).
Therefore, we get the equality (Λ α u)(x) = x in D (-1, 1), and thus by [START_REF] Hörmander | The Analysis of Linear Partial Differential Operators[END_REF]Cor. 3.1.5], in the classical sense for each y ∈ (-1, 1), too. Finally, we define the nonnegative function

Φ α (y) = γ α + 1 u γ -1/(α+1) y + M (α) with γ -1 = 2M (α) α + 1 .
Now, for y α = γ 1/(α+1) = [2M (α)] -1/(α+1) , we can check easily that Φ α is exactly as stated in Theorem 2.1, which ends the proof.

Let us note that we will not use in the sequel the explicit form of the function Φ α , but only its properties listed in Theorem 2.1.

Remark 3.1. It has been known since the work of Head and Louat [START_REF] Head | The distribution of dislocations in linear arrays[END_REF] (see also [START_REF] Head | Dislocation group dynamics III. Similarity solutions of the continuum approximation[END_REF]) that the function v(x) = K 1 -|x| 2 1/2 (with a suitably chosen constant

K = K(1) > 0) is the solution of the equation (Λ 1 v)(x) = 1 on (-1, 1
). This result is a consequence of an inversion theorem due to Muskhelishvili, see either [28, p. 251] or [START_REF] Tricomi | Integral Equations[END_REF]Sec. 4.3].

Notion of viscosity solutions

Here, we consider equation (2.1) and its vanishing viscosity approximation, i.e. the following initial value problem for α ∈ (0, 2) and η ≥ 0

u t = ηu xx -|u x | Λ α u on R × (0, +∞), (4.1) u(x, 0) = u 0 (x) for x ∈ R. (4.2)
In this section, we present the framework of viscosity solutions to problem (4.1)-(4.2). To this end, we recall briefly the necessary material, which can be either found in the literature or is essentially a standard adaptation of those results. We also refer the reader to Crandall et al. [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF] for a classical text on viscosity solutions to local (i.e. partial differential) equations.

Let us first recall the definition of relaxed lower semi-continuous (lsc, for short) and upper semi-continuous (usc, for short) limits of a family of functions u ε which is locally bounded uniformly with respect to ε lim sup

ε→0 eq * u ε (x, t) = lim sup ε→0 y→x,s→t u ε (y, s) and lim inf ε→0 * u ε (x, t) = lim inf ε→0 y→x,s→t u ε (y, s).
If the family consists of a single element, we recognize the usc envelope and the lsc envelope of a locally bounded function u u * (x, t) = lim sup y→x,s→t u(y, s) and u * (x, t) = lim inf y→x,s→t u(y, s). Now, we recall the definition of a viscosity solution for (4.1)-(4.2). Here, the difficulty is caused by the measure |z| -1-α dz appearing in the Lévy-Khintchine formula (2.4) which is singular at the origin and, consequently, the function has to be at least C 1,1 in space in order that Λ α u(•, t) makes sense (especially for α close to 2). We refer the reader, for instance, to [START_REF] Sayah | Équations d'Hamilton-Jacobi du premier ordre avec termes intégro-différentiels. I Unicité des solutions de viscosité, II Existence de solutions de viscosité[END_REF][START_REF] Barles | Second-order elliptic integro-differential equations: viscosity solutions' theory revisited[END_REF][START_REF] Jakobsen | A "maximum principle for semicontinuous functions" applicable to integro-partial differential equations[END_REF] for the stationary case, and to [START_REF] Jakobsen | Continuous dependence estimates for viscosity solutions of integro-PDEs[END_REF][START_REF] Imbert | Homogenization of first order equations, with (u/ε)periodic Hamiltonians. Part II: application to dislocations dynamics[END_REF] for the evolution equation where this question is discussed in detail. Now, we are in a position to define viscosity solutions. Definition 4.1 (Viscosity solution/subsolution/supersolution). A bounded usc (resp. lsc) function u : R×R + → R is a viscosity subsolution (resp. supersolution) of equation (4.1) on R×(0, +∞) if for any point (x 0 , t 0 ) with t 0 > 0, any τ ∈ (0, t 0 ), and any test function φ belonging to C 2 (R × (0, +∞)) ∩ L ∞ (R × (0, +∞)) such that (u -φ) attains a maximum (resp. minimum) at the point (x 0 , t 0 ) on the cylinder

Q τ (x 0 , t 0 ) := R × (t 0 -τ, t 0 + τ ),
we have

∂ t φ(x 0 , t 0 ) -ηφ xx (x 0 , t 0 ) + |φ x (x 0 , t 0 )| (Λ α φ(•, t 0 ))(x 0 ) ≤ 0 (resp. ≥ 0),
where (Λ α φ(•, t 0 ))(x 0 ) is given by the Lévy-Khintchine formula (2.4).

We say that u is a viscosity subsolution (resp. supersolution) of problem (4.1)-(4.2) on R × [0, +∞), if it satisfies moreover at time t = 0

u(•, 0) ≤ u * 0 (resp. u(•, 0) ≥ (u 0 ) * ) .
A function u : R × R + → R is a viscosity solution of (4.1) on R × (0, +∞) (resp. R × [0, +∞)) if u * is a viscosity subsolution and u * is a viscosity supersolution of the equation on R × (0, +∞) (resp. R × [0, +∞)).

Other equivalent definitions are also natural, see for instance [START_REF] Barles | Second-order elliptic integro-differential equations: viscosity solutions' theory revisited[END_REF].

(4.2). If u(x, 0) ≤ u 0 (x) ≤ v(x, 0) for some u 0 ∈ BU C(R), then u ≤ v on R × [0, +∞).
Proof. Recall that in [START_REF] Imbert | Homogenization of first order equations, with (u/ε)periodic Hamiltonians. Part II: application to dislocations dynamics[END_REF]Th. 5], the comparison principle is proved for α = 1 and η = 0 under the additional assumption that u 0 ∈ W 1,∞ (R). Looking at the proof of that result, the regularity of the initial data u 0 is only used to show that

(4.3) sup x∈R ((u 0 ) ε (x) -(u 0 ) ε (x)) → 0 as ε → 0,
where (u 0 ) ε and (u 0 ) ε are respectively sup and inf-convolutions. It is easy (and classical) to check that (4.3) is still true for u 0 ∈ BU C(R). The general case can be done either considering a variation of the proof of [START_REF] Imbert | Homogenization of first order equations, with (u/ε)periodic Hamiltonians. Part II: application to dislocations dynamics[END_REF] taking into account the additional Laplace operator, or applying the "maximum principle" from [START_REF] Jakobsen | A "maximum principle for semicontinuous functions" applicable to integro-partial differential equations[END_REF], or following, for instance, the lines of [START_REF] Barles | Second-order elliptic integro-differential equations: viscosity solutions' theory revisited[END_REF]. We skip here the detail of this adaptation. This finishes the proof. Here, the result for the time dependent problem is again a classical adaptation of that argument, so we skip details.

Remark 4.5. One can generalize directly Theorem 4.4 assuming that {u ε } ε>0 are solutions to the sequence of equations (4.1) with η = ε. Then, in the limit ε → 0 + , we obtain viscosity subsolutions (resp. supersolutions) of equation (2.1). We use this property in the proof of Theorem 2.7.

Remark 4.6. In Theorem 4.4, we only claim that the limit u is a supersolution on R × (0, +∞), but not on R × [0, +∞). In other words, we do not claim that u satisfies the initial condition. Without further properties of the initial data u 0 , it may happen that u(•, 0) ≤ u * 0 is not true. Proof. Applying the argument of [START_REF] Imbert | A non-local regularization of first order Hamilton-Jacobi equations[END_REF] (already adapted from the classical arguments), we can construct a solution by the Perron method, if we are able to construct suitable barriers.

Case 1: First, assume that u 0 ∈ W 2,∞ (R). Then the following functions (4.4) u ± (x, t) = u 0 (x) ± Ct are barriers for C > 0 large enough (depending on the norm u 0 W 2,∞ (R) ), and we get the existence of solutions by the Perron method.

Case 2: Let u 0 ∈ BU C(R). For any ε > 0, we can regularize u 0 by a convolution, and get a function u ε 0 ∈ W 2,∞ (R) which satisfies, moreover, (4.5)

|u ε 0 -u 0 | ≤ ε.
Let us call u ε the solution of (4.1)-(4.2) with the initial condition u ε 0 instead of u 0 . Then, from the fact that the equation does not see the constants and from the comparison principle Theorem 4.3, we have for any ε, δ > 0

|u ε -u δ | ≤ ε + δ.
Therefore, {u ε } ε>0 is the Cauchy sequence which converges in L ∞ (R × [0, +∞)) to some continuous function u (because all the functions u ε are continuous). By the stability result Theorem 4.4, we see that u is a viscosity solution of equation (4.1) on R×(0, +∞). To recover the initial boundary condition, we simply remark that u ε (x, 0) = u ε 0 (x) satisfies (4.5), and then passing to the limit, we get u(x, 0) = u 0 (x). This shows that u is a viscosity solution of problem (4.1)-(4.2) on R × [0, +∞), and concludes the proof of Theorem 4.7. Proof. Using Remark 4.2 and properties of Φ α gathered in Theorem 2.1, it is straightforward to check that the self-similar solution u α (x, t) given in (2.6) is a viscosity solution of equation (4.1)-(4.2) with the initial condition (2.8). Now, we show the inequality (u α ) * ≤ v * . Let v be a viscosity supersolution of (4.1)-(4.2) with the Heaviside initial datum (2.8). Given a > 0 and v a (x, t) = v(a + x, t), we have

Uniqueness and stability of the self-similar solution

(u α ) * (x, 0) ≤ (u 0 ) * (x) ≤ (u 0 ) * (a + x) ≤ v a (x, 0).
Because of the translation invariance of the equation (2.1), we see that v a is still a supersolution. Moreover, for any a > 0, we can always find an initial condition u a ∈ BU C(R) such that u α (x, 0) ≤ u a (x) ≤ v a (x, 0). Therefore, applying the comparison principle (Theorem 4.3), we deduce that

u α ≤ v a .
Because this is true for any a > 0, we can take the limit as a → 0 and get (u α ) * ≤ v * .

For a subsolution v, we proceed similarly to obtain v * ≤ (u α ) * . This finishes the proof of Lemma 5.1.

Proof of Theorem 2.4. We consider a viscosity solution v of equation (2.1) with the Heaviside initial datum (2.8). Using the both inequalities of Lemma 5.1, and the fact that (u α ) * = (u α ) * on (R × [0, +∞))\ {(0, 0)}, we deduce the equality v = u α on (R × [0, +∞)) \ {(0, 0)} , which ends the proof of Theorem 2.4.

We will now prove the following weaker version of Theorem 2.5. Theorem 5.2 (Convergence for suitable initial data). The convergence in Theorem 2.5 holds true under the following additional assumption

(5.1) lim y→-∞ u 0 (y) = 0 ≤ u 0 (x) ≤ 1 = lim y→+∞ u 0 (y).
Proof.

Step 1: Limits after rescaling of the solution. Consider a solution u of (2.1)-(2.2) with an initial condition u 0 satisfying (5.1). Recall that for any λ > 0, the rescaled solution is given by u λ (x, t) = u(λx, λ α+1 t). Let us define u = lim sup λ→+∞ * u λ and u = lim inf λ→+∞ * u λ .

From the stability result Theorem 4.4, we know that u (resp. u) is a subsolution (resp. supersolution) of (2.1) on R × (0, +∞).

Step 2: The initial condition. We now want to prove that

(5.2) u(x, 0) = u(x, 0) = H(x) for x ∈ R\ {0} ,
where H is the Heaviside function. To this end, we remark that u 0 satisfies for some γ > 0 the inequality |u 0 (x)| ≤ γ (note that γ = 1 under assumption (5.1)), and for each ε > 0, there exists M > 0 such that |u 0 (x)| < ε for x ≤ -M .

In particular, we get

u 0 (x) < ε + γH(x + M ),
and then from the comparison principle, we deduce

(5.3) u(x, t) ≤ ε + (u γ α ) * (x + M, t) with (5.4) u γ α (x, t) = Φ γ α x t 1/(α+1)
and Φ γ α (y) = γΦ α γ -1/(α+1) y .

Here Φ γ α is the self-similar profile solution of (2.7) with the boundary conditions 0 and γ at infinity. Moreover, because u γ α is continuous off the origin, we can simply drop the star * , when we are interested in points different from the origin. This implies

u λ (x, t) ≤ ε + Φ γ α x + M λ -1 t 1/(α+1) ,
and then u(x, t) ≤ ε + Φ γ α x t 1/(α+1) . Therefore, for every x < 0 we have

u(x, 0) ≤ ε + Φ γ α (-∞) = ε.
Because this is true for every ε > 0, we get u(x, 0) ≤ 0 for every x < 0. We get the other inequalities similarly, and finally conclude that (5.2) is valid.

Step 3: Initial condition at the origin, using assumption (5.1). We now make use of (5.1) to identify the initial values of the limits u and u. We deduce from the comparison principle that 0 ≤ u(x, 0) ≤ u(x, 0) ≤ 1, and then for every x ∈ R we have u(x, 0) ≤ H * (x) and u(x, 0) ≥ H * (x).

Step 4: Identification of the limits after rescaling. From Lemma 5.1, we obtain u ≤ (u α ) * = (u α ) * ≤ u on (R × [0, +∞))\ {(0, 0)} .

We have by the construction u ≤ u, hence we infer

u = u = u α on (R × [0, +∞))\ {(0, 0)} .
Step 5: Conclusion for the convergence. Then for any compact K ⊂ (R × [0, +∞))\ {(0, 0)}, we can easily deduce that sup

(x,t)∈K |u λ (x, t) -u α (x, t)| → 0 as λ → +∞,
which finishes the proof of Theorem 5.2.

Further decay properties and

the end of the proof of Theorem 2.5 Theorem 6.1 (Decay of a solution with compact support). Let u be the solution to (2.1)-(2.2) with the initial datum u 0 ∈ BU C(R) satisfying for some A > 0 (6.1) u 0 (x) ≤ 0 for |x| ≥ A, and u 0 (x) ≤ γ for some γ > 0 and all x ∈ R. Then, there exist β, β > 0 (depending on α, but independent of A, γ) such that First, we need the following Lemma 6.2 (Decay after the first interaction). Consider Φ α and y α defined in Theorem 2.1. Let ν ∈ (1/2, 1) and ξ ν ∈ (0, y α ) be such that Φ α (ξ ν ) = ν.

u(x, t) ≤ Ct -β ,
Let T > 0 be defined by

(6.2) A γ 1/(α+1) T 1/(α+1) = ξ ν .
Then, under the assumptions of Theorem 6.1, we have

(6.3) u(x, t) ≤ νγ for all t ≥ T, x ∈ R, and
(6.4) u(x, t) ≤ 0 for all 0 ≤ t ≤ T and |x| ≥ A 1 + y α ξ ν . Proof. Let us denote Φ γ α (y) = γΦ α γ -1/(α+1) y . Then we have γH(x + A) ≥ u 0 (x) for x ∈ R, where γH(x + A) = lim t→0 + Φ γ α x + A t 1/(α+1)
for x + A = 0. Now, we apply the comparison principle to deduce that Φ γ α x + A t 1/(α+1) ≥ u(x, t) for (x, t) ∈ R × (0, +∞). This argument can be made rigorous by simply replacing the function γH(x+ A) by Φ γ α (x + A + δ)/(t 1/(α+1) ε

) with δ > 0 and some sequence t ε → 0 + , and then taking the limit δ → 0 + . Therefore we have

γΦ α x + A γ 1/(α+1) t 1/(α+1) ≥ u(x, t) for (x, t) ∈ R × (0, +∞).
From the properties of the support of Φ α , we also deduce that u(x, t) ≤ 0 for x ≤ -A + y α (γt) 1/(α+1) , and then, by symmetry, u(x, t) ≤ 0 for |x| ≥ A + y α (γt) 1/(α+1) .

Moreover, it follows from the monotonicity of Φ α that γΦ α A (γt) 1/(α+1) ≥ u(x, t) for x ≤ 0, and by symmetry we can prove the same property for x ≥ 0. Then for T > 0 defined in (6.2) we easily deduce (6.3) and (6.4). This ends the proof of Lemma (6.2).

Proof of Theorem 6.1. We apply recurrently Lemma 6.2. Define A 0 = A, γ 0 = γ, and

A n+1 = A n 1 + y α ξ ν , γ n+1 = νγ n , and A n (γ n T n ) 1/(α+1) = ξ ν .

This gives

A n = A 0 1 + y α ξ ν n , γ n = ν n γ 0 , T n = Kµ n , with K = 1 γ 0 A 0 ξ ν α+1 , 1 < µ = 1 ν 1 + y α ξ ν α+1
, and therefore

u(x, t) ≤ γ n for t ≥ T 0 + ... + T n-1 = K µ n -1 µ -1 .
In particular, we get for any

n ∈ N u(x, t) ≤ γ 0 ν n for t ≥ K 0 µ n with K 0 = K/(µ -1). This implies u(x, t) ≤ γ 0 K β 0 t -β for any t > 0, x ∈ R, with β = - log ν log µ > 0.
Similarly, we have

u(x, t) ≤ 0 for |x| ≥ A n if t ≤ T 0 + ... + T n-1 = K µ n -1 µ -1 .
In particular, we get for any n ∈ N\ {0}

u(x, t) ≤ 0 for |x| ≥ A 0 1 + y α ξ ν n , if t ≤ K 0 µ n with K 0 = K/µ. This implies u(x, t) ≤ 0 for |x| ≥ A 0 (K 0 ) -β t β for t ≥ 0, with β = log 1 + yα ξν log µ > 0.
This ends the proof of Theorem 6.1.

As a corollary, we can now remove assumption (5.1) in Theorem 5.2 and complete the proof of Theorem 2.5.

Proof of Theorem 2.5. We simply repeat Step 3 of the proof of Theorem 5.2, but here without assuming (5.1). Then, for any ε > 0 there exists A > 0 such that u 0 (x) ≤ 1 + ε for |x| ≥ A.

By Theorem 6.1 applied to the solution u(x, t)-1-ε, this implies that there exists a constant C > 0 (depending on ε) such that

u(x, t) ≤ 1 + ε + Ct -β .
Therefore, for any for λ > 0 the following inequality

u λ (x, t) ≤ 1 + ε + Ct -β λ -β
holds true, which implies that u = lim sup

λ→+∞ * u λ satisfies u(x, t) ≤ 1 + ε for (x, t) ∈ R × (0, +∞).
Since this is true for any ε > 0, we deduce that u(x, t) ≤ 1 for (x, t) ∈ R × (0, +∞).

Let us now define ũ = min (1, u) . By the construction,

ũ(x, t) = u(x, t) for (x, t) ∈ R × [0, +∞)\ {(0, 0)} , and, by (5.2)
, we have ũ(x, 0) ≤ H * (x) for all x ∈ R. Therefore, ũ is a subsolution of (2.1)-(2.2) on R × [0, +∞) with the initial datum being the Heaviside function.

Similarly, we can show that u = lim sup λ→+∞ * u λ satisfies u ≥ 0 for (x, t) ∈ R × (0, +∞).

Hence, the function ũ = max (0, u) , which is a supersolution of (2.1)-(2.2) on R × [0, +∞) with the Heaviside initial datum. Finally, the conclusion of the proof is the same as in the proof of Theorem 5.2 where u (resp. u) is replaced by ũ (resp. ũ). This finishes the proof of Theorem 2.5.

Approximate equation and gradient estimates

In this section, in order to prove our gradient estimates for viscosity solutions stated in Theorem 2.7, we replace equation (2.1) by an approximate equation for which smooth solutions do exist. Indeed, with ε > 0, we consider the following initial value problem

u t = εu xx -|u x |Λ α u on R × (0, +∞), (7.1) u(x, 0) = u 0 (x) for x ∈ R. (7.2)
We have added to equation (2.1) an auxiliary viscosity term which is stronger than Λ α u and u x . In the case α ∈ (0, 1], we will see later (in Section 8) that it is possible to pass to the limit ε → 0 + in L ∞ (R), which is the required convergence for the framework of viscosity solutions. The difficulty in the case α ∈ (1, 2) comes from the fact that, for the limit equation with ε = 0, we are not able to give a meaning to the product |u x | (Λ α u) in the sense of distributions, while it is possible when α ∈ (0, 1].

Our results on qualitative properties of solutions to the regularized problem (7.1)-(7.2) are stated in the following two theorems. Theorem 7.1 (Approximate equation -existence of solutions). Let α ∈ (0, 1] and ε > 0. Given any initial datum

u 0 ∈ C 2 (R) such that u 0,x ∈ L 1 (R)∩L ∞ (R)
, there exists a unique solution u ∈ C(R×[0, +∞))∩C 2,1 (R× (0, +∞)) of (7.1)-(7.2). This solution satisfies

(7.3) u x ∈ C([0, T ], L p (R)) ∩ C((0, T ]; W 1,p (R)) ∩ C 1 ((0, T ], L p (R))
for every p ∈ (1, ∞) and each T > 0.

Theorem 7.2 (Approximate equation -decay estimates). Under the assumptions of Theorem 7.1, the solution u = u(x, t) of (7.1)-(7.2) satisfies

(7.4) u(•, t) ∞ ≤ u 0 ∞ , u x (•, t) ∞ ≤ u 0,x ∞ , and (7.5)
u x (•, t) p ≤ C p,α u 0,x pα+1 p(α+1) 1 t -1 α+1 1-1 p ,
for every p ∈ [1, ∞), all t > 0, and constants C p,α > 0, see (7.20) below), independent of ε > 0, t > 0 and u 0 .

Existence theory. First, we construct solutions to the initial value problem for the regularized equation.

Proof of Theorem 7.1. Note first that

(7.6) Λ α u = Λ α-1 Hu x ,
where H denotes the Hilbert transform, see (1.10). We recall that the Hilbert transform is bounded on the L p -space for any p ∈ (1, +∞) (see [30, Ch. 2, Th. 1]), i.e. it satisfies for any function v ∈ L p (R) the following inequality (7.7)

Hv p ≤ C p v p with a constant C p independent of v.
For α ∈ (0, 1), the operator Λ α-1 defined analogously as in (2.3) corresponds to the convolution with the Riesz potential Λ

α-1 v = C α | • | -α * v.
Hence, by [30, Ch. 5, Th. 1], for any p > 1/α with α ∈ (0, 1] and any function v ∈ L q (R), we have

(7.8) Λ α-1 v p ≤ C p,α v q with 1 q = 1 p + 1 -α. Now, if u = u(x, t
) is a solution to (7.1)-(7.2), using identity (7.6), we write the initial value problem for v = u x v t = εv xx -(|v|Λ α-1 Hv) x on R × (0, +∞), (7.9) (7.10) as well as its equivalent integral formulation (7.11)

v(•, 0) = v 0 = u 0,x ∈ L 1 (R) ∩ L ∞ (R)
v(t) = G(εt) * v 0 - t 0 ∂ x G(ε(t -τ )) * (|v|Λ α-1 Hv) dτ,
with the Gauss-Weierstrass kernel G(x, t) = (4πt) -1/2 exp(-x 2 /(4t)). The next step is completely standard and consists in applying the Banach contraction principle to equation (7.11) in a ball in the Banach space

X T = C([0, T ]; L 1 (R) ∩ L ∞ (R))
endowed with the usual norm v T = sup t∈[0,T ] ( v(t) 1 + v(t) ∞ ). Using well known estimates of the heat semigroup and inequalities (7.7)-(7.8) combined with the imbedding

L 1 (R) ∩ L ∞ (R) ⊂ L p (R) for each p ∈ [1, ∞],
we obtain a solution v = v(x, t) to equation (7.11) in the space X T provided T > 0 is sufficiently small. We refer the reader to, e.g., [START_REF] Amour | Global existence and decay for viscous Hamilton-Jacobi equations[END_REF][START_REF] Ben-Artzi | The local theory for viscous Hamilton-Jacobi equations in Lebesgue spaces[END_REF] for examples of such a reasoning. This solution satisfies (7.3) for every p ∈ (1, ∞) and each T > 0, by standard regularity estimates of solutions to parabolic equations. Moreover, following the reasoning in [START_REF] Amour | Global existence and decay for viscous Hamilton-Jacobi equations[END_REF], one can show that the solution is regular.

Finally, this local-in-time solution can be extended to global-in-time (i.e. for all T > 0) because of the estimates v(t) p ≤ v 0 p for every p ∈ [1, ∞] being the immediate consequence of inequalities (7.17), (7.18), and (7.21) below.

Gradient estimates. In the proof of the decay estimates of u x , we shall require several properties of the operator Λ α . First, we recall the Nash inequality for the operator Λ α . Lemma 7.3 (Nash inequality). Let α > 0. There exists a constant C N > 0 such that (7.12) w

2(1+α) 2 ≤ C N Λ α/2 w 2 2 w 2α 1
for all functions w satisfying w ∈ L 1 (R) and Λ α/2 w ∈ L 2 (R).

The proof of inequality (7.12) is given, e.g., in [26, Lemma 2.2].

Our next tool is the, so called, Stroock-Varopoulos inequality. where w + = max{0, w} and w -= max{0, -w}.

Inequality (7.13) is well known in the theory of sub-Markovian operators and its statement and the proof is given, e.g., in [27, Th. 2.1 combined with the Beurling-Deny condition (1.7)]. Inequality (7.14), called the (generalized) Kato inequality, is used, e.g., in [START_REF] Droniou | Fractal first order partial differential equations[END_REF] to construct entropy solutions of conservation laws with a Lévy diffusion. It can be easily deduced from [13, Lemma 1] by an approximation argument. The proof of (7.15) can be found, for example, in [START_REF] Liskevich | Some problems on Markov semigroups, Schrödinger operators, Markov semigroups[END_REF]Prop. 1.6].

Remark 7.5. Remark that inequality (7.14) appears to be a limit case of (7.13) for p = 1. Inequality (7.15) for w + follows easily from (7.14) by a comparison argument if, for instance, w ∈ C ∞ c (R). Finally, remark that the constant appearing in (7.13) is the same as for the Laplace operator

∂ 2 /∂x 2 = -Λ 2 .
Our proof of the decay of v(t) = u x (t) is based on the following Gagliardo-Nirenberg type inequality Lemma 7.6 (Gagliardo-Nirenberg type inequality). Assume that p ∈ (1, ∞) and α > 0 are fixed and arbitrary. For all v ∈ L 1 (R) such that Λ α/2 |v| (p+1)/2 ∈ L 2 (R), the following inequality is valid

(7.16) v a p ≤ C N Λ α/2 |v| (p+1)/2 2 2 v b 1 , where a = p(p + α) p -1 , b = pα + 1 p -1 ,
and C N is the constant from the Nash inequality (7.12).

Proof. Without loss of generality, we can assume that v 1 = 0. Substituting w = |v| (p+1)/2 in the Nash inequality (7.12) we obtain

v (p+1)(1+α) p+1 ≤ C N Λ α/2 |v| (p+1)/2 2 2 v α(p+1) (p+1)
/2 . Next, it suffices to apply two particular cases of the Hölder inequality

v p v 1/p 2 1 p 2 /(p 2 -1) ≤ v p+1 as well as v (p+1)/2 ≤ v p/(p+1) p v 1/(p+1) 1
, and compute carefully all the exponents which appear on the both sides of the resulting inequality.

Proof of Theorem 7.2. The first inequality in (7.4) is an immediate consequence of the comparison principle from Theorem 4.3, because classical solutions are viscosity solutions, as well. The maximum principle and an argument based on inequalities (7.15) (cf. [START_REF] Karch | On the convergence of solutions of fractal Burgers equation toward rarefaction waves[END_REF] for more detail) lead to the second inequality in (7.4). We also discuss this inequality in Remark 7.7 below.

For the proof of the L 1 -estimate (7.17) u x (t) 1 ≤ u 0,x 1 (i.e. (7.5) with p = 1 and C p,α = 1), we multiply equation (7.9) by sgn v = sgn u x and we integrate with respect to x to obtain

d dt R |v| dx = ε R v xx sgn v dx - R (Λ α-1 Hv)|v| x sgn v dx.
The first term on the right hand side is nonpositive by the Kato inequality (i.e. (7.14) with α = 2) hence we skip it. Remark that (formally)

R (Λ α-1 Hv)|v| x sgn v dx = R (Λ α-1 Hv)v x (sgn v) 2 + (Λ α-1 Hv x )v dx = R (Λ α-1 Hv)v x dx = 0.
Now, approximating the sign function in a standard way by sgn δ (z) = z/ √ z 2 + δ, integrating by parts, and passing to the limit δ → 0 + , one can show rigorously that the second term on right hand side of the above inequality is nonpositive. This completes the proof of (7.17) with p = 1.

Next, we multiply equation in (7.9) by |v| p-2 v with p > 1 to get 1 p

d dt R |v| p dx = ε R v xx |v| p-2 v dx - R (Λ α-1 Hv)|v| x |v| p-2 v dx.
We drop the first term on the right hand side, because it is nonpositive by (7.13) with α = 2. Integrating by parts and using the elementary identity

|v| |v| p-2 v x = p -1 p |v| p-1 v x ,
we transform the second quantity on the right hand side as follows

- R (Λ α-1 Hv)|v| x |v| p-2 v dx = - p -1 p R (Λ α v)|v| p-1 v dx.
Consequently, by the Stroock-Varopoulos inequality (7.13) (with the exponent p replaced by p + 1), we obtain

(7.18) d dt v(t) p p ≤ - 4p(p -1) (p + 1) 2 Λ α/2 |v| (p+1)/2 2 2 .
Hence, the interpolation inequality (7.16) combined with (7.17) lead to the following inequality for v(t) p p 1) .

(7.19) d dt v(t) p p ≤ - 4p(p -1) (p + 1) 2 C N v 0 (pα+1)/(p-1) 1 -1 v(t) p p (p+α)/(p-
Recall now that if a nonnegative (sufficiently smooth function) f = f (t) satisfies, for all t > 0, the inequality f (t) ≤ -Kf (t) β with constants K > 0 and β > 1, then f (t) ≤ (K(β -1)t) -1/(β-1) . Applying this simple result to the differential inequality (7.19), we complete the proof of the L p -decay estimate (7.5) with the constant (7.20)

C p,α = C -1 N 4p(α + 1) (p + 1) 2 -1 α+1 1-1 p ,
where C N is the constant from the Nash inequality (7.12).

Remark 7.7. Note that, for every fixed α, we have lim p→∞ C p,α = +∞. By this reason, we are not allowed to pass directly to the limit p → +∞ in inequalities (7.

v(•, t) ∞ ≤ v 0 (•) ∞ .
It is natural to expect that, under the assumptions of Theorem 7.2, the quantity v(•, t) ∞ should decay at the rate t -1/(α+1) . For a proof, one might follow an idea from [START_REF] Castro | Global existence, singularities and ill-posedness for a nonlocal flux[END_REF]Lemma 4.7] where the decay estimates of v x (•, t) were obtained for solutions of a certain regularization of equation (1.15). Here, however, we did not try to go this way, because our main goal was to study decay estimates for the problem (2.1)-(2.2) whose viscosity solutions are not regular enough a priori to handle decay properties of u xx (x, t) = v x (x, t).

8. Passage to the limit and the proof of Theorem 2.7

Now, we are in a position to complete the proof of the gradient estimates (2.11). First, we show that form the sequence {u ε } ε>0 of solutions to the approximate problem (7.1)-(7.2) one can extract, via the Ascoli-Arzelà theorem, a subsequence converging uniformly. Theorem 4.4 on the stability and Remark 4.5 imply that the limit function is a viscosity solution to (2.1)-(2.2). Passing to the limit ε → 0 + in inequalities (7.4) and (7.5) we complete our reasoning.

Proof of Theorem 2.7. First, let us suppose that u 0 ∈ C ∞ (R) ∩ W 2,∞ (R) with u 0,x ∈ L 1 (R) ∩ L ∞ (R). Denote by u ε = u ε (x, t) the corresponding solution to the approximate problem with ε > 0.

Step 1: Modulus of continuity in space. Under this additional assumption, we have and γ p = 1 α+1 1 -1 p . The Sobolev imbedding theorem implies that there exist some β ∈ (0, 1) and C 0 > 0 such that (8.2)

|u ε (x + h, t) -u ε (x, t)| ≤ |h| β C 0 C p t -γp .

Step 2: Modulus of continuity in time. Let us consider a nonnegative function ϕ ∈ C ∞ (R) with supp ϕ ⊂ [-1, 1] such that R ϕ(x) dx = 1, and for any δ > 0 set ϕ δ (x) = δ -1 ϕ(δ -1 x). Then, multiplying (7.1) |u ε (x, t + s) -u ε (0, t + s)| + |u ε (x, t) -u ε (0, t)| holds true. Using the Hölder inequality (8.2), we deduce that there exists a constant C I depending on I, but independent of δ and of ε ∈ (0, 1], such that |u ε (0, t + s) -u ε (0, t)| ≤ |s|C I,δ + C I δ β .

Since the above inequality is true for any δ, this shows the existence of a modulus of continuity ω I satisfying |u ε (0, t + s) -u ε (0, t)| ≤ ω I (|s|) for any t, t + s ∈ I.

By the translation invariance of the problem, this estimate is indeed true for any x ∈ R, i.e.

(8.4) |u ε (x, t + s) -u ε (x, t)| ≤ ω I (|s|) for any t, t + s ∈ I, x ∈ R.

Step 3: Convergence as ε → 0 + . From estimates (8.2) and (8.4), and using the Ascoli-Arzelà theorem and the Cantor diagonal argument, we deduce that there exists a subsequence (still denoted {u ε } ε ) which converges to a limit u ∈ C(R × (0, +∞)). By the stability result in Theorem 4.4 (see also Remark 4.5), we have that u is a viscosity solution of (2.1) on R × (0, +∞).

Step 4: Checking the initial conditions for u 0 smooth. Remark that for u 0 ∈ W 2,∞ we can use the barriers given in (4.4) with some constant C > 0 uniform in ε ∈ (0, 1]. This ensures that u is continuous up to t = 0 and satisfies u(•, 0) = u 0 , so this proves the result under additional assumptions.

Step 5: General case. The proof in the case of less regular initial conditions simply follows by an approximation argument as was in the proof of Theorem 4.7.

Step 6: Gradient estimates. To pass to the limit ε → 0 + in estimates (7.5), we use the inequality (8.5) h -1 u ε (• + h, t) -u ε (•, t) p ≤ u ε x (•, t) p with fixed h > 0. Hence, by the Fatou lemma combined with the pointwise convergence of u ε toward u, we deduce from (8.5) and (7.5) that h -1 u(• + h, t) -u(•, t) p ≤ C p,α u 0,x This finishes the proof of Theorem 2.7.

( 3

 3 .2) Λ α v(x) = 1 for |x| < 1. Now, for the function v, we define the bounded, nondecreasing, C 1+α/2function u(x) = x 0 v(y) dy which obviously satisfies u(x) = M (α) for all x ≥ 1 and u(x) = -M (α) for x ≤ -1 with

Remark 4 . 2 .

 42 Any bounded function u ∈ C 1+β (with some β > max{0, α -1}) which satisfies pointwisely (using the Lévy-Khintchine formula (2.4)) equation (4.1) with η = 0, is indeed a viscosity solution.

Theorem 4 . 3 (

 43 Comparison principle). Consider a bounded usc subsolution u and a bounded lsc supersolution v of (4.1)-

Theorem 4 . 4 (

 44 Stability). Let {u ε } ε>0 be a sequence of viscosity subsolutions (resp. supersolutions) of equation (4.1) which are locally bounded, uniformly in ε. Then u = lim sup * u ε (resp. u = lim inf * u ε ) is a subsolution (resp. supersolution) of (4.1) on R × (0, +∞). Proof. A counterpart of Theorem 4.4 is proved in [4, Th.1].

Theorem 4 . 7 (

 47 Existence). Consider u 0 ∈ BU C(R). Then there exists the unique bounded continuous viscosity solution u of (4.1)-(4.2).

Lemma 5 . 1 (

 51 Comparison with the self-similar solution). Let v be a subsolution (resp. a supersolution) of equation (2.1) with the Heaviside initial datum given in (2.8). Then we have v * ≤ (u α ) * (resp. (u α ) * ≤ v * ).

  and u(x, t) ≤ 0 for |x| ≥ C t β with some constants C = C(α, A, γ) and C = C (α, A, γ).

Lemma 7 . 4 ( 4 2 dx

 7442 Stroock-Varopoulos inequality). Let 0 ≤ α ≤ 2. For every p > 1, we have(7.13) R (Λ α w)|w| p-2 w dx ≥ for all w ∈ L p (R) such that Λ α w ∈ L p (R). If Λ α w ∈ L 1 (R), we obtain (7.14) R (Λ α w) sgn w dx ≥ 0. Moreover, if w, Λ α w ∈ L 2 (R), it follows that (7.15) R (Λ α w)w + dx ≥ 0 and R (Λ α w)w -dx ≥ 0,

  t) p ≤ C p t -γp with C p = C p,α u 0,x pα+1 p(α+1)1

1 p

 1 for all h > 0. For every fixed t > 0, the sequence {h -1 (u(•+h, t)-u(•, t))} h>0 is bounded in L p (R) and converges (up to a subsequence) weakly in L p (R) toward u x (•, t) (see, e.g., [30, Ch. V, Prop. 3]). Using the well known property of a weak convergence in Banach spaces we concludeu x (•, t) p ≤ lim inf h→0 + h -1 u(• + h, t) -u(•, t) p ≤ C p,α u 0

  5) (as was done in, e.g.,[START_REF] Karch | On the convergence of solutions of fractal Burgers equation toward rarefaction waves[END_REF] Th. 2.3]) in order to obtain a decay estimate of v(t) in the L ∞ -norm. Nevertheless, using (7.[START_REF] Head | The distribution of dislocations in linear arrays[END_REF]) we immediately deduce the inequality v(•, t) p ≤ v 0 (•) p valid for every p ∈ (1, ∞). Hence, passing to the limit p → +∞ we get(7.21)

  by ϕ δ and integrating in space, we getd dt R u ε (x, t)ϕ δ (x) dx = ε u ε (•, t), (ϕ δ ) xx (x, t)ϕ δ (x) dx ≤ ε u ε (•, t) ∞ (ϕ δ ) xx 1 + ϕ δ ∞ u ε x (•, t) p H Λ α-1 u ε x (•, t) p .Here, we have used relation(7.6). Combining inequalities (7.7) and (7.8) with estimate (8.1), we get for p > 1/αH Λ α-1 u ε x (•, t) p ≤ C p C p ,α C q t -γq .

		-	ϕ δ (x) |u ε x (x, t)|(H Λ α-1 u ε x (x, t)) dx,
		R
	and then with 1/p + 1/p = 1
		d
	(8.3)	dt

R u ε

Then for any bounded time interval I ⊂ (0, +∞) there exists a constant C I,δ such that for all t ∈ I, we have for any ε ∈ (0, 1]

d dt R u ε (x, t)ϕ δ (x) dx ≤ C I,δ .

Now, for any t, t + s ∈ I, we get

R u ε (x, t + s)ϕ δ (x) dx -R u ε (x, t)ϕ δ (x) dx ≤ |s|C I,δ .

Therefore, the following estimate

|u ε (0, t + s) -u ε (0, t)| ≤ |s|C I,δ + R ϕ δ (x) dx × sup x∈[-δ,δ]

thank the anonymous referee for calling their attention to the one-dimensional counterpart of the quasi-geostrophic equation (1.15). This work was supported by the contract ANR MICA (2006MICA ( -2009)), by the European Commission Marie Curie Host Fellowship for the Transfer of Knowledge "Harmonic Analysis, Nonlinear Analysis and Probability" MTKD-CT-2004-013389, and by the Polish Ministry of Science grant N201 022 32/0902.