4.2.1. Representation of piecewise linear concave and convex functions

In this section, we assume that all of the functions considered are in and ultimately linear. Considering functions in is not a technical limitation, but this will ease the notations by replacing linear functions and potential discontinuities at 0 with token-bucket functions. Being ultimately linear ensures the finiteness of the representation of a function. Furthermore, the functions used in practice are in . There are two natural ways to represent piecewise linear concave functions:

• – by a finite list of token-bucket functions (the concave function is then the minimum of those functions);
• – by a finite list of segments, which are open on the left (to take into account the potential discontinuity at 0). This representation explicitly contains useful information about the intersections of the token-buckets of the former representation.

Let us first give the equivalence between those two representations and then discuss them.

DEFINITION 4.1 (Concave piecewise linear normal form).– Let be non-negative numbers and set . The piecewise linear concave function

[4.1]

is said to be in normal form, if are sorted by a decreasing slope and no can be removed without modifying the minimum:

[4.2]

[4.3]

If is in normal form, we can define the sequence of the respective intersection points of and

PROPOSITION 4.1 (Concave piecewise linear function properties).– Let be a piecewise linear concave function in normal form. The following properties hold:

1. 1) f is concave;
2. 2) the sequence is increasing ;
3. 3) the sequence (defined above) is increasing ;
4. 4) the function is piecewise linear. More precisely,

PROOF.– 1) is a direct consequence of Proposition 3.12.

2) If there exists i such that , as , so condition [4.3] is not satisfied for i.

3) We again use the notation . As is decreasing and is increasing,

Now, by contradiction, if there exists i such that which contradicts condition [4.3] of normal form.

4) As is increasing, and . Therefore, for all .

□

This proposition leads to two representations of piecewise linear and concave function f : either , and the representation is a list , or as a list of segments, and the representation is a list . In the latter case, the information is redundant, as can be recovered from the list .

Depending on the operation to be implemented, it will be more interesting to use a representation with a list of linear functions or a list of segments. For example, the minimum can be efficiently implemented with a list of linear functions: it is the concatenation of the two lists. To obtain a normal form, it suffices to merge the two sorted lists (which can be done in time linear in the number of functions, eliminating the useless functions on the fly). The (min,plus) convolution is similar.

For computing the sum of two functions, using the linear representation would lead to a quadratic time algorithm (the minimum distributes over the sum). It is possible to define a more efficient algorithm using the segments representation. The number of segments of the result is linear in the total number of segments of the operands (see section 4.3.2 for details).

The class of convex piecewise linear functions can be defined as the maximum of rate-latency functions, defining intersection points similarly. In this class, the maximum of two functions is the concatenation of the linear representations, but the (min,plus) convolution is efficiently implemented with the segment representation, as will be explained in section 4.2.2.1.

4.2.2. (min,plus)-convolution of convex and concave functions

We have already seen in Proposition 3.12 that the convolution of two concave functions is the minimum, up to an additive constant, of these functions.

In this section, we focus on the convolution of two convex functions and of a convex function by a concave function.

4.2.2.1. Convolution of two convex functions

The convolution of two convex functions can be efficiently implemented with the segment representation. The most classical proof uses the Legendre–Fenchel transform (see, for example, [BOU 08b]), but we present here a direct and algorithmic proof.

THEOREM 4.1.– Let f and g be two convex piecewise linear functions. Let (resp. ) be the (possibly infinite) slope of the last semi-infinite segment of f (resp. g). The convolution consists of concatenating all of the segments of the slope at most in the increasing order of the slopes starting from , including the semi-infinite segment.

This computation is illustrated in Figure 4.4.

PROOF.– Consider the first segment of f of slope , and the first segment of g of slope , and suppose without loss of generality that and that the length of the first segment of f is . Then, for every ,

As g is convex, , so .

If , then is a linear function consisting of the infinite segment of f (with the smallest slope).

Otherwise, consists of the segment of the smallest slope on .

Let t > and suppose that and .

But , so and u can be chosen to not be smaller than .

Therefore, we can always write

