Keywords: Network Calculus, functional (min, +) algebra, computational complexity Network Calculus, algbre des fonctions (min, +), complexit

Ce rapport rassemble une série d'exemples et de contre-exemples recontrés dans l'étude de l'algorithmique des opérations du Network Calculus.

 un ensemble d'algorithmes implémentant les opérations du Network Calculus pour une classe de fonctions bien choisie. Dans ce travail, nous avons construit un certain nombre d'exemples et de contre-exemples justifiant les limites de notre classe choisie. Beaucoup ont été omis dans [2] et c'est pourquoi nous les présentons maintenant.

Exemples et contre-exemples pour les opérations des fonctions (min, +)

1 Definitions and notation

Network Calculus is a theory of deterministic queuing systems encountered in communications networks and based on (min, +) algebra. It enables to analyze complex systems and to prove deterministic bounds on delays, backlogs and other Quality-of-Service (QoS) parameters. To get some introductory material about this theory, the reader is urged to look at the two reference books: Chang's book [START_REF] Chang | Performance Guarantees in Communication Networks[END_REF] and Le Boudec and Thiran's book [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF].

In [START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF], we study the algorithmic aspects of the (min, +) functional operations used in Network Calculus. In particular, we provide algorithms for a class of input functions for which we prove stability (i.e. the output always belongs to the class). This section presents the operations and the classes of functions studied in [START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF]. Then Section 2 is a patchwork of remarks, examples and counterexamples about the mathematical properties of the Network Calculus operations for the considered classes of input functions.

The main operations

In the usual setting, Network Calculus functions take their values in the dioid (min, +), denoted (R min , min, +), which is defined on R min = R ∪ {+∞} and where the two basic operations are the usual minimum min and addition +. These functions are also commonly supposed to be non-decreasing.

However, for sake of generality, we will allow functions which are not necessarily increasing and with values within R = R ∪ {-∞, +∞}.

Let X = N or R + and f, g be two functions from X into R, the Network Calculus makes use of the following operations: 1. Minimum: ∀t ∈ X, min(f, g)(t) = min(f (t), g(t)). We will also use the infixe notation ⊕: f ⊕g = min(f, g). 2. Addition: ∀t ∈ X, (f + g)(t) = f (t) + g(t). 3. Convolution: ∀t ∈ X, (f * g)(t) = inf 0≤s≤t (f (s) + g(t -s)).

4. Deconvolution: ∀t ∈ X, (f g)(t) = sup u≥0 (f (t + u) -g(u)).

Subadditive

closure: ∀t ∈ X, f * (t) = inf n≥0 f (n) (t), where f (n) (t) = (f * • • • * f n times
)(t) for n ≥ 1, and f (0) (t) = 0 if t = 0 and +∞ if t > 0.

Note that we can similarly define the maximum (max) and the substraction (-) of two functions. Depending on whether X = N orX = R + , we will denote by D the set of all functions from N into R (discrete model ) and by F the set of all functions from R + into R (fluid model ). Let f ∈ D or F, the subset Supp(f ) = {t ∈ X | |f (t)| < +∞} is called the support of f .

The first comment on these operations is that the output function is always well-defined, unless some infinite values interfere. We actually consider that (+∞) + (-∞), (+∞) -(+∞) and (-∞) -(-∞) are undefined values and any operation on two given functions whose definition involves such cases will lead to an undefined output. Checking whether a combination of functions and operations is undefined for some arguments is easy (from both mathematical and algorithmic points of view).

Let f, g ∈ D or F, min(f, g) and max(f, g) are always defined, f + g is undefined if ∃t, f (t) = +∞ and

g(t) = -∞ (or the contrary), f -g is undefined if ∃t, f (t) = g(t) = +∞ (or -∞), f * g is undefined if ∃t 1 , t 2 , f (t 1 ) = +∞ and g(t 2 ) = -∞ (or the contrary), f g is undefined if ∃t 1 ≤ t 2 , f (t 2 ) = g(t 1 ) = +∞ (or -∞), f * is undefined if ∃t 1 , t 2 , f (t 1 ) = +∞ and f (t 2 ) = -∞.
Thus in the paper, each time we write formulas, we will assume that all conditions are fulfilled so that they are well-defined for all arguments.

When f ∈ D or F, the subadditive closure can be equivalently defined as f * (0) = 0 and for t > 0,

f * (t) = inf k∈N, t1,...,t k ≥0, t1+•••+t k =t (f (t 1 ) + • • • + f (t k )). (1)
When f ∈ D and f (0) ≥ 0, the subadditive closure also has an equivalent recursive definition: f * (0) = 0 and for t > 0, f [START_REF] Chang | Performance Guarantees in Communication Networks[END_REF]).

