Keywords: Network Calculus, algèbre des fonctions (min, +), algorithmique, complexité

Stabilité et étude algorithmique des opérations du Network Calculus

Résumé : Le Network Calculus est un outil puissant pour analyser les performances des réseaux de communication, en particulier pour obtenir des bornes déterministes. Cette théorie s'appuie sur l'algèbre (min, +) et ses aspects théoriques ont fait l'objet de nombreuses études. Malgré cela, les aspects algorithmiques de cette théorie ont très peu été regardés. Dans ce rapport, nous fournissons des algorithmes efficaces pour implémenter les opérations du Network Calculus.

Les fonctions les plus utilisées sont les fonctions affines qui ont ultimement un taux de croissance constant. Une première étape de notre travail est de présenter une classe stable de fonctions sous les opérations du Network Calculus contenant ces fonctions (ce sont les fonctions affines par morceaux ultimement pseudo-périodiques). Comme ces fonctions sont finiment représentables, on peut trouver des algorithmes pour les opérations étudiées. Nous nous intéressons aussi à leur complexité.

Introduction

Network Calculus is a theory of deterministic queuing systems encountered in communications networks. It is based on (min, +) algebra and it can be seen as a (min, +) filtering theory by analogy with the (+, ×) filtering theory used in traditional system theory. More than just a formalism, it enables to analyze complex systems and to prove deterministic bounds on delays, backlogs and other Quality-of-Service (QoS) parameters. The information about the system features are stored in functions, such as arrival curves for data flows or service curves for service guarantees of the network nodes. These functions can be combined together thanks to special Network Calculus operations, in order to analyze the system and compute bounds.

At the present time, the theory has developed and yield accomplished results which are mainly recorded in 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].

However a central question has not been much addressed for now: which algorithms efficiently implement the Network Calculus operations?

Several results presented in the reference books [START_REF] Chang | Performance Guarantees in Communication Networks[END_REF][START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF] have an algorithmic flavor. They present some formularies with algebraic rules of transformation when combining the different Network Calculus operations, they give some examples of functions for which the output of some operations can be easily described (such as convex piecewise linear functions, concave functions or star-shaped functions). Moreover they illustrate their results by examples and sometimes provide closed formulas for very special cases. For instance an exact value of the deconvolution of some Variable Bit Rate (VBR) arrival curves by rate-latency services, is given in [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF]. However the question of the implementation of Network Calculus operations does not appear in the topics. Some authors have explored the Legendre-Fenchel Transform (f (t) → C(λ) = sup t (λtf (t))) in order to simplify calculations. This transform, also called convex conjugate function or C-transform [START_REF] Chang | Deterministic traffic specification via projections under the min-plus algebra[END_REF], is a powerful tool of convex analysis [START_REF] Rockfellar | Convex Analysis[END_REF]. It is an analogue in the (min, +) setting of the Fourier Transform or the Laplace Transform in (+, ×) conventional signal and system theory [START_REF] Oppenheim | Signals and Systems[END_REF]. Its use seemed promising (e.g. convolution becomes addition for the transformed functions), however one important issue is that this transform is not injective for non-convex functions. Attempts to use such a transform to achieve computations have not succeeded yet for general cases [START_REF] Pandit | Optimization of the min-plus convolution computation under Network Calculus constraints[END_REF].

Several attempts also aimed at providing some closed formulas for special cases. For instance, the authors of [START_REF] Pandit | Optimization of the min-plus convolution computation under Network Calculus constraints[END_REF] managed to give a closed formula for the convolution of two piecewise linear functions with three pieces each. Their formula already contains a lot of cases and they could not avoid a very heavy case by case proof. There is little hope to generalize such a proof since the number of cases seems to explode quickly. For an interesting discussion about all these attempts, the reader is referred to Pandit et al. works [START_REF] Pandit | Optimization of the min-plus convolution computation under Network Calculus constraints[END_REF][START_REF] Pandit | Optimal allocation of service curves by exploiting properties of the min-plus convolution[END_REF]. However, a software is being developed using this theory for the study of feed-forward networks. In [START_REF] Schmitt | The DISCO Network Calculator -A Toolbox for Worst Case Analysis[END_REF], the tool DISCO Network Calculator is described and algorithms are given for convex and concave functions.

From a practical point of view, some other implementations of Network Calculus operations have been proposed, but as far as we know they rather use brute force algorithms and work for very restricted sets of functions, for instance functions defined over a bounded set (and not [0, +∞[). One can mention the Mathematica implementation of Thiele [START_REF] Thiele | Real-time calculus Research Project[END_REF]: it deals with piecewise affine functions defined over R + which are not necessarily increasing. The code is short, but a careful look shows that the set of input functions for which it produces an exact output is not clearly specified. Moreover there is no algorithm computing exactly the subadditive closure and no complexity analysis is given.

Among the works related to these questions, one must mention the studies of (min, +) or (max, +) linear systems in Baccelli et al's book [START_REF] Baccelli | Synchronization and Linearity[END_REF] and in Gaubert's thesis [START_REF] Gaubert | Théorie Linéaire des Systèmes dans les Dioïdes[END_REF]. In particular, they introduce formal power series in two variables γ and δ, which can be used to represent some functions from N into R or from R + into R, and to perform calculations close to the Network Calculus operations. In [START_REF] Pandit | Optimal allocation of service curves by exploiting properties of the min-plus convolution[END_REF], their use is shortly discussed as the Γ-transform, but dismissed by those authors for exact calculations due to discretizations which lead to approximative representations. However this tool provides exact results for a large class of functions. Moreover the manipulation of these series has been implemented by Gaubert [START_REF] Gaubert | [END_REF] and Hardouin's team [START_REF] Hardouin | Modèles et Systèmes Dynamiques[END_REF] for Scilab.

Our results are actually related to the ones presented in [START_REF] Baccelli | Synchronization and Linearity[END_REF][START_REF] Gaubert | Théorie Linéaire des Systèmes dans les Dioïdes[END_REF], in particular our stability theorems. We will discuss it in the paper.

Our approach has two steps:

1. finding a good class of functions for the Network Calculus operations; 2. designing algorithms which implement these operations for this class.

Section 2 presents the main Network Calculus operations, namely +, -, min, max, * , and the sub-additive closure.

The first step consisting in finding a good class of functions is developed in Section 3. Transferring the mathematical theory into the algorithmic field involves making choices to restrict a little the general theory so that we can apply effective methods: functions with a finite representation and that are stable for the Network calculus operations constitute a good class of functions.

Our first concern was to include some usual functions of Network Calculus like the piecewise affine functions which ultimately have a constant growth. They are used for instance to describe arrival curves which constrain input flows (such as γ r,b (t) = rt + b arrival curves) and service curves which garantee the services provided by network elements (such as β R,T (t) = R(t -T ) + service curves).

We were also confronted to the choice of the definition sets of our functions. functions are usually defined from a set X into a set Y , where these two sets are chosen among N, Z, Q or R. In this paper, we will both focus on functions from N into R (discrete model ) and functions from R + into R (fluid model ). We will carefully discuss the associated issues when switching between all these sets.

The main result of this section is the characterization of a set of functions closed under all the operations and containing the usual functions. The good news is that the functions of this closed set are ultimately pseudo-periodic and thus can be finitely described which enables algorithmic design.

The second part of our work, developed in Section 4, consists in finding efficient algorithms that compute the Network Calculus operations for this closed set of functions. The algorithms are derived from the stability results of the first part and their proofs. In particular they use the decomposition of functions into elementary functions, for which the calculations are simple. We point out how computational geometry may help.

In Network Calculus, the manipulated functions are usually supposed to be positive and non-decreasing, however we will not restrict ourselves to these conditions since we wish to design algorithms as general as possible, for instance to allow some intermediate calculations that may use some non increasing or negative functions, even if they do not have a direct "physical" interpretation.

Section 5 concludes the paper with a discussion and some perspectives.

2 Definitions and notation

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(ts)).

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. Remark that if f (0) < 0, then ∀t ∈ X, f * (t) = -∞.

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), fg is undefined if ∃t, f (t) = g(t) = +∞ (or -∞), f * g is undefined if ∃t 1 , t 2 , INRIA 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.

Note that most of the results presented in this paper remain true when forbidding the infinite values. Moreover allowing them has the drawback to lengthen the proofs because it introduces each time a few special cases to deal with. However these new cases can be solved quickly, and allowing infinite values proves to be interesting for modelization purposes as well as for algebraic manipulations and decompositions. Consequently, for sake of generality and commodity, we allow them.

When f ∈ D or F, and f (0) ≥ 0, 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).

In the sequel of the paper, we will focus on some functions that can be finitely described, which is interesting from a computational point of view. Note that working with R for values or arguments of the functions presents some issues. The main one is not the storage of the functions, which can be approximated with floats if e.g. they are piecewise affine, but rather the change of behavior of some operations. We will come back to this problem and see that the use of Q instead of R ensures good behaviors such as the preservation of nice asymptotic shapes.

These operations have some good behaviors when combined: for example, it is known that ∀f, g, h ∈ D or F,

min(f, g) * h = min(f, h) * min(g, h); min(f, g) * = f * * g * ; max(f, g) h = max(f h, g h); f min(g, h) = max(f g, f h).
We will use some of these algebraic properties in our proofs and algorithms.

For a comprehensive survey on these properties, the reader is referred to Le Boudec and Thiran's book [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF] as well as Chang's book [START_REF] Chang | Performance Guarantees in Communication Networks[END_REF]. A few other simple properties are listed in [START_REF] Bouillard | Some examples and counterexamples for (min, +) filtering operations[END_REF].

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) = -∞. RR n 6094 ¡ f is plain if it is ultimately plain as above, and ∀ 0 ≤ t < T , f (t) ∈ R, and f (T ) ∈ R or possibly f (T ) = +∞ (resp. -∞) if ∀t > T , f (t) = +∞ (resp. -∞).

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 ∪ {-∞, +∞}.
-continuous) if ∀i ≥ 0, f (a i ) = f (a i -) (resp. f (a i ) = f (a i +)). We will mainly consider F[N, R], F[Q + , R], F[R + , R] and 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.

Links between discrete and fluid calculations