with . In other words, is constructed from by removing the first segment in (and = 0). Function is also convex, so we can iteratively compute the remainder of * g. The segments of and g are clearly concatenated in increasing order of the slopes. If there is a segment of infinite length, then the segments of greater slopes are ignored.

□

4.2.2.2. Convolution of a convex function by a concave function

The convolution of a concave function by a convex function is more involving. However, it is possible to do it in time (n log n). Up to now, it is not directly useful in the network calculus framework, but it has been used for the fast (min,plus) convolution in the Hamiltonian system [BOU 16a].

The convolution of a segment by a piecewise linear convex function can be deduced from the convolution of two convex functions in Theorem 4.1. Let : [a, b] → be a convex piecewise linear function, represented by a list of segments : [a_i, a_i+1 ] → , i ∈ {1, n} and g : [c, d] → be a segment. Then, * g : [a + c, b + d] → is a convex piecewise linear function defined by

where u = min{a_i ∈ [a, b] | }.

Figure 4.5 illustrates this construction. In the rest of the section, we will use the decomposition of such a convolution into three parts: * g = min(g¹, g^c, g²), where

In other words, g¹ is composed of the segments of whose slope is strictly less than that of g, g^c corresponds to the segment g and g² is composed of the segments of , whose slope is greater than or equal to that of g. Note that g^c is also concave.

Now, suppose that g : [c, d] → is a concave piecewise linear function represented by the list of segments g_j : [c_j ,c_j+1] → , j ∈ [1, m]. Then, by distributivity (Lemma 2.1), and as ,

Let us study where the segments are placed. The following lemma, which considers two consecutive segments of g, leads to an efficient algorithm to compute the convolution of a convex function by a concave function.

LEMMA 4.1.– Consider the convolutions * g_j-1 and * g_j. Let

and

Then:

• – ;
• – .

PROOF.– First, as is convex and , we have u_j-1 u_j. From the above section, for all t c_j + u_j,

Either t c_j-1 + u_j-1, then * g_j-1 (t) = (t - c_j-1) + g(c_j-1) and

as t – c_j–1 u_j-1, the derivative of at t - c_j-1 is less than , so (t - c_j-1) - (t - c_j) .(c_j - c_j-1) and * g_j(t) - * g_j-1(t) 0;

or t > c_j-1 + u_j-1, then * g_j-1(t) = (u_j-1) + g(t - u_j-1). As c_j-1 < t - u_j-1 t - u_j c_j, we have g(c_j) - g(t - u_j-1) = . (c_j + u_j-1 - t). Moreover, by definition of u_j-1, the derivative of before u_j-1 is less than and (u_j-1) - (t - c_j) .(c_j + u_j-1 - t), so finally, * g_j(t) - * g_j-1(t) 0.

The second statement can be proved similarly.

□

Another formulation of Lemma 4.1 is that and , and that the two functions intersect at least once. Hence, and cannot appear in the minimum of * g_j and * g_j-1. By transitivity, there is no need to compute entirely the convolution of the convex function by every linear component of the decomposition of the concave function. If there are more than two segments, successive applications of this lemma show that only the position of the segments of the concave function has to be computed, except for the extremal segments.

The intersection of * g_j-1 and * g_j can then happen in one and only one of the four cases:

1. 1) and intersect;
2. 2) and intersect;
3. 3) and intersect;
4. 4) and intersect.

As a direct consequence of this lemma, a more precise shape of the convolution of a convex function by a concave function can be deduced.

THEOREM 4.2 (Convolution of a convex function by a concave function).– The convolution of a convex function by a concave function can be decomposed in three (possibly trivial) parts: a convex function, a concave function and a convex function.

A formal proof of those result can be found in [BOU 16a]. The main idea is to proceed by induction using Lemma 4.1 for the initialization.

If the concave function is composed of m segments and the convex function of n segments, then the convolution of those two functions can be computed in time (n + m log m). The log m term comes from the fact that we have to compute the minimum of m segments (see [BOU 08c] for more details).