* (t) = min[f (t), min 0<s<t (f * (s) + f * (t -s))] (see
Concerning the deconvolution, we should say truncated deconvolution since the usual definition gives a function f g which is defined on Z in the discrete model or R in the fluid model, rather than N or R + . However in the context of Network Calculus where we will combine all these operations starting from functions in D or F, we can restrict ourselves to the definition on N or R + without loss of generality, as it can be seen from the definitions of the operations (where the arguments of functions are always non negative).

Classes of functions

Stability of classes. A class of functions is closed under some set of operations if combining members of the class with any of these operations outputs (if defined) a function which remains in the class. The closure of a class of functions under some set of operations is the smallest class containing these functions and closed under these operations.

Asymptotic behaviors.

Definition 1. Let f be a function from X into R where X = N or R + , then: For affine and ultimately affine functions, ρ is the growth rate. For a pseudo-periodic function f , d is called a period of f , c is its associated increment, and the period of f is its smallest period (if different from 0). For an ultimately affine (resp. ultimately pseudo-periodic) function, we also say that it is ultimately affine (resp. ultimately pseudo-periodic) from T , and we say that T is a rank of the function. Given an ultimately pseudo-periodic function, there exists a smallest rank of pseudo-periodicity, called the rank of the function. More generally let f, g ∈ F, we say that ultimately f = g if ∃T ∈ N, ∀t > T, f (t) = g(t). An ultimately affine function is clearly ultimately plain and pseudo-periodic, and admits any > 0 as a period. Note that being plain is equivalent to have a support equal to [0, T ] or [0, T [ where T ∈ R ∪ {+∞}. A non-decreasing function is always ultimately plain, and if f (0) ∈ R, it is plain.

f is affine if ∃σ, ρ ∈ R, ∀t ∈ X, f (t) = ρt + σ or ∀t ∈ X, f (t) = +∞ (resp. -∞). f is ultimately affine if ∃T ∈ X, ∃σ, ρ ∈ R, ∀t > T, f (t) = ρt + σ or ∀t > T, f (t) = +∞ (resp. -∞). f is pseudo-periodic if ∃(c, d) ∈ R × X * , ∀t ∈ X, f (t + d) = f (t) + c. f is ultimately pseudo-periodic if ∃T ∈ X, ∃(c, d) ∈ R × X * , ∀t > T, f (t + d) = f (t) + c. f is ultimately plain if ∃T ∈ X, ∀t > T , f (t) ∈ R, or ∀t > T , f (t) = +∞ or ∀t > T , f (t) = -∞. f is plain if it is ultimately plain and ∀ 0 ≤ t < T , f (t) ∈ R, and f (T ) ∈ R or possibly f (T ) = +∞ (resp. -∞) if ∀t > T , f (t) = +∞ (resp. -∞). σ (a) (b) (c) (d) σ T
Remark 1. We have chosen to define ultimately as ∃T ∈ X, ∀t > T , but we could also have put ∀t ≥ T . Note that for all the properties we investigate, having ultimately the property for each of these definitions is equivalent, for the simple reason that if a function has the studied property when t > T , then for any T > T , it also has the property when t ≥ T . Inversely if it has the property when t ≥ T , then it also works when t > T . In fact, our choice was guided by the definition of rank as T satisfying the property. With the first definition and the properties we investigate, there always exists a smallest rank from which the property is true (the infimum of all ranks is still a rank). On the contrary, with the second definition, a smallest rank always exists in the discrete model or for continuous functions in the fluid model, but without continuity this is not necessarily the case (e.g. consider the ultimaly affine function equal to 0 at t = 0 and to 1 elsewhere). The existence of a smallest rank is useful to define the compressed form of the ultimately pseudo-periodic functions. However note that in some proofs, e.g. the stability of ultimately affine functions under * , it will be sometimes more convenient to use the second definition with ≥ (in the example of ultimately affine functions, it enables to get rid of a term in the asymptotic formula, note that one can also do the proof with >, it requires to keep this later term but the final result is exactly the same).

INRIA Piecewise affine functions. Definition 2. We say that a function f ∈ F is piecewise affine if there exists an increasing sequence (a i ) i∈N which tends to +∞, such that a 0 = 0 and ∀i ≥ 0,

f is affine on ]a i , a i+1 [, i.e. ∀t ∈]a i , a i+1 [, f (t) = +∞ or ∀t ∈]a i , a i+1 [, f (t) = -∞ or ∃σ i , ρ i ∈ R, ∀t ∈]a i , a i+1 [, f (t) = σ i + ρ i t.
The (a i )'s are called jump points.

Let f ∈ F a piecewise affine function and a ∈ R + , the right limit of f at a is defined as f (a+) = lim t→a,t>a f (t) and the left limit of f at a is defined as f (a-) = lim t→a,t<a f (t). Those limits exist.

Let X ⊆ R + and Y ⊆ R, we denote by F[X, Y ] the set of all piecewise linear functions in F such that there exists a sequence (a i ) i∈N with the properties above and satisfying ∀i ≥ 0, a i ∈ X and f

(a i ), f (a i +), f (a i -) ∈ Y ∪ {-∞, +∞}. We will mainly consider F[N, R], F[Q + , R], F[R + , R] or F[Q + , Q].
Note that a piecewise affine function up to T + d which is ultimately pseudo-periodic of period d from T is clearly piecewise affine with regard to Definition 2.

Mathematical properties

Some algebraic properties

The distributivity between some operators can be easily checked from their definitions. The next proposition is not new, but we wish to emphasize that it applies to infinite families of functions. We will use it later.

Proposition 1 (Distributivity). Let (f i ) i∈I and (g j ) j∈J be two families of functions both in D (or both in F) where I and J are any sets (possibly infinite). Then, as long as the output functions are well defined,

(sup i∈I f i ) (inf j∈J g j ) = sup i∈I,j∈J (f i g j ) (2)
(inf

i∈I f i ) * (inf j∈J g j ) = inf i∈I,j∈J (f i * g j ) (3)
The following proposition concerns the multiplication by a positive constant and is a simple consequence of the definitions of the operations (we do not refer to this property as linearity because in this work we may switch between (+, ×)-linearity and (min, +)-linearity). Multiplying by a negative constant exchanges min and max (inf and sup) in the definitions. Here we abusively denote by αf (t) the function t → αf (t).

Proposition 2 (Multiplying by a constant). Multiplying functions by a fixed positive constant commutes with the Network Calculus operations. More precisely, let f, g ∈ D or F, and α ∈ R + . Then

αf (t) + αg(t) = α(f + g)(t), αf (t) -αg(t) = α(f -g)(t), min(αf (t), αg(t)) = α min(f, g)(t), max(αf (t), αg(t)) = α max(f, g)(t), (αf (t)) * (αg(t)) = α(f * g)(t), (αf (t)) (αg(t)) = α(f g)(t), (αf (t)) * = αf * (t).
The next proposition shows that transforming functions by adding linear terms t → λt or constant terms t → µ does not complicate calculations, since the new outputs can be easily deduced from the former ones. Here we abusively denote by

f (t) + λt + µ the function t → f (t) + λt + µ. Proposition 3 (Lifting). Let f, g ∈ D or F, and λ, µ ∈ R. Then (f (t) + λt + µ) + (g(t) + λt + µ) = (f + g)(t) + 2λt + 2µ, (f (t) + λt + µ) -(g(t) + λt + µ) = (f -g)(t), min((f (t) + λt + µ), (g(t) + λt + µ)) = min(f, g)(t) + λt + µ, max((f (t) + λt + µ), (g(t) + λt + µ)) = max(f, g)(t) + λt + µ, (f (t) + λt + µ) * (g(t) + λt + µ) = (f * g)(t) + λt + 2µ, (f (t) + λt + µ) (g(t) + λt + µ) = (f g)(t) + λt, (f (t) + λt) * = f * (t) + λt (adding µ may induce more complex changes).
The proof is also a direct consequence of the definitions of the operations. The transformation f (t) → f (t)+λt can be seen as a "lifting", in particular it enables to transform any function f ∈ D or F such that ∃p ∈ R + , ∀t < t , f (t ) -f (t) ≥ -p • (t -t), into a non-decreasing function by choosing λ = p. As a consequence, it is not clear that it is possible to take advantage of monotony properties of input functions to design faster algorithms than the ones for the general case.

From discrete to fluid calculations: several issues

All the results of Subsection 2.3 in [START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF] show how to use fluid calculations to perform discrete ones by first interpolating the discrete input functions, then making fluid calculations and finally coming back to a discrete output function. We may wish to set a kind of reciprocal property, like in the next proposition. However it only applies to a very restricted set of operations ! Its proof is easy. Proposition 4. Let f, g be two continuous functions in F[N, R], whenever = +, -, * , we have

[[f ] N N [g] N ] R = f R g.
This proposition works neither for min, max (intersections may occurs at non-integer points) nor for (see the next subsection where the piecewise affine shape is lost). Some issues also arise for the convolution, even if we consider non-decreasing functions f, g s.t. f (0) = g(0) = 0. The convolution f * g of the functions depicted on Figure 2 (in bold), has a jump point at t = T + (r1-r2)T1

R-r2

which is usually not an integer even if T 1 , T ∈ N and r 1 , r 2 , R ∈ Q. The same kind of problem appears for the subadditive closure f * of f ∈ F[N, R] continuous, even if the function is non-decreasing and f (0) = 0. On the example on Figure 3, the function f * represented on the right (in bold) has a jump point at t = 4.5.

Unstability of piecewise affine functions

The next proposition implies that the class of piecewise affine functions is not stable for the deconvolution.

Proposition 5. Let h be any convex C 1 function on [0, 1]. Then there exists f, g ∈ F[N, R] such that h = f g on [0, 1].
To exhibit such functions, we use the following lemmas. Lemma 1. Let φ be any application from N into [0, 1] s.t. φ(N) is dense within [0, 1] (e.g. any surjection N → Q ∩ [0, 1]). Let p x be the equation of the tangent to h at x (i.e. p x (t

) = σ x + ρ x • t = h (x) • (t -x) + h(x)). Then h = sup n∈N p φ(n) . INRIA 1 2 3 4 5 t 0 0 1 2 3 4 5 f 1 2 3 4 5 t 0 0 1 2 3 4 5 f * Figure 3: f ∈ F[N, R] is continuous and f (0) = 0, but f * ∈ F[N, R].
We do not develop the proof of this classical result which states that the envelope of a dense set of tangents matches the initial convex function.

Lemma 2. For all n ≥ 0, consider the functions defined on R by

f n (t) = p φ(n) (t -2n) on [2n, 2n + 1], -∞ elsewhere. g n (t) = α n • (t -2n) on [2n, 2n + 1], +∞ elsewhere.
where α n is any constant at least

ρ φ(n) = h (φ(n)), Then ∀i ∈ N, f i g i = p φ(i) on [0, 1], ∀i = j ∈ N, f i g j = -∞ on [0, 1].
The results of this lemma are a direct application of Lemma 8 in [START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF] which describes the deconvolution of two segments. Proof of Proposition 5. Given h, consider the functions f n and g n defined in Lemma 2, and aggregate these segments by taking f = sup i∈N f i and g = inf j∈N g j .

The general distributivity stated in Proposition 1 with Lemma 1 and 2 implies that:

f g = sup i,j f i g j = sup i f i g i on [0, 1] = sup i p φ(i) on [0, 1] = h on [0, 1].
The functions f and g may seem pathological and far from what is encountered in Network Calculus (they are non-increasing and their supports are ∪ n∈N [2n, 2n + 1]). However this example may be easily adjusted in order to provide some regular properties to the functions. Proposition 6. Let h be any convex C 1 function on [0, 1] s.t. h (0) > 0, thus strictly increasing. Then there exists increasing continuous functions f, g ∈ F[N, R] such that h = f g on [0, 1].

Proof. The principle remains the same but special care is given to the connections between the segments on the intervals [2n, 2n + 1].

We define f and g as continuous increasing functions such that for all n ∈ N,

f = f n on [2n, 2n + 1], f = fn on [2n + 1, 2n + 2], g = g n on [2n, 2n + 1], g = gn on [2n + 1, 2n + 2],
where f n is a segment on [2n, 2n + 1] equal to -∞ elsewhere, fn is a segment on [2n + 1, 2n + 2] equal to -∞ elsewhere, g n is a segment on on [2n, 2n + 1] equal to +∞ elsewhere, gn is a segment on [2n + 1, 2n + 2] equal to +∞ elsewhere. The functions f n and g n correspond the ones introduced in the proof of Proposition 5, the functions fn and gn are the adjustment functions chosen to ensure regular properties but without changing the deconvolution on [0, 1]. We first define f n and g n on [2n, 2n + 1] by:

f n (t) = h (φ(n)) • (t -2n) + f (2n) g n (t) = h (φ(n)) • (t -2n) + g(2n).
Thus f n and g n are parallel segments and we will set f (2n) and g(2n) such that f (2n) -g(2n) = σ φ(n) .

For the interval [2n + 1, 2n + 2], we consider two cases: we know that f (2n + 1) -g(2n + 1) = σ φ(n) (due to f n and g n parallel and f (2n) -g(2n) = σ φ(n) ). Then if σ φ(n+1) ≥ σ φ(n) , fn = segment such that fn (2n + 1) = f n (2n + 1) fn (2n + 2) = f n (2n + 1) + σ φ(n+1) -σ φ(n) and gn = segment such that gn (2n + 2) = gn (2n + 1) = g n (2n + 1).

If σ φ(n+1) < σ φ(n) , fn = segment such that fn (2n + 2) = fn (2n + 1) = f n (2n + 1) and gn = segment such that gn (2n + 1) = g n (2n + 1) gn (2n + 2) = g n (2n + 1) + σ φ(n) -σ φ(n+1) .

In both cases, we garantee that f (2n+2)-g(2n+2) = fn (2n+2)-gn (2n+2) = σ φ(n+1) , and f, g are continuous and increasing.

The distributivity for the deconvolution implies that, on [0, 1],

f g = sup i (f | [i,i+1] g| [i,i+1] ) ∨ sup i (f | [i+1,i+2] g| [i,i+1] ).
This equation can be rewritten as, on [0, 1],

f g = sup n∈N (f n g n ) ∨ sup n∈N ( fn gn ) ∨ sup n∈N ( fn g n ) ∨ sup n∈N (f n+1 gn ). (4)
We choose φ such that the slopes of the adjustment segments of f and g on ∪ n∈N [2n + 1, 2n + 2] are ≤ the slopes on ∪ n∈N [2n, 2n + 1].

The slopes on ∪ n∈N [2n, 2n + 1] are all ≥ h (0). Now choose any 0 < α ≤ h (0) (which is possible since h (0) > 0). The application x → σ x = h(x) -xh (x) is continuous on [0, 1] which is compact, thus it is uniformly continuous and ∃ > 0, ∀x, y

∈ [0, 1], |x -y| ≤ =⇒ |σ x -σ y | ≤ α.
The slope of fn or gn is always 0 or |σ φ(n+1) -σ φ(n) |, thus it is sufficient to choose φ such that ∀n ∈ N, |φ(n + 1) -φ(n)| ≤ . We must also have φ(N) dense within [0, 1] to ensure h = sup n∈N p φ(n) .

One way to fullfill both constraints on φ is to choose k such that 1 2 k ≤ , and

∀i, 0 ≤ i < 2 k , φ(i) = i 2 k ∀i, 0 ≤ i < 2 k+1 , φ(i + 2 k ) = 1 -i 2 k+1 ∀i, 0 ≤ i < 2 k+2 , φ(i + 2 k + 2 k+1 ) = i 2 k+2
. . .

It goes forth and back on [0, 1], refining the subdivision at each new pass. Now we analyze the terms of Equation 4. We directly give the output on [0, 1] of the deconvolution of the segments, by using Lemma 8 in [START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF]. Let n ∈ N, the next equalities apply on [0, 1].

•f n g n = p φ(n) fn gn σ φ(n) σ φ(n) INRIA • fn gn (t) = constant = σ φ(n) if σ φ(n) > σ φ(n+1) ≤ σ φ(n) + ρ φ(n) t ≤ f n g n (t). = σ φ(n+1) if σ φ(n) ≤ σ φ(n+1) ≤ σ φ(n+1) + ρ φ(n+1) t ≤ f n+1 g n+1 (t),
so fn gn disappears in f g.

σ φ(n) σ φ(n+1) fn gn fn σ φ(n) gn σ φ(n+1)
• fn g n (t) = (slope of fn ) × t + value at 0

= (slope of fn ) × t + σ φ(n) ≤ ρ φ(n) t + σ φ(n) ≤ f n g n (t).
•f n+1 gn (t) = (slope of gn ) × t + value at 0 = (slope of gn )

× t + σ φ(n+1) ≤ ρ φ(n+1) t + σ φ(n+1) ≤ f n+1 g n+1 (t),
so these terms disappear in f g. Finally, on [0, 1], we have f g = sup n∈N f n g n = sup n∈N p φ(n) = h.

The next figure illustrates the schematic shape of f and g, note that the two curves may cross each other but since the increment of σ φ(n) is always bounded by α, the distance between the two curves evolves in a regular way.

Remark 2.

If h is a rational function (quotient of polynoms) with coefficients in Q, then we can add that f, g ∈ F[N, Q].

These constructions remain valid if the interval is ]0, 1[ where h is C 1 and convex (e.g. t → 1/(1 -t)). In order to construct the sweeping function φ, go forth and back on a sequence of closed intervals [l n , r n ] s.t. l n (resp. r n ) is decreasing (resp. increasing) and tends to 0 (resp. 1), and where each interval [l n , r n ] leads to a step n (instead of ) of uniform continuity constraining the movement.

This result shows that, without ultimate pseudo-periodicity, one can not ensure that the deconvolution preserves piecewise affine shapes. For functions in F[R + , R], even with pseudo-periodicity, other pathological phenomena may occur when the ratio between the periods of the two input functions is irrational. The next proposition provides such an example in case (i) where the output may not remain piecewise affine (and thus gives a new example for the unstability of F[R + , R]). Moreover an example of loss of the plain property is given in case (iii).

Let S ⊆ R + (resp. N), we denote by 1 1 S the indicator function of S, i.e. ∀t ∈ R + (resp. N), 1 1 S (t) = 1 if t ∈ S and = 0 otherwise. With this definition, note that 1 1 S ∈ F[R + , R] if and only if S admits no finite accumulation point (a real which is the limit of a sequence of different values extracted from S). We also denote by dist(t, S) the distance of t from S, i.e. inf{|t -s|, s ∈ S}.

Let α, β ∈ R * + , we will use the notations

Nα = {s ∈ R | ∃n ∈ N, s = nα}, Zα = {s ∈ R | ∃n ∈ Z, s = nα} and Nα -Nβ = {s ∈ R | ∃p, q ∈ N, s = pα -qβ}. It is known that if α/β ∈ Q, then Nα -Nβ = Z(α ∧ β), and if α/β ∈ Q, then Nα -Nβ is dense within R. Proposition 7. Let α, β ∈ R * + (resp. α ∈ 2N, β ∈ N)
and f, g ∈ F (resp. D), then: (ii) Let t ∈ R + (resp. N), the deconvolution at t is (f g)(t) = sup s≥0 (dist(t + s, Nα) -dist(s, Nβ)) = sup s≥0 (dist(s, Nα -t) -dist(s, Nβ)). It is clear that (f g)(t) ≤ α 2 and by considering s ∈ Nβ, we also have (f g)(t) ≥ 0. Let us first show that the supremum in (f g)(t) can be taken for s ∈ Nβ instead of s ≥ 0 without changing its value. Let s ≥ 0, consider a ∈ Nα -t (resp. b ∈ Nβ) such that |s -a| = dist(s, Nα -t) (resp. |s -b| = dist(s, Nβ)). These three numbers s, a, b may have a few different relative positions:

(i) Let f = 1 1 Nα and g = 1 -1 1 Nβ , then f g = 1 1 Nα-Nβ . If β/α ∈ Q, then f g = 1 1 Z(α∧β)∩R+ . If β/α ∈ Q, then f g ∈ F[R + , R]. (ii) Let f (t) = dist(t, Nα) and g(t) = dist(t, Nβ). If β/α ∈ Q, then (f g)(t) = α 2 -dist(t, Z(α ∧ β) + α 2 ). If β/α ∈ Q, then (f g)(t) = α 2 . (iii) Let f (t) = t.dist(t, Nα) and g(t) = t.dist(t, Nβ). If β/α ∈ N, then (f g)(t) = t α 2 if t ∈ Nα and = +∞ if t ∈ Nα. If β/α ∈ N, then f g = +∞ over R + . Proof. (i) From the definitions, it is clear that ∀t ∈ R + (resp. N), (f g)(t) ∈ {-1, 0, +1}. In fact (f g)(t) = sup s≥0 (f (t + s) -g(s)) ≥ 0 by choosing s ∈ Nβ. Now (f g)(t) = sup s≥0 (f (t + s) -g(s)) = 1 if and only if ∃s ≥ 0, f (t + s) =
-Suppose that s ≤ a < b or b < a ≤ s, then dist(s, Nα -t) -dist(s, Nβ) = dist(s, a) -dist(s, b) < 0 whereas (f g)(t) ≥ 0,
Nα -t) -dist(s, Nβ) = dist(s, a) -dist(s, b) = dist(s , a) - dist(s , b) = dist(s , Nα -t) -dist(s , Nβ).
-Suppose that a ≤ s ≤ b. By definition of a, we have a

≤ s ≤ a + α 2 ≤ b. Either a ≤ s ≤ a + α 2 ≤ a + α < b and such s is not necessary in the supremum since dist(s, a) -dist(s, b) = dist(s, Nα -t) -dist(s, Nβ) ≤ 0, or a ≤ s ≤ a + α 2 ≤ b ≤ a + α.
Nα -t) -dist(s , Nβ) = dist(s , Nα - t) -dist(s , Nβ) ≥ dist(s, Nα -t) -dist(s, Nβ). INRIA -Suppose that b ≤ s ≤ a.
It is symmetric to the previous case but one should be careful about one detail. As above, we can restrict ourselves to the case a -α ≤ b ≤ a -α 2 ≤ s ≤ a. Moving s to s = a -α 2 increases dist(s, Nα -t) -dist(s, Nβ), we only have to check that s ≥ 0: it is true since b ∈ Nβ and thus 0 ≤ b ≤ a -α 2 . Then when moving s = a -α 2 to s = b, to do the same reasoning as the previous case, we have to check that the new potential closest point a -α actually belongs to Nα -t: it is true since a ∈ Nα -t, t ≥ 0 and 0 ≤ s ≤ a implies that a ∈ N * -t.

We have shown that (f g)

(t) = sup s≥0 (dist(s, Nα -t) -dist(s, Nβ)) = sup s∈Nβ (dist(s, Nα -t) - dist(s, Nβ)). Thus (f g)(t) = sup s∈Nβ dist(s, Nα -t) = α 2 -inf s∈Nβ dist(s, Nα + α 2 -t) = α 2 -dist(Nβ, Nα + α 2 -t) = α 2 -dist(Nα -Nβ, t - α 2 ) If β/α ∈ Q, we have Nα -Nβ = Z(α ∧ β) and (f g)(t) = α 2 -dist(t, Z(α ∧ β) + α 2 ). If β/α ∈ Q, the set Nα -Nβ is dense within R, thus there exists a sequence a n α -b n β, a n , b n ∈ N, which tends to t -α 2 . It means that dist(Nα -Nβ, t -α 2 ) = 0 and (f g)(t) = α 2 . (iii) Let t ∈ R + , we have (f g)(t) = sup s≥0 ((t + s).dist(t + s, Nα) -s.dist(s, Nβ)) = t. sup s≥0 dist(t + s, Nα) + sup s≥0 (s.dist(t + s, Nα) -s.dist(s, Nβ)) = t α 2 + sup s≥0 (s.dist(t + s, Nα) -s.dist(s, Nβ))
Analyzing the second term leads to several cases:

-Suppose that β/α ∈ Q. The second term is larger than sup s≥Nβ (s.dist(t + s, Nα) -s.dist(s, Nβ)) = sup s∈Nβ s.dist(s, Nα -t). Since Nβ -Nα is dense within R, we know that there exists a sequence b n β -a n α, a n , b n ∈ N, which tends to α 2 -t without ever reaching this value. It implies that the set {b n , n ∈ N} is infinite and we can extract a subsequence b φ(n) which is increasing. We have sup s∈Nβ s.dist(s,

Nα -t) ≥ sup n∈N b φ(b) β.dist(b φ(b) β, Nα -t) = +∞ since b φ(n) → +∞ and dist(b φ(b) β, Nα -t) = dist(b φ(b) β -a φ(n) α, Nα -t) → dist( α 2 -t, Nα -t) = α 2 . Thus (f g)(t) = +∞. -If β/α ∈ Q, we know from case (ii) that h(t) = sup s≥0 (dist(t + s, Nα) -dist(s, Nβ)) = α 2 - dist(t, Z(α ∧ β) + α
2 ). This supremum h(t) is equal to 0 if and only if α∧β 2 = α 2 and t ∈ Z(α ∧ β), i.e. β/α ∈ N and t ∈ Nα (since t ≥ 0). In this case, we have sup s≥0 (s.dist(t + s, Nα) -s.dist(s, Nβ)) = sup s≥0 s.(dist(s, Nα)-dist(s, Nβ)) = 0 and finally (f g)(t) = t α 2 . Otherwise h(t) is strictly positive, and there exists some s 0 ≥ 0 s.t. dist(t + s 0 , Nα) -dist(s 0 , Nβ) = c > 0. In this latter case, consider the sequence s n = s 0 + n(α ∨ β), n ∈ N. We have dist(t + s n , Nα) -dist(s n , Nβ) = c for all n ∈ N. Thus sup n∈N (s n .dist(t + s n , Nα) -s n .dist(s n , Nβ)) = +∞ and finally (f g)(t) = +∞. Remark 3. Note that the example g(t) = t.dist(t, 2N) giving (g g)(t) = t if t is even and = +∞ otherwise, was already considered in Remark ??? in [START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF] where it was proved for f ∈ D, f (t) = t is t is odd and = 0 otherwise, and stated for [f ] R = g without proof. [START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF]. The arrows between boxes indicate where the output function lands when applying the operations which label each arrow. If an arrow ends out of its starting point, it means that there exists some input functions whose output does not belong any longer to the initial class. In [START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF], examples illustrating some of those "unstability" arrows are given. This subsection completes this study by presenting the missing examples in order to illustrate the whole picture.

Illustrations for the stability big picture

F[R+, R] F[Q+, R] F[Q+, Q] F[R+, R] F[Q+, R] F[Q+, Q] N → R N → R
. , n k ∈ N * , s = n 1 s 1 + • • • + n k s k }. Note that NS = N * S ∪ {0}.
We denote by 1 1 S the indicator function of S i.e. ∀t ∈ R + (resp. N), 1 1 S (t) = 1 if t ∈ S and = 0 otherwise. We also recall that the function dist(t, S) = inf{|t -s|, s ∈ S} gives the distance between t and the set S. (ii) Let f (t) = dist(t, Nα) and g(t) = dist(t, Nβ), then (f * g)(t) = dist(t, Nα + Nβ).