Let f ∈ F, we denote by [f ] N its restriction on N. Let f ∈ D, we denote by [f ] R its continuous piecewise affine interpolation: ∀n ∈ N, [f ] R (n) = f (n) and if f (n), f (n + 1) ∈ R, then [f ] R on ]n, n + 1[ is the affine interpolation between the two points, if f (n) ∈ R and f (n+1) = +∞ (resp. -∞), then [f ] R (t) = +∞ (resp. -∞) on ]n, n+1[ INRIA (do symetrically if f (n + 1) ∈ R and f (n) = +∞ or -∞), and if f (n), f (n + 1) ∈ {-∞, +∞}, then [f ] R is equal to f (n) on ]n, n + 1 2 ] and f (n + 1) on ]n + 1 2 , n + 1[. Thus [f ] R ∈ F[N, R].

Let

be a Network Calculus operation, we denote by R its version for functions in F and by N its version for functions in D. The difference is mainly for * , and the subadditive closure which use indices in the corresponding spaces, whereas the other operations are just point-wise operations.

The following lemma draws a first link between the discrete model and the fluid model: it provides a way to transfer results about calculations in F to calculations in D.

Proposition 1. Let f, g ∈ D, whenever = min, max, +, -, * , , we have

[[f ] R R [g] R ] N = f N g. Moreover [[f ] * R ] N = f * . Proof.
The result is clear for the operations min, max, +, -, because the result of these operations at a point only depends on the values of the functions at that point.

Consider the operator * .

The support of [f ] R * R [g] R is clearly an union of closed intervals of R + . Let t ∈ N, then [f ] R * R [g] R (t) = inf 0≤s≤t [f ] R (s) + [g] R (t -s).
Suppose that it has a finite value and that this minimum (this is a minimum because s →

[f ] R (s) + [g] R (t -s) is continuous on the support within [0, t] which is compact) is reached for s 0 / ∈ N. Then [f ] R * R [g] R (t) = [f ] R (s 0 ) + [g] R (t -s 0 ). Let ρ f = f ( s 0 ) -f ( s 0 ) and ρ g = g(t -s 0 ) -g(t -s 0 ). If ρ f ≥ ρ g then f ( s 0 ) + g(t -s 0 ) ≤ [f ] R (s 0 ) + [g] R (t -s 0 ). On the other hand, if ρ f ≤ ρ g then f ( s 0 ) + g(t -s 0 ) ≤ [f ] R (s 0 ) + [g] R (t -s 0 ).
In both cases, we could have taken s 0 ∈ N. To find a value of

[f ] R * R [g] R at an integer coordinate, it is sufficient to consider the functions [f ] R et [g] R on their integer coordinates, which is the same as computing f * N g. In case [f ] R * R [g] R (t) is +∞ or -∞, it
can be easily seen that the minimum can be also reached for an integer coordinate.

Using the same kind of reasoning gives the proof for the subadditive closure (with the characterization of Equation 1) and the deconvolution (choose s 0 as the index in R + which approaches the supremum as close as we want).

However note that this correspondence only works for "depth 1" level of operations. Given a formula with functions in D and operations over N, doing all the calculations in F with the interpolated functions and then going back to D by restricting the output function to N does not always provide the right result.

Example 1. Let f : t → 3 and g : t → 2t. Figure 3 gives on the left the result of the computation of max(f, g) in R and in N. Restricted to the natural numbers, the result of this computation is the same. But the result of max(f, g) * max(f, g) on the right shows that the values for t = 3 differ.

3 in R + in N max(3, 2t) max(3, 2t) * max(3, 2t)
Figure 3: Computation of max(3, 2t) * max (3, 2t) in R + and in N.

RR n 6094

The continuity and linearity of that piecewise affine interpolation on its support play an important role. Some other ways to interpolate functions defined on N into functions defined on R + , such as 4 shows that function and its interpolation f R . The right part of Figure 4 shows the convolution of those functions by themselves. We have f *

f → f R (t) = f ( t ) or f → f R (t) = f ( t ), do not yield the same general lemma. Example 2. Let f : N → R with f (0) = 0, f (1) = 2, f (2) = 1 f (3) = 4, and ∀t ≥ 4, f (t) = ∞. The left part of Figure
N f (3) = f (1) + f (2) = 3 = f R * R f R (3) = f R (1.5)+ f R (1.5) = 2. f f * f in R+ in N
Figure 4: Issues for some interpolations of functions.

The same kind of issues arises for

f → f R . Consider f : t → t on N, then f * N f (2) = 2 but f R * R f R (2) = 0.5 + 1.5 = 1.
However for particular classes of functions, some of those other interpolations may behave well, as shown in the next proposition.

Proposition 2. Let f, g ∈ D, if f or g is non-decreasing, whenever = min,max,+,-, * , , we have f R R g R N = f N g. Moreover if f is non-decreasing, f * R N = f * . Proof.
As in Proposition 1, we can focuss on * , and the subadditive closure. To obtain the result for * , which is commutative, suppose that g is non-decreasing and let t ∈ N, then observe that ∀s 0 ∈ [0, t], f R (s 0 ) + g R (ts 0 ) = f ( s 0 ) + g( ts 0 ) ≥ f ( s 0 ) + g(ts 0 ) since ts 0 = ts 0 ≥ ts 0 . The same reasoning applies for the subadditive closure characterized by Equation 1. For the deconvolution, it is not even necessary to have any non-decreasing function since for t ∈ N and s

0 ∈ R + , f R (t + s 0 ) -g R (s 0 ) = f ( t + s 0 ) -g( s 0 ) = f (t + s 0 ) -g( s 0 ).
Remark 1. One should also mention the simplest "interpolation" from D into F where f ∈ D is interpolated by f ∈ F s.t. f = f on N and is +∞ elsewhere. This interpolation clearly satisfies Proposition 1, except for where another simple interpolation is needed: given f ∈ D, the function f ∈ F is defined by f = f on N and is -∞ elsewhere. Then f N g = [ f R g] R . One drawback of this pair of direct interpolations is the loss of some properties like being plain or ultimately plain.

Stability under Network Calculus operations

In this section, we give the proofs of the main theorems of this paper, that is the stability of the discrete functions and piecewise affine functions which are plain and ultimately pseudo-periodic. Let us first give some additional notations.

For all x ∈ R, we use the notation x + = max(0, x). By extension, let f ∈ D or F, we denote by f + the function such that f + (t) = (f (t)) + for all t. For all a, b ∈ N, and by extension for a, b ∈ R + such tthat a/b ∈ Q, we will denote by a ∨ b their greatest common divisor and a ∧ b their lowest common multiple.

Stability of asymptotic behaviors.

We now study the behavior of the classes of affine, ultimately affine and ultimately pseudo-periodic functions. Unless specified, the following results are true for both the discrete model and the fluid model. Each result could be presented in both settings with corresponding proofs which would be identical. However some of the proofs are only stated for the fluid model, then one can refer to Proposition 1 to ensure that the same result holds for the discrete model.

INRIA

To get rid of some special cases involved by infinite values, we first set the following lemma.

Lemma 1. Let f ∈ F (resp. D) such that ∃a ∈ R + (resp. N), f (a) = -∞. Then for all t ≥ a, f * (t) = -∞. Moreover for all g ∈ F (resp. D), if f * g is well defined, then ∀t ≥ a, (g * f )(t) = -∞. Let g ∈ F (resp. D) such that ∃t ∈ R + (resp. N), g(t) = -∞. If f g is well defined, ∀t ≥ 0, (f g)(t) = +∞.
Proof. The proof is a direct application of the definitions of the operations.

Before addressing ultimate affine and pseudo-periodic behaviors, we state a proposition concerning plain and ultimately plain functions. Proposition 3. The classes of plain and ultimately plain functions in D (resp. F) are closed under min, max, +,and * , but not under . Plain functions are closed under the subadditive closure, but ultimately plain functions are not.

Proof. The result is a clear for min, max, + and -. For the convolution, if f 1 (resp. f 2 ) is ultimately plain from T 1 (resp. T 2 ), then f 1 * f 2 is clearly ultimately plain from T 1 + T 2 (with values either in R or equal to +∞ or equal to -∞ depending of the ultimate values of f 1 and f 2 ). Moreover, for plain functions, if the support of f 1 (resp.

f 2 ) is [0, T 1 [, [0, T 1 ], N or R + (resp. [0, T 2 [, [0, T 2 ], N or R + ) then the support of f 1 * f 2 is clearly [0, T 1 + T 2 [, [0, T 1 + T 2 ], N or R + . For the subadditive closure, let f ∈ D (resp. F) be plain, if f (0) < 0 then f * = -∞ over R + , if f = +∞ over R * + , then f * = f and the case of ∃a ∈ R + , f (a) = -∞ is treated in Lemma 1. In all other cases, f (1) ∈ R (resp. ∃ > 0, ∀t ∈ [0, ], f (t) ∈ R) and thus ∀t ∈ R + , f * (t) ∈ R.
We now illustrate the negative statements of the proposition. The subadditive closure of ultimately plain function is not necessarily ultimately plain: let f ∈ D (or F) such that f (t) = 0 if t = 2 and = +∞ otherwise, it is ultimately plain but f * (t) = 0 if t is an even integer and = +∞ otherwise, is not.

For the deconvolution, let f ∈ D (or F) such that f (t) = t if t is an odd integer and = 0 otherwise, a careful application of the definition of f f gives (f f )(t) = t if t is an even integer and = +∞ otherwise. Although f is plain, this output is not ultimately plain. Note that with [f ] R being the affine interpolation of f ∈ D above, [f ] R [f ] R gives the same output (see [START_REF] Bouillard | Some examples and counterexamples for (min, +) filtering operations[END_REF]).

Non-decreasing functions f such that f (0) ∈ R are a particular case of plain functions which remain plain under all the Network Calculus operations since the deconvolution preserves the non-decrease [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF].

Proposition 4. The affine functions are closed under +, -, * , , but not under min, max and the subadditive closure.

Proof. It is clear for the addition and the substraction, and when one of the functions is +∞ or -∞ over R + . Then let f 1 and f 2 two affine functions s.t. ∀t ≥ 0,

f i (t) = ρ i t + σ i , ρ i , σ i ∈ R, i = 1, 2, f 1 * f 2 (t) = min 0≤s≤t ((ρ 1 s + σ 1 ) + (ρ 2 (t -s) + σ 2 )) (2) = min(ρ 1 , ρ 2 )t + σ 1 + σ 2 . (3)
Thus the convolution of affine functions remains affine. In the same way, ∀t ∈ N,

f 1 f 2 (t) = sup u≥0 ((ρ 1 (t + u) + σ 1 ) -(ρ 2 u + σ 2 )) (4) = sup u≥0 (ρ 1 t + (ρ 1 -ρ 2 )u + σ 1 -σ 2 ). ( 5
) Thus if ρ 1 ≤ ρ 2 , f 1 f 2 (t) = ρ 1 t + σ 1 -σ 2 which is affine. Otherwise ρ 1 > ρ 2 and f 1 f 2 (t) = ∞ for all t ≥ 0, which is also affine. Let f be an affine function, f (t) = ρt + σ, ρ, σ ∈ R. Then ∀t, s ∈ N, n ∈ N * , f (n) (t) = ρt + nσ. Thus if σ ≥ 0, then f * (0) = 0 and for all t > 0, f * (t) = ρt + σ, it is affine if and only if σ = 0. If σ < 0, then t ≥ 0, f * (t) = -∞.
Figure 5 shows that the minimum of two affine functions is generally not affine. If the growth rates of the functions are close, the rank from which their minimum is affine may be far away.

Proposition 5. Let f 1 , f 2 ∈ F two ultimately affine functions from respectively T 1 and T 2 such that ∀t ≥ T i , f i (t) = ρ i t + σ i , with ρ i , σ i ∈ R. then:

1. min(f 1 , f 2 ) is ultimately affine from T = max(T 1 , T 2 , σ2-σ1
ρ1-ρ2 ) if ρ 1 = ρ 2 and from max(T 1 , T 2 ) otherwise, and its rate is min(ρ 1 , ρ 2 ), 2. max(f 1 , f 2 ) is ultimately affine from T = max(T 1 , T 2 , σ2-σ1 ρ1-ρ2 ) if ρ 1 = ρ 2 and from max(T 1 , T 2 ) otherwise, and its rate is max(ρ 1 , ρ 2 ),

3. f 1 + f 2 is ultimately affine from max(T 1 , T 2 ), with rate ρ 1 + ρ 2 , 4. f 1 -f 2 is ultimately affine from max(T 1 , T 2 ), with rate ρ 1 -ρ 2 , 5. f 1 * f 2 is ultimately affine from T 1 + T 2 if ρ 1 = ρ 2 and from max(T 1 + T 2 , T ) with T = σ1-σ2+inf 0≤u≤T 2 (f2(u)-ρ1s)-inf 0≤s≤T 1 (f1(s)-ρ2s) ρ2-ρ1 if ρ 1 < ρ 2 and in both cases its rate is min(ρ 1 , ρ 2 ) (unless ∃t ≥ 0, f 1 (t) or f 2 (t) = -∞, then it is equal to -∞ from T 1 + T 2 ). 6. f 1 f 2 is ultimately affine from T 1 , with rate ρ 1 (unless ∃t ≥ 0, f 2 (t) = -∞, then it is equal to +∞ from 0).
To deal with functions which are ultimately infinite, consider that

f 1 = +∞ (resp. -∞) from T 1 is equivalent to ρ 1 = +∞ (resp.
-∞), idem for f 2 and apply the cases above. Moreover if f 1 and f 2 are plain, then all the outputs are also plain.

Proof.

1. Suppose first that f 1 and f 2 are both affine:

f i (t) = ρ i t + σ i , i = 1, 2. If ρ 1 = ρ 2
, then there exists a unique point t 0 such that f 1 (t 0 ) = f 2 (t 0 ), and

t 0 = σ2-σ1 ρ1-ρ2 . If ρ 1 = ρ 2 , then min(f 1 , f 2 ) is either f 1 if σ 1 ≤ σ 2 , or f 2 otherwise.
If f 1 and f 2 are ultimately affine, then it is easy to see that min(f 1 , f 2 ) is ultimately affine from T = max(T 1 , T 2 , σ2-σ1 ρ1-ρ2 ) if ρ 1 = ρ 2 or T = max(T 1 , T 2 ) if ρ 1 = ρ 2 . Note that T may be arbitrarily large if ρ 1 and ρ 2 are close.

2. Same as 1.

3. Clear since adding two affine functions remains affine. 4. Same as 3.

Let

t ≥ T 1 + T 2 . Let us calculate f 1 * f 2 (t): f 1 * f 2 (t) = inf 0≤s≤t f 1 (s) + f 2 (t -s) = inf 0≤s≤T1 f 1 (s) + f 2 (t -s) ⊕ inf T1≤s≤t-T2 f 1 (s) + f 2 (t -s) ⊕ inf t-T2≤s≤t f 1 (s) + f 2 (t -s) = inf 0≤s≤T1 (f 1 (s) + f 2 (t -s)) ⊕ inf T1≤s≤t-T2 (f 1 (s) + f 2 (t -s)) ⊕ inf 0≤u≤T2 (f 1 (t -u) + f 2 (u)) = inf 0≤s≤T1 (f 1 (s) + ρ 2 (t -s) + σ 2 ) ⊕ inf T1≤s≤t-T2 (ρ 1 s + σ 1 + ρ 2 (t -s) + σ 2 ) ⊕ inf 0≤u≤T2 (ρ 1 (t -u) + σ 1 + f 2 (u))
The infimum over T 1 ≤ s ≤ t -T 2 of the second term is taken for an affine function. Thus it is reached for s = T 1 or s = t -T 2 , and then it is equal to

f 1 (T 1 ) + f 2 (t -T 1 ) (resp. f 1 (t -T 2 ) + f 2 (T 2 )
) which is larger than the first term (resp. the third term) since it is the value when s = T 1 (resp. s = t -T 2 ) in the infimum over 0 ≤ s ≤ T 1 (resp. t -T 2 ≤ s ≤ t). We can simplify the formula by removing the second term and we have:

f 1 * f 2 (t) = ρ 2 t + σ 2 + inf 0≤s≤T1 (f 1 (s) -ρ 2 s) ⊕ ρ 1 t + σ 1 + inf 0≤u≤T2 (f 2 (u) -ρ 1 u). INRIA Let m 2 = inf 0≤s≤T1 (f 1 (s) -ρ 2 s) and m 1 = inf 0≤u≤T2 (f 2 (u) -ρ 1 u). We have m 1 , m 2 < +∞ since f 1 (T 1 ) = ρ 1 T 1 + σ 1 ∈ R and f 2 (T 2 ) = ρ 2 T 2 + σ 2 ∈ R.
Depending on the comparison between ρ 1 and ρ 2 and the finiteness of m 1 and m 2 , we get a few cases, all leading to an ultimately affine behaviour:

if m 1 or m 2 = -∞, f 1 * f 2 is -∞ from T = T 1 + T 2 , if |m 1 | and |m 2 | < ∞, and ρ 1 = ρ 2 , f 1 * f 2 is ultimately affine with rate ρ 1 = ρ 2 from T = T 1 + T 2 , if |m 1 | and |m 2 | < ∞, and ρ 1 = ρ 2 , suppose w.l.o.g. that ρ 1 < ρ 2 , f 1 * f 2 is ultimately affine with rate ρ 1 from T = max(T 1 + T 2 , T ) with T = σ 1 -σ 2 + inf 0≤u≤T2 (f 2 (u) -ρ 1 s) -inf 0≤s≤T1 (f 1 (s) -ρ 2 s) ρ 2 -ρ 1 . 6. ∀t ≥ T 1 , f 1 f 2 (t) = sup s≥0 (f 1 (t + s) -f 2 (s)) = sup s≥0 (σ 1 + ρ 1 (t + s) -f 2 (s)) = σ 1 + ρ 1 t + sup s≥0 (ρ 1 s -f 2 (s)).
As sup s≥0 (ρ 1 sf 2 (s)) is a constant, f 1 f 2 is ultimately affine from T 1 with a behaviour which depends on the finiteness of sup s≥0 (ρ 1 sf 2 (s)).

To check the preservation of the plain property under (not guaranteed by Proposition 3), we also use that f 2 is ultimately affine. When ρ 1 > ρ 2 , for any fixed t ≥ 0, f 1 (t + s)f 2 (s) → +∞ when s → +∞, and thus (f

1 f 2 )(t) = +∞. Suppose now that ρ 1 ≤ ρ 2 . When t + s ≥ T 1 and s ≥ T 2 , the difference f 1 (t + s) -f 2 (s) = ρ 1 (t + s) + σ 1 -ρ 2 s -σ 2 is non-increasing when s increases. Thus (f 1 f 2 )(t) = sup 0≤s≤max(T2,T1-t) (f 1 (t + s) -f 2 (s)) ∈ R since f 1 and f 2 are plain.
To deal with ultimately infinite functions, apply the same reasonings with straight simplifications and check that the results correspond to the statements of the proposition with ρ 1 or ρ 2 appropriately associated with +∞ or -∞. The statement about plain functions is a consequence of Proposition 3, except for .

Remark 2. The subadditive closure of an ultimately affine function is not always ultimately affine, such an example is presented in [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF], Chapter 3, for some β R,T +K functions defined on R + . Another example is depicted on Figure 6. Let f be the function defined on N by

f (t) = t if t = 0 or 1, t -1 if t ≥ 2
and represented on Figure 6. Then f * is not ultimately affine: an easy computation gives

f * (t) = t/2 if t is even, (t + 1)/2 if t is odd. (6)
One can notice that f * is pseudo-periodic of period 2.

f f * 1 2 3 4 5 t 0 0 1 2 3 4 Figure 6: f is ultimately affine but f * is not.
Before considering pseudo-periodicity, we define a local finiteness property for fonctions in the fluid model.

RR n 6094

Definition 3. A function f ∈ F is locally bounded if f is bounded over any bounded subset of its support.

For instance, this property is not satisfied by f (t) = 1/(1t) on [0, 1[ and = +∞ on [1, +∞[. Piecewise affine functions are an example of locally bounded functions. Proposition 6. Let f 1 , f 2 ∈ F two ultimately plain pseudo-periodic functions from respectively T 1 and T 2 , with respective periods d 1 and d 2 and respective increments c 1 and c 2 . Suppose that they are both locally bounded, that

d 1 /d 2 ∈ Q and that ∀t ≥ T i , f i (t) ∈ R. Then 1. min(f 1 , f 2 ) is locally bounded and ultimately plain pseudo-periodic. If c1 d1 < c2 d2 , then ultimately min(f 1 , f 2 ) = f 1 (period d 1 , increment c 1 ). If c2 d2 < c1 d1 , then ultimately min(f 1 , f 2 ) = f 2 (period d 2 , increment c 2 ). Oth- erwise, the period is d = d 1 ∨ d 2 and the increment is c1 d1 d. 2. max(f 1 , f 2 ) is locally bounded and ultimately plain pseudo-periodic. If c1 d1 < c2 d2 , then ultimately min(f 1 , f 2 ) = f 2 (period d 2 , increment c 2 ). If c2 d2 < c1 d1 , then ultimately min(f 1 , f 2 ) = f 1 (period d 1 , increment c 1 ). Oth- erwise, the period is d = d 1 ∨ d 2 and the increment is c1 d1 d. 3. f 1 + f 2 is locally bounded and ultimately plain pseudo-periodic from T = max(T 1 , T 2 ), with period d = d 1 ∨ d 2 , and increment c = ( c1 d1 + c2 d2 )d, 4. f 1 -f 2 is locally bounded and ultimately plain pseudo-periodic from T = max(T 1 , T 2 ), with period d = d 1 ∨ d 2 , and increment c = ( c1 d1 -c2 d2 )d, 5. f 1 * f 2 is
locally bounded and ultimately plain pseudo-periodic with period d = d 1 ∨ d 2 and increment min( c1 d1 , c2 d2 )d. 6. f 1 f 2 is locally bounded and ultimately plain pseudo-periodic from T 1 with period d 1 and increment c 1 .

To deal with functions which are ultimately infinite, consider that

f 1 = +∞ (resp. -∞) from T 1 is equivalent to c 1 = +∞ (resp.
-∞), idem for c 2 and apply the cases above. Moreover if f 1 and f 2 are plain, then all the outputs are also plain.

Proof. Let f 1 and f 2 be two ultimately plain pseudo-periodic functions such that ∀t ≥ T

i , f i (t+d i ) = f i (t)+c i , i ∈ {1, 2}. Let d = d 1 ∨ d 2 , c 1 = c1 d1 d and c 2 = c2 d2 d.
The functions f 1 and f 2 are both ultimately pseudo-periodic of period d and with respective increment c 1 and c 2 .

1. First ∀t ≥ max(T 1 , T 2 ), f i (t + d) = f i (t) + c i and min(f 1 , f 2 )(t + d) = min(f 1 (t + d), f 2 (t + d)) = min(f 1 (t) + c 1 , f 2 (t) + c 2 ). If c 1 = c 2 , then ∀t ≥ max(T 1 , T 2 ), min(f 1 , f 2 )(t + d) = min(f 1 , f 2 )(t) + c 1 .
It is clear that min(f 1 , f 2 ) remains locally bounded and ultimately plain like f 1 and f 2 (note that in this case, we did not use those hypotheses to prove the ultimate pseudo-periodicity).

Otherwise, suppose without loss of generality that

c 1 < c 2 . Let M 1 = sup T1≤t<T1+d1 (f 1 (t) -ρ 1 t) with ρ 1 = c1 d1 = c 1 d , then M 1 < +∞ since f 1 is locally bounded and finite from T 1 . We have ∀t ≥ T 1 , f 1 (t) ≤ ρ 1 t + M 1 . Let m 2 = inf T2≤t<T2+d2 (f 2 (t) -ρ 2 t), then m 2 > -∞ and ∀t ≥ T 2 , f 2 (t) ≥ ρ 2 t + m 2 . As soon as t ≥ max(T 1 , T 2 ) and ρ 1 t+M 1 ≤ ρ 2 t+m 2 , that is to say t ≥ T = M1-m2 ρ2-ρ1 , we have min(f 1 (t), f 2 (t)) = f 1 (t). Thus min(f 1 , f 2 ) is ultimately plain and pseudo-periodic from max(T 1 , T 2 , T ). It is also clearly locally bounded.
As a complement, note that if c 1 ≤ c 2 , another way to ensure that min(f 1 , f 2 ) is locally bounded, ultimately plain and pseudo-periodic, is to keep locally bounded and pseudo-periodicity assumptions on inputs but suppose that only f 1 is ultimately plain with ∀t ≥ T 1 , f 1 (t) ∈ R and that f 2 is not necessarily ultimately plain (it may have +∞ values from

T 2 ) but ∀t ≥ T 2 , f 2 (t) = -∞. If c 1 = c 2 ,
the minimum is still clearly plain and pseudo-periodic from max(T 1 , T 2 ). If c 1 < c 2 , then proceed exactly as above (we still have M 1 < +∞ and m 2 > -∞) and remark that min(f 1 , f 2 ) is clearly ultimately plain from T 1 .

2. Same as 1.

INRIA 3. ∀t ≥ max(T 1 , T 2 ), (f 1 + f 2 )(t + d) = f 1 (t + d) + f 2 (t + d) = f 1 (t) + c 1 d 1 d + f 2 (t) + c 2 d 2 d = (f 1 + f 2 )(t) + ( c 1 d 1 + c 2 d 2 )d.
Moreover being locally bounded and ultimately plain is clearly preserved for +.

4. Same as 3. except that the increment is ( c1 d1 -c2 d2 )d.

First decompose each function into a transient part and a pseudo-periodic part, namely

f 1 = f 1 ⊕ f 1
where f 1 = f 1 on [0, T 1 [ and = +∞ elsewhere, and

f 1 = f 1 on [T 1 , +∞[ and = +∞ elsewhere. The function f 2 is decomposed in the same way into f 2 = f 2 ⊕ f 2 with respect to T 2 . Then f 1 * f 2 = f 1 * f 2 ⊕ f 1 * f 2 ⊕ f 1 * f 2 ⊕ f 1 * f 2 .
The first term f 1 * f 2 is clearly equal to +∞ from T 1 + T 2 . The second term can be written for all t ≥ 0,

f 1 * f 2 (t) = inf 0≤s<T1 (f 1 (s) + f 2 (t -s)). When t ≥ T 1 + T 2 , if 0 ≤ s < T 1 , then t -s ≥ T 2 , thus f 1 * f 2 (t + d 2 ) = inf 0≤s<T1 (f 1 (s) + f 2 (t + d 2 -s)) = inf 0≤s<T1 (f 1 (s) + f 2 (t -s)) + c 2 = f 1 * f 2 (t) + c 2 .
The function f 1 * f 2 is pseudo-periodic from T 1 + T 2 with period d 2 and increment c 2 . The symmetrical result holds for

f 1 * f 2 .
To study the last term, let t ≥ T 1 + T 2 + d (this bound is necessary for the second equality below), then

f 1 * f 2 (t + d) = inf T1≤s≤t+d-T2 (f 1 (s) + f 2 (t + d -s)) = inf T1≤s≤t-T2 (f 1 (s) + f 2 (t + d -s)) ⊕ inf T1+d≤s≤t+d-T2 (f 1 (s) + f 2 (t + d -s)) = inf T1≤s≤t-T2 (f 1 (s) + f 2 (t + d -s)) ⊕ inf T2≤u≤t-T1 (f 1 (t + d -u) + f 2 (u)) = inf T1≤s≤t-T2 (f 1 (s) + f 2 (t -s) + c 2 ) ⊕ inf T2≤u≤t-T1 (f 1 (t -u) + f 2 (u) + c 1 ) = min(f 1 * f 2 (t) + c 2 , f 1 * f 2 (t) + c 1 ) = f 1 * f 2 (t) + min(c 1 , c 2 ) Thus f 1 * f 2 is pseudo-periodic from T 1 + T 2 + d, with period d and increment min(c 1 , c 2 ).
Now we state that these four terms are locally bounded. Since f 1 and f 2 are locally bounded, f 1 , f 1 , f 2 , f 2 are also locally bounded. Then remark that the convolution f * g of two locally bounded functions f, g is always locally bounded. Let A ∈ R + , ∀t ∈ [0, A], f * g(t) only depends on the restriction of f and g on

[0, A] for which ∃M f , M g ∈ R + such that f (s) ∈ R =⇒ |f (s)| ≤ M f and g(s) ∈ R =⇒ |g(s)| ≤ M g . Thus ∀t ∈ [0, A], f * g(t) ∈ R =⇒ |f * g(t)| ≤ M f + M g .
It applies to our four terms which are consequently locally bounded.

Next it can be easily checked from their definitions as infima that the four terms are ultimately plain. It ensures that their minimum is ultimately plain and pseudo-periodic: f 1 * f 2 is ultimately plain pseudoperiodic with period d and increment min(c 1 , c 2 ).

As a complement, note that to preserve the ultimate pseudo-periodicity, we only need one input function to be ultimately plain as shown now. Suppose that f 1 is ultimately plain from T 1 (here possibly ∈ R or = +∞ or = -∞), but that f 2 is not necessarily ultimately plain. We first dismiss the case treated in Lemma 1 when

∃a ∈ R + , f 1 (a) = -∞ or f 2 (a) = -∞, both leading to f 1 * f 2 = -∞ from a, i.e.
an ultimately plain pseudo-periodic output. In the reasoning, the first term f 1 * f 2 is still equal to +∞ from T 1 + T 2 , and we consider two cases depending of f 1 which represents the ultimate behaviour of f 1 :

If f 1 = +∞ all over R + , then f 1 * f 2 = f 1 * f 2 = +∞ all over R + . Since f 1 * f 2 = +∞ from T 1 + T 2 , we have f 1 * f 2 = f 1 * f 2 from T 1 + T 2
which is ultimately pseudo-periodic with period d 2 and increment c 2 . But it is not necessarily ultimately plain (e.g. choose f 1 (t) = 0 if t = 0 and = +∞ otherwise, and f 2 (t) = t if t is an even integer and = +∞ otherwise, and then

f 1 * f 2 = f 2 ). If f 1 (t) ∈ R from T 1 , then either ∃a ≥ T 2 , f 2 (a) ∈ R or f 2 = +∞ all over R + . In the first case, f 1 * f 2 is ultimately plain with values in R from T 1 + a.
Since it is ultimately pseudo-periodic with period d and increment min(c 1 , c 2 ), whereas f 1 * f 2 and f 1 * f 2 are ultimately pseudo-periodic with same period but larger increments (resp. c 2 and c 1 ), their minimum is ultimately plain and pseudoperiodic (see the complement in the study of the minimum). In the second case when

f 2 = +∞ all over R + , f 1 * f 2 = f 1 * f 2 from T 1 + T 2
which is also clearly ultimate plain and pseudo-periodic.

6. ∀t ≥ T 1 ,

f 1 f 2 (t + d 1 ) = sup s≥0 (f 1 (t + d 1 + s) -f 2 (s)) = sup s≥0 (f 1 (t + s) + c 1 -f 2 (s)) = c 1 + sup s≥0 (f 1 (t + s) -f 2 (s)) = c 1 + f 1 f 2 (t).
So we get the ultimate pseudo-periodicity just by using the ultimate pseudo-periodicity of f , in particular no assumption on g is necessary. On the contrary, remaining locally bounded and plain or ultimately plain requires some further assumptions of the proposition.

Remark that if c 1 > c 2 , then ∀t ∈ R + , f 1 f 2 (t) = +∞. Otherwise if c 1 ≤ c 2 , then ∀t ∈ [0, T 1 + d 1 [, sup s≥0 (f 1 (t + s) -f 2 (s)) is clearly reached when s ≤ max(T 1 , T 2 ) + d = T . It first implies that if f 1 and f 2 are locally bounded then f 1 f 2 is bounded on its support in [0, T 1 + d 1 [
. Thanks to pseudo-periodicity, it extends to any bounded part of the support and f 1 f 2 is locally bounded. In addition, since the supremum is reached over [0, T ] which does not depend on T and thanks to pseudo-periodicity, f 1 f 2 is ultimately plain (resp. plain) as soon as f 1 is ultimately plain (resp. plain).

To deal with ultimately infinite functions, apply the same reasonings with straight simplifications and check that the results correspond to the statements of the proposition with increments appropriately associated with +∞ or -∞. The statement about plain functions is a consequence of Proposition 3, except for . Note that all the values of ranks considered in the proof still apply if we use ranks with strict inequalities as in their initial definition, i.e. if we start with

f i (t) ∈ R and f i (t + d i ) = f i (t) + c i , ∀t > T i instead of ∀t ≥ T i .
Remark 3. A careful look shows that preserving pseudo-periodicity under min and max, requires in general that both functions are locally bounded and ultimately plain. For instance f 1 (t) = 1 1-(tt ) and f 2 (t) = t are both plain and pseudo-periodic but f 1 is not locally bounded and min(f 1 , f 2 ) is not ultimately pseudo-periodic. Moreover let f 1 (t) = t on all intervals ]2n, 2n + 1], n ∈ N, and = +∞ elsewhere, and f 2 (t) = 2t on R + , they are both locally bounded and pseudo-periodic but f 1 is not ultimately plain and min(f 1 , f 2 ) is not ultimately pseudo-periodic.

The convolution requires in general that at least one input function is ultimately plain to ensure the pseudoperiodicity. Consider in the discrete model the functions f 1 (t) = 2t if t is even and = +∞ otherwise, and f 2 (t) = t if t is odd, = 0 if t = 0 and = +∞ otherwise. They are both ultimately pseudo-periodic, but f 1 * f 2 (t) = 2t if t is even and = t if t is odd, which is not ultimately pseudo-periodic. Interpolate as in Proposition 1 to get a fluid version.

If we restrict all the previous results to functions in D, we can almost state our first stability result. The next proposition achieves that for the last operation, namely the subadditive closure. Note that its proof is specially designed for functions in D. In Subsection 3.2, we will propose another proof for the fluid model yielding the result in D as a corollary. The two proofs are essentially different, so we choose to keep them both. Proposition 7. Let f ∈ D be an ultimately pseudo-periodic function, then f * is ultimately pseudo-periodic.

Proof. Let f ∈ D be an ultimately pseudo-periodic function such that ∀t ≥ T , f (t + d) = f (t) + c, with c ∈ R.
This includes the ultimately affine functions in D, which have period 1. We dismiss the cases when f (0) < 0 or when f = +∞ over all N, for which the result is clear. The subadditive closure f * is given by Equation 1:

f * (t) = min k∈N min t 1 + • • • + t k = t, t 1 , . . . , t k ∈ N * f (t 1 ) + • • • + f (t k ).
The idea of the proof is to use the (min, +) matrix theory. We first build a directed weighted graph G = (N, A, W ) in the following way:

N = {1, • • • , T + d -1} is the set of vertices;
INRIA ∀i ∈ {1, . . . , T + d -2} put an arc from node i to node i + 1 of weight 0 (i.e. W (i, i + 1) = 0); ∀i ∈ N , put an arc from node i to node 1 of weight f (i) (i.e. W (i, 1) = f (i)); put an arc from node

T + d -1 to node T of weight c (i.e. W (T + d -1, T ) = c).
The construction is illustrated by Figure 7. The graph G is strongly connected and if we only consider arcs with weight < +∞, the new graph either remains G if ∃t ≥ T , f (t) < +∞, or has an unique strongly connected component on nodes {1, . . . , T 0 } where T 0 = min{t 0 | ∀t > t 0 , f (t) = +∞}. Let i ∈ N, by construction, there is exactly one path from node 1 to itself of length i that does not visit node 1 except at the beginning and at the end of the path. The weight of that path is f (i). Now, consider a path from node 1 to itself. That path is an union of paths from 1 to itself. If the length of that path is t, there exists a decomposition of t, t

c 0 1 2 T 0 0 0 0 T+d-1 f (1) f (T ) f (T + d -1) f (2)
= t 1 + • • • + t k such that the weight of the path is f (t 1 ) + • • • + f (t k ).
Conversely, for every t 1 , . . . , t k , there is a path from 1 to itself of length

t 1 + • • • + t k of weight f (t 1 ) + • • • + f (t k ).
Let A be the (min,+) matrix associated to G (i.e. A i,j = min(+∞, W (i, j))). The matrix A is irreducible (or has a unique irreducible submatrix containing coefficient 1,1) and for every t ∈ N, f * (t) = A t 1,1 . Let d * be its cyclicity and λ be its unique (min,+) eigenvalue. According to the Fundamental Theorem of the (min,+) matrices [START_REF] Baccelli | Synchronization and Linearity[END_REF] (Section 3.7, page 143-151), there exists a rank

T * such that ∀t ≥ T * , A t+d * = A t + λd * . Then, f * (t + d * ) = f * (t) + λd * = f * (t) + c * with c * = λd * . Then f * is ultimately pseudo-periodic of period d * and increment c * .
More precisely, the eigenvalue λ = c * /d * of A is the minimal average weight of a circuit of G. By construction, this is equal to min(c/d, min 1≤t≤T +d-1 f (t)/t) (note that it is also inf t∈N * f (t)/t). Consider the vertices and edges of the circuits achieving λ. . In this later case, one can give a tighter period for f * by proving that gcd(S) works. It is known that if an ultimately pseudo-periodic function admits two periods d 1 and d 2 (possibly from different ranks), then it also admits d 1 ∧ d 2 as a period. Thus it is sufficient to prove that for all s ∈ S, f * admits s as a period. Let s ∈ S, then by definition ∀t ≥ 0,

f * (t + s) ≤ f * (t) + f (s) = f * (t) + λs. Since s divides d * = lcm(d, gcd(S)), we have ∀t ≥ 0, f * (t) ≥ f * (t + s) -λs ≥ f * (t + 2s) -2λs ≥ • • • ≥ f * (t + d * ) -λd * . When t ≥ T * , f * (t + d * ) = f * (t) + λd * which
means that all these inequalities are equalities. It implies that ∀t ≥ T * , f * (t + s) = f * (t) + λs and thus s is a period of f * . Computational considerations will be discussed in Subsection 4.7. Now we can state our first stability theorem: it is a direct consequence of Proposition 3, Proposition 6 and Proposition 7 for the discrete model. Theorem 1. The class of plain ultimately pseudo-periodic functions of D is stable under the Network calculus operations, that is +, -, min, max, * , and the subadditive closure.

Remark 4. Weakening the property plain by ultimately plain does not ensure that compositions will preserve the ultimate pseudo-periodicity. As a mix of previous remarks, let f (t) = 0 if t = 2 and = +∞ elsewhere, and g(t) = 3 if t = 3 and = +∞ elsewhere, which are both ultimately plain. Then

min(f * , g * )(t) =    0 if t = 6k, 6k + 2 or 6k + 4, k ∈ N t if t = 6k + 3, k ∈ N +∞ otherwise.
This function is not ultimately pseudo-periodic.

A careful look at previous references reveals that an important part of this theorem, namely the stability under min, * and the subadditive closure, was already known for some non-decreasing functions, but mainly stated in terms of (γ, δ) formal power series, and in a (max, +) framework instead of (min, +) which has no consequence on the result. Those power series are for instance used to describe precisely the dynamics of some Petri nets. The reader is referred to Baccelli et al's book [START_REF] Baccelli | Synchronization and Linearity[END_REF]: Theorem 5.39, page 255, involves the stability result for non-decreasing functions from N into N. Some extensions are also given in Chapter 6, like Theorem 6.32, Remark 6.33 and Corollary 6.34, page 290-291, which imply stability results for some non-decreasing fluid functions. For detailed proofs and algorithmic design, see also Gaubert's thesis [START_REF] Gaubert | Théorie Linéaire des Systèmes dans les Dioïdes[END_REF]. Even if the underlying mathematics are the same, it is not clear for us yet whether the stability of non-decreasing functions from N into R (under min, * and the subadditive closure) or the stability without imposing non-decrease can be directly deduced from all these theorems and proofs. We will mention in Subsection 3.2 the extensions to fluid functions presented in [START_REF] Baccelli | Synchronization and Linearity[END_REF].

Stability of some piecewise affine classes

Whereas in the discrete model, the combination of functions in D clearly outputs (when defined) a function in D (meaning that D is closed under Network Calculus operations), such a result needs a proof for piecewise affine functions of the fluid model. Proof. Trivial. Just observe that two affine functions from Q + into Q intersect at a rational point.

The class F[Q + , R] is also stable under +, -. However it is false under min or max, e.g. consider ∀t ∈ R + , f (t) = √ 2t and g(t) = 1, both f and g belong to

F[Q + , R] but min(f, g)(t) = √ 2t on [0, 1/ √ 2] and = 1 on ]1/ √ 2, +∞[ does not belong to F[Q + , R] because 1/ √ 2 ∈ Q + .
Definition 4 (Spots and segments). Iterated segments and spots are the ultimately pseudo-periodic versions of segments and spots. Any piecewise affine function can be decomposed into spots and segments. Definition 5. Let f ∈ F[R + , R] with jump points (a n ) n∈N . Let f 2n+1 be the segment of support ]a n , a n+1 [, n ≥ 0 that is equal to f on that interval and f 2n be the spot on a n with value f (a n ). Then, f = inf n∈N f n . We call the sequence (f n ) n∈N the elementary decomposition of f . That decomposition is very useful to show the stability of the piecewise affine functions by the Network Calculus operations.

¡ For a ∈ R + , a function f ∈ F is a spot on a if ∀t ∈ R + -{a}, f (t) = +∞ and f (a) = +∞. ¡ For a, b ∈ R + , a < b, a function f ∈ F is a segment on ]a, b[ if ∃σ, ρ ∈ R such that f (t) = ρ(t -a) + σ if t ∈]a
f 1 * f 2 is a spot on a + b and f 1 * f 2 (a + b) = f 1 (a) + f 2 (b).
Lemma 3 (Convolution of a spot and a segment). Let f 1 be a segment on ]a, b[ and f 2 be a spot on c. Then,

f 1 * f 2 is a segment on ]a + c, b + c[ and ∀t ∈]a, b[, f 1 * f 2 (c + t) = f 1 (t) + f 2 (c). Proof. By definition, f 1 * f 2 (t) = inf 0≤s≤t f 1 (s)+f 2 (t-s). As f 2 is a spot, f 2 (t-s) = ∞ if and only if t-s = c, that of s = t -c. As a consequence, f 1 * f 2 (t) = f 1 (t -c) + f 2 (c), which is finite if and only if t ∈]a + c, b + c[.
Lemma 4 (Convolution of segments [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF]). Let f 1 , f 2 ∈ F be two segments on respectively ]a, b[ and ]c, d[ with respective slopes ρ 1 and ρ 2 such that

ρ 1 ≤ ρ 2 . Then f 1 * f 2 is equal to +∞ outside ]a + c, b + d[. Otherwise, ∀t ∈]0, b + d -a -c[, f 1 * f 2 (a + c + t) = f 1 (a+) + f 2 (c+) + ρ 1 t if t ≤ b, f 1 (a+) + f 2 (c+) + ρ 1 b + ρ 2 (t -b) if t > b.
Geometrically, it means that the segments representing f 1 and f 2 are concatenated by increasing slopes (see Figure 8).

Proof. By definition, f 1 * f 2 (t) = inf 0≤s≤t (f 1 (s) * f 2 (t -s)). Then f 1 * f 2 (t) is different from +∞ if and only if there exists s such that f 1 (s) = +∞ and f 2 (t -s) = +∞, which means s ∈]a, b[ and t -s ∈]c, d[. The support of f 1 * f 2 is thus ]a + c, b + d[. Let t ∈]a + c, b + d[. Then, f 1 * f 2 (t) = inf 0≤s≤t f 1 (s) + f 2 (t -s) = inf max(a,t-d)≤s≤min(b,t-c) [f 1 (a+) + ρ 1 (s -a) + f 2 (c+) + ρ 2 (t -s -c)] = f 1 (a+) + f 2 (c+) -ρ 1 a -ρ 2 c + ρ 1 min(b, t -c)
As a consequence, Proof. A consequence of Lemma 4 is that the convolution of two segments of

f 1 * f 2 (t) = f 1 (a+) + f 2 (c+) + ρ 1 (t -a -c) if t ≤ b + c f 1 (a+) + f 2 (c+) + ρ 1 (b -a) + ρ 2 (t -b -c) otherwise.
F[R + , R] (resp. F[Q + , Q]) is piecewise affine in F[R + , R] (resp. F[Q + , Q]). Let f, g be two functions in F[R + ,

Stability for the deconvolution

Let f be a segment or a spot and define f as the function equal to f on its support and to -∞ elsewhere. For a piecewise affine function with an elementary decomposition into segments and spots f = inf n∈N f n , one can associate the other decomposition f = sup n∈N fn .

Lemma 5 (Deconvolution of spots). Let f 1 and f 2 be two spots respectively on a and b.

If a ≥ b, then f1 f 2 is a spot on a -b and f1 f 2 (a -b) = f 1 (a) -f 2 (b). If a < b, then f1 f 2 (t) = -∞, ∀t ∈ R + .
Lemma 6 (Deconvolution of a segment and a spot). Let f 1 be a segment on ]a, b[ with slope ρ and f 2 be a spot on c. Then,

f1 f 2 is a segment on ]a -c, b -c[∩R + where f1 f 2 (t) = ρ(t -a) + f 1 (a+) -f 2 (c). Proof. By definition, f1 f 2 (t) = sup s≥0 f1 (t + s) -f 2 (s). As f 2 is a spot on c, f1 f 2 (t) = f 1 (t + c) -f 2 (c). Then, f1 f 2 (t) is finite if and only if t+c ∈]a, b[ thus the support of f1 f 2 is ]a-c, b-c[∩R + . Let t ∈]a-c, b-c[, then f1 f 2 (t) = f 1 (t + c) -f 2 (c) = ρ(t -a) + f 1 (a+) -f 2 (c).
Lemma 7 (Deconvolution of a spot and a segment). Let f 1 be a spot on a and f 2 be a segment on ]b, c[ with slope ρ. Then,

f1 f 2 is a segment on ]a -c, a -b[∩R + where f1 f 2 (t) = f 1 (a) -f 2 (b+) + ρ(t + b -a). Proof. By definition, f1 f 2 (t) = sup s≥0 f1 (t + s) -f 2 (s). As f 1 is a spot on a, f1 f 2 (t) = f 1 (a) -f 2 (a -t). Then f1 f 2 (t) is finite if and only if a -t ∈]b, c[ and the support is ]a -c, a -b[. Let t ∈]a -c, a -b[. Then, f1 f 2 (t) = f 1 (a) -f 2 (a -t) = f 1 (a) -ρ(a -t -b) -f 2 (b+) = f 1 (a) -f 2 (b+) + ρ(t + b -a).
Lemma 8 (Deconvolution of segments). Let f 1 and f 2 be two segments respectively defined on ]a, b[ and ]c, d[ with respective slopes ρ 1 and ρ 2 . Then, f1

f 2 has support ]a -d, b -c[∩R + and, if ρ 1 ≥ ρ 2 , f1 f 2 (t) =    f 1 (t + d) -f 2 (d-) if a -d < t ≤ b -d f 1 (b-) -f 2 (b -t) if b -d ≤ t < b -c -∞ otherwise and if ρ 1 ≤ ρ 2 , f1 f 2 (t) =    f 1 (a+) -f 2 (a -t) if a -d < t ≤ a -c f 1 (t + c) -f 2 (c+) if a -c ≤ t < b -c -∞ otherwise .
Graphically, the deconvolution of two segments is the concatenation of them in decreasing slopes, starting from point (ad, f 1 (a)f 2 (d)) (see Figure 9).

Proof. We denote σ 1 = f 1 (a+) and σ 2 = f 2 (c+). We have f1 f 2 (t) = sup s≥0 ( f1

(t + s) -f 2 (s)). So, f1 f 2 (t) = -∞ if and only if ∃s ∈]c, d[ such that t + s ∈]a, b[, i.e. t ∈]a -d, b -c[. Let t ∈]a -d, b -c[, then, f1 f 2 (t) = sup s∈R+ ( f1 (t + s) -f 2 (s)) = sup(ρ 1 (t + s -a) + σ 1 -ρ 2 (s -c) -σ 2 | s ∈] max(c, a -t), min(d, b -t)]) = σ 1 -σ 2 + ρ 1 (t -a) + ρ 2 c + sup((ρ 1 -ρ 2 )s | s ∈] max(c, a -t), min(d, b -t)]). If ρ 1 ≥ ρ 2 , then f1 f 2 (t) = σ 1 -σ 2 + ρ 1 (t -a)ρ 2 c + (ρ 1 -ρ 2 ) min(d, b -t). If t ≤ b -d, f1 f 2 (t) = σ 1 -σ 2 + ρ 1 (t -a) + ρ 2 c + (ρ 1 -ρ 2 )d = f 1 (t + d) -f 2 (d-). If t ≥ b -d, f1 f 2 (t) = σ 1 -σ 2 + ρ 1 (t -a) + ρ 2 c + (ρ 1 -ρ 2 )(b -t) = f 1 (b-) -f 2 (b -t). If ρ 1 ≤ ρ 2 , then f1 f 2 (t) = σ 1 -σ 2 + ρ 1 (t -a) + ρ 2 c + (ρ 1 -ρ 2 ) max(c, a -t). If t ≤ a -c, f1 f 2 (t) = σ 1 -σ 2 + ρ 1 (t -a) + ρ 2 c + (ρ 1 -ρ 2 )(a -t) = f 1 (a+) + f 2 (a -t). If t ≥ a -c, f1 f 2 (t) = σ 1 -σ 2 + ρ 1 (t -a) + ρ 2 c + (ρ 1 -ρ 2 )c = f 1 (t + c) -f 2 (c+).
Proposition 10. The class of the ultimately pseudo-periodic functions in

F[Q + , Q] is stable under the decon- volution. INRIA d b c a u v x y f g a -d b -c f g a -c b -d or u -y
Proof. Let f, g ∈ F[Q + , Q] be two ultimately pseudo-periodic functions such that ∀t ≥ T f (resp. T g ), f (t+d f ) = f (t) + c f (resp. g(t + d g ) = g(t) + c g ).
The reasoning follows the study of the deconvolution in Proposition 6.

It has already been proved there that f g is ultimately pseudo-periodic from T f , with period d f (even if f and g are not plain or ultimately plain). It remains to show that f g is piecewise affine on [0,

T f + d f [. First remark that if c g /d g < c f /d f , then ∀t ∈ R + , f g(t) = +∞. Otherwise if c f /d f ≤ c g /d g , then ∀t ∈ [0, T f + d f [, sup s≥0 (f (t+s)-g(s)) is reached over 0 ≤ s ≤ max(T f , T g )+d f ∨d g = T . So, to compute f g| [0,T f +d f [ , f
and g can be replaced by two ultimately affine functions f and g having the same values up to respectively T + T f + d f and T , from which they are respectively equal to -∞ and +∞. These functions have finite decompositions into spots and segments f = sup 0≤n≤n0 fn and g = inf 0≤m≤m0 g m . Over [0,

T f + d f [, f g = f g = sup n,m fn g m .
By using the four elementary lemma combining spots and segments (Lemma 5, 7, 6, 8), f g is clearly piecewise affine. By pseudo-periodicity, f g is thus piecewise affine over R + .

Remark 6. Without the ultimate pseudo-periodicity and unlike the other operations (the subadditive closure is treated in the next subsection), the classes F[R + , R] and F[Q + , Q] are not stable under the deconvolution. As proved in [START_REF] Bouillard | Some examples and counterexamples for (min, +) filtering operations[END_REF], let h be any

C 1 convex function over [0, 1], there exist f, g ∈ F[N, R] such that h = f g on [0, 1]. Moreover when considering ultimately pseudo-periodic functions f, g ∈ F[R + , R], if d f /d g ∈ Q (e.g. if f, g ∈ F[Q + , R]
) then all the reasoning of the preceding proof works and

f g ∈ F[R + , R]. However if d f /d g ∈ Q,
some pathological cases may occur leading to an output which is not piecewise affine any longer (see [START_REF] Bouillard | Some examples and counterexamples for (min, +) filtering operations[END_REF]). Proof. It is a direct corollary of the preceding proposition (since ultimately affine functions are ultimately pseudo-periodic for any positive period) and of Proposition 5 ensuring the stability of ultimately affine functions under the deconvolution.

Another way to prove the result is to decompose directly both functions with a finite set of spots and segments by allowing a semi-infinite segment for each function (i.e. segments with supports ]T f , +∞[ and ]T g , +∞[) and then note that Lemma 6, 7 and 8 can be easily reformulated to take into account semi-infinite segments and provide the same kind of output.

Stability for the subadditive closure

We first consider the subadditive closure of spots and iterated spots before focussing on segments and iterated segments, and we end by stating the stability results.

In some cases, we will use the following version of the Frobenius lemma:

Lemma 9 ([24, 27]). Let a 1 , . . . , a n ∈ Q + , there exists T ∈ Q + such that (Na 1 + • • • + Na n ) ∩ [T, +∞[= T + (a 1 ∧ . . . ∧ a n )N.
The infimum of such values T also satisfies this relation, it is denoted F rob(a 1 , . . . , a n ).

When n = 2, F rob(a 1 , a 2 ) = a 1 ∨ a 2 -a 1 -a 2 + a 1 ∧ a 2 .
Lemma 10. The subadditive closure of a spot f on 0 is a spot on 0 with f * (0) = 0 if f (0) ≥ 0 and f * (0) = -∞ otherwise. The subadditive closure of a spot f on a = 0 is the function such that f * (ia) = if (a), ∀i ∈ N and f * (t) = +∞ elsewhere.

Lemma 11. Let f ∈ F be an iterated spot from T with period d and increment c. Then for all k ∈ N * , f (k) is an iterated spot from kT with period d and increment c. The subadditive closure of f ∈ F[Q + , Q] is ultimately pseudo-periodic and can be explicitely computed.

Proof. The first part of the lemma follows from the definition of the convolution:

for k ∈ N * , ∀t ∈ R + , f (k) (t) = inf{f (t 1 ) + • • • + f (t k ) | t 1 , • • • , t k ∈ R + , t 1 + • • • + t k = t}. We have f (t 1 ) + • • • + f (t k ) = +∞ if and only if ∀ 1 ≤ j ≤ k, ∃i j ∈ N, t j = T + i j d, which implies that t ∈ {kT + id, i ∈ N}. Then, f (t 1 ) + • • • + f (t k ) = kf (T ) + (t -kT )c/d
, which does not depend on the decomposition. We now show how to compute explicitely the subadditive closure. We dismiss the case when T = 0 and f (T ) < 0 treated in Lemma 1. Let us consider three cases:

f (T ) T
> c d : we show that there exists β ∈ N * such that for all k ≥ 0, f (k+β) > f (k+1) . Since T, d ∈ Q + , there exist α, β ∈ N such that T + αd = βT , i.e. α β-1 = T d . To get the smallest β, choose β -1 as the smallest denominator of the fraction T d , which can be also written β -1 = d T ∧d . Then we have f (T + αd) = f (T ) + αc = +∞ and f (β) (βT ) = βf (T ) = f (T ) + αdf (T )/T = +∞. As f (T )/T > c/d, f (T + αd) < f (β) (βT ) and more generally f (k+1) (T + αd) < f (k+β) (βT ) for all k ≥ 0. Consequently f * = min k∈{0,...,β-1} f (k) , which is ultimately pseudo-periodic from (β -1)T with period d and increment c (like the β functions of this minimum).

f (T ) T

< c d : as in the previous case, take α, β ∈ N such that T + αd = βT . The smallest α satisfying this relation is T T ∧d . For k ∈ N * and i ∈ N, denote by f k,i the spot valued kf (T ) + ic at kT + id. Then f (k) = inf i≥0 f k,i , and if we define g i = inf k≥1 f k,i for i ≥ 0, we have f * = f (0) ⊕ inf i≥0 g i . The functions g i are iterated spots with period T and increment f (T ) from rank T + id. Since f (T )/T < c/d, we have f (T + αd) = f (T ) + αc > f (T ) + αdf (T )/T = f (β) (βT ), in other words f 1,α > f β,0 . More generally, it can be checked that f k+1,α+i > f k+β,i for all k, i ≥ 0. Thus g α+i > g i and f * = f (0) ⊕ min i∈{0,...,α-1} g i . Like all the functions in this infimum, f * is ultimately pseudo-periodic with period T and increment f (T ) from T + (α -1)d = βTd.

f (T ) T = c d : we know that the support of f * is {kT + id, i ∈ N, k ∈ N * } = T + NT + Nd,

and for any decomposition

t = t 1 + • • • + t k with t i ∈ T + Nd, we have f (t 1 ) + • • • + f (t k ) = kf (T ) + (t -kT )c/d = tc/d which is independent from the decomposition. Thus f * (t) = t c
d on its support, and due to Frobenius Lemma 9, f * is ultimately pseudo-periodic with period T ∧d and increment c d (T ∧d) from rank F rob(T, d).

Applying i times Lemma 4 on a segment gives the following lemma.

Lemma 12. Let i ∈ N * and f ∈ F be the segment on ]a, b[ with parameters σ, ρ. Then f (i) is the segment on ]ia, ib[ with parameters iσ, ρ.

The next lemma gives an explicit formula for the subadditive closure of a segment.

Lemma 13. Let f ∈ F be the segment on ]a, b[ with parameters σ, ρ.

If a = 0 and f (a+) < 0, then f * = -∞ over R + . If f (a+)/a ≤ f (b-)/b, then f * is ultimately plain and pseudo-periodic with period a and increment f (a+) = σ, from rank a( a/(ba) + 1). More precisely, f * (0) = 0 and on any interval ]ia, (i + 1)a], i ∈ N,

f * = f (i) i.e. ∀t ∈]0, a], f * (ia + t) =      if (a+) + ρt if i > a/(b -a) , if (a+) + ρt if i ≤ a/(b -a) and t < i(b -a), +∞ if i ≤ a/(b -a) and t ≥ i(b -a).
If f (a+)/a > f (b-)/b, then f * is ultimately plain and pseudo-periodic with period b and increment f (b-) = σ + ρ(ba), from rank b( a/(ba) + 1). More precisely, on any interval

[(i -1)b, ib[, i ∈ N * , f * = f (i) i.e. ∀t ∈]0, b], f * (ib -t) =      if (b-) -ρt if i > a/(b -a) + 1, if (b-) -ρt if i ≤ a/(b -a) + 1 and t < i(b -a), +∞ if i ≤ a/(b -a) + 1 and t ≥ i(b -a).
Proof. The case a = 0 and f (0+) < 0 is simple and treated in Lemma 1. The case a = 0 and f (a+) = 0 leads to f * (t) = ρt, ∀t ∈ R + , but it can be seen as a particular case of f (a+)/a ≤ f (b-)/b. The case a = 0 and f (a+) > 0 is part of the case when f (a+)/a > f (b-)/b. Suppose that f (a+)/a ≤ f (b-)/b, i.e. σ/a ≤ ρ. By definition, f * = inf i∈N f (i) and from Lemma 12, while 1 ≤ i ≤ a/(ba) , the functions f (i) have disjoint supports, which are also disjoint from the union of the

INRIA supports of f (j) , j > a b-a . Thus if i ≤ a/(b -a) , f * = f (i) on ]ia, (i + 1)a]. If i > a/(b -a)
, we have ∀t ∈]ia, (i + 1)a], f * (t) = inf 0≤j≤i f (j) (t) and for 0 ≤ j < i, either f (j) (t) = +∞ or f (j) (t) = jσ + ρ(tja). In both cases, we have f

(j) (t) ≥ iσ + ρ(t -ia) = f (i) (t) ∈ R (since σ -ρa ≤ 0, j ≤ i and ]ia, (i + 1)a] ⊆]ia, ib[) and thus f * (t) = f (i) (t) = iσ + ρ(t -ia) on ]ia, (i + 1)a].
Suppose that f (a+)/a > f (b-)/b, i.e. σ/a > ρ. While 1 ≤ i ≤ a/(ba) , the functions f (i) have disjoint supports, which are also disjoint from the union of the the supports of f

(j) , j > a b-a . Thus if i ≤ a/(b -a) , f * = f (i) on [(i -1)b, ib[. If i > a/(b -a) , we have ∀t ∈ [(i -1)b, ib[, f * (t) = inf i≤j f (j) (t)
and for j > i, either f (j) (t) = +∞ or f (j) (t) =∈ R. In this later case, it implies f (i) (t) ∈ R (since ia ≤ ja) and we have f (j) (t) = jσ + ρ(tja) ≥ iσ + ρ(tia) = f (i) (t) (since σρa > 0 and j ≥ i). In both cases,

f (j) (t) ≥ f (i) (t) and finally f * = f (i) over [(i -1)b, ib[. It means that if i = a/(b -a) + 1, on [(i -1)b, ib[, f * (t) = f (i) (t) = iσ +ρ(t-ia) = i(σ +ρ(b-a))-ρ(ib-t) if t ∈]ia, ib[ and f * (t) = f (i) (t) = +∞ if t ∈ [(i-1)b, ia[ (since (i-1)b ≤ ia). If i > a/(b-a) +1, f * (t) = f (i) (t) = iσ+ρ(t-ia) = i(σ+ρ(b-a))-ρ(ib-t) on [(i-1)b, ib[.
The case a = 0 and f (0+) < 0 is simple and treated in Lemma 1. The case a = 0 and f (a+) = 0 leads to f * (t) = ρt, ∀t ∈ R + , but it can be seen as a particular case of f (a+)/a ≤ f (b-)/b. The case a = 0 and f (a+) > 0 is part of the case when f (a+ Lemma 14. Let f ∈ F be an iterated segment with parameters T, d, a, c, ρ i.e. whose support is ∪ i∈N ]T +id, T + id + a[ and such that ∀i ∈ N, ∀x ∈]0, a[, f (T + id + x) = f (T +) + ic + ρx. Then f * is ultimately finite (thus ultimately plain) and utimately pseudo-periodic.

)/a > f (b-)/b. a b 2a 4a a b 2a 3b 4a 2b 3a a 3a a 4b b 4b 3b b 2b f (a+) a ≥ f (b-) b f (a+) a ≤ f (b-) b
Proof. We dismiss the case when T = 0 and f (T +) < 0 already treated in Lemma 1.

We first study the terms f (k) , k ∈ N * . The function f (k) is finite on the intervals ]kT + id, kT + id + ka[, i ∈ N. If ka ≤ d, all these intervals are disjoint, and for all x ∈]0, ka[, we have f (k) (kT + id + x) = kf (T +) + ic + ρx. Indeed any decomposition of kT + id + x into a sum of k values of the support of f has the form (T + i

1 d + x 1 ) + • • • + (T + i k d + x k ) with i 1 + • • • + i k = i and x 1 + • • • + x k = x, because ka ≤ d. Then we have f (T + i 1 d + x 1 ) + • • • + f (T + i k d + x k ) = kf (T +) + c(i 1 + • • • + i k ) + ρ(x 1 + • • • + x k ) = kf (T +) + ic + ρx whatever the decomposition is.
If ka > d, then the intervals ]kT + id, kT + id + ka[, i ∈ N, overlap. For any x > 0, to get the value of f (kT + x), we have to minimize f (T + i

1 d + x 1 ) + • • • + f (T + i k d + x k ) where T + i 1 d + x 1 , ..., T + i k d + x k sum to kT +x.
In other terms, we wish to minimize kf (T +)+( 1≤j≤k i j )c+( 1≤j≤k x j )ρ under the constraints that ( 1≤j≤k i j )d + ( 1≤j≤k x j ) = x and i 1 , . . . , i k ∈ N, x 1 , . . . , x k ∈]0, a[, knowing that d < ka. By putting I = 1≤j≤k i j and X = 1≤j≤k x j , it is equivalent to minimizing Ic + Xρ where Id + X = x, I ∈ N and X ∈]0, ka[. We clearly have to consider two cases depending on the comparison between ρ and c/d.

If c/d ≤ ρ, we should maximize Id rather than X in the decomposition of x. It leads to I = x d -1 (due to the constraint X > 0) which also ensures that 0 < X ≤ d < ka. Then for all x > 0, f (k) (kT + x) = kf (T +) +

Ic + ρ(x -Id) = kf (T +) + c( x d -1) + ρ(x -d( x d - 1
)). In other terms, on any interval ]kT + id, kT + (i + 1)d], i ∈ N, we have ∀x ∈]0, d], f (k) (kT + id + x ) = kf (T +) + ic + ρx . Thus the function f (k) is ultimately pseudo-periodic from kT , with period d and increment c.

If ρ < c/d, we should maximize X rather than Id, leading to I = x-ka d + 1 if x ≥ ka (it satisfies 0 < X ≤ d < ka) and I = 0 if x < ka (due to I ∈ N), and all constraints are fulfilled. To write it in a convenient way, on any interval [kT + (i -1)d + ka, kT + id + ka[, i ∈ N * , we have ∀x ∈]0, d], f (k) (kT + ka + idx ) = kf (T + a-) + icρx . The function f (k) is ultimately pseudo-periodic from k(T + a), with period d and increment c. Note that for x ∈]0, ka[, f (k) (kT + x) = kf (T +) + ρx.

Figure 11 illustrates the shapes of these iterated convolutions f (k) of the iterated segment f , depending on k and the comparison between c/d and ρ. -Suppose that f (T +) T < c d . Note that it implies T > 0. We know that from k 0 = min{k | ka > d} = d a + 1, all the functions f (k) , k ≥ k 0 , are the same functions up to a translation. For k ≥ k 0 and i ∈ N, let f k,i be the semi-closed segment of slope ρ on the support ]kT + id, kT + (i + 1)d] such that f k,i (kT + id+) = kf (T +) + ic, then we have f (k) = inf i≥0 f k,i . For i ∈ N, we define g i = inf k≥k0 f k,i which is clearly ultimately pseudo-periodic from k 0 T + id with period T and increment f (T +) (but not necessary ultimately plain, it depends on whether T ≤ d). The subadditive closure can be written f * = inf 0≤k<k0 f (k) ⊕ inf k≥k0 f (k) . The first term is ultimately pseudo-periodic from (k 0 -1)T with period d and increment c. To analyze the second term which is clearly ultimately plain from k 0 T like f (k0) , we first show that ∃k 1 > k 0 such that f (k1) ≤ f (k0) all over the support of f (k1) . More INRIA precisely, ∃i 0 ≥ 1, k 1 > k 0 such that inf i≥i0 f k0,i ≥ inf i≥0 f k1,i over R + . One can follow the proof of Lemma 11 by choosing α, β ∈ N such that k 0 T + αd = βT with β > k 0 . However we can prove the result without even supposing that T /d ∈ Q + . We wish to find some i 0 and k 1 such that the start of f k0,i0 is above f k1,0 , i.e. more formally:

k 1 T ≤ k 0 T + i 0 d < k 1 T + d, and f k0,i0 (k 0 T + i 0 d+) ≥ f k1,0 (k 0 T + i 0 d+) With K = k 1 -k 0 , it is equivalent to: i 0 -1 < KT d ≤ i 0 , and k 0 f (T +) + i 0 c ≥ ρ((k 0 T + i 0 d) -k 1 T ) + k 1 f (T )
That is:

i 0 = KT d , and i 0 c d -ρ ≥ KT d f (T +) T -ρ
It leads to the inequation:

KT d ρ - c d ≤ KT d ρ - f (T +) T Such an integer K ∈ N * exists since 0 ≤ ρ -c d < ρ -f (T +) T (in case T d ∈ Q + ,
it is satisfied e.g. for the denominator of T d , and in all cases it is satisfied for large enough K since KT d -KT d ≤ 1). Choose any solution K of the inequation (note that it is better to choose the smallest K satisfying the inequation in order to minimize i 0 and k 1 to have a shorter expression of f * as we will see). Then due to the respective positions of the segments f k,i , we have inf i≥i0 f k0,i ≥ inf i≥0 f k1,i = f (k1) over R + . More generally, by translation, we have for all

l ≥ 0, inf i≥i0 f k0+l,i ≥ inf i≥0 f k1+l,i = f (k1+l) over R + . Thus, inf k≥k0 f (k) = inf k≥k0 ( inf 0≤i<i0 f k,i ⊕ inf i≥i0 f k,i ) = ( inf k≥k0 inf 0≤i<i0 f k,i ) ⊕ lim k→+∞ f (k) = inf 0≤i<i0 inf k≥k0 f k,i = inf 0≤i<i0 g i
which is ultimately pseudo-periodic from k 0 T + (i 0 -1)d with period T and increment f (T +), and we already noted that it is also ultimately plain from this rank. The term lim k→+∞ f (k) disappears since it converges to +∞ over R + due to T > 0. Finally, since c d > f (T +) t , the function f * = inf 0≤k<k0 f (k) ⊕ inf 0≤i<i0 g i is ultimately plain and pseudo-periodic with period T and increment f (T +).

-Suppose that f (T +) T > c d . We keep the same definition for k 0 = min{k | ka > d} = d a + 1, as well as for f k,i and g i . We have f * = inf 0≤k<k0 f (k) ⊕ inf k≥k0 f (k) . The first term is still ultimately pseudo-periodic from (k 0 -1)T with period d and increment c. The second is clearly ultimately plain from k 0 T like f (k0) . We now show that there existss k 1 > k 0 such that f (k0) ≤ f (k1) over R + , that will lead by translation to f (k0+l) ≤ f (k1+l) for all l ≥ 0. We wish to find some i 0 and k 1 (we will choose the smallest ones to shorten the final expressions) such that the start of f (k1) , i.e. the start of f k1,0 , is above f k0,i0 , i.e. more formally

k 0 T + i 0 d ≤ k 1 T < k 0 T + (i 0 + 1)d, and f k0,i (k 1 T +) ≤ f k1,0 (k 1 T +) With K = k 1 -k 0 , it is equivalent to: i 0 ≤ KT d < i 0 + 1, and k 0 f (T +) + i 0 c + ρ(k 1 T -(k 0 T + i 0 d)) ≤ k 1 f (T +) That is: i 0 = KT d , and i 0 ρ -c d ≥ KT d ρ -f (T +) T It leads to the inequation: KT d ρ - c d ≥ KT d ρ - f (T +) T Such an integer K ∈ N * exists since 0 ≤ ρ -f (T +) T < ρ -c d .
We can choose any solution K to the inequation (choose the smallest one to minimize the associated i 0 and k 1 and thus the next expression of the subadditive closure). Then we clearly have f (k1) ≥ f (k0) and by translation f (k1+l) ≥ f (k0+l) for all l ≥ 0. Thus f * = inf 0≤k<k0 f (k) ⊕inf k0≤k<k1 f (k) which is ultimately plain and pseudo-periodic from (k 1 -1)T with period d and increment c.

-Suppose that f (T +) T = c d . We can apply any of the two preceding reasonings leading to the same inequations and assuming that T d ∈ Q + ensures the existence of solutions K and enables to conclude. We can also use the following description which is more precise. All the segments composing the functions f (k) , k ≥ 1, have the same slope ρ, are finite over intervals open on the left, and start from points belonging to the line from the origin (0, 0) of slope f (T +) T = c d . More precisely, the set of jump points starting the segments of

f (k) , k ≥ 1, is S k = kT + dN. Let S = ∪ k≥k0 S k = {x = kT + ld, k, l ∈ N, l ≥ 0, k ≥ k 0 } with k 0 = min{k ∈ N | ka > T ∧ d}. Then due to Frobenius Lemma 9, let T * = k 0 T + F rob(T, d), we have S ∩ [T * , +∞[= T * + (T ∧ d)N. Moreover since ρ ≥ c d , it is clear that inf k≥k0 f (k) is ultimately pseudo-periodic from T * with period T ∧ d and increment (T ∧ d) c d . On each interval ]T * + i(T ∧ d), T * + (i + 1)(T ∧ d)], i ∈ N, it is equal to the semi-closed segment of slope ρ starting at point (T * + i(T ∧ d), c d (T * + i(T ∧ d))). Then note that for all 1 ≤ k < k 0 , S k ∩ [T * , +∞[⊆ S ∩ [T * , +∞[ since T ∧ d divides T and d. Thus inf 1≤k<k0 f (k)
does not introduce new jump points to inf k≥k0 f (k) after T * , and f * = inf k≥k0 f (k) from T * . It implies that f * is ultimately plain and pseudo-periodic from T * with period (T ∧ d) and increment (T ∧ d) c d . Suppose that c d > ρ.

-Suppose that f (T +a-)

T +a > c d . For k ≥ 1, let f k,0 be the segment of slope ρ on the support ]kT, k(T +a)[ such that f k,0 (k(T + a)-) = kf (T + a-) = kf (T +) + ρka, and for i ≥ 1, let f k,i be the semi-closed segment of slope ρ on the support [kT + ka + (i -1)d, kT + ka + id[ such that f k,i (kT + ka + id-) = kf (T + a-) + ic. We know that for all k ≥ k 0 = min{k | ka > d}, f (k) = inf i≥0 f k,i which is ultimately pseudo-periodic with period d and increment c. We also define for all i ≥ 0, g i = inf k≥k0 f k,i . All the semi-closed segments f k,i , k, i ≥ 1, are identical up to a translation, and for all i ≥ 1, g i is clearly ultimately pseudo-periodic with period (T + a) and increment f (T + a-). For i = 0, the asymptotic behaviour of g 0 depends on the comparison between ρ and f (T +a-) T +a (or equivalently ρ and f (T +) T since f (T + a-) = f (T +) + ρa and thus either f (T +)

T ≥ f (T +a-) T +a ≥ ρ or ρ > f (T +a-) T +a > f (T +) T ). If ρ > f (T +a-) T +a > f (T +) T
, then g 0 is ultimately pseudo-periodic from k 0 T with period T and increment f (T +), it is composed of semi-closed segments of slope ρ. Otherwise if ρ ≤ f (T +a-)

T +a ≤ f (T +) T
, then g 0 is ultimately pseudo-periodic from k 0 (T + a) with period T + a and increment f (T + a-), it is composed of semi-closed segments of slope ρ. The subadditive close can be written f * = inf 0≤k<k0 f (k) ⊕ inf k≥k0 f (k) . The first term is ultimately pseudo-periodic from (k 0 -1)(T + a) with period d and increment c. To study the second term, we show that ∃k 1 > k 0 such that the end of f k1,0 is above some f k0,i . More formally, we wish to find some i 0 ≥ 1 anf k 1 > k 0 such that

k 0 (T + a) + (i 0 -1)d < k 1 (T + a) ≤ k 0 (T + a) + i 0 d, f (k0) (k 1 (T + a)-) ≤ f (k1) (k 1 (T + a)-) With K = k 1 -k 0 , it is equivalent to: i 0 -1 < K(T +a) d ≤ i 0 , k 0 f (T +) + i 0 c + k 0 ρa ≤ k 1 f (T +) + k 1 ρa -ρ((k 0 -k 1 )(T + a) + i 0 d) INRIA That is: i 0 = K(T +a) d , i 0 c + Kρ(T + a) -ρi 0 d ≤ Kf (T +) + Kρa i 0 = K(T +a) d , i 0 d( c d -ρ) ≤ K(T + a)( f (T +)+ρa T +a -ρ)
It leads to the inequation:

K(T + a) d ( c d -ρ) ≤ K(T + a) d ( f (T + a-) T + a -ρ)
which is satisfied for some integer K ∈ N * since 0 < c d -ρ < f (T +a-) T +a -ρ. Then for k 1 and i 0 satisfying the constraints, due to the respective positions of the segments f k,i , we have inf 0≤i<i0 f k0,i ≤ f k1,0 over R + , and more generally, for all l, m ≥ 0, we have inf m≤i≤i0+m f k0+l,i ≤ f k1+l,m . It implies that for all l ≥ 0, f (k0+l) ≤ f (k1+l) over R + and thus inf k0≤k f (k) = inf k0≤k<k1 f (k) which is ultimately pseudo-periodic from (k 1 -1)(T + a) with period d and increment c (like the functions f (k) , k 0 ≤ k < k 1 ). Finally, f * is ultimately pseudo-periodic from (k 1 -1)(T + a) with period d and increment c.

-Suppose that f (T +a-)

T +a < c d .
With the same notation, we wish to find some k > k 0 and i 0 such that the end of f k0,i0 is above f k1,0 , i.e. more formally

k 1 (T + a) -d < k 0 (T + a) + i 0 d ≤ k 1 (T + a), f (k0) (k 0 (T + a) + i 0 d-) ≥ f (k1) (k 0 (T + a) + i 0 d-) With K = k 1 -k 0 , it is equivalent to: i 0 ≤ K(T +a) d < i 0 + 1, k 0 f (T + a-) + i 0 c ≥ k 1 f (T + a-) -ρ((k 1 -k 0 )(T + a) -i 0 d) That is: i 0 = K(T +a) d , i 0 d( c d -ρ) ≥ K(T + a)( f (T +a-) T +a -ρ)
It leads to the inequation:

K(T + a) d ( c d -ρ) ≥ K(T + a) d ( f (T + a-) T + a -ρ)
which is satisfied for some integer K ∈ N * since f (T +a-)

T +a -ρ < c d -ρ. Then for k 1 and i 0 satisfying the constraints, due to the respective positions of the segments f k,i , we have inf i≥i0 f k0,i ≥ inf i≥0 f k1,i = f (k1) over the support of f (k1) . More generally, for all l ≥ 0, we have inf i≥i0 f k0+l,i ≥ inf i≥0 f k1+l,i = f (k1+l) over the support of f (k1+l) . It leads to inf k≥k0 f (k) = inf 0≤i<i0 g i and we have two cases.

If ρ ≤ f (T +a-) T +a ≤ f (T +)
T , then inf 0≤i<i0 g i is ultimately pseudo-periodic with period T + a and increment f (T + a-) (like all g i , 0 ≤ i < i 0 ). In this case, f * is ultimately pseudo-periodic with period T + a and increment f (T + a-) (since f (T +a-)

T +a < c d ). If f (T +) T < f (T +a-)
T +a < ρ, then inf 0≤i<i0 g i is ultimately equal to g 0 which is ultimately plain and pseudo-periodic with period T and increment f (T +) (since f (T +)

T < f (T +a-) T +a < c d ). -Suppose that f (T +a-) T +a = c d .
We can apply any of the two preceding reasonings leading to the same inequations and assuming that T +a d ∈ Q + ensures the existence of solutions K and enables to conclude. We can also use the following description which is more precise. All the segments composing the functions f (k) , k ≥ 1, have the same slope ρ, are finite over intervals open on the right and end at points belonging to the line from the origin (0, 0) of slope f (T +a-)

T +a = c
d . More precisely the set of jump points ending the segments of

f (k) , k ≥ 1, is E k = k(T + a) + dN. Let E = ∪ k≥k0 E k with k 0 = min{k ∈ N | ka > (T + a) ∧ d}. Then due to Frobenius Lemma 9, let T * = k 0 (T + a) + F rob(T + a, d), we have E ∩ [T * , +∞[= T * + ((T + a) ∧ d)N. Since ρ < c d , it is clear that inf k≥k0 f (k)
is ultimately plain and pseudo-periodic from T * with period (T + a) ∧ d and increment ((T +a)∧d) c d . On each interval [T * +i((T +a)∧d), T * +(i+1)((T +a)∧d)[, i ∈ N, it is equal to the semi-closed segment og slope ρ starting at point (T k) does not introduce new jump points to inf k≥k0 f (k) from T * and f * = inf k≥k0 f (k) from T * , which implies that f * is ultimately plain and pseudo-periodic from T * with period ((T + a) ∧ d) and increment ((

* + i((T + a) ∧ d), c d (T * + i((T + a) ∧ d))). Then note that for all 1 ≤ k < k 0 , E k ∩ [T * , +∞[⊆ E ∩ [T * , +∞[ since (T + a) ∧ d divides T + a and d. Thus inf 0≤k<k0 f (
T + a) ∧ d) c d Proposition 11. The classes F[R + , R] and F[Q + , Q] are stable under the subadditive closure. Moreover, let f ∈ F[Q + , Q] (resp. F[Q + , R]) be an ultimately pseudo-periodic function, then f * is ultimately pseudo-periodic in F[Q + , Q] (resp. F[R + , R]). Proof. Let f ∈ F[R + ,
R] and let (f n ) n∈N be its decomposition into segments and spots. Let A ∈ R + and n 0 be the smallest integer n such that f n and g n have a support disjoint from [0, A]. Since for all t ∈ R + , f * (t) only depends on the values of f and g on

[0, t], on [0, A], f * = (min 0≤i≤n0 f i | [0,A] ) * = f * 0 * • • • * f * n0
by the morphism property of the star from min to * . Applying Lemma 10, Lemma 13 and Proposition 9 for the stability of the convolution, we get that f * is piecewise affine on [0, A], and consequently on R + . Note that everything remains in

F[Q + , Q] if f belongs to this class. Let f ∈ F[Q + , Q]
be an ultimately plain pseudo-periodic function, we decompose f into a finite number of elementary functions f i , 1 ≤ i ≤ n, which are spots, segments, iterated spots or iterated segments and such that f = min i f i . Then the morphism property of the star from min to * gives

f * = f * 1 * • • • * f * n .
Lemma 10, Lemma 11, Lemma 13 and Lemma 14 ensure that each f * i is ultimately pseudo-periodic. Then we must consider two cases. In the first case, at least one f i is a segment or an iterated segment which means that f * i is ultimately pseudo-periodic and ultimately finite (thus ultimately plain). Together with Proposition 6 for * and the last remark in its proof, composing f * i with the other functions f * j yields an ultimately pseudo-periodic function which is also ultimately finite (thus ultimately plain). In the second case, all the f i 's are spots or iterated spots. One can not directly apply Proposition 6 (see Remark 3). However since

f ∈ F[Q + , Q], its jump points have a smallest common denominator d. Let g ∈ D such that g(t) = f ( t d ), then we clearly have f * (t) = [g * ] R (dt).
Due to Proposition 7 for the discrete model, g * is ultimately pseudo-periodic, thus f * is also ultimately pseudo-periodic.

If f ∈ F[Q + , R] is ultimately plain pseudo-periodic, the same reasoning still applies to prove the ultimate pseudo-periodicity, and f * ∈ F[R + , R] since this class is stable, but there exists some [START_REF] Bouillard | Some examples and counterexamples for (min, +) filtering operations[END_REF]).

f ∈ F[Q + , R] such that f * ∈ F[Q + , R] (see
Putting together the results of the section gives the second stability theorem: Theorem 2. The class of plain ultimately pseudo-periodic functions of F[Q + , Q] is stable under the Network Calculus operations +, -, min, max, * , and the subadditive closure.

Like Theorem 1, weakening the statement to ultimately plain pseudo-periodic functions in F[Q + , Q] does not work (see Remark 4).

In fact, thanks to the Interpolation Proposition 1, Theorem 2 provides a new proof of Theorem 1 for D. One could argue that it is not really true since the proof of Proposition 11 for the subadditive closure makes use of Theorem 1, but a careful look shows that the case requiring Theorem 1 does not occur for

[f ] R if f ∈ D is plain: [f ] R is either +∞ or -∞ on R *
+ , or contains at least a segment. Here are some other corollaries of Theorem 2:

Corollary 2. The non-decreasing ultimately pseudo-periodic functions of F[Q + , Q] are stable under the Network Calculus operations +, min, max, * , and the subadditive closure, except -.

Proof. It is known that the Network calculus operations, except -, preserve the non-decrease of the functions (e.g. see [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF]).

Let f ∈ F[R + , R],
f is called a staircase function if all its affine parts have a slope equal to 0. Corollary 3. The plain ultimately pseudo-periodic staircase functions of F[Q + , R] are stable under the Network Calculus operations +, -, min, max, * , and the subadditive closure.

INRIA

Proof. As seen in the various preceding lemma and propositions, given a set of piecewise affine functions whose segment slopes all belong to a fixed set S ⊆ R, then combining them a finite number of times with Network Calculus operations yields a set of output functions whose segment slopes all belong to ZS = {a

1 s 1 + • • • + a k s k | k ∈ N * , a i ∈ Z, s i ∈ S}.
Thus staircase functions remain staircase functions, and a careful look at the proofs of the lemma and propositions show that if they belong to F[Q + , R] then their outputs remain in F[Q + , R] since segments never intersect.

As mentioned before, some stability results were already known for some classes of fluid functions. Recorded in [START_REF] Baccelli | Synchronization and Linearity[END_REF], they are mainly stated through a representation of functions by formal power series in two variables γ and δ, and for (max, +) versions of Network Calculus operations which directly imply the same for their (min, +) counterparts up to a few small adjustments (e.g. right-continuous becomes left-continuous, convex becomes concave). Theorem 6.32 which is extended by Remark 6.33, pages 290-291, can be translated into "non-decreasing left-continuous ultimately pseudo-periodic staircase functions of F[N, R] are stable under the operations min, * and the subadditive closure". It yields the same result for such staircase functions in F[Q + , R], up to reducing the jump points to N by multiplying them by a common denominator (such denominators always exist in ultimately pseudo-periodic functions in F[Q + , R]). This result is generalized in Corollary 6.34, page 291, which yields the stability of a more general class of functions. Let us call a function f a concave staircase if it is piecewise affine and for any segment of f of support ]a, b[, the continuation of this segment over [0, b[ is above f on [0, b[ (as a consequence those functions are non-decreasing). Non-decreasing staircase functions are clearly concave staircases. Corollary 6.34 in [START_REF] Baccelli | Synchronization and Linearity[END_REF] can be translated into "left-continuous ultimately pseudo-periodic concave staircase functions of F[Q + , R] are stable under the operations min, * and the subadditive closure". The original (max, +) version is stated for functions in F[N, R] (but ultimate pseudo-periodicity enables to switch from N to Q + as above), with a finite set of slopes (which is even more precise).

Concerning usual modelling assumptions, in [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF], it is shown that when dealing with arrival curves of left-or right-continuous cumulative flows, one can assume w.l.o.g. that they are left-continuous (Lemma 1.2.1, page 9).

Piecewise affine functions in

F[R + , R].
Note that we have also proved that stability results apply for the ultimately affine functions of F[R + , R] (for all operations except the subadditive closure) but they are lost for the ultimately pseudo-periodic functions: the combination of such pseudo-periodic functions is usually not pseudo-periodic. For instance it is well-know that the sum of two periodic functions with respective minimum periods d 1 and d 2 is aperiodic if d 1 /d 2 is irrational [START_REF] Corduneanu | Almost Periodic Functions[END_REF], this directly implies the same for pseudo-periodic functions.

Algorithmic aspects

As a consequence of Theorems 1 and 2, we will mainly design algorithms implementing the Network Calculus operations for plain ultimately pseudo-periodic functions in F[Q + , Q] and in D. Thanks to the Interpolation Proposition 1, we can clearly deduce the output functions in D by performing the operations in

F[Q + , Q] or F[Q + , R].
We will however dedicate Subsection 4.7 to the discrete model to discuss the extra complexity cost of interpolation and to suggest adaptations of the algorithms for D.

Storage of ultimately pseudo-periodic functions

Let f ∈ F[Q + , Q] be an ultimately pseudo-periodic function from T , with period d and increment c, such that ∀t ≥ T , f (t + d) = f (t) + c. We choose to store the affine pieces of the function (in particular their slopes) on the interval [0, T +d[. One can store f as ([t 1 , . . . ,t k ],(T,d,c)), where T is the rank from which f is pseudo-periodic, d is a period of f and c the corresponding increment, [t 1 , . . . , t k ] is the list of its affine pieces (spot+segment). More precisely,

∀1 ≤ i ≤ k, t i = (x i , f (x i ), y i , ρ i ) such that f is affine on ]x i , x i+1 [ (resp. ]x k , T + d[ when i = k), y i = f (x i +
) and ρ i is the slope on this interval. Whenever f is equal to +∞ (resp. -∞) on ]x i , x i+1 [, we arbitrarily set y i = +∞ (resp. -∞) and ρ i = 0.

We require that x 1 = 0, that there exists i 0 such that x i0 = T , and that x k < T + d. We can use a simple linked list for [t 1 , . . . , t k ], where t k points back to t i0 . Moreover, an integer counter η f (initialized to 0) is associated with f , which tells as we move forward through the data structure how many times the link between t k and t i0 has been used. Finally, we add an extra pointer pos which points to one tuple t i so that we can access it in constant time (it marks the tuple which is currently scanned).

Note that this choice of data structure has imposed the assumption ∀t ≥ T , f (t + d) = f (t) + c rather that ∀t > T . Of course, one can easily find another simple data structure which fits better the definition with the strict inequality.

T d c x2 x k t2 t1 ti 0 t k x1 f (x1) y1 f (xi 0 ) f (x k ) ρ1 f (x2) y2 ρ2 xi 0 yi 0 ρi 0 y k ρ k pos η f
Figure 12: A simple data structure to store ultimately pseudo-periodic functions.

We have deliberately chosen a simple data structure sufficient to run our algorithms implementing Network Calculus operations. It is clear that this data structure can be adjusted to specific programming languages or can be enforced if there is a need to perform efficiently some other operations, e.g. given the function f , quickly compute f (x) for any x ∈ R + .

In all the section, we choose this data structure to describe our algorithms and analyze their complexities.

Let us first give some basic functions we will use:

Next.point(f ) makes pos point to the next tuple (x i , f (x i ), y i , ρ i ) of f . If the link between t k and t i0 is used, η f is set to η f + 1. The function returns x i + η f d.

Next.point(f 1 , f 2 ) compares the values that would be returned by Next.point(f 1 ) and Next.point (f 2 ), and it returns a couple (x, I) where x the minimum of those two values and I ⊆ {1, 2} is the set of indice(s) of the corresponding function(s). The function(s) that achieve(s) that minimum make their pointer pos i point to the next tuple. The values η f1 or η f2 are updated as above if necessary.

Value-plus(f, x) returns

y i + ρ i (x -x i -η f d) + η f c when pos points to t i . If x ∈]x i + η f d, x i+1 + η f d[ or ]x k + η f d, x i0 + (η f + 1)d[, that value is f (x). If x = x i + η f d, that value is f (x+).
Value(f, x) returns y i +ρ i (x-x i -η f d)+η f c when pos points to t i and x = x i +η f c or returns f (x i )+cη f if x = x i + η f c. In both cases, thath returned value is f (x).

Slope(f ) returns the slope ρ i of the tuple t i pointed by pos.

Length(f ) returns the segment length of the tuple t i = (x i , f (x i ), y i , ρ i ) pointed by pos. If i < k, that is x i+1x i , and if i = k, that is (x i0 + dx k ).

Start(f ) returns x i + η f d the starting point of the tuple t i = (x i , f (x i ), y i , ρ i ) pointed by pos.

End(f ) returns the ending point of the tuple t i = (x i , f (x i ), y i , ρ i ) pointed by pos, i.e. Start(f )+Length(f ).

Extend(f, T , d ) returns f if x ≤ T or if d does not divide d , and otherwise returns a extended description of f where all tuples over [0, T [ and then over [T , T + d [ are given in the linked list and where the loop pointer joins the last tuple to the tuple starting at T . These functions run in constant time.

Concerning the main parameters and the storage space of an ultimately pseudo-periodic function f (resp. f i ) in F[Q + , Q], we will denote by T f (resp. T i ), d f (resp. d i ), c f (resp. c i ) a rank of pseudo-periodicity, a period and its associated increment. We will also denote by n f (resp. n i ) the number of tuples in the transient part of the function, i.e. over [0, T [, and by p f (resp. p i ) the number of tuples in the pseudo-periodic part of the function, i.e. over [T, T + d[, and we will use the notation N f = n f + p f (resp. N i = n i + p i ) for the size of all tuples representing f (resp. f i ). Let be a Network Calculus operation, then given an algorithm implementing it, notations like N f g or d f g will refer to the size or the parameter of the output for this algorithm.

Note that, as shown in Subsection 2.1, checking whether the output of any Network Calculus operation is well-defined can be easily done from inputs in linear time.

Addition of ultimately pseudo-periodic functions

Let f 1 and f 2 be two ultimately pseudo-periodic functions in F[Q + , Q]. From Proposition 6, we know that the addition of those two functions is ultimately pseudo-periodic from max(T 1 , T 2 ) with a period d = d 1 ∨ d 2 and an associated increment c = c1 d1 d + c2 d2 d. As a consequence, it is sufficient to compute the addition on the interval [0, T 1 + T 2 + d[. The jump points of f 1 + f 2 are included within the union of the jump points of f 1 and f 2 . Thus one way to compute f 1 + f 2 consists in merging the sorted lists of jump points of f 1 and f 2 , and compute the additions at each jump point and between consecutive pairs of jump points. It can be done through a single pass over f 1 and f 2 as detailed in Algorithm 2 and with the following complexity (N e i stands for the number of tuples when extending the function):

Proposition 12. Let f 1 , f 2 ∈ F[Q + , Q] both ultimately pseudo-periodic. If T 1 = T 2 = T and d 1 = d 2 = d, then f 1 + f 2 can be computed in time O(N f1 +f2 ) where N f1+f2 = N 1 + N 2 .
Consequently, in the general case, f 1 + f 2 can be computed in time O(N f1+f2 ) where

N f1+f2 = N e 1 + N e 2 with N e 1 = n 1 + p 1 (T +d)-T1 d1 , N e 2 = n 2 + p 2 (T +d)-T2 d2 , T = max(T 1 , T 2 ) and d = d 1 ∨ d 2 .
Algorithm 1: Addition of two functions (sketch). Data: Data:

f 1 , f 2 ∈ F[Q + , Q] both ultimately pseudo-periodic. Result: f 1 + f 2 with parameters T , d, c. begin T ← T 1 + T 2 ; d ← d 1 ∨ d 2 ; c ← ( c1 d1 + c2 d2 )d; Extend(f 1 , T, d); Extend(f 2 ,
f 1 := ([(x 1 1 , f 1 (x 1 1 ), y 1 1 , ρ 1 1 ), . . . , (x 1 k , f 1 (x 1 k ), y 1 k , ρ 1 k )], (T 1 , d 1 , c 1 )
) and f 2 := ([(x 2 1 , f 2 (x 2 1 ), y 2 1 , ρ 2 1 ), . . . , (x 2 , f 2 (x 2 ), y 2 , ρ 2 )], (T 2 , d 2 , c 2 )). Result: f := ([(x 1 , f (x 1 ), y 1 , ρ 1 ), . . . , (x n , f (x n ), y n , ρ n )], (T, d, c)) ,(T,d,c)) end Substractions of functions work exactly in the same way.

such that f = f 1 + f 2 . begin T ← T 1 + T 2 ; d ← d 1 ∨ d 2 ; c ← c 1 d/d 1 + c 2 d/d 2 ; x ← 0; g ← [(0, f 1 (x 1 1 ) + f 1 (x 2 1 ), y 1 1 + y 2 1 , ρ 1 1 + ρ 2 1 )]; repeat x ←Next.point(f 1 , f 2 ); ρ ←Slope(f 1 )+ Slope(f 2 ); f (x) ←Value(f 1 , x)+Value(f 2 , x); y ←Value-plus(f 1 , x)+Value-plus(f 2 , x); g ← g :: [(x, f (x), y, ρ)]; until x ≥ T + d; return (g
Addition of several ultimately pseudo-periodic functions. There are several solutions to compute the sum of k functions f 1 , . . . , f k . Whether the algorithm does a single pass over the data structures or not, the computation necessarily merge the sets of jump points of the functions f i , 1 ≤ i ≤ k. Several solutions work.

One is to modify Algorithm 2 so that it takes k functions in argument, and at each new jump point, it computes the sum of the values of f i and the sum of the next segments. Finding the next jump point can be made in O(log 2 (k)) with the use of a binary heap, and updating the sum of all functions at a new jump point and between the next consecutive jump points requires O(1) amortized complexity (each input jump point induces the change of only one term in the sum). Up to extending the functions, suppose that ∀1 ≤ i ≤ k, T i = T and d i = d, then the overall complexity is O(log 2 (k) k i=1 N i ). Another solution is to add functions two by two (using Algorithm 2) by organizing the whole calculation as a balanced binary tree with the k inputs at the leaves and finally the output at the root (Divide& Conquer scheme). It gives a O(log 2 (k)N P fi ) algorithm where N P fi ≤ k i=1 N i , since each input jump point leads to at most log 2 (k) constant time operations (comparisons or sums) along the branch from its leaf to the root. Another way to organize the pairwise sums of functions is to use the binary tree constructed with Huffman algorithm (where weights are the number of jump points, i.e. tuples in the data structure), it is proven that the overall complexity is better than the balanced binary tree.

Minimum of ultimately pseudo-periodic functions

Let f 1 and f 2 be two ultimately pseudo-periodic functions in F[Q + , Q]. Proposition 6 gives a sufficient condition so that their minimum is also ultimately pseudo-periodic: it works if they are both ultimately plain. If c1 d1 = c2 d2 , then the minimum has a period d = d 1 ∨ d 2 and an associated increment c = c1 d1 d. Otherwise if c1 d1 < c2 d2 , the minimum has a period d = d 1 and an associated increment c = c 1 . There are at least two ways to compute the minimum:

1. One can precompute a rank T from which the minimum is pseudo-periodic, and then extend the functions over [0, T + d[ and merge the two lists of jump points to compute the minimum at each jump point and between each pair of consecutive jump points (see Algorithm 3 when both inputs are ultimately plain).

2. Otherwise one can compute the minimum in a single pass , and find on the fly a rank from which the output is pseudo-periodic (see Algorithm 4).

Algorithm 3: Minimum of two functions (sketch). Data: , N e 2 = n 2 + p 2 (T +d)-T2 d2

f 1 , f 2 ∈ F[Q + , Q] both ultimately plain pseudo-periodic. Result: min(f 1 , f 2 ) with parameters T , d, c. begin case c1 d1 < c2 d2 : d ← d 1 ; c ← c 1 ; M 1 ← sup T1≤t<T1+d1 (f 1 (t) -c1 d1 t); m 2 ← inf T2≤t<T2+d2 (f 2 (t) -c2 d2 t); T ← max( M1-m2 c 2 d 2 - c 1 d 1 , T 1 , T 2 ); case c1 d1 > c2 d2 : d ← d 2 ; c ← c 2 ; Compute T symetrically as above; case c1 d1 = c2 d2 : d ← d 1 ∨ d 2 ; c ← (d 1 ∨ d 2 ) c1 d1 ; T ← max(T 1 , T 2 ); Extend(f 1 , T, d); Extend(f 2 ,
and N min(f1,f2) ≤ 2(N e 1 + N e 2 ).

INRIA Theorem 3 ([2,[START_REF] Attalah | Some dynamic computational geometry problems[END_REF][START_REF] Hershberger | Finding the upper envelope of n line segments in O(n log n) time[END_REF][START_REF] Nielsen | An output-sensitive convex hull algorithm for planar objects[END_REF]). The minimum (lower envelope) of a set of n continuous total functions, each pair of whose graphs intersect in at most s points, can be constructed, in an appropriate model of computation, in O(λ s (n) log n) time and the size of the output is O(λ s (n)). If the functions are partial, then their minimum can be computed in O(λ s+1 (n) log n) time and the size of the output is O(λ s+2 (n)). In the particular case when the functions are segments, the minimum can be computed in O(n log N ) time, where N is the size of the output which satisfies N ≤ λ 3 (n) = Θ(nα(n)).

The appropriate model assumes that each intersection between two functions can be computed in O(1) amortized time. It is actually the case when the functions are segments. The complexity for n total functions can be achieved thanks to a straight forward Divide & Conquer algorithm, which can be directly extended into a O(λ s+2 log n) algorithm for partial functions [START_REF] Agarwal | Davenport-Schinzel sequences and their geometric applications[END_REF][START_REF] Boissonat | Algorithmic Geometry[END_REF]. The complexity for partial functions was improved in [START_REF] Hershberger | Finding the upper envelope of n line segments in O(n log n) time[END_REF] by reorganizing the Divide & Conquer computation, yielding a O(λ s+1 (n) log n) algorithm and thus a O(n log n) algorithm for segments since λ 2 (n) = 2n -1. The output sensitive O(n log N ) algorithm in [START_REF] Nielsen | An output-sensitive convex hull algorithm for planar objects[END_REF] uses those previous works but also introduces a preprocessing step called Marriage-before-Conquest. Some of these algorithm are implemented in libraries like CGAL [START_REF] Cgal | Computational Geometry Algorithms Library (interfaced with Scilab through CGLAB[END_REF]. Concerning the upper bound on the output size, note that it can be deduced from [START_REF] Agarwal | Davenport-Schinzel sequences and their geometric applications[END_REF] that for all n, λ 3 (n) ≤ 68(α(n) + 1)n, which has been refined into λ 3 (n) ≤ 3nα(n) for sufficiently large n in [START_REF] Klazar | On the maximum lengths of Davenport-Schinzel sequences[END_REF].

As we will see in the next subsections, those results are useful for the computation of the convolution and the deconvolution.

Convolution of ultimately pseudo-periodic functions

Let f 1 and f 2 be two ultimately pseudo-periodic functions in F[Q + , Q]. The next algorithm for the convolution of f 1 and f 2 follows the proof of stability in Proposition 6:

1. The function f 1 is decomposed into f 1 = f 1 ⊕ f 1 where f 1 = f 1 on [0,
f 2 = f 2 ⊕ f 2 . 2. We have f 1 * f 2 = (f 1 * f 2 ) ⊕ (f 1 * f 2 ) ⊕ (f 1 * f 2 ) ⊕ (f 1 ⊕ f 2 )
, and some information about the pseudoperiodicity of each term.

3. The function f 1 * f 2 has a support included in [0, T 1 + T 2 [, and is equal to +∞ outside. To compute this term, let (f 1,i ) i∈I (resp. (f 2,j ) j∈J ) be the set of segments and spots of f 1 (resp f 2 ), i.e. f 1 = min i∈I f 1,i (resp. f 2 = min j∈J f 2,j ). Then f 1 * f 2 = min i∈I,j∈J f 1,i * f 2,j where each f 1,i * f 2,j is either a spot, a segment or two consecutive segments (see Lemma 2,3 and 4). This minimum over i ∈ I and j ∈ J is the minimum of at most 2(|I| + |J|) segments and can be computed thanks to the algorithms from computational geometry presented in the previous subsection. [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF]. The minimum of the four terms can be computed with a simple algorithm for the minimum like the ones presented in the previous subsection.

As explained in Proposition 6, it is sufficient that at least one of the two functions is ultimately plain to ensure that this scheme works.

INRIA f 1 * f 2 f 1 * f 2 f 1 * f 2 f 1 * f 2 Interval of computation (transitory & pseudo- periodic parts) [0, T1 + T2[ [T2, T1 + T2 + d2[ [T1, T1 + T2 + d1[ [T1 + T2, T1 + T2 + 2d[ Interval to consider for f1 [0, T1[ [0, T1[ [T1, T1 + T2 + d1[ [T1, T1 + 2d[ Tuples to consider in f1 n1 n1 p1 T 2 +d 1 d 1 p1 2d d 1 Interval to consider for f2 [0, T2[ [T2, T1 + T2 + d2[ [0, T2[ [T2, T2 + 2d[ Tuples to consider in f2 n2 p2 T 1 +d 2 d 2 n2 p2 2d d 2
Number of elementary convolutions

N 1 ,2 = n1n2 N 1 ,2 = n1p2 T 1 +d 2 d 2 N 1 ,2 = n2p1 T 2 +d 1 d 1 N 1 ,2 = p1 2d d 1 p2 2d d 2
Complexity to compute their minimum

N 1 ,2 log(N 1 ,2 ) N 1 ,2 log(N 1 ,2 ) N 1 ,2 log(N 1 ,2 ) N 1 ,2 log(N 1 ,2 )
Tuples in f1 acting in the definition over [0, T + d[

N e 1 = n1 N e 1 = n1 N e 1 = p1 (T +d)-T 1 d 1 N e 1 = p1
(ia+) = if (a+); Return f * equal to inf 0≤i≤ a b-a +1 f i over [0, ( a b-a + 2
)a] and ultimately pseudo-periodic from a( a b-a + 1) with period a and increment f (a+); case f (a+) a > f (b-) b : Let f 0 be the spot at 0 with value 0; For all 1 ≤ i ≤ a b-a + 1, let f i be the segment on ]ia, ib[ with slope ρ and s.t. Data: f an iterated segment with parameters T, d, a, c, ρ.

f i (ia+) = if (a+); For i = a b-a + 2, let f i be the semi-closed segment on [(i -1)b, ib[ with slope ρ s.t. f i (ib-) = if (b-); Return f * equal to inf 0≤i≤ a b-a +2 f i over [0, ( a b-a +
Result: f * . begin case c d ≤ ρ: case f (T +) T < c d : k 0 ← d a + 1; Choose K ∈ N * s.t. KT d (ρ -c d ) ≤ KT d (ρ -f (T +) T ); i 0 ← KT d ; Return inf 0≤k<k0 f (k) ⊕ inf 0≤i<i0 g i ,
which is ult. pseudo-periodic with period T and increment f (T +); k) , which is ult. pseudo-periodic with period d and increment c; k) , which is ult. pseudo-periodic with period d and increment c; end RR n 6094

case f (T +) T ≥ c d : k 0 ← d a + 1; Choose K ∈ N * s.t. KT d (ρ -c d ) ≥ KT d (ρ -f (T +) T ); k 1 ← k 0 + K; Return inf 0≤k<k1 f (
case c d > ρ: case f (T +a-) T +a < c d : k 0 ← d a + 1; Choose K ∈ N * s.t. K(T +a) d ( c d -ρ) ≥ K(T +a) d ( f (T +a-) T +a -ρ); i 0 ← K(T +a) d ; Return inf 0≤k<k0 f (k) ⊕ inf 0≤i<i0 g i , which is ult. pseudo-periodic with period and increment T, f (T +) if f (T +) T ≤ f (T +a-) T +a or T + a, f (T + a-) if f (T +) T > f (T +a-) T +a ; case f (T +a-) T +a ≥ c d : k 0 ← d a + 1; Choose K ∈ N * s.t. K(T +a) d ( c d -ρ) ≤ K(T +a) d ( f (T +a-) T +a -ρ); k 1 ← k 0 + K; Return inf 0≤k<k1 f (

Computations in the discrete model

The first natural method to store an ultimately periodic function f ∈ D such that ∀t ≥ T , f (t + d) = f (t) + c, is to store these three parameters and all the values f (t) from t = 0 to t = T + d -1, for instance in an array. We can call it the extensive encoding. One drawback is clearly the space consumption, which may explode after an operation as simple as the minimum (consider for instance f (t) = min(ρ 1 t + σ 1 , ρ 2 t + σ 2 ) when ρ 1 is close to ρ 2 ).

The alternative method that we choose is to store its continuous interpolation [f ] R defined in Subsection 2.3. Up to a small constant factor, the storage space is never larger than the extensive storage, but in some cases it may be exponentially smaller (e.g. for the preceding example f (t) = min(ρ 1 t + σ 1 , ρ 2 t + σ 2 )). We call it a fluid encoding, it belongs to

F[Q + , R].
Moreover, as proved in Proposition 1, we can do the computations on these fluid interpolations of the input functions and then go back to D by restricting the outputs on N. First, note that to use the algorithms for the fluid model, it is necessary to have the slopes ρ i of the affine pieces of [f ] R (which, at first sight, might have seemed unnecessary for functions in D). Then, note that the output provided by the fluid algorithms is not exactly the right encoding of the real output in D: as a last step, we have to apply Algorithm 14 which computes the encoding of the restriction on N of the function calculated by the fluid algorithms. Moreover a careful look at each operation shows that we will apply Algorithm 14 on outputs which belong to F[R + , R] and have periods in N * . The extra cost of this adjustment algorithm is linear in the size of the output and thus does not change the order of complexity of the algorithms implementing the Network Calculus operations.

Algorithm 14: Adjustment of fluid encodings for functions in D.

Data: If the extensive encoding is used, specific algorithms can be designed like the next ones. For all operations except the subadditive closure, they follow the schemes of the fluid algorithms except that they only deal with spots and not segments (it can be seen as the use of the direct interpolations of Remark 1). A careful look at the literature shows that the next algorithms are very close to the ones studied by Gaubert [START_REF] Gaubert | Théorie Linéaire des Systèmes dans les Dioïdes[END_REF] and Hardouin et al, and currently implemented in Scilab [START_REF] Gaubert | [END_REF][START_REF] Hardouin | Modèles et Systèmes Dynamiques[END_REF], up to a translation where (max, +) becomes (min, +) and formal series are seen as functions, and up to a generalization to D.

f = ([(x 1 , f (x 1 ), y 1 , ρ 1 ), . . . , (x k , f (x k ), y k , ρ k )], (T, d, c)) ∈ F[R + , R] s.t. d ∈ N * . Result: g ∈ F[Q + , R] a fluid encoding of [f ] N . begin g ← []; x ← 0; v ←Value(f,
Let f 1 , f 2 ∈ D be two plain ultimately pseudo-periodic functions with respective rank, period and increment T 1 , d 1 , c 1 and T 2 , d 2 , c 2 . Their extensive encodings have respective sizes O(T 1 + d 1 ) and O(T 2 + d 2 ) that will be denoted N 1 and N 2 . More generally, we will reuse some notations of the analyses of fluid algorithms.

To conclude, when the size of the fluid encoding is about the same as the size of the extensive encoding, the preceding algorithms specially designed for the discrete model have better complexities than the fluid algorithms. In other terms, if the fluid encoding stores the values at almost all integer points like the extensive encoding, INRIA introducing the slopes between these points does not speed up our algorithms and rather adds a small amount of work.

However when the input discrete functions have short fluid encodings, which can be exponentially smaller than extensive encodings, the fluid algorithms clearly outperform the discrete algorithms in both time and space.

Note that the complexity upper bounds that we find for the brute force algorithm and for the fluid algorithm are both exponential for the subadditive closure. One could hope for improvements or a tighter analysis of the complexity. However in the next subsection, we point out some intrinsic difficulties.

Compressed form and computational consequences

An important question raised by all these algorithms is whether the computed output is a compressed representation of the output. Given an ultimately pseudo-periodic function f ∈ D or F[R + , R], it admits several encodings ([t 1 , . . . , t k ], (T, d, c)) depending on the choice of a period d and of the rank T . However one may look for a compressed version where we store the period of the function, i.e. the smallest period, and its associated increment, as well as the smallest rank from which it is pseudo-periodic, in particular in order to save storage space. Note that the data structure of Section 4.1 uses ranks such that ∀t ≥ T , f (t + d) = f (t) + c and not ∀t > T which is the initial definition of rank. However this data structure could be easily adjusted to deal with it (e.g. by putting each spot at the end of a tuple rather than at the beginning).

Proposition 16 (Compressed form). Let f be an ultimately pseudo-periodic function in F[R + , R] or in D (given by a fluid or an extensive encoding). Then its smallest period and its smallest rank can be computed in linear time.

Proof. The smallest rank can be computed by shifting the periodic part from the right to the left.

The periodic part of the function can be seen as a word w where the letters are the tuples. The smallest prefix u of that word such that w is a power of u gives the smallest period. Computing u can be done in linear time.

For an ultimately plain pseudo-periodic function from N into N, the existence and the computation of such a compressed form was already well-known and expressed as the existence of a canonical form of periodic γ, δ-formal power series (see [START_REF] Baccelli | Synchronization and Linearity[END_REF]).

The following proposition gives an insight into the difficulty of predicting those smallest values when computing the subadditive closure.

Proposition 17 (Complexity for the subadditive closure parameters). Let f an ultimately pseudo-periodic function in D given by its fluid encoding, computing the smallest rank from which f * is pseudo-periodic is NP-hard. This remains true even if f is non-decreasing and ultimately affine.

Proof. The NP-hardness result can be proved thanks to a reduction from the Frobenius problem which takes as input n integers a 1 , . . . , a n such that gcd(a 1 , . . . , a n ) = 1. It is well-known that ∃t 0 ≥ 0, ∀t ≥ t 0 , t ∈ Na 1 + • • • + Na n , but as proved by Ramirez-Alfonsin [START_REF] Ramirez-Alfonsin | Complexity of the Frobenius problem[END_REF], computing F rob(a 1 , . . . , a n ) = min{t 0 ∈ N | ∀t ≥ t 0 , t ∈ Na 1 + • • • + Na n } is NP-hard.

Construct the function f = 1 1 N\{a1,...,an} the indicator function of the set N\{a 1 , . . . , a n }, i.e. ∀1 ≤ i ≤ n, f (a i ) = 0 and ∀t ∈ {a 1 , . . . , a n }, f (t) = 1 (1 1 S (t) = 1 if t ∈ S, and = 0 if t ∈ S). This function is ultimately affine and the size of its fluid encoding is O( 1≤i≤n log 2 (a i )), the reduction is linear.

Using Equation 1, we easily obtain that if t ∈ Na 1 + • • • + Na n , f * (t) = 0 and otherwise f * (t) = 1, i.e. f * = 1 1 N\(Na1+•••+Nan) . It is an ultimately affine function, and its smallest rank of pseudo-periodicity is exactly F rob(a 1 , . . . , a n ) -1. Thus the computation of the smallest rank of pseudo-periodicity of f * is NP-hard.

To get the hardness result for non-decreasing functions, in the construction, "lift" the function by considering f (t) + t instead of f (t). It is non-decreasing and it is known that (f (t) + t) * = f * (t) + t (see [START_REF] Bouillard | Some examples and counterexamples for (min, +) filtering operations[END_REF]), thus everything applies in the same way.

Beware that this result is strongly connected to the way the functions are encoded. It does not contradict the preceding subsection which presents a polynomial algorithm for the subadditive closure but where the input is the extensive encoding of f ∈ D.

A consequence of Proposition 17 for the fluid encoding, is that there is no polynomial algorithm which computes the subadditive closure, unless P=NP.

This last result could be expected for the fluid encoding, since there exist input functions such that their subadditive closure (even in its compressed form) has an exponential size compared to the input size. For instance, let a 1 , a 2 ∈ N * such that a 1 ∧ a 2 = 1, then as shown in the proof of Proposition 17, (1 1 N\{a1,a2} ) * = 1 1 N\(Na1+Na2) which has a smallest rank equal to F rob(a 1 , a 2 ) -1 = a 1 a 2a 1a 2 . Whereas the fluid encoding size of the input is always constant, the size of the subadditive closure is of the order of #(Na 1 + Na 2 ) ∩ [0, F rob(a 1 , a 2 )], i.e. Θ(a 1 + a 2 ).

In fact Proposition 17 tells a bit more. In the search for other efficient encodings, it should be noted that this hardness result remains true for any encoding of the utimately pseudo-periodic functions in Dsuch that the smallest rank of pseudo-periodicity of a function can be computed in polynomial time and which stores 1 1 N\{a1+•••+Nan} within 1≤i≤n log 2 (a i ) space (up to a constant factor). For such encodings, due to the tricky underlying Frobenius problem, there is no algorithm which computes the subadditive closure in polynomial time, unless P=NP.

Note that the hardness result is also true when we deal with ultimately pseudo-periodic functions in F[Q + , Q], even if they are continuous, non-decreasing and ultimately affine (see [START_REF] Bouillard | Some examples and counterexamples for (min, +) filtering operations[END_REF]).

Conclusion

The main stability results obtained in this article are summed up in Figure 5. 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. The paper contains most of the examples illustrating this picture, the complementary ones are presented in [START_REF] Bouillard | Some examples and counterexamples for (min, +) filtering operations[END_REF].

We have also shown that we can make effective the stability results by describing algorithms which implement the Network Calculus operations for our stable plain ultimately pseudo-periodic classes.

Beyond the correction of the algorithms, we have tried to analyze their theoretical complexities the better we could. Most of our complexity bounds take into account both the size of the inputs and the size of the output. It is natural since the whole output must be returned, but it raises two questions which require further work. What are the precise links and bounds between the size of the inputs and the size of the output, for each of the Network Calculus operations ? This may enable to refine the complexity bounds for our algorithms. In particular, one can notice that we do not quantify the complexity of our algorithms for the subadditive closure, except that the size of the output may be exponential with the size of the inputs and that there exists an underlying NP-complete problem, which implies in both ways that our algorithms are exponential. Then

INRIA

we can wonder what are the ways to avoid outputs of size exponential with the size of their inputs ? This is mainly an encoding question. For instance one could think of compressing the functions by taking into account the repeated patterns in the transitory part of the ultimately pseudo-periodic functions, as well as doing lazy computations, i.e. doing the full computation of a sequence of operations only when it is really necessary and otherwise maintain a formal expression of the output as an undeveloped combination of operations, or finally by introducing new decompositions or transformations of the functions.

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: A piecewise affine function with respect to Definition 2. Such functions are left-continuous (resp. right-continuous) if ∀i ≥ 0, f (a i ) = f (a i -) (resp. f (a i ) = f (a i +)). We will mainly consider F[N, R], F[Q + , R], F[R + , R] and 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.

Figure 5 :

 5 Figure 5: Minimum of two affine functions.

Figure 7 :

 7 Figure 7: From the function f to a directed graph.

  It yields a subgraph of G called the critical graph and denoted G c . The cyclicity d * is the lcm of the gcd of the lengths of the circuits of each strongly connected component of G c . Consider S = {t ∈ {1, . . . , T + d -1} | f (t) t = λ} the arguments reaching the minimum (if there are some). Then If c d > λ, the critical graph is the induced graph over vertices {1, . . . , max(S)} and d * = gcd(S). If c d = λ and S = ∅, the critical graph is a single circuit and d * = d. If c d = λ and S ∩ {T, . . . , T + d -1} = ∅, the critical graph is G and d * = gcd(S ∪ {d}). If c d = λ and S ⊆ {1, . . . , T -1}, the critical graph has two strongly connected components and d * = lcm(d, gcd(S))

Proposition 8 .

 8 The classes F[R + , R] and F[Q + , Q] are stable under the operations +, -, min, max.

  , b[ and = +∞ otherwise. We call ]a, b[ the support of f , σ and ρ are called the parameters of f , ρ is called the slope. ¡ With the same notation, if the support is]a, b] or [a, b[ (resp. [a, b]), f is called a semi-closed (resp. closed) segment. ¡ For T ∈ R + and a ∈ R * + , a function f is an iterated spot from T with period d and increment c if ∀i ∈ N, f (T + id) = f (T ) + ic, and f (t) is +∞ elsewhere. ¡ For T ∈ R + , c ∈ R and d ∈ R *+ , a function f ∈ F is an iterated segment from T , with period d and increment c and slope ρ if ∃a ∈ R * + , ∃f (T +), σ ∈ R such that a ≤ d and ∀i ∈ N, on the interval ]T + id, T + id + a[, f is affine with ∀t ∈]0, a[, f (T + id + t) = f (T +) + ic + ρt, and on all other intervals f is +∞.

INRIA

3. 2 . 1

 21 Stability for the convolution Lemma 2 (Convolution of spots). Let f 1 and f 2 be two spots respectively on a and b. Then

Remark 5 .Figure 8 :Proposition 9 .

 589 Figure 8: Convolution of two segments.

  R] and let (f n ) n∈N and (g n ) n∈N be their respective elementary decompositions into segments and spots. Let A ∈ R + and n 0 = min{n ∈ N | f n and g n have a support disjoint from [0, A]}. Since for all t ∈ R + , f * g(t) depend only on the values of f and g on [0, t], the restriction of f * g on [0, A] satisfies f * g = min i,j∈{0,...n0} (f i * g j )| [0,A] . Thus f * g is piecewise affine on [0, A]. It is true for every A ∈ R + , which means that f * g is piecewise affine. The stability of the classes F[R + , R] and F[Q + , Q] is a consequence of their stability for the minimum.

Figure 9 :

 9 Figure 9: Deconvolution of two segments.

Corollary 1 .

 1 The classes of ultimately affine functions in F[R + , R] and F[Q + , Q] are stable under the deconvolution.

Figure 10 :

 10 Figure 10: Subadditive closure of the two types of segments.

Figure 11 :

 11 Figure 11: Iterated convolution f (k) of the iterated segment f .To study the subadditive closure, we will consider two cases depending on the comparison of ρ and c/d and their subcases.Suppose that c d ≤ ρ.

2 :

 2 T, d); Merge the sorted lists of jump points of f 1 and f 2 on [0, T + d[; Compute f 1 + f 2 at each jump point and between each pair of consecutive jump points in the merged list; end Algorithm Addition of two functions (detailed single pass version).

  T, d); Merge the sorted lists of jump points of f 1 and f 2 on [0, T + d[; Compute min(f, g) at each jump point and between each pair of consecutive jump points in the merged list; end Proposition 13. Let f 1 , f 2 ∈ F[Q + , Q] both ultimately plain pseudo-periodic. Then, with the notation of Algorithm 3, min(f 1 , f 2 ) can be computed in time O(N e 1 + N e 2 ) where N e 1 = n 1 + p 1 (T +d)-T1 d1

  T 1 [ and = +∞ elsewhere, is the transient part, and f 1 = f 1 on [T 1 , +∞[ and = +∞ elsewhere, is the pseudo-periodic part. The same decomposition is applied to

  2)b[ and ultimately pseudo-periodic from b( a b-a + 1) with period b and increment f (b-); end Algorithm 11: Subadditive closure of an iterated segment (using Algorithms 12 and 13 as subroutines).

  x); y ←ValuePlus(f, x); ρ ←Slope(f ); g ← g :: (x, v, y, ρ); e ←End(f ); while e < T + d do if e ∈ N then x ←Next.Point(f ); v ←Value(f, x); y ←ValuePlus(f, x); ρ ←Slope(f ); g ← g :: (x, v, y, ρ); e ←End(f ); else v ←Value(f, e ); repeat x ←Next.Point(f ) until End(f ) > e v ←Value(f, e ); y ←ValuePlus(f, e ); ρ ←Slope(f ); g ← g :: ( e , v, v, vv) :: ( e , v , y , ρ ); e ←End(f ); g ← g + ( T , d, c); end

F

  sub. clos. sub. clos. ult. plain ps.-period. ps.-period. plain ult. ps.-period. plain ult. ps.-period. plain ult. affine plain ult. affine plain ult. affine plain ult. affine * , min, max, * plain F[R+, R]

  4. The term f 1 * f 2 is ultimately pseudo-periodic from T 1 + T 2 with period d 2 and increment c 2 , thus it is sufficient to compute it on [0, T 1 + T 2 + d 2 [ (note that its support is within [T 2 , +∞[). This computation requires the values of f 1 over [0, T 1 [ and the values of f 2 over [T 2 , T 1 + T 2 + d 2 [. Following the method for f 1 * f 2 , decomposing into spots and segments the two functions on those intervals enables to compute the convolution on [0, T 1 + T 2 + d 2 [. 5. The same method applies to f 2 * f 1 which is ultimately pseudo-periodic from T 1 + T 2 with period d 1 and increment c 1 . 6. The term f 1 * f 2 is ultimately pseudo-periodic from T 1 + T 2 + d with period d = d 1 ∨ d 2 and increment d min( c1 d1 , c2 d2 ), thus it is sufficient to compute it on [0, T 1 + T 2 + 2d[ (note that its support is within [T 1 + T 2 , +∞[). This computation requires the values of f 1 over [T 1 , T 1 + 2d[ and the values of f 2 over [T 2 , T 2 + 2d[. Decomposing into spots and segments the two functions on those intervals enables to compute the convolution on [T 1 + T 2 , T 1 + T 2 + 2d[ and thus [0, T 1 + T 2 + 2d[.

Table 1 :

 1 Analysis of the different steps of Algorithm 5 Let f 0 be the spot at 0 with value 0; For all 1 ≤ i ≤ a b-a , let f i be the segment on ]ia, ib[ with slope ρ s.t. f i (ia+) = if (a+); For i = a b-a + 1, let f i be the semi-closed segment on ]ia, (i + 1)a] with slope ρ s.t. f i

	(T +d)-T 1
	d 1

RR n 6094

INRIA

Proof. Computing M 1 (resp. m 2 ) can be done in O(p 1 ) (resp. O(p 2 )). Extending the data structure for f 1 and f 2 up to T + d requires O(N e 1 + N e 2 ) steps, and merging the two corresponding lists of jump points can be done in O(N e 1 + N e 2 ). Then between two jump points of the merged list, at most one new jump may appear (at the intersect of two segments), which justifies the bound N min(f1,f2) ≤ 2(N e 1 + N e 2 ). Algorithm 4 is the single pass algorithm which ends and outputs the right result if the minimum is ultimately pseudo-periodic. Its runtime is at worst the same as Algorithm 3. But it may be better since it detects a rank of pseudo-periodicity as soon as it is encountered, whereas the rank T computed in Algorithm 3 is a rough bound which may be larger than the one of Algorithm 4.

Algorithm 4: Minimum of two functions (detailed single pass version).

Data: f 1 = ([(x 1 1 , f 1 (x 1 1 ), y 1 1 , ρ 1 1 ), . . . , (x 1 k , f 1 (x 1 k ), y 1 k , ρ 1 k )], (T 1 , d 1 , c 1 )) and f 2 = ([(x 2 1 , f 2 (x 2 1 ), y 2 1 , ρ 2 1 ), . . . , (x 2 , f 2 (x 2 ), y 2 , ρ 2 )], (T 2 , d 2 , c 2 )) which are ultimately plain. Result: g = min(f 1 , f 2 ) with parameters T , d, c. begin case c1 d1 < c2 d2 :

if not((min = 1 and I = {2} and v 2 ≥ v 1 and (y 2 > y 1 or (y 2 = y 1 and ρ 2 ≥ ρ 1 ))) or (min = 2 and I = {1} and v 1 ≥ v 2 and (y 1 > y 2 or (y 1 = y 2 and

ρ1-ρ2 ; case y 1 > y 2 and z 2 > z 1 : g ← g :: (x, y, y, ρ 1 ); Set(min, 1); case y 1 < y 2 and z 2 < z 1 : g ← g :: (x, y, y, ρ 2 ); Set(min, 2);

The maximum of functions works exactly in the same way.

Minimum of several ultimately pseudo-periodic functions. Computing the minimum of several functions has actually been extensively studied in computational geometry where the problem is often refered as the computation of the lower envelope of functions. The next theorem sums up the main results which can be found in the literature. In the statement, a total function in F is a function whose support is R + and a partial function in F is a function whose support is an interval of R + . The parameter λ s (n) is the maximum length of an (n, s) Davenport-Schinzel sequence, it occurs in several problems from geometry, but its definition and its study belong to the theory of finite words [START_REF] Agarwal | Davenport-Schinzel Sequences and Their Geometric Applications[END_REF][START_REF] Agarwal | Davenport-Schinzel sequences and their geometric applications[END_REF]. The function α(n) is the inverse Ackermann function which grows extremely slowly, e.g. α(n) ≤ 5 when n ≤ 2 65536 [START_REF] Cormen | Introduction to Algorithms[END_REF].

Algorithm 5: Convolution of two functions (sketch).

Data:

ultimately pseudoperiodic, e.g. at least one is ultimately plain. Then using its notations, Algorithm 5 computes

where

d1 ) and

). The size of the output satisfies

)).

Proof. The sets (f

d1 , and can be generated in linear time with respect to their cardinals. The same holds for (f 2,j ) j∈J , (f 2,j ) j∈J , (f 2,j ) j∈J . The next steps of Algorithm 5 can be analyzed through the quantities presented in Table 1.

Each elementary convolution in (f

) i∈I ,j∈J can be computed in O(1) time thanks to Lemma 2, 3 and 4. The minimum (lower envelope) of each of these four families can be computed with the algorithms mentioned in Theorem 3, thus in time O(M log M ) where M is the number of spots and segments generated by the respective elementary convolutions (knowing that an elementary convolution leads to at most two consecutive segments). During the last step of Algorithm 5, the minimum of these four minima can be computed by the simple one-pass algorithm. The pass extends the four functions over R + until a rank T of pseudo-periodicity is found, i.e. they are extended over the interval [0, T +d[. One needs to know the sizes of the four functions over this interval to give an upper bound on the complexity. One way to achieve that is to decompose once more the functions into spots and segments over [0, T + d[ this time and see each function as a minimum of the corresponding elementary convolutions, i.e. a minimum of spots and segments. It gives a bound on the size of the output thanks to the Davenport-Schinzel number λ 3 cited in Theorem 3. Note that if one can precompute quickly a small rank T of pseudo-periodicity, it can directly uses this scheme of decomposition over [0, T + d[, it enables to avoid the computation of the four intermediate convolutions, and then using the output sensitive algorithm becomes really relevant. In such a scheme, the performance relies on the success and speed when precomputing the small T .

Back to Algorithm 5, with the notation of Table )) time and this is also an upper bound on the size of f 1 * f 2 . To get the shorter form in the statement of the proposition using N e 1 = N e 1 +N e 1 and N e 2 = N e 2 +N e 2 , use the fact that the function α is non-decrasing and subadditive.

RR n 6094

In the same way, the first steps of computation of the four minima have a time complexity

). Since log is non-decreasing and subadditive, this complexity is upper bounded by O(N 1 N 2 log max(N 1 , N 2 )) where

d1 ) and

d2 ).

Deconvolution of ultimately pseudo-periodic functions

To compute the deconvolution of two ultimately pseudo-periodic functions

we use the same scheme as for the convolution : we decompose f 1 and f 2 into spots and segments over appropriate intervals, then compute all the corresponding elementary deconvolutions and finally take their maximum with an upper envelope algorithm. From Proposition 10, f 1 f 2 is ultimately pseudo-periodic from T 1 with period d 1 . Thus it is sufficient to compute f 1 f 2 over [0, T 1 + d 1 [. Moreover the proof shows that ∀t ≥ 0, sup s≥0 (f (t + s)g(s)) Data:

Let (f 1,i ) i∈I be the set of spots and segments of f 1 over [0, T + T 1 + d 1 [; Let (f 2,j ) j∈J be the set of spots and segments of f 2 over [0, T [; Use an upper envelope algorithm to compute max i∈I,j∈J f 1) time, thanks to Lemma 5, 7, 6 and 8. Each elementary deconvolution yields at most to consecutive segments. Their maximum can be computed with a upper envelope algorithm such as the ones for lower envelopes cited in Theorem 3. They have the same complexities and the size of the output admits the same kind of bound.

Subadditive closure of an ultimately pseudo-periodic function

Let f ∈ F[Q + , Q] be an ultimately pseudo-periodic function, Algorithm 7 computes its subadditive closure by following the proof of Proposition 11.

Note that, due to the commutativity and associativity of * , several sequences of pairwise convolutions achieve the computation of

In the proof of Proposition 11, in case f had at least one segment, the sequence of convolutions was careful chosen so that Proposition 6 for * ensured the ultimate pseudo-periodicity of each output without using any other result like Proposition 7 for the discrete model. Such a restriction (aimed at refining the proof) is not necessary for the computations. Any sequence of convolutions will give intermediate outputs which are ultimately pseudo-periodic: any convolution of some f * j , j ∈ J ⊆ {1, . . . , k}, is the subadditive closure of an ultimately pseudo-periodic function, namely min j∈J f j , which is ultimately pseudo-periodic due to Proposition 11. Algorithm 5 can be used to compute the k -1 necessary convolutions.

Specific algorithms to compute the subadditive closure of spots, iterated spots, segments and iterated segments can be directly derived from the proofs of stability in Subsection 3.2.3, i.e. Lemma 10, 11, 13 and 14. They are described below. The four algorithms assume that the input function f satisfies f (0) ≥ 0, otherwise

begin Let (f i ) 1≤i≤k be the finite set of spots, iterated spots, segments and iterated segments such that f = min 1≤i≤k f i ; Compute f * i for all 1 ≤ i ≤ k using the specific algorithms for spots, iterated spots, segments and iterated segments;

The complexity analysis of the whole Algorithm 7 involving a non constant number of convolutions remains open.

Algorithm 8: Subadditive closure of a spot.

Data: f a spot on a.

Result: f * . begin if a = 0 then f * is the spot on 0 such that f * (0) = 0 else f * is the iterated spot from 0 such that f * (0) = 0, with period a and increment f (a). Data: f an iterated segment with parameters T, d, a, c, ρ, and an integer i ∈ N. Result: g i as defined in Lemma 14 (only relevant cases are listed). begin