Note that the shape of the function is simplified when the functions have infinite supports (b = +∞ or d = +∞). Indeed, either the last slope of is less than the last slope of g, in which case each slope of is smaller than each slope of g and * g = + g(0) (assuming without loss of generality that a = c = 0); or the last slope of g is less than the last slope of , in which case * g is composed of a convex function and a concave function only, as the convolution by the last segment of g does not make a final convex part appear.

4.3.1. Examples of instability of some classes of functions

In section 4.1, numerous classes of functions have been defined. We here justify through example why they had to be defined. As we want a simple and finitely representable class, it is therefore natural to focus on piecewise linear functions that ultimately have a periodic behavior. Indeed, those functions can be represented by a finite sequence of points and slopes. This section enumerates some examples of classes of functions that are not stable. More counterexamples can be found in [BOU 07a]. This section also justifies the class of functions we defined at the beginning of section 4.1.

Linear functions are not stable. The class of linear functions is of course not stable. For example, consider t min(3t, 5t - 2).

Ultimately linear functions are not stable. Consider

Then,

where n ∈ and t ∈ [0,2). Clearly is ultimately pseudo-periodic, but not ultimately linear. and are represented in Figure 4.7.

These two examples show that we have to choose sets of functions that are large enough. The next examples show that we have to restrict the space of functions we want to consider for a further analysis.

Piecewise linear functions are not stable. Consider a function h defined on [0,1) that is convex and on this interval (continuous and with a continuous derivative). We will build two piecewise linear functions and g such that , showing that piecewise linear functions are not stable.

As h is convex on [0,1), for all t ∈ [0,1), h(t) can be expressed as

by density of in . As [0, 1) ∩ is denumerable, there exists a sequence that enumerates all of those elements. We now consider this sequence to construct and g such that .

For n ∈ , set if t ∈ [0,1) and = –∞ otherwise and g_n(2n + t) = if t ∈ [0,1) and = +∞ otherwise. Note that for t ∈ [0,1),

Define and . For all t ∈ [0,1), . But, as t ∈ [0,1), it also holds that

Figure 4.8 illustrates this construction. Here, we have used functions that take infinite values. In [BOU 07a], it is proved that and g can be chosen finite and non-decreasing.

To avoid this problem, we will restrict to the class of functions that are ultimately pseudo-periodic and piecewise linear. This way, every function has only a finite number of slopes, and such a construction becomes impossible.

Ultimately pseudo-periodic linear functions are not stable. It is a classical result: if and g are two periodic functions, + g is periodic if and only if and g have periods and with . Therefore, we will only consider piecewise linear functions that only have discontinuities at rational coordinates and rational slopes.

Non-plain functions are not stable. Finally, we also have to consider plain functions. Indeed, if functions are not plain, it is possible to construct functions that are not ultimately periodic. For example, consider and if there exists n ∈ , such that t ∈ [2n, 2n + 1] and +∞ otherwise. Thus, min(, g) is not periodic as depicted in Figure 4.9.

4.3.2. Class of plain piecewise linear ultimately pseudo-periodic functions

In this section, we show that the class of plain ultimately pseudo-periodic functions in is stable. As these functions can be finitely represented, it is possible to algorithmically define the (min,plus) operators on these functions. For this, we first propose a data structure to represent them.

4.3.2.2. Main theorem and ideas for the algorithms

THEOREM 4.3.– The class of the plain ultimately pseudo-periodic functions of is stable by the operations of minimum, maximum, addition, subtraction, deconvolution and sub-additive closure.

The rest of the section sketches the proof of this theorem. A complete proof can be found in [BOU 08c].

Consider f and g, plain ultimately pseudo-periodic functions of . It is obvious that the combination of two plain functions is plain, and we will not prove these.

Addition, subtraction of functions

LEMMA 4.2.– is plain ultimately periodic from , with period and increment .

PROOF.– ,

using the classical equality . The subtraction is similar.

□

The addition can be done in time . Indeed, . Moreover, and . Therefore, it is sufficient to compute addition on the interval [0, T] with . One way to compute f + g is to merge the list of spots in [0, T] and compute the addition at each spot as well as the slope between two spots. It can be done through a single pass over f and g. The complexity of this algorithm is .