In both cases, if f, g ∈ F and β/α ∈ Q, then f * g is not ultimately pseudo-periodic.

Proof.

(i) It is a clear consequence of the definition of * .

(ii) Let t 1 , t 2 ∈ R + s.t. t 1 + t 2 = t, then ∃s 1 ∈ Nα (resp. s 2 ∈ Nβ) s.t. f (t 1 ) = dist(t 1 , Nα) = |t 1 -s 1 | (resp. g(t 2 ) = dist(t 2 , Nβ) = |t 2 -s 2 |). We have f (t 1 )+g(t 2 ) = |t 1 -s 1 |+|t 2 -s 2 | ≥ |t-(s 1 +s 2 )| ≥ dist(t,
| = |t 2 | < |t 2 -s 2 | = dist(t, Nα+Nβ) which is impossible. Thus (f * g)(t) ≤ f (t 1 ) + g(t 2 ) = 0 + dist(t -s 1 , Nα + Nβ) = dist(t, Nα + Nβ) since t -s 1 ≥ 0. It ends the proof that (f * g)(t) = dist(t, Nα + Nβ).
The lack of ultimate pseudo-periodicity when β/α ∈ Q is due to the fact that in this case Nβ -Nα is dense within R.

Lemma 4. Let S ⊆ R + (resp. N) and f ∈ F (resp. D), then: (ii) If f (t) = dist(t, S), then f * (t) = dist(t, N * S) for all t > 0 (and f * (0) = 0).

(i) If f (t) = 1 1 S (t), then f * (t) = 1 1 NS (t
Proof. In both cases, we use Equation 1 defining the subadditive closure, where w.l.o.g. we allow that t i ≥ 0 (instead of the overall equivalent t i > 0). For statement (i), it is clear that f * (t) = 0 if and only if t ∈ NS, and otherwise

1 ≤ f * (t) ≥ f (t) = 1. For statement (ii), let ∈ R * + , let t 1 , . . . , t k > 0 s.t. t = t 1 + • • • + t k , then ∀1 ≤ i ≤ k, ∃s i ∈ S s.t. |t i -s i | -k ≤ f (t i ) = dist(t i , S) ≤ |t i -s i | (if S has no accumulation point outside S, we have in fact the equality dist(t i , S) = |t i -s i |). Then f (t 1 ) + • • • + f (t k ) ≥ 1≤i≤k |t i -s i | -k ≥ |t -(s 1 + • • • + s k )| -≥ dist(t, NS) -. It is true for all > 0, thus it implies f * (t) ≥ dist(t, NS). Now let > 0, t > 0 and consider the smallest integer k ≥ 1 s.t. ∃s 1 , . . . , s k ∈ S, dist(t, NS) ≤ |t-(s 1 +• • •+s k )| ≤ dist(t, NS)+ (if the
infimum is achieved for some element of NS, let = 0 and manipulate an equality, it occurs for instance in the discrete model or if S is finite). Choose

t 1 = s 1 , ..., t k-1 = s k-1 , t k = t -(s 1 + • • • + s k-1 ), then t 1 + • • • + t k-1 + t k = t and t k ≥ 0, since either k = 1 and t k = t ≥ 0, or k ≥ 2 and t k ≥ 0 because t k < 0 would imply that |t k | ≤ |t k -s k | which contradicts the minimality of k. Then ∀1 ≤ i ≤ k -1, f (t i ) = 0 and f (t k ) = dist(t k , S) ≤ dist(t k , s k ) = |t k -s k | = |t-(s 1 +• • •+s k )|. Thus f * (t) ≤ f (t 1 )+• • •+f (t k ) ≤ dist(t, NS)+ ,
and it is true for all > 0. It ends the proof that f * (t) = dist(t, NS).

Note that, in case f (t) = dist(t, S), it is possible to "lift" this function into a non-decreasing function by considering f (t) + t for which the subadditive closure is f * (t) + t (the non-decrease also works for f (t) = 1 1 S (t) but only in the discrete model). To get a continuous subadditive closure, ensure that 0 ∈ S and then f * (t) = dist(t, NS) for all t ≥ 0.

Table 1 provides some examples which complete the justification of Figure 2.4. Each case is designated by a letter which labels the corresponding operation and arrow on Figure 2.4.

Computational complexity of compressed outputs

Proposition 8. Let f an ultimately pseudo-periodic function in F[Q + , Q], computing the smallest rank from which f * is pseudo-periodic is NP-hard. This remains true even if f is continuous, non-decreasing and ultimately affine.

Proof. As in the proof for the discrete case (see [START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF]), we build a reduction from the Frobenius problem. Let a 1 , . . . , a n be integers such that gcd(a 1 , . . . , a n ) = 1. The Frobenius problem consists in computing F rob(a 1 , . . . , a n ) = min{t 0 ∈ N | ∀t ≥ t 0 , t ∈ Na 1 + • • • + Na n }. It is known to be NP-hard [START_REF] Ramirez-Alfonsin | Complexity of the Frobenius problem[END_REF].

A first idea is to follow the proof of the discrete case, i.e. choose f = 1 1 N\(Na1+•••+Nan) , and add a step in the reduction by considering [f ] R ∈ F[N, N]. Although it is not true for this particular function that [f ] * R = [f * ] R , one can prove that the smallest rank from which [f ] R is ultimately pseudo-periodic is either F rob(a 1 , . . . , a n ) (if ∃i, j, |a i -a j | = 1) or F rob(a 1 , . . . , a n ) -1/2 (otherwise). This is due to the shape of the interpolation. It shows that the initial Frobenius problem can be easily deduced from the computation of the smallest rank of pseudo-periodicity, which is thus NP-hard.

However to avoid a case study, another proof consists in choosing another function having its zeros at {0, a 1 , . . . , a n }. For all t ∈ R + , consider the function f (t) = dist(t, {0, a 1 , . . . , a n }) = min{|t -a| , a ∈ {0, a 1 , . . . , a n }}. This function measures the distance of t from the set {0, a 1 , . . . , a n }, it is continuous and ultimately affine from max(a 1 , . . . , a n ). A careful application of Equation 1 gives f * (t) = dist(t, Na 1 +• • •+Na n ) (see Lemma 4). This function is ultimately pseudo-periodic of period 1 and its smallest rank of pseudoperiodicity is exactly F rob(a 1 , . . . , a n ) -1/2. Consequently its computation is NP-hard.

To add a non-decrease hypothesis, "lift" the function f (t) by considering f (t)+t. Since the slopes in f are +1 or -1, f (t) + t is non-decreasing. Moreover (f (t) + t) * = f * (t) + t, and the smallest rank of pseudo-periodicity is exactly the same as the one for f .

Figure 1 :

 1 Figure 1: Classes of functions : (a) affine function; (b) ultimately affine function; (c) pseudo-periodic function; (d) ultimately pseudo-periodic function.

Figure 2 :

 2 Figure 2: Growth rates satisfy r 1 > R > r 2 > 0.

  1 and g(s) = 0, i.e. t + s ∈ Nα and s ∈ Nβ. This can occur if and only if t ∈ Nα -Nβ. Thus f g = 1 1 (Nα-Nβ)∩R+ . The end of the statement is the consequence of the form of Nα -Nβ depending on whether α/β ∈ Q or not. Note however that in both cases and as expected f g has a period α like f .

-

  thus such s is not necessary in the supremum. Suppose that s ≤ b ≤ a or a ≤ b ≤ s, then moving s towards b does not change the value dist(s, a)dist(s, b) and a and b remain its closest points in respectively Nα -t and Nβ. In other terms, by choosing s = b ∈ Nβ, we have dist(s,

  In this later case, when moving s towards a+ α 2 , dist(s, a)-dist(s, b) increases and a et b remain the closest point in Nα-t and Nβ. Thus with s = a+ α 2 , we have dist(s, Nα-t)-dist(s, Nβ) = dist(s, a)-dist(s, b) ≤ dist(s , a)-dist(s , b) = dist(s , Nα-t)-dist(s , Nβ). Then when moving s towards b, the closest points in respectively Nα-t and Nβ become a + α and b, and the value dist(s , Nα -t) -dist(s , Nβ) = dist(s , a + α) -dist(s , b) does not change. Thus with s = b ∈ Nβ, we have dist(s ,

Figure 2 .

 2 Figure 2.4 sums up the main stability results presented in[START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF]. The arrows between boxes indicate where the output function lands when applying the operations which label each arrow. If an arrow ends out of its starting point, it means that there exists some input functions whose output does not belong any longer to the initial class. In[START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF], examples illustrating some of those "unstability" arrows are given. This subsection completes this study by presenting the missing examples in order to illustrate the whole picture.

  sub. clos.(B) * (C), (D) * (C), (D) sub. clos.(E) sub. clos.(E) ps.-period. plain ult. ps.-period. plain ult. ps.-period. plain ult. ps.-period. plain ult. affine plain ult. affine plain ult. affine plain ult. affine plain F[R+, R] * , min, max, * (G) The next lemmas provide some interesting examples of convolution and subadditive closure outputs. Let S ⊆ R + (resp. N), we will denote by S = R + \S (resp. N\S) the complementary of S and by NS = {s | ∃k ∈ N * , ∃s 1 , . . . , s k ∈ S, ∃n 1 , . . . , n k ∈ N, s = n 1 s 1 + • • • + n k s k } the finite sums of elements of S. In the same way, N * S = {s | ∃k ∈ N * , ∃s 1 , . . . , s k ∈ S, ∃n 1 , . .

Lemma 3 .

 3 Let α, β ∈ R * + (resp. N * ) and f, g ∈ F (resp. D), then: (i) Let f = 1 1 Nα and g = 1 1 Nβ , then f * g = 1 1 Nα+Nβ .

  Nα+Nβ), and thus (f * g)(t) ≥ dist(t, Nα + Nβ). On the other hand, let t ≥ 0, thenexistss 1 ∈ Nα, s 2 ∈ Nβ s.t. dist(t, Nα + Nβ) = |t -(s 1 + s 2 )|. If s 1 = s 2 = 0, then (f * g)(t) ≤ dist(t, Nα + Nβ) since it is clear that (f * g)(t) ≤ |t|for all t. Otherwise s 1 > 0 or s 2 > 0. Suppose that s 2 > 0. Choose t 1 = s 1 and t 2 = t -s 1 , we have t 1 +t 2 = t and t 2 ≥ 0, since if t 2 < 0, it would mean that |t-s 1

Table 1 :

 1 ). (t) = dist(t, {a, b}) or f (t) = 1 1 {a,b} (t) with a/b ∈ Q + (and apply Lemma 4) (C) consider Figure2with appropriate r 1 , r 2 , R ∈ R (D) use the construction of Proposition 5 which enables to output some non-decreasing continuous convex function inF[R + , R] but not in F[Q + , R], with inputs in F[N, R]Examples/counterexamples for the stability picture.

	INRIA

RR n 6095


Emmanuel Chambon

Laurent Burlion

Pierre Apkarian

Output to Input Saturation Transformation: Demonstration and Application to Disturbed Linear Systems

In the case of linear systems, control law design is often performed so that the resulting closed-loop meets specific frequency requirements. However, in many cases, it may be observed that the obtained controller does not enforce timedomain requirements amongst which the objective of keeping an output variable in a given interval. In this article, a transformation is proposed to convert expected bounds on an output variable into time-varying saturations on the synthesized linear control law. It is demonstrated that the resulting closedloop is stable and satisfies time-domain constraints in the presence of unknown bounded disturbance. An application to a linear ball and beam model is presented.

I. INTRODUCTION

To stabilise a given system, many techniques exist to obtain a control law satisfying to specified constraints. As far as MIMO systems are concerned, nonsmooth optimization techniques can for example be used to enforce frequencydomain requirements.

However it is possible that, using this control law, timedomain requirements on a so-called regulated variable α = C α x ∈ R are not enforced. This is illustrated on Fig. 1 where α time-response violates expected bounds [α(t), α(t)].

The output-to input-saturation transformation (OIST) theory was first detailed in [START_REF] Burlion | A new Saturation function to convert an output constraint into an input constraint[END_REF], [START_REF] Burlion | Keeping a Ground Point in the Camera Field of View of a Landing UAV[END_REF] and proposes to find a remedy to this by reformulating 'saturations' (or expected bounds) on the regulated variable α into saturations on the controller output u. Other strategies include [START_REF] Turner | Output violation compensation for systems with output constraints[END_REF], [START_REF] Rojas | A simple anti-windup strategy for state constrained linear control[END_REF] which use anti-windup loops to constrain the state or outputs in the time-domain. OIST is illustrated on the bottom of Fig. 1 where an ad hoc saturating block is inserted before the *Emmanuel Chambon, Laurent Burlion and Pierre Apkarian are with Systems Control and Flight Dynamics Department, Onera -Centre de Toulouse, FR-31000 Toulouse, France, emmanuel.chambon@onera.fr system control input. As illustrated on this figure, additional information may be required to express these saturations which will be demonstrated in the following.

In this paper, it is proposed to extend and demonstrate the theoretical background of the OIST approach in the case of known linear systems with unknown disturbance input and unknown error measurements. The transformation is detailed and a proof of stability making use of existing results on the stability of a class of saturated open-loop stable nonlinear systems [START_REF] Menon | General Anti-windup synthesis for input constrained nonlinear systems controlled using nonlinear dynamic inversion[END_REF], [START_REF] Herrmann | Anti-windup synthesis for nonlinear dynamic inversion control schemes[END_REF] is provided. The main addition to the OIST theory proposed in this paper is to formalize timevarying gains to avoid input saturation crossings.

The article is organised as follows: the OIST problem is formalized in Sect. II. Then, the output to input saturation transformation used to solve this problem is presented in Sect. III. Stability of the system in closed-loop with the obtained saturated control is guaranteed and proved in Sect. IV. Finally, the whole approach is applied to a linear ball and beam model in Sect. V and conclusions are drawn in Sect. VI.

II. THE OIST PROBLEM A. Definitions and Notations

If not stated otherwise, the state-space representation of a linear system (G) is denoted G = (A, B, C, D). The state is then denoted x ∈ R n , the measurements vector is denoted y ∈ R m with m ≤ n and the notation u denotes control inputs while d denotes unknown inputs and/or disturbances. Inequalities involving matrices of identical dimensions are understood component-wise. For a given bounded variable x(t), the bounds are denoted (x, x), i.e. ∀t, x(t) ≤ x(t) ≤ x(t). The saturation and deadzone functions are respectively denoted sat x x (x) and Dz(x) and are related to each other by sat

x x (x) = x -Dz(x). Definition 1: Let ∀x ∈ R, F (x) = xe x . The inverse function of F is the Lambert function denoted W 0 (y) which satisfies ∀y ∈ R, F (W 0 (y)) = W 0 (y)e W0(y) = y. Definition 2: Let define the constants ξ := 1 2 W 0 1 e + 1 2
and Ξ := ξtanh(ξ)ξ > 0. Using these notations, also define the following functions, ∀ (x, y) ∈ R 2 :

f abs (x) := tanh(x)x + Ξ f max (x, y) := 1 2 [x + y + tanh(x -y)(x -y) + Ξ] g(x, y) := f max (f abs (x), f abs (y)) (1
) Remark 1: Note ξ is the solution to the equation (2x -1) e 2x = 1. Also note that f abs , f max and g are continuous differentiable over R or R 2 . Moreover,

• ∀x ∈ R, f abs (x) ≥ |x|; • ∀(x, y) ∈ R 2 , f max (x, y) ≥ max(x, y).
Proof: straightforward using function analysis basics. Definition 3: Let k ∈ N. Considering a linear system (G), the regulated variable α = C α x is said to be of relative degree k with respect to u if and only if

∀i < k -1, C α A i B = 0 and C α A k-1 B = 0 (2) Definition 4: Let S = s 0 . . . s k ∈ R k+1 . The function σ(S) = σ(s 0 ) . . . σ(s k ) (3)
where

σ(s i ) := s i-1 if 1 ≤ i ≤ k s k if i = 0 (4)
is called the cyclic permutation of length k + 1 on the elements of S.

B. Problem formulation

Let consider a linear system (G) with the following statespace representation:

(G) ẋ = Ax + B u u + B d d y = x ( 5
)
where u is the control input and d an unknown disturbance.

It is supposed a stabilizing control law u = K(s)y has been designed for this system. The corresponding OIST problem is formalized into:

Problem 1: Find [u(t), u(t)] and C 0 such that α(t) ∈ [α(t), α(t)]
, ∀t for the system described as

           ẋ = Ax + B u u + B d d y = x α = C α x + E α e u ∈ [u(t), u(t)] x 0 ∈ C 0 (6) where x ∈ R n , y ∈ R m , u ∈ R, d ∈ R is an unknown bounded disturbance and e ∈ R n is an unknown bounded signal with E α ∈ R 1×n .

C. Hypotheses

All the hypotheses satisfied by the systems considered in this article are presented here. Notations are those of Pb. 1.

Hypothesis 1:

Let (k, l) ∈ N 2 such that 1 ≤ l ≤ k. It is supposed the regulated variable α is of relative degree k (resp. l) wrt. u (resp. d). Let D(t) = d ḋ . . . d (k-l-1) ∈ R k-l and E(t) = e ė . . . e (k) ∈ R (k+1)×n .
Hypothesis 2: Time-varying bounds D(t), D(t) on the unknown disturbance and its derivatives D(t) are supposed to be known, that is ∀t, D(t) ≤ D(t) ≤ D(t) [START_REF] Kapoor | An Anti-Windup Design for Linear Systems with Input Saturation[END_REF] or, more precisely ∀t, ∀i s.t.

0 ≤ i ≤ k -l -1, d (i) (t) ≤ d (i) (t) ≤ d (i) (t) (8)
Moreover, d is supposed to be of finite energy d 2 . The same holds for E(t) with time-varying bounds E(t), E(t) and finite energy e 2 .

Hypothesis 3: The transfer function T u→α (s) from input u to regulated variable α only has strictly stable zeros.

Hypothesis 4: Using notations in Hyp. 1, the following is satisfied: 2l > k.

III. OIST TRANSFORMATION

The output-to input-saturation transformation is presented in this section in the case of known linear systems satisfying to Hyp. 1 to 4. In presence of unknown disturbances d and e, the main idea is to use time-varying coefficients in the obtained saturations so as to avoid crossings.

A. From the regulated variable to the input Under Hyp. 1 and 4, the k-th derivative of the regulated variable α in function of u, d and e (k) has the following expression

α (k) = CαA k x + Eαe (k) + CαA k-1 Buu + k j=l CαA j-1 B d d (k-j) (9)
The derivative of order k is the first derivative of α to depend on u. By derivating k times the variable α and expected bounds [α(t), α(t)], one can thus express saturations on u.

B. Keeping a variable in an interval

Let κ(t) = κ 1 (t) . . . κ k (t) ∈ R k
+ a vector of known positive time-varying signals, α (0) = α and α (0) = α. Also consider known vectors A(t) = α . . . α (k) and Ω(t) = α (0) . . . α (k)1 . Lemma 1: Let A(0) ∈ Ω(0), Ω(0) and ∀j, 1 ≤ j ≤ k, ∀t:

α (j) (t) = κj(t) α (j-1) -α (j-1) + ˙ α (j-1) α (j) (t) = κj(t) α (j-1) -α (j-1) + ˙ α (j-1) (10)
Then,

α (k) ∈ α (k) (t), α (k) (t) , ∀t ⇒ α ∈ [α(t), α(t)] , ∀t (11)
Proof: straightforward using proof by contradiction.

C. Control saturations

Under Hyp. 1, it is ensured C α A k-1 B u = 0. Let also suppose that C α A k-1 B u > 0.
In case this is not satisfied, this means the definition of u and u were exchanged. Without changing these definitions, the saturated value of the command u is then obtained using

sat(u) = max (min (u, u) , min (u, max (u, u))) (12)
Proof:

• Suppose u > u. Then, min(u, u) = u and max(u, u) = u. Eq. ( 12) becomes sat(u) = max (u, min (u, u)).

• Suppose u < u. Then, min(u, u) = u and max(u, u) = u. Eq. ( 12) becomes sat(u) = max (u, min (u, u)).

In both cases, the expected result is obtained.

Considering Lemma 1 and Eq. ( 9), and supposing the expression of α (k) (t) is known, the lower bound from Eq. (13) on Fig. 2 is obtained (to obtain the upper bound, a similar approach is used). With a slight abuse of notation, the (more conservative) second expression will be used.

Remark 2: For this definition to be consistent and to avoid control saturations crossings, one must ensure that

α (k) (t) -α (k) (t) ≥ 2|Eα| max |e (k) |, |e (k) | + 2 k j=l |CαA j-1 B d | max(|d (k-j) |, |d (k-j) |) (14)
D. Determining α (j) and α (j) expressions

The expressions of the bounds on the successive derivatives of the regulated variable α can be determined using the iterative definition in Eq. [START_REF] Hu | Geometric Control Theory[END_REF]. For the sake of space, only the lower bounds are considered. Determining the upper bounds is then straightforward. For any integer j such that 1 ≤ j ≤ k, let consider the two following vectors:

• U j (t) = u j 0 (t) . . . u j k (t) where u j j (t) = 1 and ∀i > j, u j i (t) = 0; • V j (t) = v j 0 (t) . . . v j k-l-1 (t) where: ∀i > max(-1, j -l -1), v j i (t) = 0 and v l+1 0 (t) = u l+1 l (t)C α A l-1 B d , Let A = α ˙ α . . . (α) (k)
and Θ =

C α C α A . . . C α A k .
Using these definitions and supposing E(t) and D(t) are known, one can express the lower bound α (j) (t) to be satisfied by α (j) (t) as:

α (j) (t) = U j (t) A -Θx -E(t)E α + CαA j x + Eαe (j) -V j (t)D(t) ∈ R (15)
Then, using Eq. ( 10), the formulas in Eq. ( 16) on Fig. 3 are obtained where σ U j-1 (t) is the cyclic permutation of length k + 1 on the elements of U j-1 (t).

Proof: tedious rewriting of Eq. ( 15) in explicit form and using Eq. ( 10) to express α (j+1) for j ≥ 0 starting with α (0) (t) = α(t) leads to Eq. ( 16).

Remark 3: Using the previous iterative expressions and the fact that

u 1 0 (t) = κ 1 (t), one can easily determine that ∀j, 0 ≤ j ≤ k, u j+1 j (t) = j+1 w=1 κ w (t).
In case E(t) and D(t) are not known and using notations in Def. 2, the differentiable (yet more conservative) expression in Eq. (17) on Fig. 4 is obtained. With a slight abuse of notation, it is chosen as the new definition of α (j) (t).

E. Avoiding crossings

Let define ∀j, 1 ≤ j ≤ k, Ω j (t) := α (j) (t) -α (j) (t). Crossings of the saturations imposed to u (and the successive derivatives of α) are avoided if some properties are satisfied by those terms. In the following, it is proposed to identify these properties from which Th. 1 is obtained.

1) In case ∀j s.t. 1 ≤ j < l: the following lemma is considered Lemma 2: Supposing ∀t, κ j (t) > 0, ∀j, 1 ≤ j < l, 1) , e (j-1) + Ωj-1(t)

Ωj(t) = κj(t) Ωj-1(t) -2 |Eα| g e (j-
Proof: by definition,

Ωj(t) = α (j) (t) -α (j) (t) = κj(t) α (j-1) (t) -α (j-1) (t) + ˙ α (j-1) (t) -κj(t) α (j-1) (t) -α (j-1) (t) - ˙ α (j-1) (t) (19)
where 1) . Since e and its derivatives are not known, it is not possible to simplify α (j-1) (t) in the expression of Ω j (t). However, under Hyp. 2 and supposing κ j (t) > 0, the conservative expression in Eq. ( 18) is obtained.

α (j-1) = C α A j-1 x + E α e (j-
2) In case ∀j s.t. l ≤ j ≤ k: in the same vein Lemma 3: Supposing ∀t, κ j (t) > 0, ∀j, l ≤ j ≤ k, 1) , e (j-1)