The subtraction can be done the same way.

Minimum, maximum of functions

LEMMA 4.3.– is plain ultimately periodic, and:

• – if , then ultimately, with period d_f and increment c_f;
• – if , then ultimately, with period d_g and increment c_g;
• – if , then is ultimately periodic from with period and increment .

PROOF.– The first two cases are symmetric, so we focus on the first and third ones. Set , and . In the third case, for all ,

In the first case, there exists such that, for all , and there exists such that, for all , and by hypothesis, . Therefore, from ,

so , and the rest follows.

□

As shown in the proof, in case the two functions do not have the same growth rate, it is not easy to compute in advance the rank from which is pseudo-periodic (the proof only gives an upper bound). Algorithmically, the solution is to go through the quadruplets of functions f and g in order, computing the intersection of segments, and extending the functions from one period at a time when the transient period or a function has been treated. When the minimum is on a complete period of f (or g), let us say from time T, has become pseudo-periodic. The complexity is then in .

Convolution offunctions

LEMMA 4.4.– f ∗ g is ultimately pseudo-periodic with period and increment .

PROOF.– We use the decomposition of f and g into their transient and periodic parts:

As f_t and g_t have a finite support, so does , which is then ultimately equal to .

Let us now focus on . For all . Owing to the support of f_t, s can be taken to not be greater than T_f, so , so and is ultimately pseudo-periodic with period d_g and increment c_g. Similarly, is ultimately pseudo-periodic with period d_f and increment C_f.

Finally, let us show that is pseudo-periodic. For all ,

f ∗ g is then the minimum of four ultimately periodic functions of , so it is itself ultimately pseudo-periodic from Lemma 4.3.

□

Algorithmically, a generic way of computing the convolution of a function is to compute the convolution of each pair of segments of f and g. The (min,plus) convolution of two segments is a direct consequence of Theorem 4.1: a segment is convex. Just note that this result holds for open segments. The convolution of two segments can be made in constant time, and then, by distributivity of the convolution over the minimum, the minimum of all these convolutions has to be computed. Using Lemma 4.3, it is possible to compute the rank T from which f ∗ g will be ultimately periodic. The number of segment convolutions to compute is then in , and the minimum of all these functions has to be computed. The use of a divide-and-conquer approach leads to a complexity.

It is also possible, if it makes sense, to use the shape of the function, and decompose it into convex and concave parts in order to use efficient convolution algorithms from Theorems 4.1 and 4.2.

Deconvolution offunctions

LEMMA 4.5.– is ultimately pseudo-periodic from T_f with period d_f and increment c_f.

PROOF.-For all ,

□

To compute the deconvolution of two functions f and g, we also use the properties of the deconvolution of Propositions 2.7 and 2.8 and the following lemma for the convolution of segments.

LEMMA 4.6.– Let and be two segments, respectively, defined on the intervals I and J. Let a = inf I and d = sup J. Then, is defined on and consists of concatenating the segments f and g from , with the segment with the larger slope first, where .

Note that, in this lemma, outside J, we set by default .

PROOF.– First, is defined if and finite if there exists such that . We use the additional notations b = sup I and c = inf J, and recall that is the slope of f (resp g).

Either , and u has to be maximized, if and if or , and u has to be minimized: if , and if .

□

Similarly to the convolution, we decompose the functions into segments and spots and perform the elementary deconvolutions on these, and compute the maximum of these.

Sub-additive closure of a function

Computing the sub-additive closure of a function is more complex. The following lemma gives a trick to compute only the sub-additive closure as a finite number of convolutions of segments and spots. This result is unpublished and credited to Sébastien Lagrange.

LEMMA 4.7.– Let . Then, .

PROOF.– Recall that is the unit element of the dioid of (min,plus) functions. From Proposition 2.6, and for all . Therefore, by commutativity of the (min,plus) convolution,

□