Ωj(t) = κj(t) Ωj-1(t) -2 |Eα| g e (j-
-2 j-1 w=l CαA w-1 B d g d (j-w-1) , d (j-w-1) + Ωj-1(t) (20)
Proof: Similar to previous proof where j ≥ l implies a different expression for α (j-1) (t).

3) Theorem: the following theorem is proposed Theorem 1: Saturations crossings are avoided if • α(t) and α(t) are chosen such that ∀t, Ω0(t) = α(t) -α(t) > 2|Eα|g (e(t), e(t))

• ∀j, 1 ≤ j < l, one ensures

Ωj(t) > 2|Eα|g e (j) (t), e (j) (t) (22)
by choosing κj(t) := κj -Ωj-1(t) + 2|Eα|g e (j) (t), e (j) (t) Ωj-1(t) -2|Eα|g e (j-1) (t), e (j-1) (t)

where the constant κj satisfies

∀t, κj > Ωj-1(t) -2|Eα|g e (j) (t), e (j) (t) (24)
Note that the denominator in Eq. ( 23) is strictly positive by definition of κ j-1 (t) and of Ω 0 (t) in case j = 1.

• ∀j, l ≤ j ≤ k, one ensures Ωj(t) > 2|Eα|g e (j) (t), e (j) (t) + 2 j w=l CαA w-1 B d g d (j-w) (t), d (j-w) (t) (25)
by choosing κ j (t) as in Eq. (26) on Fig. 5 where the constant κj satisfies ∀t, κj > Ωj-1(t) -2|Eα|g e (j) (t), e (j) (t)

-2 j w=l CαA w-1 B d g d (j-w) (t), d (j-w) (t) (27)
u(t) = 1 CαA k-1 Bu α (k) (t) -CαA k x + |Eα| max |e (k) |, |e (k) | + k j=l CαA j-1 B d d (k-j) ≤ 1 CαA k-1 Bu α (k) (t) -CαA k x + |Eα| max |e (k) |, |e (k) | + k j=l CαA j-1 B d max |d (k-j) |, |d (k-j) | (13)
Fig. 2. Lower control saturation expression

U 0 (t) = 1 0 . . . 0 ∀j s.t. 1 ≤ j ≤ k, U j (t) = κ j (t)U j-1 (t) + U j-1 (t) + σ U j-1 (t) ∀j s.t. 0 ≤ j ≤ l, V j (t) = 0 ∀j s.t. l < j ≤ k -l, V j (t) = κ j (t) V j-1 (t) + CαA j-l-1 A l-1 B d . . . A 2l-k B d + V j-1 (t) +σ V j-1 (t) + j-l-1 w=0 u j-1 l-1+w (t)CαA l-1+w B d 0 . . . 0 (16)
α (j) (t) = κ j (t) U j-1 (t) {A -Θx} + f abs U j-1 (t) g E(t), E(t) E α +f abs V j-1 (t) + CαA j-l-1 A l-1 B d . . . A 2l-k B d g D(t), D(t) + CαA j x + |Eα|g e (j)
, e (j)