We can now apply the lemma by slightly modifying the representation of a function f. We still have f_t as its transient part, but we decompose the periodic part into , where f_1p is the restriction of f to (it is only the first period), and f_s is a spot defined at . Therefore, f can be expressed as . From Lemma 4.7, . Only the sub-additive closure of functions composed of a finite number of spots and segments has to be computed, which boils down to computing the sub-additive closure of spots and segments (using .

LEMMA 4.8.– Let f be a spot: f is defined on {d} and f (d) = c. Then, f ^* is a function defined on and f (nd) = nc for all .

PROOF.– For all , fⁿ is a spot defined at nd and , so the result straightforwardly holds since .

□

LEMMA 4.9.– If f is a segment defined on an open interval, then f ^* is ultimately pseudo-periodic.

PROOF.– Suppose that f is defined on (a, b) and that for all . For all , fⁿ is an open segment of slope f^' defined on (na, nb). We differentiate two cases, depending on how f^'a compares to f (a).

First, assume that . This is equivalent to . Let . Then, f ^* is ultimately pseudo-periodic from n₀b, of period b and increment f ^'b: for all

wherever is defined, that is, for t > b. Therefore, if .

If , then f ^* is ultimately pseudo-periodic from n₀a, of period a and increment f ^'a: for all ,

Therefore, for .

□

The sub-additive closure is algorithmically the most costly operator: it is even an NP-hard problem to know the rank from which a function is pseudo-periodic: considering a function that is 0 everywhere except at a finite set , it is equivalent to solve the Frobenius problem: , which is proved to be NP-hard in [RAM 96].

4.3.3. Functions with discrete domain

We discussed our choice of using as the time domain in section 1.3. Indeed, there is in general no assumption of a common clock synchronizing a network. However, for some applications where a synchronizing clock exists, such as systems-on-chip, it may be more accurate to use the time domain .

Let denote the set of functions of a discrete time domain. All the (min,plus) operators can be defined similarly to the continuous case, and are denoted . For example, .

From an algebraic viewpoint, the associativity, commutativity and distributivity properties of the (min,plus) operators remain, so that is a dioid. Some properties are even simpler to obtain, as, for example, the (min,plus) convolution is now computed as a minimum and not an infimum.

It is also possible to link the results of the operators in the continuous-time domain and the discrete-time domain. For this, we must first define projection and interpolation between the two domains. For , we denote by its projection on .

Conversely, different interpolations, illustrated in Figure 4.10, from can be defined:

1. 1) the linear interpolation ;
2. 2) the left-continuous staircase function ;
3. 3) the right-continuous staircase function .

We now can make explicit the relations between the projections and interpolations.

First, it was shown in [BOU 08c, Prop. 1] that for any operator and any function ,

and in [BOU 07b, Prop. 2] that if, moreover, f is non-decreasing,

Note that these equalities only hold for expressions involving one single operator: for more complex expressions, performing all computations in the continuous-time domain from the interpolated functions and then going back to the discrete-time domain may not lead to the right result. An example is : as a function in , we have f (3) = 6, but as a function in , we have f (3) = 7.

From an algorithmic viewpoint, the choice of the time domain strongly depends on the shape of the functions: if the linear interpolation reduces the size of the representation, it might be efficient to use it. Otherwise, a discrete-time representation might be more efficient. The algorithms can easily be adapted to the discrete-time domain.

4.4.1. Notations and context

All functions of this section belong to , the set of non-negative and non-decreasing functions. Remember that is a complete dioid.

Furthermore, the bounds of the containers are piecewise linear and ultimately linear. Among these functions, convex functions – with a constant part on (see Figure 4.11) - and almost concave functions – almost because they are constant on the interval and concave on (see Figure 4.12) – are used. Convex functions belong to the set that we denote as , and almost concave functions to the set that we denote as . The asymptotic slope of a function is the slope of the last semi-infinite segment denoted . This slope cannot be infinite.

A function of either can be seen as the following convolution:

[4.4]

where function is called an elementary function and is defined by:

[4.5]

This means that these convex and almost concave functions can always be reduced to a piecewise linear convex or concave function, null at the origin and shifted in the plane by an elementary function. Function g can also be expressed as .

During the computations, we will also need some approximation operators in order to always bring back the results in sets and . Let be a non-decreasing function of . On the one hand, is the convex hull of , i.e. the greatest convex function smaller than . Hence, . On the other hand, is the concave approximation defined as follows:

[4.6]

where and is the smallest concave function greater than on . Hence, .

Finally, (respectively ) if is an ultimately linear function, and (respectively ) if is an ultimately pseudo-periodic function with growth rate .

4.4.2. The object container

In this section, we use the Legendre–Fenchel transform introduced in section 3.3.2, and is the set of functions that have the same Legendre–Fenchel transform as .

DEFINITION 4.2 (Set F of containers).– The set of containers is denoted by F and defined by

with the subset is defined as

Hence, a container of F is a subset of an interval , the bounds of which are convex for , are almost concave for and have the same asymptotic slope . A container of F is also a subset of an equivalent class . This means that all elements of are equivalent to modulo the Legendre–Fenchel transform .

Properties of the lower bound

The lower bound plays a very important role in the definition of a container thanks to the following proposition:

PROPOSITION 4.2.– Functions , g ∈ have the same Legendre–Fenchel transform if and only if they have the same convex hull:

Moreover, the convex hull of is the least representative of :

PROOF.– First, and is an isotone mapping, so (from Proposition 3.15 because is a convex function). But is the greatest convex function smaller than and is convex, so . Thus, .

Now, we deduce .

Conversely, is convex, so . Therefore, .

The second part of the proposition is equivalent to equation [3.14].    

□

This proposition allows us to say that because , we have which is equal to . Consequently, for a function ∈ , the non-differentiable points of truly belong to . They also have the same asymptotic slope (or growth rate). Moreover, we can see that is the least representative of and so of.

Equivalence class is graphically illustrated in Figure 4.13 by the gray zone. Functions that have the same non-differentiable points and the same asymptotic slope as (which is an ultimately pseudo-periodic function in this figure) belong to this equivalent class for which is the least representative.

Finally, the following proposition says that equivalence classes modulo the Legendre–Fenchel transform are actually elements of a dioid.

PROPOSITION 4.3 (Dioid ).– The quotient of dioid by congruence (defined in equation 3.13) provides another dioid denoted as . Elements of are equivalence classes modulo the Legendre–Fenchel transform . Minimum and convolution between them are such that:

[4.7]

[4.8]

By deduction, sub-additive closure of is such that:

[4.9]

PROOF.–From Proposition 3.15, . Therefore, if and , then . So and and is well defined.

The same considerations apply to the convolution and to the sub-additive closure.    

□

As a result of this proposition, performing computations on the lower bounds of containers actually amounts to use operations of the dioid and to handle canonical representatives (the least ones) of its elements, since the elements of are equivalent to modulo the Legendre–Fenchel transform .

In addition, the following lemma provides some nice equivalences that will be used for the computations between containers. They directly follow from Propositions 4.2 and 4.3.

LEMMA 4.10.– Computing with elements of dioid is equivalent to computing with convex hulls of functions. Formally, :

[4.10]

[4.11]

[4.12]

Canonical representation

Now, by defining a canonical upper bound of and because is the canonical lower bound of a container, it is possible to obtain a canonical representation of a container as follows:

PROPOSITION 4.4 (Canonical upper bound of ).– Let be an equivalence class modulo the Legendre–Fenchel transform and be its least element, i.e. . The piecewise constant function defined below as the sum of elementary functions is a canonical upper bound of :

[4.13]

where pairs (t_i,k_i) are the coordinates of the non-differentiable points of . Therefore:

This upper bound is illustrated by the bold segments in Figure 4.14 in which the gray zone represents the equivalent class .

It must be noted that does not belong to since the asymptotic slope of , i.e. +∞, is not equal to the asymptotic slope of , the least element of .

DEFINITION 4.3 (Canonical representation of a container).– The canonical representation of a container is