+ U j-1 (t) + σ U j-1 (t) {A -Θx} + f abs U j-1 (t) + σ U j-1 (t) g E(t), E(t) E α + f abs V j-1 (t) + σ V j-1 (t) + j-l-1 w=0 u j-1 l-1+w (t)CαA l-1+w B d 0 . . . 0 g D(t), D(t) (17)
Fig. 4. Explicit expression for α (j) where coefficient κ j (t) is factorized. Note this is differentiable with respect to t

κ j (t) := κj -Ωj-1 (t) + 2|Eα|g e (j) (t), e (j) (t) + 2 j w=l CαA w-1 B d g d (j-w) (t), d (j-w) (t) Ω j-1 (t) -2 |Eα| g e (j-1) , e (j-1) -2 j-1 w=l |CαA w-1 B d | g d (j-w-1) , d (j-w-1) (26)
Fig. 5. Expression of κ j (t) for l ≤ j ≤ k

Note that the denominator in Eq. ( 26) is strictly positive by definition of the previous coefficient κ j-1 (t). Proof: straightforward using the results from Sect. III-E.1 and III-E.2.

IV. CLOSED-LOOP STABILITY

In this section, the stability of the system in closed-loop with the dynamic controller u = K(s)y = K(s)x and the proposed time-varying saturations (u, u) is proved.

A. Considered system

Replacing α (k) (t) in Eq. (13) (Fig. 2) by its expression in Eq. ( 15) and factorizing by the state vector x, the following can be defined

K oist (t) = U k (t)Θ C α A k-1 B u ∈ R 1×n (28) Let v = u + K oist (t)x and v = u + K oist (t)x.
By definition of these bounds, see Eq. ( 13), the following is straightforward

sat u u (u) = sat v v (v) -K oist (t)x (29)
In closed-loop with the dynamic controller K(s) and the saturations, the studied system is equivalent to

   ẋ = [A -B u K oist (t)] x + B u sat v v (v) + B d d y = x α = C α x + E α e (30) where v = u + K oist (t)x = C K x K + D K y + K oist (t)x.
The interest of such a reformulation is to obtain a system where the saturations (v, v) do not depend on the state x. The following Lemma is considered Lemma 4: ∀x ∈ R n , the function -K oist (t)x is Lipschitz.

Proof: Let define ∀x ∈ R n , f (x) = -K oist (t)x. Then ∀x ∈ R n , ∂f ∂x (x) = -K oist (t). Since K oist (t)
is continuous by definition of the coefficients κ(t) and continuity of E, E, D, D , the function f is continuously differentiable. This implies that K oist (t)x is a Lipschitz continuous function on R n .

B. Anti-windup design and stability proof

Due to the presence of a dynamic controller and saturations, unexpected closed-loop behaviour is expected. Antiwindup techniques have been widely studied and used to hinder such behaviour as in [START_REF] Kapoor | An Anti-Windup Design for Linear Systems with Input Saturation[END_REF], [START_REF] Grimm | Antiwindup for Stable Linear Systems with Input Saturation: An LMI-Based Synthesis[END_REF], [START_REF] Tarbouriech | Anti-windup design: an overview of some recent advances and open problems[END_REF]. The approach presented in [START_REF] Menon | General Anti-windup synthesis for input constrained nonlinear systems controlled using nonlinear dynamic inversion[END_REF], [START_REF] Herrmann | Anti-windup synthesis for nonlinear dynamic inversion control schemes[END_REF] deals with a specific class of nonlinear systems to which the system presented in Eq. ( 30) belongs. The results used from this work are presented and demonstrated here.

Considering system (30), the following anti-windup with state x a ∈ R n is introduced

   ẋa = [A -B u K oist (t)] x a -B u Dz(v) θ 1 = -K oist (t)x a θ 2 = x a (31) The control v is modified into v = K(s) (y -θ 2 ) + K oist (t)x + θ 1 (32)
Let consider the following theorem which will be necessary to prove Th. 3.

Theorem 2:

The open-loop system

ẋ = [A -B u K oist (t)] x (33)
is globally exponentially stable.

Proof: due to space restrictions, only a sketch of the proof is given here. Considering Eq. ( 29) and (30), this problem is equivalent to studying the stability of system ẋ = Ax + B u u. The transfer function between u and the regulated variable α can be written in the following statespace form:

˙ Γ Z = A Γ 0 A ZΓ A Z Γ Z (34)
where A Γ describes a chain of integrators [10, Chapter 4] and A Z describes the zero-dynamics. Considering Hyp. 3, A Z eigenvalues are strictly negative. As far as the dynamics of Eq. ( 34) is concerned, the following candidate Lyapunov positive definite function is considered

V (Γ, Z) = 1 2 Γ Γ + 2 Z Z (35)
where is a positive constant. Choosing wisely and using the common analysis, this candidate function validates as a Lyapunov function. Even more, global exponential stability of ẋ = [A -B u K oist ] x can be shown.

Before any further development, let consider the following hypothesis which ensures that the origin of the system is reachable with u = v = 0.

Hypothesis 5: 0 ∈ [v(t), v(t)] , ∀t Since v and v only depend on known model and design parameters, this hypothesis can be checked prior to any simulation. The core of this article lies in the following theorem which proves stability of the system in closed-loop with the saturated initial controller. Both this theorem and its proof are fully inspired from [START_REF] Menon | General Anti-windup synthesis for input constrained nonlinear systems controlled using nonlinear dynamic inversion[END_REF].

Theorem 3: Under Hyp. 1 to 5, the origin of the closedloop system consisting of the system (30), the control law (32) and the anti-windup compensator (31) is globally asymptotically stable.

Proof: the details of the proof of [5, Theorem 1, p. 5436] are applied to our case. Using Th. 2, the Eq. [5, (22) to (27), p. 5437] are valid hence the conclusion of the proof. Note that in our case, the deadzone function Dz(v) depends on time-varying bounds (v, v). However, the inequality Dz(v) ≤ v still stands from Hyp. 5.

V. EXAMPLE

To illustrate the theoretical results presented in this article, the OIST approach is applied to the dynamic control of a ball and beam linear model. The objective is to maintain the ball on the beam even in presence of unknown disturbances.

A. Model description

The system is considered linear in the case of small beam inclinations. The beam is actuated using a lever arm. The position of the ball is denoted r and the actuation wheel angle is denoted θ. An unknown disturbance force d is eventually applied to the ball acceleration and an unknown bias e is introduced on the measure of r. The state of the system is given by x = r ṙ . The regulated variable is defined as α = 1 0 y = r + e. The beam measuring only L = 1 m, the objective is to satisfy ∀t, 0.1 ≤ α(t) ≤ 0.9 (in meters) while driving the system from r 0 = 0.5 m to the setpoint r s = 0.6 m. Considering this regulated variable, it is observed that l = 2 and k = 2. The system state-space representation is given by:

A = 0 1 0 0 , B = 0 0 0 1 -0.21 0 , C = I 2 , D = 0 0 1 0 0 0 (36)
where the inputs are respectively, d, u and e. As far as the control design is concerned, LQR design is used on the adequate augmented system with R = diag 10 4 and Q = diag 1 10 This controller yields good results on r s -setpoint tracking. Violation of the expected time-domain performance 0.1 ≤ α(t) ≤ 0.9 is however witnessed in presence of the disturbance d. This results in the ball falling from the beam. Introducing OIST in the loop, it is expected to comply with this constraint. Note that a more precise selection of the gains K p and K i may deliver more satisfying results. For the purpose of illustrating OIST technique only, better gains are however not sought for.

B. Hypotheses

C. OIST implementation

Using results in Sect. III and considering α = 0.1 m, α = 0.9 m, the following expressions are obtained for the successive Ω i 's (1) , e (1) + Ω1 (38) where Ω 0 > 2g (e, e). Then the values of the κ i 's are deduced κ1 = κ1 +2g e (1) ,e (1) Ω 0 -2g(e,e) κ2 = κ2 -Ω1 +2g e (2) ,e (2) (1) ,e (1) (39) where κ = κ1 κ2 = 30 10 . Finally, the expressions of the saturations to apply to the controller output are inspired from Eq. (13) on Fig. 2. Note that C α AB u < 0 in this example so the operator in Eq. ( 12) is used. As far as the anti-windup design is concerned, the time-varying coefficient K oist (t) is defined as follows

Ω 0 = 0.8, Ω 1 = κ 1 [Ω 0 -2g (e, e)] , Ω 2 = κ 2 Ω 1 -2g e
+2|CαAB d | max(|d|,|d|) Ω 1 -2g e
Koist(t) = U 2 (t)Θ CαABu ( 40
)
where U 2 (t) = κ 2 κ 1 + κ1 κ 1 + κ 2 1 and Θ = C α C α A C α A 2 .

D. Simulations and results

Using results in Sect. V-C, simulations are performed over 100 s. The disturbances d and e shown on Fig. 6 are applied to the system. The disturbance d at time t = 70 s is used to confirm that when constraints are not violated then the control is not modified. Simulation results are shown on Fig. 7 and8. The system data are represented in blue when not considering OIST approach and in orange in the other case. One can see that due to the disturbance d, the ball is ejected from the beam. When OIST is considered, the ball trajectory remains in the expected interval (in red). Note that the applied saturations result in some conservatism due to the lack of knowledge on d and e. Also note that sharper variations are witnessed on the command when applying OIST approach. The trade-off between performance and command energy can be tuned using the parameters κ. In this article, the problem of keeping a linear system output -or regulated variable -in an interval has been formalized. A solution based on a transformation from this output expected 'saturation' to a saturation on the available linear control has been proposed. Thanks to the addition of an anti-windup loop, the stability of the system in closedloop with the resulting nonlinear control has been proved. A simple application to a linear system has been proposed.

However, only considering systems where y = x is a bit limited. Future works will be dedicated to extend the approach to systems with matrix C = I n . On the long term, a synthesis procedure to optimally choose the coefficients κ could perhaps be imagined. It could also be interesting to study systems with positive zeros for which more complex approaches are required.

Fig. 1 .

 1 Fig. 1. Top: system (G) in closed-loop with controller K. Bottom: expected performance (in orange) with OIST in the loop

Fig. 3 .

 3 Fig. 3. Iterative definitions of the coefficients in α (j)

Fig. 6 .

 6 Fig. 6. disturbances d and e along with their known bounds (in red)

•Fig. 7 .

 7 Fig. 7. in orange (resp. blue), system state with (resp. without) OIST in the loop

Fig. 8 .

 8 Fig. 8. saturated command in orange

  [START_REF] Hu | Geometric Control Theory[END_REF] . The following state-feedback gain K p with integral-action gain K i are obtained:

	Kp =	-0.3156 -2.0937 0.0322 -0.7661	, K i =	0.0644 1.5779	(37)

Ω(t) is defined in a similar way.


M H Fahmy

P Volland-Nail

Types of scientific publications

A scientific communication is a written and published report to transmit scientific knowledge from a scientist or a group of scientists to an interested general or specialized audience [START_REF] Day R | How to write & publish a scientific paper[END_REF]. It can take various forms namely:

Original scientific paper

Original scientific papers report results on original and usually intensive studies being reported for the first time in a printed form in a primary, peer-reviewed, periodical journal. The material should not have been previously published anywhere, except in a preliminary form such as a poster or an abstract published in proceedings of scientific meetings. Original papers should be in a form whereby peers of the author(s) can repeat the experiment and test the conclusions. Original scientific papers are organized in an agreed-upon common format (IMRAD). The paper should have the following sections in the following order: Title, should be precise and indicative of the subject of the aricle; Authorship, usually arranged according to contribution in the work and complete postal address(es) of the affiliated institutions involved; Corresponding author, if different from the senior author, and his/her full telephone, fax number and e-mail address if available; Abstract, followed by keywords (some journals require a summary either before the introduction or after the conclusions; some others require abstracts in more than one language); Introduction, giving a brief background for the study and stating clearly its objective and how it relates to available knowledge; Material(s) and methods (or procedures); Results; Discussion, or Results and Discussion combined, Conclusions (either separately or combined with discussion); Acknowledgements (optional); References, either in alphabetical order or numbered according to the order of citation.