Note that with this representation, with .

The advantage of such a canonical representation is to remove some ambiguities. Indeed, if ∈ , then . Hence, as is illustrated in Figure 4.15, is the greatest element of the container , and interval (the gray zone in Figure 4.15) contains function . Consequently, as illustrated in Figure 4.16, the same container of F can be represented by different intervals, and , as long as .In other words, we can have

In Figure 4.16, this canonical representation is given by the container since .

By conducting the concave approximation of , we are still in the set F and we propose a canonical representation of objects that we handled.

Data structure. This canonical representation will also be the one chosen as data structure for the function representation. Indeed, in addition to offering the advantage of unambiguously representing a container of F, it allows useless points of to be removed. In the example of Figure 4.16, the points of and graphically located above can thus be removed in order to keep only the canonical representation .

Maximum uncertainty of a container

Due to the canonical representation of a container, the maximal distances in time and data domains between and are finite and the loss of precision due to approximations is bounded. This uncertainty is defined below with the following precision: abscissa of the last semi-infinite segment of an ultimately linear function is the rank of denoted as , and its corresponding ordinate is .

DEFINITION 4.4 (Maximal uncertainty of a container f).– Let be a container of F in its canonical form. Its maximal uncertainty is defined as follows in the time domain (see Figure 4.17):

and in the data domain (see Figure 4.18):

4.4.3. Inclusion functions for containers

As stated at the beginning of this section, operations defined for the containers and called inclusion functions must be such that:

• – they contain the result of exact computations in a guaranteed way;
• – they are closed for set F of containers;
• – they can be computed with an interesting algorithm complexity;
• – they provide containers that are as small as possible.

The first two criteria are mathematically proven thanks to the properties of handled functions. In particular, the condition of closure is mainly fulfilled because of the dioid structure of the convex lower bound of a container. The last two criteria are conditions that we impose on definitions to get efficient and interesting results about these computations.

DEFINITION 4.5 (Inclusion functions ). –Let and be two containers of F given in their canonical forms. Inclusion functions of minimum and convolution ∗ are denoted as and . They are defined by:

[4.14]

[4.15]

Now, let be a container not necessarily given in its canonical form. Inclusion function of the sub-additive closure .* is denoted as ^[∗] and defined by:

with

[4.16]

[4.17]

are elementary functions for which pairs (t_i,k_i) are the non-differentiable points of . Functions are defined in equation [4.4]: .

In this definition of inclusion functions, the choice of picking either the canonical form of the container or the interval without the concave approximation (i.e. ), is relevant in order to obtain a weak level of complexity in all cases.

Moreover, these inclusion functions do not necessarily provide canonical results. A simple way to obtain them is to make at the end of the computation the concave approximation of the minimum between the obtained upper bound and the actual upper bound of the equivalence class of the lower bound. For instance, the canonical result of is given by:

THEOREM 4.4.–Let and be two containers of F. Inclusion functions are such that:

PROOF.– The entire proof is given in [LEC 14]. Here, we just give its general idea.

Lower bounds of inclusion functions

We saw that the lower bound of a container is the canonical representative of an element of , since it is the least element of the equivalence class modulo . Therefore, operations on elements of are closed in dioid and so obtained lower bounds are closed in the set F. In addition, because of equations [4.7]–[4.9], we know that exact computations are included in obtained containers. Indeed, the computations are made with canonical representatives of equivalence classes (the least ones), which means that they are valid for all the other functions of the equivalence classes. Therefore, and .

For the minimum and the sub-additive closure, equations [4.10] and [4.12] correspond exactly to definitions of equations [4.14] and [4.16]. For the convolution, Proposition 3.13 allows us to say that if , then so . Hence, we do not need to make the concave approximation given in equation [4.11], but simple to directly perform the computation given in equation [4.15].

Upper bounds of inclusion functions

• – For the minimum, according to equation [4.6] about the definition of the concave approximation and since is order-preserving, it is obvious that and , , that and that .
• – For the convolution, remember that functions of can always be factorized (see equation [4.4]). Therefore, we obtain with:
  
  and (because of Proposition 3.12). Then, the minimum of two concave functions that take value 0 at 0, like f ' and g', provides a concave result (again according to Proposition 3.12) and allows us to avoid making the concave approximation of . Moreover, the asymptotic slope of is equal to that of f[*]g and so to that of f * g. Finally, since * is order preserving, and , .
• – For the sub-additive closure, it is a little bit more tricky. The general idea is to use the largest element of container f, i.e. . Then, through the use of the upper bound , non-differentiable points of are introduced in the computation, which allow us to be the least pessimistic. The following sub-additive closure is computed:

In these lines, Lemma 2.6 and Proposition 3.12 are used for the equality g = g^*; Proposition 2.6 to say that the sub-additive closure of the minimum of functions is equal to the convolution of the sub-additive closures of the functions, and the fact that the sub-additive closure is linked to the Kleene star operator (Theorem 2.3).

Some sub-additive closures of elementary functions appear in the last two lines. Unfortunately, the result of these computations provides ultimately pseudo-periodic functions such that , and for which the rank is reached at t = 0 with for the growth rate. The problem is that making convolutions between such functions is not easy in an algorithmic sense. Hence, we propose to make their concave approximations and thus obtain easier functions to compute (i.e. almost concave functions that take value 0 at 0):

By doing all of these concave approximations, it is obvious that we over-approximate the result we might obtain. However, these over-approximations allow us to compute the minimum of concave functions instead of the convolution that is much better for algorithm complexity. Indeed, thanks to Proposition 3.12, we have the following equality:

which is the computation of . With this upper bound, we still have , ; and .

□

Algorithms and complexities

Now, let us deal with the ideas of algorithms used for the computations of inclusion functions. Let and be the number of non-differentiable points of , and , respectively. We also call these numbers the sizes of the bounds (instead of the case in section 4.3 where size is for the number of segments). We will see that algorithms are of linear or quasi-linear time of the size of the container bounds.

Minimum

Inclusion function can be computed in linear time in the size of the bounds of the containers.

Indeed, the first step of the computation is to make the minimum of the lower bounds and and of the upper bounds and . This requires in the worst case only one scan of non-differentiable points of each function, and so can be done in linear time in the size of the bounds.

Then, since the minimum of two convex functions is not convex, the minimum of two almost concave functions is neither a concave function nor an almost concave function, and we need to compute the convex hull of and the concave approximation of to get a closed result in F. This can also be done in linear time by using well-known algorithms of convex hull computation.

Therefore, the complexity of algorithm that computes inclusion function is in .

Convolution

Inclusion function [∗] can be computed in linear time in the size of the bounds of the containers.

First, the computation of is obtained by putting end to end the different linear pieces of and , sorted by non-decreasing slopes, up to reach the least asymptotic slope between and (see Theorem 4.1). Hence, the computation only requires a simple scan of functions¹.

Second, about the upper bound, the convolution is defined as . Hence, the minimum between and can be done with a linear complexity and the convolution by the elementary function (that corresponds to a shift in the plane) can be done in a constant time, namely in .

Therefore, the complexity of algorithm that computes inclusion function [∗] is in

Sub-additive closure

The algorithm complexity of [∗] is given separately for the two bounds and .

First, the lower bound is obtained in linear time in the size of . Indeed, its computation only requires the research of its asymptotic slope by checking the non-differentiable points of and the asymptotic slope . Therefore, the complexity of algorithm that computes is in .

Second, the upper bound is obtained in quasi-linear time. Indeed, the computation of , the first part of equation [4.17], is made thanks to algorithms such as “divide and conquer”. Therefore, by doing a two-by-two minimum of , the computation of the n functions is solved in . According to the second part of the equation, the minimum between and g (from ) is made in linear time, namely , where N_g is the number of non-differentiable points of g. Then, the shift of is in as well as the minimum with e (the unit element of the dioid). The concave approximation does not modify this result since its computation is in linear time. Thus, the complexity of this part of the equation is in . Therefore, the complexity of algorithm that computes is in .