Technical notes and short communications

Technical notes are concise but complete description of a limited investigation or based on a limited data. Short communications report preliminary results of original research experiments that need to be available to the scientific community within a short period of time. Results published in these types of publication should not be included in a later paper. They should be as completely documented, both by reference to the literature and description of the experimental procedures employed, as an original paper. They should not occupy more than 6 printed pages including figures, tables and references. Some journals require sectioning them as in original papers, some others may accept them with an Abstract, a combined Introduction-Material and methods-Discussion section, and References. They take shorter time to publish than original papers.

Review articles and book chapters

A review is a summary of previously published original scientific papers to put them into some kind of perspective. A review is based on several already published papers, so it is not considered as an original publication. To be an effective source of information, review articles should cover subjects falling within the scope of the journal publishing them and should generate active current interest [START_REF] Day R | How to write & publish a scientific paper[END_REF]. In review articles, there are no Material and methods and Results sections, however, the Introduction and Discussion sections are expanded. Review articles should not be summaries of original papers, cut and pasted one after the other, but rather a kind of summary of the similar or different results from various studies. In review articles the reader is expected to learn the state of the art in the subject treated. In good review articles, the author is expected to arrive to some concensus or authoritative and critical evaluation of the published literature on a subject, for example if he (or she) reports on estimates of heritablility of a trait he (or she) should make the effort to get the average of all the estimates reported.

The list of references should include most if not all the recent and relevent publications. Authors of review articles should take into consideration that their audience is much larger than if they were writing an original scientific paper. Review articles are often read by many people in related fields since reading reviews is the best way to keep up in one's broad areas of interest. Book chapters are usually written by invitation from the editor and are similar in arrangement and objectives to review articles.

Conference report and abstracts

Papers presented at conferences to be later published in proceedings are mostly reviews but some may be original. Publication of papers in a conference proceeding would generally disqualify them for later publication in primary journals. Because the space allowed in proceedings for each presentation is limited, normally 1 or 2 pages, and often maximum of 4 pages, it is not wise to publish important findings in proceeding since the author will be forced to compact his (or her) paper to fit the allowed space. In addition, the acquisition of proceedings by libraries is much less than original journals which results of important findings may not be readily available to a large audience.

Conference papers may report on original work in progress with only preliminary results presented.

Abstracts or summaries of papers presented at scientific meetings, whether reporting on completed research or research still underway, are usually published in the proceedings of the meeting. Although reference to these abstracts can be made, the publication of just an abstract is not considered as a primary publication and the same results can be published later in periodicals.

Case report

Mostly published in veterinary journals. A case report may have various objectives: alert veterinarians to new diseases not previously recognized in a particular species or observed in a particular geographic area; demonstrate novel treatment or surgical procedure for a known disease. A case report is usually short, rarely exceeding 4 printed pages. It should include a complete description of the animal(s) affected by the disease known in veterinary terms as "signalment". The structure of a case report varies according to the journal but is should include an appropriate literature review and discussion to demonstrate the uniqueness of the case and/or the new approach to treatment or management.

Letter to the editor

Authors can question the scientific content of any published paper by writing to the Editor-inchief. Some journals publish these letters as part of their regular features. Some journals also publish scientific knowledge which may not fit as a "technical note" as a "letter to the editor". These can be cited as any scientific publication.

Choosing the appropriate journal for publishing the research

The impact of a scientific paper on the scientific community does not depend exclusively of its own value but also of the journal in which it is published. So, choosing the right journal is a critical step in planning an original scientific paper [START_REF] Matthews | Successful scientific writing. A step-by-step guide for biological and medical sciences[END_REF]. The choice must be made before typing the manuscript to be in accordance with the "Guide for Authors" published regularly by each journal.

Several criteria must be examined carefully, step by step:

Aims and scope of the journal

First, the choice depends on the subject area covered by the journal, on the nature of the work and on the journal's audience. "Is the topic of the paper within the journal's scope ?" must be the first question.

The journals'name indicates the field covered, but it is necessary to read the part "Aims and Scope" of the journal or the brief statement of purpose always printed on the cover of each issue of the journal. It is also appropriate to examine carefully the "Table of Contents" of recent issues.

Prestige of the journal

The "notoriety" of a journal in the scientific community is a subjective criterion, but it can be estimated by looking at the members of the editorial board, by the peers'judgment on the journal, and by the prominence of scientists who publish in the journal. A more objective "prestige factor" is given by the "impact factor" of the journal. The impact factor created by the Institute for Scientific Information (ISI) [START_REF][END_REF][START_REF]Citation indexing -its theory and application in science, technology, and humanities[END_REF]) is published annually along with a series of other indicators in what is commonly known as the Journal Citation Reports (JCR). JCR is based on the analysis of citations of the articles by other scientists.

The exact definition given by Garfield (1996) is: "The impact factor is basically a ratio between citations and recent citeable items published. Thus, the impact factor of Journal X would be calculated by dividing the number of all current citations of source items published in Journal X during the two previous years by the number of articles Journal X published in those two years".

To use this criterion, it is necessary to compare the impact factors for two or more journals in their specific fields. Such comparison should be made carefully: the use of this criteria often based on isolated impact factor values has no doubt led to over-or under-estimation of journals.

A rereading of the data based on the notion of belonging to a group of journals enables fuller and more nuance judgements to be made on journals [START_REF] Magri | NAIL P. (coordinator) : Un point sur L'information scientifique et technique: nouveaux enjeux documentaires et éditoriaux[END_REF].

Diffusion factor

The criterion of "diffusion" of the journal is also essential. The size of the journal's audience must be evaluated, at the same time as the ways of its diffusion. It is important to verify:

• Indexation of the journal in the secondary sources of information: Current Contents, which international databases, etc… • Diffusion via Internet: is the journal accessible online via the Web or not?

• The circulation factor: it can be estimated in American journals with the "Statement of Ownership, Management and Circulation" which publish every year all the data about the number of copies, the total distribution, etc …

Functioning of the journal

Several other functioning criteria of the journal are important for the choice:

• The "frequency factor": publishing time in a monthly journal is almost always shorter than publishing in a quarterly journal.

• The "rapidity" of publication: if the journal publishes information on date of reception it is possible to evaluate the average lag of time from submission to publication.

• The process of reviewing the papers: it is better to publish in a journal with peer-review than without.

• The accuracy of "Guide for Authors": if they are precise and clear, it is easier to prepare the manuscript because they answer many pertinent questions.

• The material "quality" of the journal, particularly for graphics and photographic (half-tone) reproduction.

• Publication cost is also an important criterion of choice: some journal charge for each page published.

• Reprint cost: some journals provide a certain number of free reprints while others charge for each reprint ordered.

The processes of submission, peer-reviewing, editing and printing

Preparing the manuscript for publication

Before typing the manuscript, the author should read the "Guide for Authors" and follow them carefully. Each journal has its own format and papers can be rejected if they do not conform to that format, or at least delayed if they have to be sent back to authors. The "Guide for Authors" are printed regularily in the journal, available on Internet or could be obtained by writing to the journal or the editor.

Submitting the manuscript

After typing the paper according to the format of the choosen journal, authors should prepare a covering letter indicating their mailing address, telephone and fax numbers as well as their e-mail address. It is important to write the title of the paper submitted and provide two return labels. Authors should always send the original and the required number of copies, and make sure that they are all easy to read. Authors should also make sure that they send the package in well sealed and strong envelops. Also to write the name and address of the current editor clearly and correctly. If the paper is sent by airmail, the required postage should be used.

The review process

3.3.1. Reception and acknowledgement. Upon receipt of the manuscipt by the Editorial office or the Editor-in-chief, a letter of acknowledgement is sent to inform the corresponding author that his/her manuscript was received and inform him/her of the log number of the paper. Also this letter is used to inform the author of the name and address of the associate editor processing his/her paper. The log number should always be used in any correspondence since it facilitates tracking down the paper.

3.3.2. Peer reviewing. The Editor-in-chief is assisted by associate editors and members of the editorial board as well as scientists in the field. These cover a wide range of specialization and expertise. The Editor-inchief channels the papers to associate editors according to their specialization. These in turn send the papers to expert peers to evaluate the papers technically. Referees write a detailed evaluation and make a recommendation on whether to accept the paper or not. Based on that, the associate editor, either inform the authors that their paper is not acceptable, or indicate the changes and modifications the authors have to do to have their papers accepted.

Revising manuscripts

Upon receipt of the editorial comments and suggestions, the authors are required to follow them or give reasons why they think they should not accept them. All authors of the paper should approve the changes made on the revised version. Some journal require all authors to sign a form indicating their approval. The authors then re-type their revised papers and send two copies of the revised version together with a copy of the revised version on diskette. Some journals also require that authors return the marked copy(ies).

The publishing process

Accepted papers are sent to the printer for publication. They are type-set and a galley proof is produced. A copy is sent to the author for his (or her) final approval and to correct any typesetting mistakes. At this stage any major changes in the text can result in delaying the publication or can cost the author(s) money. Authors should make their corrections and return the proofs as soon as possible. This is also the time to order reprints and release copyrights to the journal.


Christian Herlin
email: c-herlin@chu-montpellier.fr

Benjamin Gilles

Gérard Subsol

Guillaume Captier

Generic 3D Geometrical and Mechanical Modeling of the Skin/Subcutaneous Complex by a Procedural Hybrid Method

Keywords: biomechanics, soft tissue, skin/subcutaneous complex, plastic surgery, procedural method

The aim of this work is to build a 3D geometric and mechanical model of the skin/subcutaneous complex (SSC) which could be adapted to the different parts of the body and to the morphological parameters of the patient. We present first the anatomical pattern of the SSC. Then, we propose a hybrid model which combines volume, membranous and unidimensional models. The complex internal structure of the SSC is automatically created by a procedural process. All the models are defined by some parameters which can be easily measured by medical imaging. We describe several preliminary experiments which show how this hybrid method models realistic geometrical deformations and physical behaviors and could be used for surgery simulation and planning.

Introduction

Surgeons, biomechanicians and digital designers are all looking for accurate, realistic means of predicting the deformation of soft tissues. Although different objectives have been pursued in each case, the main problem arising has been that of modelling a heterogeneous three-dimensional structure showing complex mechanical behavior. In fact, there exists no mechanical model so far which accurately simulates the anatomy of the skin/subcutaneous complex (SSC), taking the connective arrangements and the mobility of the components into account.

Most models are uni-or bi-lamellar, composed of layers which often have a constant thickness and which show linear isotropic mechanical behavior (see for example [START_REF] Chabanas | Patient specific finite element model of the face soft tissues for computer-assisted maxillofacial surgery[END_REF][START_REF] Barbarino | Physically based finite element model of the face[END_REF][START_REF] Hung | A framework for generating anatomically detailed subject-specific human facial models for biomechanical simulations[END_REF][START_REF] Roose | Simulation of soft-tissue deformations for breast augmentation planning[END_REF][START_REF] Lapuebla-Ferri | A patientspecific FE-based methodology to simulate prosthesis insertion during an augmentation mammoplasty[END_REF] for the face or the breast). They differ considerably from the genuine architecture of the human SSC, which is supported by a complex three dimensional collagen network causing a non-linear anisotropic mechanical behavior. Moreover, these models are dedicated to a specific anatomical area.

Although the structure of subcutaneous tissue differs between various regions of the human body, common components have been identified in several anatomical parts. The existence of a generic pattern of organization of the SSC was put forward several years ago [START_REF] Lockwood | Superficial fascial system (SFS) of the trunk and extremities: a new concept[END_REF], then confirmed in recent radiological work [START_REF] Abu-Hijleh | The membranous layer of superficial fascia: evidence for its widespread distribution in the body[END_REF] at the level of the arms, legs and trunk. Nevertheless, this anatomical finding has never been the basis of a generic modeling of the human SSC.

The aim of this work is to build, from anatomical knowledge, medical imaging and histological observation, a generic 3D geometric and mechanical model of the skin/subcutaneous complex which could be adapted to the different parts of the body and to the morphological parameters of the patient. In section 2, we present the anatomical pattern of the SSC. In section 3, we propose a hybrid model which combines volume, membranous and unidimensional models of the different substructures. The complex internal structure of the SSC is automatically created by a procedural process. All the models are defined by some parameters which can be easily inferred by medical imaging. In section 4, we describe several preliminary experiments which show how this method models realistic geometric deformations and physical behaviors and could be used for surgery simulation and planning.

Anatomical Considerations

Generic Pattern of the Skin/Subcutaneous Complex

The generic model of organization of the human skin/subcutaneous complex was confirmed by our 3T MRI studies at the level of the face, the trunk and the limbs [START_REF] Herlin | Three-dimensional study of the skin/subcutaneous complex using in vivo whole body 3 tesla MRI. review of the literature and confirmation of a generic pattern of organisation[END_REF]. We can summarize this organization into a multi-layered model retained by a collagen network which combines the following substructures (see Fig. 1):

-Skin which has a very variable thickness (1 to 7 mm) depending on locations; -Superficial Adipose Tissue (SAT) consisting of fat lobules of variable size organized in clusters rather like palisades bands; -Retinacula Cutis Superficialis (RCS) formed by the septal densifications lobules of the SAT; -Membranosum Stratum (SM) or membranous layer of the superficial fascia; it can be either fibrous and/or muscular and either single or multiple; -Deep Adipose Tissue (DAT) composed of polyhedral fat lobules, as in a honeycomb arranged more randomly than in the SAT; -Retinacula Cutis Profondus (RCP) formed by the septal densifications lobules of the DAT; -Skin ligaments (SL) [START_REF] Nash | Skin ligaments: regional distribution and variation in morphology[END_REF], also perpendicular to the skin which are a particular specialization of RCS and RCP . They allow the maintenance of the skin or SM in deep plane or skin. They have already been described at the face, breast, the fingers, the sole or the scalp. -Deep Layer which is the inferior limit of the SSC. This may be muscle, aponeursosis or periosteum.

Regional Specificity

At the level of the face, the SM endorses a particular muscle specialization called Superficial Musculo Aponevrotic System (SMAS) ensuring facial expressions [START_REF] Hung | A framework for generating anatomically detailed subject-specific human facial models for biomechanical simulations[END_REF]. This residue of the panniculus carnosus is found to be in continuity with the temporoparietal fascia and the superficial layer of the cervical fascia. However, this continuity is interrupted between the two nasojugal fold where the layers are intermingled, making the stratigraphic pattern more difficulty to identify. At the level of the breast and thorax, the SM identified beyond the mammary region is continuous anteriorly, in the breast area, with a superficial layer located 3 to 4 mm under the skin. The collagen network, less developed in male chest, corresponds to the Cooper's ligament in female breast.

In the antero-lateral part of the abdomen, the SM forms a single layer. More anteriorly, it is divided into two parts when the adipose tissue becomes thicker. In the peri-umbilical region, the SM takes a deeper course and merges with the pre-muscular fasciae of the rectus abdominis muscles.

Finally, for the lower limbs and buttocks, the SM and Retinacula Cutis show a similar pattern of organization. A clear-cut increasing gradient in the number of RC in the knee and buttocks, correspond to the preferential fat storage sites.

3D Modeling of the Skin/Subcutaneous Complex

Procedural Geometrical Modeling

In order to deal with the variability of the SSC with respect to the regional specificity or the morphology of the patient, we introduce a procedural method to build a detailed 3D geometrical model. This model is based on some global parameters which can easily be measured in MRI or echography.

Skin, SM and Deep Layer are modeled by a layer of a given thickness (called respectively skin t , SM t and deep t ). SAT and DAT correspond respectively to the spaces between skin and SM and SM and Deep Layer, and are parameterized by their thickness SAT t and DAT t . These spaces are filled by a 3D Voronoï tessellation where each Voronoï cell, defined by its center point, represents a fat lobule. Center points are randomly located but evenly-spaced by using the Lloyd's algorithm. The mean diameter of a fat lobule called lobule d gives the average distance between the center points. The walls of the Voronoï tessellation correspond to the septa of RCS and RCP which separates the lobules. They are extracted as a 3D triangle mesh. We assume plane stress conditions for these walls, meaning that we neglect bending over stretching; so wall thickness is not geometrically represented. Fig. 2 and3 demonstrate that specificity of the anatomical region is taken into account. At the level of the buttocks, the skin is thick, the thickness of the DAT is very variable depending on the location. The mesh formed by the RCS and RCP is very dense in areas of fat storage. At the level of the face, the SM, thicker, has a muscle differentiation. The volume of lobules is small and RCS as RCP are thin.

Hybrid Mechanical Modeling

From a mechanical point of view, the SSC is composed of elements of variable mechanical behaviors: hyperelastic for the skin and visco-elastic for the fat. This assembly has a global non-linear anisotropic behavior principally due to the existence and orientation of collagen fibers. Detailing the stratigraphic and lobular organization of the sub-cutaneous fat, we wanted to recreate the overall anisotropy of the SSC by adding linear isotropic elements. This approximation is permitted by the architectural complexity of the geometrical model.

To model the different substructures, we built an hybrid model. It combines a volume model for the skin, SM, SAT and DAT, a membranous model for the interlobular septa of RCS and RCP and a unidimensional model for the skin ligaments.

We used the SOFA framework [START_REF] Allard | SOFA -an open source framework for medical simulation[END_REF] which is particularly suitable for implementing and processing this type of composite models in nearly real-time. Programming is based on a Python script that allows flexibility in the geometrical and mechanical parameterization.

Volume, membranous and unidimensional components of our model were discretized using respectively hexahedral, triangular and edge finite elements. To mechanically couple them, these elements were embedded in a coarser regular grid using barycentric interpolation. The typical size of a coarse hexahedron was 2 mm. Time integration for coarse nodes was performed using the Euler implicit scheme and conjugate gradient algorithm. Strain was measured using the corotational method.

For each substructure, we extracted Young's modulus data from the literature, and performed an average. We try to assess these values by a simulation of indentation in similar conditions of some published research. Poissons ratio was fixed at 0.49 due to the incompressible nature of the materials.

Some Experiments

Simulation of Indentation

In order to validate the behavior of our model, we simulated an indentation test of the forearm with the parameters found in an in vivo MRI study [START_REF] Tran | Caractérisation des propriétés mécaniques de la peau humaine in vivo via l'IRM[END_REF]. Geometrical parameters are listed in Fig. 4, right. In paticular, DAT is very thin. Young modulus of skin, fat, SM, RC and muscle were respectively set to 20, 1 , 60, 100 and 15 kPa.

The indenter was modeled as a cylinder of diameter 5 mm. Such as in the experiment presented in [START_REF] Tran | Caractérisation des propriétés mécaniques de la peau humaine in vivo via l'IRM[END_REF], we simulated several indentations between 0.35 and 1.8 N. Fig. 4, shows a comparison between real data and the obtained vertical displacements at equilibrium. On average the error was 18% suggesting that our model is rather realistic.

Accuracy could be improved in future using non-linear material laws. However, this will raise the problem of parameter identification, as a high discrepancy in the reported material parameter can be found in the literature, depending on the measurement modality and test specimen.

Simulation of the Phenomenon of Cellulite

Cellulite is considered for the majority of authors as a consequence of the increased content of fat lobes associated with a deterioration of collagen tissue of the skin and the relative stability of RC underlying the skin [START_REF] Hexsel | A comparative study of the anatomy of adipose tissue in areas with and without raised lesions of cellulite using magnetic resonance imaging[END_REF]. We simulated the increase of 24 cm 3 of fat in the SAT and DAT of the buttocks model of Figure 2 by modifying the rest shape of fat material. This results in skin dimpling and nodularity as shown in Fig. 5 left. Then we reduced the stiffness of the skin to simulate aging. Cellulite is enhanced as we can see in Fig. 5 right.

Simulation of Fat Injection in the Subcutaneous Tissue

Fat grafting is a major technique in reconstructive surgery. During this procedure, the injection site significantly affects the outcome. In a deep injection (that is in DAT), the effect is said "volumizer" and the main purpose is usually to increase the projection of an anatomical structure (cheekbone, buttocks, breasts...). In contrast, if the injection is more superficial, the effect is more on the shape of the injection site and it is most often used to fill wrinkles or scars.

We simulated an injection of 0.5 cm 3 of fat inside the DAT of the cheek model of Fig. 3. It results in a smooth and global elevation of the skin surface (see Fig. 6 left). Fig. 6 right shows the simulation of a similar injection inside the SAT. Our model allows to simulate the "orange peel" phenomenon with a high fidelity. This problem during surface injection is common in daily clinical practice and feared if a too large volume of injection is carried out in a too superficial plane. If the injection is too superficial, the "peel orange" phenomenon appears.

Future Work

If we have the external shape of the patient, for example by using MRI or a 3D surface scanner, we could deform the generic model and fit it to his specific and exact morphology. Such a registration will allow us to perform pre-operative simulations of plastic surgeries of the face, the thorax or the breast. In particular, we think that our model will be able to simulate breast augmentation surgery in a more faithful way because it includes an accurate modeling of RC, which corresponds to the Cooper's ligament which has a major role in the final shape of the breast. This model will also permit to simulate fat grafting inside the adipose tissue taking into account its lobular composition and its retaining connective tissue. Some studies focus on fat injection as [START_REF] Comley | Deep penetration and liquid injection into adipose tissue[END_REF] and more recently [START_REF] Majorczyk | Simulation of lipofilling reconstructive surgery using coupled eulerian fluid and deformable solid models[END_REF] but none is able to simulate fat grafting considering the destruction of septa or skin ligaments. Such a technique called fasciotomy is common in daily practice, in a particular in breast reconstruction [START_REF] Agha | Use of autologous fat grafting for reconstruction post-mastectomy and breast conserving surgery: A systematic review and meta-analysis[END_REF]. The simulation could be done procedurally by deleting the walls of the Voronoî cells corresponding to the RCS and cutting the skin ligaments.

Nevertheless, to simulate a more accurate behavior of the skin, it will be necessary to add to our model the anisotropic behavior of the skin and the preexisting tension. These properties have been described in details and are often represented as Langer's lines. This would allow us to simulate other type of plastic surgeries as skin incision or lifting.

Fig. 1 .

 1 Fig. 1. Generic model of the Skin/Subcutaneous Complex with all the substructures

Fig. 2 .

 2 Fig. 2. SSC model for the buttocks based on parameters measured in a MR image

Fig. 3 .

 3 Fig. 3. SSC model for the cheek based on parameters measured in a MR image

Fig. 4 .

 4 Fig. 4. Simulation of indentation of the forearm according to an in vivo MRI study

Fig. 5 .

 5 Fig. 5. Simulating cellulite in buttocks by increasing fat volume in SAT and DAT. Right: cellulite enhancement due to aging simulation.

Fig. 6 .

 6 Fig. 6. Simulating fat injection in the cheek at the level of DAT (left) and SAT (right).If the injection is too superficial, the "peel orange" phenomenon appears.

Acknowledgments. We want to thank the radiology team of University Hospital of Nîmes, France for MR acquisitions and Ms. Witt for the quality of her drawings.