H L M Kerivin
email: kerivin@clemson.edu

M Lacroix
email: lacroix@lamsade.dauphine.fr

A R Mahjoub
email: mahjoub@lamsade.dauphine.fr

On the complexity of the Eulerian closed walk with precedence path constraints problem

Keywords: Eulerian closed walk, precedence path constraints, NP-completeness, polynomial-time algorithm

The Eulerian closed walk problem in a digraph is a well-known polynomial-time solvable problem. In this paper, we show that if we impose the feasible solutions to fulfill some precedence constraints specified by paths of the digraph, then the problem becomes NP-complete. We also present a polynomial-time algorithm to solve this variant of the Eulerian closed walk problem when the paths are arcdisjoint. We also give necessary and sufficient conditions for the existence of feasible solutions in this polynomial-time solvable case.

Introduction

In this paper, we consider a variant of the famous Eulerian Closed Walk Problem (ECWP) which consists of finding an Eulerian closed walk starting from a fixed vertex and fulfilling some precedence constraints on the arcs, specified by a partial order on arcs, the latter being defined by a set of paths. Let D = (V, A) be a loopless Eulerian digraph and let v 0 ∈ V be a specified vertex. A walk of length k is a sequence P = (a 1 , . . . , a k ) of k arcs of A with k ≥ 1, a i = (u i , v i ) for all i = 1, . . . , k and v i = u i+1 for i = 1, . . . , k -1. The vertex u 1 (respectively v k ) is called the starting (respectively ending) vertex of P . A path is a walk so that the vertices u 1 , v i , i = 1, 2, . . . , k are all different. A closed walk is a walk having v k = u 1 . A closed walk P is Eulerian if each arc of D appears exactly once in P . Given a walk P composed of distinct arcs, we write a ≺ P a ′ if the arc a precedes the arc a ′ = a in P , that is, if P traverses a before a ′ . Moreover if we consider a path Q = (a 1 , a 2 , . . . , a k ) of D, k ≥ 1, we say that the walk P respects the path Q if a ≺ Q a ′ and P contains a ′ imply that P also contains a and a ≺ P a ′ . (Remark that two adjacent arcs of Q are not necessarily adjacent in P .) We now precisely define the problem we consider hereafter. Let D = (V, A) be a loopless Eulerian digraph and let v 0 ∈ V be a specified vertex. (Note that D is not necessarily simple, that is, it may have multiple arcs.) The required partial order on A is given by a set K = {Q 1 , Q 2 , . . . , Q q } of paths of D, q ≥ 1. The Eulerian Closed Walk with Precedence Path Constraints Problem (ECWPPCP) consists of finding an Eulerian closed walk P of D whose starting vertex is v 0 and which respects all the paths of K, that is, for i = 1, 2, . . . , q, if a ≺ Q i a ′ then a ≺ P a ′ for all a, a ′ ∈ A. An instance of the ECWPPCP then is defined by the (ordered) triple (D, v 0 , K).

Studying the ECWPPCP was originally motivated by the so-called Singlevehicle Preemptive Pickup and Delivery Problem (SPPDP) [START_REF] Kerivin | Models for the single-vehicule preemptive pickup and delivery problem[END_REF]. In this vehicle routing problem with a single vehicle having limited capacity, each demand may be temporarily unloaded elsewhere than its destination and picked up later. Given a closed walk P corresponding to the vehicle route and the set K of the demand paths, Kerivin et al. [START_REF] Kerivin | Models for the single-vehicule preemptive pickup and delivery problem[END_REF] showed that (P, K) corresponds to a feasible solution to the SPPDP if the capacity constraints are satisfied and P respects the paths of K. To avoid carrying too much information (and then variables when formulating the SPPDP as a mixed-integer linear program), a natural question is whether or not one can get rid of the sequence of arcs of the ve-hicle route, that is, can we represent a solution by an ordered pair (D, K), where D corresponds to the digraph induced by the set of arcs traversed by the vehicle, and determine in polynomial time if (D, K) is a feasible solution? Since, given (D, K), it is easy to check if the capacity constraints are satisfied, and since the digraph induced by the set of arcs of a closed walk is Eulerian, the problem of determining whether or not (D, K) corresponds to a feasible solution to the SPPDP is nothing but determining if the instance (D, v 0 , K) of the ECWPPCP, where v 0 corresponds to the depot of the vehicle, admits a feasible solution.

To the best of our knowledge, the ECWPPCP has not been considered yet. However, a close-related problem, called the Eulerian Superpath Problem (ESP) has been considered by Pevzner et al. [4]. This problem has the same input as the ECWPPCP, except that each path in K is specified by a sequence of adjacent vertices, instead of a set of arcs. The ESP consists of determining an Eulerian closed walk starting at v 0 and having all the paths specified in K as subpaths (whereas in the ECWPPCP, the Eulerian closed walk may not contain paths of K as subpaths ; it must just respect these paths). Pevzner et al. [START_REF] Pevzner | An Eulerian path approach to DNA fragment assembly[END_REF] proved that the ESP is NP-complete by reducing the DNA fragment assembly problem, known for being NP-hard [START_REF] Kececioglu | Combinatorial algorithms for DNA sequence assembly[END_REF], to it. They also pointed out that the ESP can be solved in polynomial time whenever the digraph D is simple. Note that despite looking alike, the ESP and ECWPPCP are quite different; for instance, as we will see in Section 2, the ECWPPCP remains NP-complete even when D is a simple digraph.

In the next section, we prove the NP-completeness of the ECWPPCP for the general case. Section 3 is dedicated to the polynomial-time solvable case of ECWPPCP where the demand paths are arc-disjoint.

NP-completeness of the ECWPPCP

In this section, we prove the NP-completeness of the ECWPPCP. To do so, we a polynomial reduction from the Directed Hamiltonian Circuit of indegrees and outdegrees exactly two Problem (2DHCP), which can be stated as follows.

Let D H = (V H , A H ) be a digraph having all its vertices of indegree and outdegree two, that is,

deg in G H (v) = deg out G H (v) = 2 for all v ∈ V H = {v 1 , v 2 , . . . , v n } with n ≥ 2.
The 2DHCP consists of asserting whether or not D H contains a Hamiltonian circuit, that is, a closed walk traversing all the vertices of V H exactly once. The 2DHCP is known to be NP-complete [START_REF] Plesnik | The NP-Completeness of the Hamiltonian Cycle Problem in Planar Digraphs with Degree Bound Two[END_REF]. We remark that the proof given by Plesnik [START_REF] Plesnik | The NP-Completeness of the Hamiltonian Cycle Problem in Planar Digraphs with Degree Bound Two[END_REF] was devised for planar digraphs with indegrees and outdegrees at most two, yet by considering some additional arcs, we can easily extend this result to planar digraphs (with possible multiple arcs) with indegrees and outdegrees two.

The first step of our reduction is the construction of an instance (D, v 0 , K) of the ECWPPCP from D H . We construct D as follows. With vertex

v 1 of V H , we associate six vertices v 1 1 , v 2 1 , v 3 1 , v 4 1 , w 1 , w 2 , together with the follow- ing arc set A 1 composed of the ten following arcs (v 1 1 , v 3 1 ), (v 3 1 , v 2 1 ), (v 2 1 , v 4 1 ), (v 1 1 , w 1 ), (w 1 , w 2 ), (w 2 , v 2 1 ), (v 4 1 , w 1 ), (w 1 , v 2 1 ), (v 3 1 , w 2 ), (w 2 , v 3 1
). For any i ∈ {2, 3, . . . , n}, we associate, with v i , four vertices

v 1 i , v 2 i , v 3 i , v 4
i , together with the arc set A i defined by the eight following arcs (v

1 i , v 3 i ), (v 3 i , v 2 i ), (v 2 i , v 4 i ), (v 4 i , w 1 ), (w 1 , v 2 i ), (v 3 i , w 2 ), (w 2 , v 3 i ). Let V = {v j i : i = 1, 2, . . . , n and j = 1, 2, 3, 4} ∪ {w 1 , w 2 }.
We now consider the arcs of D H in the following manner. With every arc

(v i , v j ) in A H , we associate the arc (v 2 i , v 1 j ). Let A = n i=1 A i ∪ {(v 2 i , v 1 j ) : (v i , v j ) ∈ A H }.
The digraph D = (V, A) obtained by our construction is clearly Eulerian. To obtain an instance of the ECWPPCP, we set v 0 equal to v 2 1 and we define the path set K as follows. For all i = 1, 2, . . . , n, we consider the paths

P i = ((v 4 i , w 1 ), (w 1 , w 2 ), (w 2 , v 3 i ), (v 3 i , v 2 i )) and Q i = ((v 4 i , w 1 ), (w 1 , v 2 i )). The path set K is then equal to K = {P i : i = 1, 2, . . . , n}∪{Q i : i = 1, 2, . . . , n}∪{ (v 1 1 , w 1 ), (w 1 , w 2 ), (w 2 , v 2 1 ) }.
The instance of the ECWPPCP obtained from D H is then (D, v

= ((v 1 , v 2 ), (v 2 , v 3 ), . . . , (v n-1 , v n ), (v n , v 1 )
). We construct an Eulerian closed walk C of D starting from v 2 1 and respecting the paths of K in several steps. Let C 1 be the arc sequence obtained by substituting arc

(v i , v i+1 ) of C H by the path (v 2 i , v 4 i ), (v 4 i , w 1 ), (w 1 , v 2 i ), (v 2 i , v 1 i+1 ), (v 1 i+1 , v 2
i+1 ) for any i = 1, 2, . . . , n-1, and arc (v n , v 1 ) by the path ((

v 2 n , v 4 n ), (v 4 n , w 1 ), (w 1 , v 2 n ), (v 2 n , v 1
1 ), (v 1 1 , w 1 ), (w 1 , w 2 )). C 1 clearly corresponds to a walk starting at v 2 1 , since C H is a closed walk of D H . Note that neither the arcs (w 2 , v 3 i ), (v 3 i , w 2 ), for i = 1, 2, . . . , n, nor arc (w 2 , v 2 1 ) appears in C 1 . Since for i = 1, 2, . . . , n, the paths Q i and ((v 1 i , w 1 ), (w 1 , w 2 )) are subpaths of C 1 , the latter straightforwardly respects K. Consider now the digraph D * = (V * , A * ) induced by the remaining arcs of D except arc (w 2 , v 2 1 ), that is, by ). Note that C is composed of all the arcs in A. Moreover, since C 1 starts at v 2 1 and ends at w 2 which is the starting vertex of closed walk C 2 , C is an Eulerian closed walk of D starting at v 2 1 . For any i = 1, 2, . . . , n, the paths ((v 4 i , w 1 ), (w 1 , w 2 )) and ((w 2 , v 3 i ), (v 3 i , w 2 )) are subpaths of C 1 and C 2 , respectively. Recalling that all the paths Q i , for i = 1, 2, . . . , n, are subpaths of C 1 , we can conclude that C respects all the paths of K.

A \ {C 1 ∪ {(w 2 , v 2 1 )}}. We have V * = V \ ({v 4 i : i = 1, 2, . . . , n} ∪ {w 1 }) and deg in D * (v) -deg out D * (v) = 0 for all v ∈ V * . Moreover, D * is weakly connected, that is its underlying graph is connected, since it contains the arcs (w 2 , v 3 i ), (v 1 i , v 3 i ) and (v 3 i , v 2 i ) for i = 1,
(⇐) Let C be an Eulerian closed walk of D starting at v 2 1 and respecting all the paths of K. Due to the definition of K, arc (w 1 , w 2 ) appears in C before all the arcs of D leaving w 2 , that is, (w 1 , w 2 ) ≺ C a for all a ∈ δ out (w 2 ). Moreover, since we have deg out (v) = deg in (v) for all v ∈ V , we deduce that arc (w 1 , w 2 ) appears in C before any other entering arc of w 2 , that is, (w 1 , w 2 ) ≺ C a for all a ∈ δ in (w 2 ) \ {(w 1 , w 2 )}. Let C be the walk obtained from C by only considering the arcs of D preceding (w 1 , w 2 ) in C. By considering all the paths P i of K, we deduce that (w 1 , w 2 ) ≺ C (v 3 i , v 2 i ) for all i = 1, 2, . . . , n which implies, with the previous results, that C does not contain any vertex in {v 3 i : i = 1, 2, . . . , n}. Moreover, due to the vertex degree conditions, C contains arc (v 4 i , w 1 ) for all i = 1, 2, . . . , n. Since w 1 is not the starting vertex of C, by considering Q i , we deduce that (v 1 1 , w 1 ) is the last arc of C and every path

Q i , i = 1, 2, . . . ,
: i = 1, 2, . . . , n}, we clearly have δ in D (v 2 i ) ∩ C = {(v 1 i , v 2 i )} for all i = 2, 3, . . . , n. Therefore, C contains all the vertices in {v 1 i , v 2 i : i = 1, 2, . . . , n} exactly once. Consequently, C is an alternate sequence of arcs of {(v 2 i , v 2 j ) : (v i , v j ) ∈ A H } and of {(v 1 i , v 2 i ) : i = 2, 3, .
. . , n} so that every arc from both sets appears once. Therefore, contracting the vertices v 1 i and

v 2 i into vertex v i , for i = 1, 2, . . . , n, transforms C into a Hamiltonian circuit of D H . 2
Theorem 2.2 The Eulerian closed walk with precedence path constraints problem is NP-complete.

Proof. Clearly the problem is in NP. Moreover, the construction from an instance of the NP-complete 2DHCP into an instance of the ECWPPCP can be performed in polynomial time. Therefore, the NP-completeness of the Eulerian closed walk with precedence path constraints problem directly follows from Lemma 2.1. 2

We remark that, on the contrary of the ESP, the ECWPPCP remains NPhard if the digraph D is simple. To prove this, one has just to modify the construction of (D, v 0 , K) from D H by sequentially replacing, in D and every path of K, each multiple arc (u, v) by the two arcs (u, w) and (w, v) where w is a new vertex with indegree and outdegree one.

A polynomial-time solvable case

Throughout this section, we consider an instance (D, v 0 , K) of the ECWP-PCP where K is composed of arc-disjoint paths. We prove that, in this case, the ECWPPCP can be solved in polynomial time. From now on, we say that arc a ∈ A is a predecessor of an arc a ′ ∈ A \ {a} if there exists a path Q of K with a ≺ Q a ′ . (Note that, since K is composed of arc-disjoint paths, given two distinct arcs, at most one is the predecessor of the other.) We now define particular subdigraphs of D. Let D ′ = (V ′ , A ′ ) be an Eulerian digraph induced by an arc subset A ′ ⊆ A. A vertex v ∈ V ′ is said D ′ -impregnable if either it is different from v 0 and incident with no arc in A ′ , or all its leaving arcs in A ′ have a predecessor in δ in D ′ (v). The subdigraph D ′ is then called impregnable (with respect to (D, v 0 , K)) if all its vertices are D ′ -impregnable. By definition, the impregnable Eulerian subdigraphs are composed of arcs that cannot appear in a closed walk of D starting from v 0 and respecting the paths of K. Therefore, if (D, v 0 , K) contains an impregnable Eulerian subdigraph, then the ECWPPCP associated with instance (D, v 0 , K) has not a feasible solution.

Given an instance (D, v 0 , K) of the ECWPPCP so that v 0 is not Dimpregnable, one can easily construct a closed walk C of D starting from v 0 and respecting K as follows. (Remark that C may not be Eulerian.) Since v 0 is not D-impregnable, there exists an arc leaving v 0 , say (v 0 , v 1 ), with no predecessor. Therefore, the walk C = ((v 0 , v 1 )) respects K. Moreover, as long as the ending vertex of C, say v, is different from v 0 , we can extend C by pushing back to C a new arc leaving v. Indeed, since D is Eulerian, we have |δ out (v) \ C| = |δ in (v) \ C| + 1. Since K is composed of arc-disjoint paths, each arc of δ in (v) \ C is the predecessor of at most one of δ out (v) \ C, which implies that there exists an arc (v, w) of A \ C with no predecessor in δ in (v) \ C. therefore, the walk (C, (v, w)) respects K. By iteratively pushing back arcs to C until reaching v 0 , we obtain a closed walk C starting at v 0 and respecting K.

By definition, if (D, v 0 , K) contains an impregnable Eulerian subdigraph, then it admits no feasible solution. Suppose now that (D, v 0 , K) does not contain any impregnable Eulerian subdigraph. Using the previous routine, we now construct a feasible solution to the ECWPPCP as follows. We first compute a closed walk C of (D, v 0 , K). If C is Eulerian, then it corresponds to a feasible solution to the ECWPPCP. Otherwise, let D = (V , A) be the digraph induced by the arc set A\C. It is clear that each connected component of D corresponds to an Eulerian subdigraph of D. Let D ′ = (V ′ , A ′ ) be any of these connected components. By hypothesis, D ′ is not impregnable. Therefore, let v ′ 0 ∈ V ′ be the last vertex appearing in C that is not D ′impregnable and K ′ the restriction of K on D ′ . (D ′ , v ′ 0 , K ′ ) corresponds to an instance of the ECWPPCP. Using the previous routine, we can construct a closed walk C ′ of D ′ starting at v ′ 0 and respecting K ′ . Inserting C ′ into C after the last time v ′ 0 appears in C leads to a new closed walk C ′′ starting at v 0 . Suppose now that C ′′ does not respect K. Since C and C ′ respect K, this implies that there exists an arc a ′ in C ′ that has a predecessor in C, say a, which appears after a ′ in C ′′ . We suppose, without loss of generality, that a = (u, v) and a ′ = (v, w) are incident. Vertex v is not D ′ -impregnable because it is incident to at least one arc of C and a ′ has only one predecessor in δ in (v), namely a, which does not belong to D ′ . Since v appears after v ′ 0 in C, this contradicts the fact that v ′ 0 is the last vertex of C that is not D ′impregnable. Thus, C ′′ respects K. By iteratively inserting closed walks into the current one, we finally obtain a solution to the ECWPPCP. (Otherwise, the digraph induced by the remaining arcs contains at least one impregnable Eulerian subdigraph.) These results lead to the following theorem.

Theorem 3.1 The ECWPPCP can be solved in polynomial time if the paths are arc-disjoint. Moreover, (D, v 0 , K) admits a feasible solution if and only if it does not contain any impregnable Eulerian subdigraph.

Conclusion

In this paper, we introduced a new variant of the Eulerian closed walk problem where some precedence constraints are specified by a set of paths K. We first proved that this problem is NP-complete. We also presented a polynomialtime algorithm to solve the problem if K is composed of arc-disjoint paths.

  2 1 , K). We show in the next lemma the relation between D H and (D, v 2 1 , K). Lemma 2.1 D H has a Hamiltonian circuit if and only if D has an Eulerian closed walk starting at v 2 1 and respecting the precedence path constraints specified by K. Proof. (⇒) Let C H be a Hamiltonian circuit of D H . Without loss of generality, we suppose that C H

  2, . . . , n, which implies that D * is Eulerian. Furthermore, the digraph D * -w 2 = D * [V * \{w 2 }] may not be weakly connected, yet each vertex in V * \ {w 2 } clearly has equal indegree and outdegree. Let Dw 2 which obviously are Eulerian. Since D *w 2 is not weakly connected only if D H -C H is not weakly connected either, then for any k = 1, 2, . . . , p, there must exist i k ∈ {1, 2, . . . , n} so that v 3 i starting at w 2 in the following manner. The first arc of B k is (w 2 , v 3 i k ). All the arcs of B * k are then added to B k sequentially. If the head of the added arc is a vertex v 3 before moving to the next arc of B * k . Once we have dealt with all the arcs of B * k , we complete B k by adding (v 3 i k , w 2 ). Since any B k , for k = 1, 2, . . . , p, starts at vertex w 2 , the concatenation (B 1 , B 2 , . . . , B p ) of these Eulerian closed walks clearly forms an Eulerian closed walk C 2 of D * . Let C be the concatenation of C 1 , C 2 and arc (w 2 , v 2 1

* 1 , D * 2 , . . . , D * p , p ≥ 1, be the strongly connected components of D * k is a vertex of D * k . Consider any strongly connected component D * k , k = 1, 2, . . . , p. Any Eulerian closed walk B * k of D * k starting at v 3 i k can be transformed into a closed walk B k of D * i , for some i ∈ {1, 2, . . . , n}, then the path ((v 3 i , w 2 )(w 2 , v 3 i )) is added to B k

  n is a subpath of C. As every vertex v 4 , and containing all the vertices in {v 2 i : i = 1, 2, . . . , n}. Since C does not contain any vertex in {v 3 i

	i has only one
	entering arc, namely (v 2 i , v 4 i ), removing closed walks ((v 2 i , v 4 i ), (v 4 i , w 1 ), (w 1 , v 2 i )) for all i = 1, 2, . . . , n, and arc (v 1 1 , w 1 ) leads to a walk C starting at v 2 1 , ending
	at v 1 1


I Bouraoui

M Farza

T Ménard

R Ben Abdennour

M M'saad

H Mosrati

Observer design for a class of uncertain nonlinear systems with sampled outputs -Application to the estimation of kinetic rates in bioreactors

Keywords: Nonlinear systems, high gain observers, impulsive systems, continuous-discrete time observers, bioreactors, reactions rates

A continuous-discrete time observer is proposed for a class of uncertain nonlinear systems where the output is available only at non uniformly spaced sampling instants. The underlying correction term depends on the output observation error and is updated in a mixed continuous-discrete fashion. The proposed observer is first introduced under a set of differential equations with instantaneous state impulses corresponding to the measured samples and their estimates. Two features of the proposed observer are worth to be pointed out. The first one consists in the simplicity of its calibration while the second one lies in its comprehensive convergence analysis. More specifically, it is shown that in the case of noise-free sampled outputs, the observation error lies in a ball centered at the origin and which radius is proportional to the bounds of the uncertainties and the sampling partition diameter. Moreover, in the free uncertainties case, the exponential convergence to zero of the observation error is established under a well-defined condition on the maximum value of the sampling partition diameter. The ability of the proposed observer to perform a suitable estimation of the reactions rates in biochemical reactors is highlighted through a simulation study dealing with an ethanolic fermentation.

Introduction

Although a considerable research activity has been devoted to the observer design for nonlinear systems over the last decades, the available contributions deal mainly with the continuous-time measurements case [START_REF] Gauthier | Deterministic Observation Theory and Applications[END_REF][START_REF] Kazantzis | Nonlinear observer design using Lyapunov's auxiliary theorem[END_REF][START_REF] Farza | High gain observer for a class of non-triangular systems[END_REF][START_REF] Andrieu | On the existence of Kazantzis-Kravaris / Luenberger observers[END_REF][START_REF] Rajamani | Observers for Lipschitz Nonlinear Systems[END_REF][START_REF] Krener | Linearization by output injection and nonlinear observers[END_REF]. In order to handle the non continuous availability of the output measurements, many works have focused on the redesign of the continuous time state observers that have been proposed for the underlying systems. An early contribution was made using a high gain observer for a class of nonlinear systems that are observable for any input [START_REF] Deza | High gain estimation for nonlinear systems[END_REF]. The design was firstly carried out assuming continuous-time output measurements before being appropriately modified to deal with the case where these measurements are only available at sampling instants. Based on the aforementioned contribution, many other observers have been proposed for specific classes of continuous time systems with sampled output measure-Email address: mondher.farza@unicaen.fr (M. Farza).

ments [START_REF] Hammouri | Constant gain observer for continuous-discrete time uniformly observable systems[END_REF][START_REF] Nadri | Observer design for uniformly observable systems with sampled measurements[END_REF]. In all these contributions, the continuousdiscrete time observer operates as follows: a dynamical system, which is similar to the underlying system, is used to provide a state prediction over the sampling intervals. At the sampling instants, the output measurements are used to update the state prediction provided by the dynamical system. An output predictor approach has been proposed in [START_REF] Karafyllis | From continuous-time design to sampled-data design of observers[END_REF] to cope with the non-availability of the output measurements between the sampling instants. It consists in a continuous time observer involving a suitable predictor of the output over the sampling intervals. More specifically, the output prediction is provided by the solution of an ordinary differential equation between two successive sampling instants with the value of the measured output sample as initial condition. The underlying observer is a hybrid system which is able to recover the continuous time observer properties for relatively fast sampling. Another approach was described in [START_REF] Raff | Observer with sample-and-hold updating for Lipschitz nonlinear systems with nonuniformly sampled measurements[END_REF] where the authors proposed an impulsive continuous-discrete time observer for a class of uniformly observable systems with sampled outputs. The correction term of the pro-posed observer is the product of a constant gain by the difference between the estimated and measured values of the last output sample. The determination of the observer gain is carried out through the resolution of an appropriate LMI. In this paper, our objective consists in synthesizing a continuous-discrete time observer for a class of uncertain nonlinear systems where the output measurements are available only at non uniformly spaced sampling instants. In the absence of uncertainties, the considered class of nonlinear systems is observable for any input and has been considered in [START_REF] Farza | Observer design for a class of MIMO nonlinear systems[END_REF] for observer design purposes in the case where the output measurements are available in a continuous manner. The proposed continuous-discrete time observer is issued from a redesigned version of the high gain continuous time observer proposed in [START_REF] Farza | Observer design for a class of MIMO nonlinear systems[END_REF]. This observer shares the impulsive nature of the observer given in [START_REF] Raff | Observer with sample-and-hold updating for Lipschitz nonlinear systems with nonuniformly sampled measurements[END_REF] up to an adequate modification of the observer gain matrix. Indeed, unlike in [START_REF] Raff | Observer with sample-and-hold updating for Lipschitz nonlinear systems with nonuniformly sampled measurements[END_REF], the gain of the proposed observer does not necessitate the resolution of any system and its expression is given. This gain is time-varying and depends on the sampling periods. There are two main features of the proposed continuous-discrete time observer that are worth to be emphasized with respect to the existing ones. The first one concerns the ease with which the observer gain is updated at sampling instants together with the simplicity of its implementation. The second feature is related to the convergence analysis simplicity and its ability to provide precise expressions of the upper bounds of the sampling partition diameter as well as the rate of the observation error convergence. More specifically, it is shown that the observation error lies in a ball centered at the origin with a radius proportional to the magnitude of the bounds of the uncertainties, the noise measurements and the maximum sampling partition diameter. Moreover, it is shown that in the noise-free outputs case, the ultimate bound of the observation error can be made arbitrarily small, as in the continuous-time output case, when the maximum sampling partition diameter tends to zero. A particular emphasis is put on the fact that the observation error converges exponentially to the origin in the absence of uncertainties and noise measurements. Of particular interest, the expression of the underlying decay rate is given. The paper is organized as follows. In the next section, the class of systems under consideration and the notations employed throughout this paper are introduced together with concise convergence results on the continuous time high gain observer on which the proposed continuousdiscrete time observer is based upon. The output noise measurements are taken into account in the provided convergence analysis. A technical lemma with its proof are also given in this section and this lemma is used to establish the main result of the paper. Section 3 is devoted to the main contribution of the paper, namely the design of the continuous-discrete time observer. The fundamental result is given with a comprehensive proof thanks to the technical lemma derived in Section 2. In Section 4, the effectiveness of the proposed observer is highlighted via simulation results involving the estimation of the reactions rates in a bioreactor involving an ethanolic fermentation. Finally, some concluding remarks are given in Section 5. Throughout the paper, Ip and 0p will denote the pdimensional identity and zero matrices respectively and ∥ • ∥ denotes the euclidian norm; λ M (resp. λm) is the maximum (resp. minimum) eigenvalue of a certain Symmetric Positive Definite (SPD) matrix P and σ = √ λ M /λm is its conditioning number.

Problem statement and preliminaries

Consider the class of multivariable nonlinear systems that are diffeomorphic to the following bloc triangular form:

   ẋ(t) = Ax(t) + φ(u(t), x(t)) + Bε(t) y(t k ) = Cx(t k ) + w(t k ) = x 1 (t k ) + w(t k ) (1) with x =         x 1 . . . x q-1 x q         ∈ IR n , φ(u, x) =            φ 1 (u, x 1 ) φ 2 (u, x 1 , x 2 ) . . . φ q-1 (u, x 1 , . . . , x q-1 ) φ q (u, x)            A =   0 (q-1)p,p I (q-1)p 0p,p 0 p,(q-1)p   , B = ( Ip 0p . . . 0p ) T , C = ( Ip 0p . . . 0p ) (2)
where x i ∈ IR p for i ∈ [1, q] are the state variables blocks, u(t) ∈ U a compact subset of IR m denotes the system input and y ∈ IR p denotes the system output which is available only at the sampling instants that satisfy 0 ≤ t 0 < . . . < t k < t k+1 < . . . with time-varying sampling intervals τ k = t k+1 -t k and lim k→∞ t k = +∞; w(t) is the output noise and ε : IR + → IR p is an unknown function describing the system uncertainties and may depend on the state, the input and uncertain parameters. As it is mentioned in the introduction, our main objective is to design a continuous-discrete time observer providing a continuous time estimation of the full state of system (1) by using the output measurements that are available only at the sampling instants. Such a design will be carried out under the following assumptions : A1. The state x(t) is bounded i.e. there exists a compact set Ω ∈ IR n such that ∀t ≥ 0, x(t) ∈ Ω. A2. The functions φ i for i ∈ [1, q] are Lipschitz with respect to x uniformly in u, i.e.

∀ρ > 0; ∃L > 0; ∀u s.t. ∥u∥ ≤ ρ; ∀(x, x) ∈ Ω × Ω : ∥φ i (u, x) -φ i (u, x) ∥ ≤ L∥x -x∥ (3)
A3. The unknown function ε is essentially bounded, i.e.

0 < τm ≤ τ k = t k+1 -t k ≤ τ M , ∀k ≥ 0 (4)
There are two remarks that are worth to be pointed out. Firstly, the class of systems described by (1) may seem very restrictive since it assumes a non prime dimension (n = pq) and the state blocks x k have the same dimension p. This is not the case since it is shown in [START_REF] Hammouri | Nonlinear observers for locally uniformly observable systems[END_REF] that in the uncertainties-free case, system (1) is a normal form which characterizes a class of uniformly observable nonlinear systems that can be put under this form via an injective map (see e.g. [START_REF] Hammouri | Nonlinear observers for locally uniformly observable systems[END_REF][START_REF] Farza | Adaptive observers for nonlinearly parameterized class of nonlinear systems[END_REF] for more details). Secondly, since the system state trajectory lies in a bounded set Ω, one can extend the nonlinearities φ(u, x) in such a way that this extension becomes globally Lipschitz on the entire state space IR n . The observer synthesis will then be based on the resulting extended system which coincides with the original system on the domain of interest i.e. Ω. One can refer to [START_REF] Shim | Semi-global observer for multi-output nonlinear systems[END_REF][START_REF] Andrieu | On the existence of Kazantzis-Kravaris / Luenberger observers[END_REF] and references therein for more details on how to carry globally Lipschitz prolongations in the state observation context.

The underlying continuous-time high gain observer design

As mentioned above, the continuous-discrete time impulsive observer we shall propose is issued from an appropriate redesign of a purely continuous-time high gain observer that has been proposed for system (1) in the case where the output measurements are available in a continuous manner i.e.

   ẋ(t) = Ax(t) + φ(u(t), x(t)) + Bε(t) y(t) = Cx(t) + w(t) = x 1 (t) + w(t) (5)
We will particularly use a continuous-time observer similar to that proposed in

ẋ(t) = Ax(t) + φ(u(t), x(t)) -θ∆ -1 θ K(C x(t) -y(t)) (6)
with

∆ θ = diag ( Ip, 1/θIp, . . . , 1/θ q-1 Ip ) (7)
where x ∈ IR n denotes the state estimate, K = (K 1 = k 1 Ip . . . K q = kqIp) T where the k i 's, i = 1, . . . , q are chosen such that the matrix Ā ∆ = A -KC is Hurwitz and θ ≥ 1 is a scalar design parameter. Before stating the results summarizing the main properties of observer [START_REF] Boizot | An adaptive high-gain observer for nonlinear systems[END_REF], we recall that since the matrix Ā ∆ = A -KC is Hurwitz, there exist a n × n SPD matrix P and a positive real µ such that

P Ā + ĀT P ≤ -2µIn (8)
We now state the following result. Theorem 2.1 Consider system [START_REF] Birol | Mathematical description of ethanol fermentation by immobilised saccharomyces cerevisiae[END_REF] subject to assumptions A1 to A4 together with the observer [START_REF] Boizot | An adaptive high-gain observer for nonlinear systems[END_REF]. Then,

∀ρ > 0; ∃θ 0 > 0; ∀θ ≥ θ 0 ; ∀u s.t. ∥u∥∞ ≤ ρ; ∀x(0) ∈ IR n ; we have ∥x(t) -x(t)∥ ≤ σθ q-1 e -µθ 2λ M t ∥x(0) -x(0)∥ + 2σλ M µ ( δε θ + θ q-1 ∥K∥δw )
where x is the unknown system trajectory associated to the input u, x is any trajectory of the observer associated to (u, y), µ > 0 is a positive real given by ( 8) and δε and δ w are the upper essential bounds of ∥ε(t)∥ and ∥w(t)∥, respectively with

θ 0 = max(1, 2L √ nλ M /µ) and σ = √ λ M /λm
is the conditioning number of the matrix P given by [START_REF] Dochain | State and parameter estimation in chemical and biochemical processes: a tutorial[END_REF].

The proof of the observation error convergence is similar to that given in [START_REF] Farza | Observer design for a class of MIMO nonlinear systems[END_REF] in the free noise output case. For clarity purposes and since the link between this observer and the continuous-discrete time one shall be raised, we shall detail the convergence analysis which accounts for the output noise measurements. Indeed, let x = x -x be the observation error. One has

ẋ = (A -θ∆ -1 θ KC)x + φ(u, x) -φ(u, x) -Bε(t) + θ∆ -1 θ Kw(t) Let x = ∆ θ x.
Taking into account the following identities

∆ θ A∆ -1 θ = θA and C∆ -1 θ = C (9)
one gets

ẋ = θ Āx + ∆ θ (φ(u, x) -φ(u, x)) -∆ θ Bε(t) + θKw(t) ( 10
)
Let us show that V (x) = xT P x is a Lyapunov function for system [START_REF] Farza | Adaptive observers for nonlinearly parameterized class of nonlinear systems[END_REF]. Indeed, one has

V (x) ≤ -2µθ∥x∥ 2 + 2x T P ∆ θ (φ(u, x) -φ(u, x)) -2x T P ∆ θ Bε(t) + θx T P Kw(t) (11)
According to the Lipschitz assumption and the triangular structure of φ, one can show that for θ ≥ 1 [START_REF] Farza | Observer design for a class of MIMO nonlinear systems[END_REF][START_REF] Hammouri | Nonlinear observers for locally uniformly observable systems[END_REF]:

2x T P ∆ θ (φ(u, x) -φ(u, x)) ≤ 2 √ nλ M L∥x∥ 2 ( 12
)
where L is the Lipschitz constant of φ. Similarly, according to the structures of B and ∆ θ , one has

2x T P ∆ θ Bε(t) ≤ 2 ∥ε(t)∥ √ λ M θ q-1 √ V (x) 2θx T P Kw(t) ≤ 2θ∥w(t)∥ √ λ M ∥K∥ √ V (x) (13)
And combining ( 11), ( 12) and ( 13), one gets

V (x) ≤ -2(µθ - √ nλ M L)∥x∥ 2 + 2 √ λ M ( ∥ε(t)∥/θ q-1 + θ∥K∥∥w(t)∥ ) √ V (x) (14)
Choosing θ such that 2(µθ -

√ nλ M L) > µθ i.e. θ > θ ′ 0 ∆ = 2L √ nλ M /µ (15)
Inequation ( 14) becomes

V (x) ≤ -µθ λ M V (x) + 2 √ λ M ( ∥ε(t)∥ θ q-1 + θ∥K∥∥w(t)∥ ) √ V (x)
Or equivalently

d dt √ V (x(t)) ≤ -µθ 2λ M √ V (x(t)) + √ λ M ( ∥ε(t)∥ θ q-1 + θ∥K∥∥w(t)∥ )
Using the comparison lemma [START_REF] Khalil | Nonlinear systems. Printice Hall[END_REF], one gets

√ V (x(t)) ≤ exp [ -µθ 2λ M t ] √ V (x(0)) + 2λ 3/2 M µθ ( δε θ q-1 + θ∥K∥δw ) This yields to ∥x(t)∥ ≤ σ exp [ - µθ 2λ M t ] ∥x(0)∥+ 2λ M σ µθ ( δε θ q-1 + θ∥K∥δw ) (16)
Now, since x = ∆ θ x, one has ∥x(t)∥ ≤ ∥x(t)∥ ≤ θ q-1 ∥x(t)∥ and inequation ( 16) leads to

∥x(t)∥ ≤ θ q-1 σ exp [ - µθ 2λ M t ] ∥x(0)∥ + 2λ M σ µ ( δε θ + θ q-1 ∥K∥δw) ( 17
)
and is finite, the observation error lies in some ball centered at the origin with a radius proportional to δε but it can be made arbitrarily small by choosing values of θ sufficiently high. However, high values of θ have to be avoided in practice where the presence of noise measurements is unavoidable. Indeed, in such a case and according to [START_REF] Jin | Kinetics of batch fermentations for ethanol production with immobilized saccharomyces cerevisiae growing on sweet sorghum stalk juice[END_REF], high values of θ give rise to a high bound for the estimation error since this bound is of the order of θ q-1 . Thus, the choice of θ is a compromise between fast convergence and sensitivity to noise.

A technical lemma

In what follows, a technical lemma together with its proof are given. This lemma will be used to establish the main result of the paper in the next section. Then, the function v satisfies

Lemma 2.1 Consider a differentiable function

v : t ∈ IR + → v(t) ∈ IR + satisfying the following inequality: v(t)≤-av(t) + b ∫ t t k v(s)ds + p(t) ∀t ∈ [t k , t k+1 [ ( 18
)
with k ∈ IN, t 0 ≥ 0 where 0 < τm ≤ τ k = t k+1 -t k ≤ τ M <
v(t) ≤ e -η(t-t 0 ) v(t 0 ) + cτ M 2 -e -ητm 1 -e -ητm with 0 < η = (a -bτ M ) e -aτ M ( 19
)
Proof of lemma 2.1. We shall first prove that [ and use this property to establish the key inequality [START_REF] Kazantzis | Nonlinear observer design using Lyapunov's auxiliary theorem[END_REF]. By integrating (18) from t k to t, we obtain

v(t) ≤ v(t k ) + c(t -t k ) ∀t ∈ [t k , t k+1
v(t) ≤ v(t k ) -a ∫ t t k v(s)ds + b ∫ t t k ∫ s t k v(ν)dνds + c(t -t k ) ≤ v(t k ) + (bτ M -a) ∫ t t k v(s)ds + c(t -t k ) (20)
And since bτ M -a < 0, the last inequality [START_REF] Khalil | Nonlinear systems. Printice Hall[END_REF] becomes

v(t) ≤ v(t k ) + c(t -t k ) (21)
Now, we shall establish the inequality (19) using the property [START_REF] Krener | Linearization by output injection and nonlinear observers[END_REF]. Indeed, inequality [START_REF] Karafyllis | From continuous-time design to sampled-data design of observers[END_REF] becomes

v(t) ≤ -av(t) + b ∫ t t k (v(t k ) + c(s -t k )) ds + p(t) ≤ -av(t) + bτ M (v(t k ) + c(t -t k )) + p(t) (22)
Using the comparison lemma and the fact that bτ M < a, one gets

v(t) ≤ e -a(t-t k ) v(t k ) + bτ M v(t k ) + c a ( 1 -e -a(t-t k ) ) + ca ∫ t t k (s -t k )e -a(t-s) ds (23)
Now, using an integration by part, one can show that

a ∫ t t k (s -t k )e -a(t-s) ds = (t -t k ) - 1 -e -a(t-t k ) a ( 24
)
And substituting [START_REF] Raff | Observer with sample-and-hold updating for Lipschitz nonlinear systems with nonuniformly sampled measurements[END_REF] in [START_REF] Oueder | A high gain observer with updated gain for a class of MIMO non-triangular systems[END_REF], one gets

v(t) ≤ e -a(t-t k ) v(t k ) + bτ M v(t k ) + c a ( 1 -e -a(t-t k ) ) +c((t -t k ) - 1 -e -a(t-t k ) a ) = g(t)v(t k ) + c(t -t k ) (25)
where

g(t) ∆ = e -a(t-t k ) (1 -bτ M /a) + bτ M /a.
Let us show that g(t) ≤ e -η(t-t k ) where η is given as in [START_REF] Kazantzis | Nonlinear observer design using Lyapunov's auxiliary theorem[END_REF]. To this end, it suffices to show that

δ(t) = ( g(t) -e -η(t-t k ) )
≤ 0 for all t ≥ t k . This can be done by simply showing that δ(t) ≤ 0 since one can easily check that δ(t k ) = 0. In fact, this is actually the case since

δ(t)= ġ(t) + ηe -η(t-t k ) =-ae -a(t-t k ) (1 - bτ M a )+ηe -η(t-t k ) ≤-e -aτ M (a -bτ M ) + η = 0 ( 26
)
The last equality results from the expression of η given by [START_REF] Kazantzis | Nonlinear observer design using Lyapunov's auxiliary theorem[END_REF]. Hence, inequality [START_REF] Rajamani | Observers for Lipschitz Nonlinear Systems[END_REF] becomes

v(t) ≤ e -η(t-t k ) v(t k ) + c(t -t k ), ∀t ∈ [t k , t k+1 [, k ∈ IN (27)
Iterating inequality (27), one can show that

v(t k ) ≤ e -η(t k -t 0 ) v(t 0 ) + c ( τ k-1 + τ k-2 e -ητ k-1 + τ k-3 e -η(τ k-1 +τ k-2 ) + . . . + τ 0 e -η(τ k-1 +...+τ 1 ) ) (28)
And using (28), inequality (27) becomes

v(t) ≤ e -η(t-t 0 ) v(t 0 ) + c(t -t k ) + ce -η(t-t k ) (τ k-1 + τ k-2 e -ητ k-1 + τ k-3 e -η(τ k-1 +τ k-2 ) + . . . + τ 0 e -η(τ k-1 +...+τ 1 ) ) ≤ e -η(t-t 0 ) v(t 0 ) + cτ M (1 + k-1 ∑ j=0 e -jητm ) ≤ e -η(t-t 0 ) v(t 0 ) + cτ M 2 -e -ητm 1 -e -ητm
This ends the proof of the lemma.

Design of the continuous-discrete time observer

Before giving the equations of the discrete-continuous time observer, we need the following additional hypothesis on the boundedness of the noise samples w(t k ): A5. For all t k , the samples w(t k ) are bounded by δw where δw is the essential bound given by Assumptions A4. Now, let us consider the following impulsive system

ẋ(t) = Ax(t) + φ(u(t), x(t)) -θ∆ -1 θ Ke -θk 1 (t-t k ) (C x(t k ) -y(t k )), t ∈ [t k , t k+1 [ ( 29
)
where x = ( x1T . . . xqT ) T , K = (k 1 Ip . . . kqIp) T is the gain matrix where the k i 's, i = 1, . . . , q are chosen such that the matrix Ā ∆ = A-KC is Hurwitz and ∆ θ is the (bloc) diagonal matrix defined in [START_REF] Deza | High gain estimation for nonlinear systems[END_REF] with θ ≥ 1. The following result shows that this impulsive system is a continuous-discrete time observer for system (1). Theorem 3.1 Consider the system (1)-( 2) subject to Assumption A1 to A5. Then, ∀ρ > 0; ∃θ 0 > 0; ∀θ ≥ θ 0 ; ∀u s.t. ∥u∥∞ ≤ ρ; there exist positive constants χ θ > 0 and η θ (τ M ) > 0 such that if the upper bound of the sampling partition diameter τ M is chosen such that τ M < χ θ , then 4 CONFIDENTIAL. Limited circulation. For review only Automatica submission 13-0946.5

Preprint submitted to Automatica Received February 16, 2015 05:56:13 PST for every x(0) ∈ IR n , we have:

∥x(t) -x(t)∥ ≤ σθ q-1 e -η θ (τ M )t ∥x(0) -x(0)∥ + στ M 2-e -η θ (τ M )τm 1-e -η θ (τ M )τm ( δε/θ + θ q-1 ∥K∥ ( 2 -e -k 1 θτ M ) δw )
where x is the unknown trajectory of (1) associated to the input u, x is any trajectory of system (29) associated to (u, y), θ 0 is that of theorem 2.1, τm and τ M are defined in [START_REF] Battista | Specific growth rate estimation in (fed-)batch bioreactors using secondorder sliding observers[END_REF] with

η θ (τ M ) = a θ ( 1 -τ M χ θ ) e -a θ τ M χ θ = µ 2(L + θ)σ∥K∥λ M , a θ = µθ 2λ M
Proof of Theorem 3.1: Let x(t) = x(t) -x(t) be the observation error, it can be easily checked that

ẋ(t) = Ax + Φ(u, x, x) -θ∆ -1 θ Ke -θk 1 (t-t k ) C x(t k ) -Bε(t) + θ∆ -1 θ Ke -θk 1 (t-t k ) w(t k )
where Φ(u, x, x) = φ(u, x) -φ(u, x). Setting x = ∆ θ x and using the identities (9) allow to get:

ẋ = θAx + ∆ θ Φ(u, x, x) -θKe -θk 1 (t-t k ) C x(t k ) - 1 θ q-1 Bε(t) + θKe -θk 1 (t-t k ) w(t k ) (30)
Moreover, adding and subtracting the term θKC x in the last equation yields

ẋ = θ (A -KC) x + ∆ θ Φ(u, x, x) + θK(C x -e -θk 1 (t-t k ) C x(t k )) -Bε(t)/θ q-1 + θKe -θk 1 (t-t k ) w(t k ) = θ Āx + ∆ θ Φ(u, x, x) + θKz -Bε(t)/θ q-1 + θKe -θk 1 (t-t k ) w(t k )
where

z(t) = C x(t)-e -θk 1 (t-t k ) C x(t k ) = x1 (t)-e -θk 1 (t-t k ) x1 (t k ).
Notice that z(t k ) = 0 and according to (30), the time derivative of z can be written as follows

ż(t) = ẋ1 (t) + k 1 θe -θk 1 (t-t k ) x1 (t k ) = θx 2 + Φ 1 (u, x1 , x 1 ) + θk 1 e -k 1 θ(t-t k ) w(t k ) ( 31
)
where Φ 1 (u, x1 , x 1 ) = φ 1 (u, x1 ) -φ 1 (u, x 1 ). Now, let us consider the following candidate quadratic Lyapunov function: V (x) = xT P x where P is defined as in [START_REF] Dochain | State and parameter estimation in chemical and biochemical processes: a tutorial[END_REF]. Proceeding as in the continuous-time output case, one can show that

V (x) = 2x T (t)P ( θ Āx + ∆ θ Φ(u, x, x) + θKz ) -2x T (t)P Bε(t)/θ q-1 + 2θx T (t)P Ke -θk 1 (t-t k ) w(t k ) ≤ -(2µθ -2L √ nλ M )∥x∥ 2 + 2θx T P Kz -2x T (t)P Bε(t)/θ q-1 + 2θx T (t)P Ke -θk 1 (t-t k ) w(t k ) ( 32
)
Choosing θ as in [START_REF] Hammouri | Nonlinear observers for locally uniformly observable systems[END_REF], the last inequality (32) becomes

V (x) ≤ -µθ λ M V (x) + 2θ √ λ M ∥K∥∥z(t)∥ √ V (x) + 2 √ λ M ( ∥ε(t)∥ θ q-1 + θ∥K∥∥w(t k )∥ ) √ V (x)
Furthermore, integrating equation (31) from t k to t while using the fact that z(t k ) = 0 yields

z(t) = ∫ t t k ( θx 2 (s) + Φ 1 (u(s), x1 (s), x 1 (s)) ) ds + ( 1 -e -k 1 θ(t-t k ) ) w(t k )
Bearing in mind that Φ 1 (u, x1 , x 1 ) = φ 1 (u, x1 ) -φ 1 (u, x 1 ), one gets

∥z(t)∥ ≤ (θ + L) ∫ t t k ∥x(s)∥ds + ( 1 -e -k 1 θ(t-t k ) ) δw ≤ ((θ + L)/ √ λm) ∫ t t k √ V (x(s))ds + ( 1 -e -k 1 θτ M ) δw
Combining the above inequalities, one obtains

V (x(t)) ≤ -µθ λ M V (x(t)) + 2θ √ λ M λm ∥K∥(θ + L) √ V (x(t)) ∫ t t k √ V (x(s))ds + 2 √ λ M ( ∥ε(t)∥ θ q-1 + θ∥K∥ ( 2 -e -k 1 θτ M ) δw ) √ V (x)
or equivalently

d dt √ V (x(t)) ≤ -µθ 2λ M √ V (x(t)) + θσ∥K∥(L + θ) ∫ t t k √ V (x(s))ds + √ λ M ( ∥ε(t)∥ θ q-1 + θ∥K∥ ( 2 -e -k 1 θτ M ) δw )
where σ = √ λ M /λm is the conditioning number of P . Finally, let

a θ = µθ/(2λ M ), b θ = θσ∥K∥(L + θ) and p θ (t) = √ λ M ( ∥ε(t)∥ θ q-1 + θ∥K∥ ( 2 -e -k 1 θτ M ) δw ) ( 33
)
and assume that the upper diameter of the sampling partition τ M satisfies the following condition

τ M < a θ b θ = µ 2(L + θ)σ∥K∥λ M ∆ = χ θ (34)
Then, according to Lemma 2.1, one has

√ V (x(t)) ≤ e -η θ t √ V (x(0)) + c θ τ M 2 -e -η θ τm 1 -e -η θ τm ( 35
)
where

c θ = sup t≥0 Ess p θ (t) = √ λ M ( δε θ q-1 + θ∥K∥ ( 2 -e -k 1 θτ M ) δw ) and η θ (τ M ) = (a θ -b θ τ M ) e -a θ τ M (36)
Coming back to the original coordinates of the observation error x and proceeding as in the continuous measurements case, we get

∥x(t)∥ ≤ σθ q-1 e -η θ (τ M )t ∥x(0)∥ + θ q-1 c θ τ M √ λm 2 -e -η θ (τ M )τm ( 1 -e -η θ (τ M )τm ) (37)
Substituting in the above inequality c θ by its expression (33) leads to

∥x(t)∥ ≤ σθ q-1 e -η θ (τ M )t ∥x(0)∥ +N θ (τm, τ M ) ( δε/θ + θ q-1 ∥K∥ ( 2 -e -k 1 θτ M ) δw ) ( 38
)
where

N θ (τm, τ M ) = σθτ M 2 -e -η θ (τ M )τm 1 -e -η θ (τ M )τm (39)
constants η θ and N θ respectively defined by ( 36) and ( 39) can be considered as functions of the sampling period Ts and specify as follows:

η θ (Ts) ∆ = (a θ -b θ Ts) e -a θ Ts N θ (Ts) ∆ = σθTs
2 -e -η θ (Ts)Ts 1 -e -η θ (Ts)Ts = σθTs

( 1 + 1 1 -e -η θ (Ts)Ts ) (40)
It is easy to check that for all T s ≥ 0 satisfying (34), the first derivative of the function η θ (Ts) with respect to Ts is non positive and therefore η θ is a decreasing function of Ts.

We now shall show that N θ (Ts) is a non decreasing function of Ts. To this end, let us show that the derivative of this function with respect to Ts, denoted by N ′ θ (Ts), is positive. Indeed, one has:

1 σθ N ′ θ (Ts) = 1 + 1 1 -e -η θ (Ts)Ts -Ts Tsη ′ θ (Ts) + η θ (Ts) ( 1 -e -η θ (Ts)Ts
) 2 e -η θ (Ts)Ts ≥ 1 + 1 1 -e -η θ (Ts)Ts -Tsη θ (Ts)e -η θ (Ts)Ts ( 1 -e -η θ (Ts)Ts ) 2

(since η ′ θ (Ts) ≤ 0) = + 1 1 -e -η θ (Ts)Ts - 1 1 -e -η θ (Ts)Ts ( Tsη θ (Ts)e -η θ (Ts)Ts ( 1 -e -η θ (Ts)Ts ) ) ≥ 1 (since Tsη θ (Ts)e -η θ (Ts)Ts ( 1 -e -η θ (Ts)Ts ) ∆ = αe -α (1 -e -α ) ≤ 1 ∀α ≥ 0)
Now, let us take the limits of these functions when Ts tends to zero. Indeed, one has: Furthermore, it is clear that the function

Ts → ( δε/θ + θ q-1 ∥K∥ ( 2 -e -k 1 θTs ) δw ) is a non decreasing function of Ts with lim Ts→0 ( δε θ + θ q-1 ∥K∥ ( 2 -e -k 1 θTs ) δw ) = ( δε θ + θ q-1 ∥K∥δw )
So, the results obtained in the sampled output case are in accordance with those derived in the continuous output one: the decreasing to zero of the observation error is inversely proportional to the magnitude of the sampling period while the value of the ultimate bound is proportional to this magnitude. Moreover, when the sampling period tends to zero, the expressions for the decay rate and ultimate bound are identical to those derived in the continuous output case.

The properties of the continuous-discrete time observer (29) are quite similar to those of the purely continuoustime one. Indeed, in the noise free case and in the absence of uncertainties, i.e. δε = δn = 0, the observation error converges exponentially to zero. If δε ̸ = 0 and is finite, the observation error lies in some ball centered at the origin with a radius proportional to δε but it can be made arbitrarily small by choosing θ sufficiently high. However and as in the continuous case, high values of θ are to be avoided in practice where the presence of the noise measurement is unavoidable. According to [START_REF] Jin | Kinetics of batch fermentations for ethanol production with immobilized saccharomyces cerevisiae growing on sweet sorghum stalk juice[END_REF], high values of θ give rise to a high bound for the estimation error since this bound is of the order of θ q-1 . Moreover, very high values of θ may not be allowed since they could violate the condition τ M < χ θ given by theorem 3.1. On other aspects, It is worth noticing that the calibration of the continuous-discrete time observer (29) is mainly achieved through the tuning of the observer design parameter θ as in the continuous-time output case. The specification of this design parameter is commonly carried out bearing in mind a suitable compromise between the convergence speed and the noise measurements insensitivity as pointed out in the earlier contributions on high gain observers [START_REF] Gauthier | A simple observer for nonlinear systems -application to bioreactors[END_REF][START_REF] Farza | Simple nonlinear observers for on-line estimation of kinetic rates in bioreactors[END_REF]. This suitable compromise is generally obtained from a trial and error approach since conditions ( 15) and ( 34) are too conservative to provide a reasonable specification of the involved design parameters. An admissible value of the design parameter θ can be used to determine the maximum allowable value for the sampling partition diameter according to inequation (34). Nevertheless, it is possible to find a higher value than the theoretical bound using an appropriate trial and error approach. This issue shall be more discussed and illustrated in simulation through a bioreactor where takes place an ethanolic fermentation.

Notice that thorough investigations addressing the challenging performance improvement issue of high gain observers noise sensitivity have been recently carried out in [START_REF] Andrieu | High gain observers with updated gain and homogeneous correction terms[END_REF][START_REF] Boizot | An adaptive high-gain observer for nonlinear systems[END_REF][START_REF] Oueder | A high gain observer with updated gain for a class of MIMO non-triangular systems[END_REF].

On-line estimation of the reactions rates in bioreactors

The use of state observers for on-line estimation of the reactions rates in bioreactors has been widely discussed in the literature (see for instance [START_REF] Bastin | On-line estimation and adaptive control of bioreactors[END_REF][START_REF] Farza | Simple nonlinear observers for on-line estimation of kinetic rates in bioreactors[END_REF][START_REF] Dochain | State and parameter estimation in chemical and biochemical processes: a tutorial[END_REF][START_REF] Battista | Specific growth rate estimation in (fed-)batch bioreactors using secondorder sliding observers[END_REF] and references therein). However, in most contributions, the proposed estimators assumed continuous outputs measurements. Discrete-time estimators have been proposed to handle the usual case where the output measurements are available only at sampling instants. The underlying design is based on a discrete-time model of the bioreactor resulting from a forward Euler discretization of the continuous time model. We shall show here through a fermentation process how the proposed continuous-discrete time observer can be used for the on-line estimation of the kinetic rates from the available samples corresponding to some components concentrations. More specifically, we consider a fermentation dealing with the production of ethanol (product) by Saccharomyces cerevisiae (biomass) which grow on sweet sorghum stalk juice containing glucose as carbon source (substrate) [START_REF] Jin | Kinetics of batch fermentations for ethanol production with immobilized saccharomyces cerevisiae growing on sweet sorghum stalk juice[END_REF][START_REF] Birol | Mathematical description of ethanol fermentation by immobilised saccharomyces cerevisiae[END_REF]. The bioprocess is operating in a continuous mode with a time-varying dilution rate D(t) and a constant input substrate concentration S in . The mathematical dynamical model of the process is:

           Ẋ = r 1 -DX Ṡ = - 1 y X/S r 1 - 1 y P/S r 2 + D(S in -S) Ṗ = r 2 -DP (41)
where X, S, P are the respective concentrations of biomass, substrate and product, r 1 and r 2 are the reactions rates and y X/S and y P/S are yield coefficients. The reactions rates r 1 and r 2 are generally very complex functions of the operating conditions and the state of the process. The analytical modelling of these functions is often cumbersome and still constitutes the subject of further and intensive investigations. To tackle this problem, these functions are treated as time-varying parameters that need to be estimated using the measurements of some components concentrations.

6

CONFIDENTIAL. Limited circulation. For review only Automatica submission 13-0946.5

Preprint submitted to Automatica Received February 16, 2015 05:56:13 PST By adopting such a strategy, bioengineers would not be brought to choose a particular model amongst the several ones described in the literature. Moreover, these estimates, which are interesting for process control, can also be used for basic investigations of the culture under consideration. In this example, we shall suppose that the substrate and product concentrations are measured and their corresponding measurements are available at sampling instants. The reactions rates r 1 and r 2 shall be treated as time-varying kinetic parameters with unknown dynamics and the objective consists in estimating these key parameters from the measured samples of S and P . Such an objective shall be achieved by considering the following system:

             ẋ1 (t) = Y x 2 (t) -Dx 1 +   DS in 0   ẋ2 (t) = ε(t) y(t k ) = x 1 (t k ) (42)
where

x 1 =   x 1 = S x 2 = P   , x 2 =   x 3 = r 1 x 4 = r 2   , Y =   -1/y X/S -1/y P/S 0 1   is the matrix of yield coefficients and ε =   ε 1 = ṙ1 ε 2 = ṙ2   is an unknown bounded function.
System (42) can be put under the form (1) by considering the following linear change of coordinates:

Φ :   x 1 x 2   -→ z =   z 1 = x 1 z 2 = Y x 2   .
Hence, a continuousdiscrete time impulsive observer of the form (29) can be synthesized for the on line-estimation of the reactions rates r i 's. The equations of the observer can be written in the original coordinates, by considering the inverse of the jacobian transformation as follows:

             ẋ1 (t) = Y x2 (t) -Dx 1 +   DS in 0   -2θe -2θ(t-t k ) (x 1 (t k ) -x 1 (t k )) ẋ2 (t) = -θ 2 e -2θ(t-t k ) Y -1 (x 1 (t k ) -x 1 (t k )) (43)
Notice that the gain of the observer (29) is specified in this example as K 1 = 2I 2 and K 2 = I 2 in such a way that the matrix A -KC has all its eigenvalues located at (-1). We shall provide in the next section some simulation results in order to illustrate performance and the main properties of the proposed observer.

Simulation results

For simulation purposes and in order to generate the pseudo-measurements of S and P , the reactions rates have to be expressed as functions of the components concentrations. The following expressions have been chosen [START_REF] Jin | Kinetics of batch fermentations for ethanol production with immobilized saccharomyces cerevisiae growing on sweet sorghum stalk juice[END_REF][START_REF] Birol | Mathematical description of ethanol fermentation by immobilised saccharomyces cerevisiae[END_REF]:

r 1 = µmaxXS K SX + S (1 -K P X P ), r 2 = qmaxXS K SP + S (1 -K P P P ) (44)
where µmax, qmax, K SX , K SP , K P X and K P P are constant kinetic parameters. The simulation experiments have been performed using the following initial conditions: S(0) = Ŝ(0) = 92.45(g/L), P (0) = P (0) = 1.37(g/L), X(0) = 0.19(g/L), r1 (0) = r2 (0) = 0(1/h)The values of the kinetic parameters are: µmax = 0.259(1/h), qmax = 1.916(1/h), y X/S = 0.043(g/g), y P/S = 0.424(g/g), K SX = 0.258(g/L), K SP = 0.83(g/L), K P X = 0.007 (g/L) -1 , K P P = 0.01 (g/L) -1 , S in = 100(g/L). The dilution rate varies as a sinusoidal signal as shown in figure 1. Two simulation sets of results shall be presented depending on whether the outputs are corrupted or not by noise measurements.

The noise-free case

Although this ideal situation is not realistic, it is considered to corroborate the theoretical results obtained through the convergence analysis carried in the above sections. Indeed, according to these results, the ultimate bound for the estimation error can be made as small as desired in the case where the output are available in a continuous manner. If these outputs are available at sampling instants only, then the ultimate bound is an increasing function of the sampling period and it tends to the continuous ultimate bound when the sampling period tends to zero. Indeed, we have reported in figure 2 the estimation errors on the reactions rates provided by the continuous-time observer for two values of θ, namely 50 and 10 and it is clear that the estimation errors decrease when θ increases. Similarly, we have compared in figure 3 the estimation errors issued from the continuous time observer with those corresponding to the continuous-discrete time one when the sampling period is very small, namely Ts = 0.01h. For each estimation error, the curves corresponding to the purely continuous-time and continuousdiscrete time observers are superimposed. This clearly confirms that the continuous-discrete time observer has a similar behaviour as the purely continuous-time one when the sampling period approaches zero. The estimates of the reactions rates provided by the continuous-discrete time observer are compared with their true evolution, issued from the simulation of system (41), are also provided in figure 3. The accuracy of the provided estimates are worth to be emphasized. However, such an accuracy has been obtained by using sufficiently high values of the observer design parameter θ. As mentioned throughout the previous sections, such values give rise to poor performance in the presence of noise measurements. As a result, in the next section which deals with noisy outputs, lower values for θ shall be considered to ensure a good compromise between accuracy and sensitivity to noise measurements.

On other aspects, one recall that the expressions of the reactions rates given by equations (44) are ignored by the the observers ( 6) and (29). These expressions have been considered in order to generate the pseudo-measurements of S and P used by these observers.

The noisy outputs case

In order to simulate practical situations, the measurements of S and P issued from the simulation of system ( 41 mean value and a variance equal to 0.1 and 0.05, respectively (see figure 4). The simulation study has been performed as follows. First, several simulation experiments have been carried out assuming continuous time output measurements. This allows to obtain a lower bound on the design parameter θ for which the underlying continuous time observer performs well: it ensures a good compromise between a satisfactory tracking of the kinetics unknown dynamics and a well behavior with respect to noise measurements (see figure 5). The value of θ ensuring such a compromise was about 5 which, as expected, is smaller than the values considered in the noise-free case which gave very accurate estimates. Then, the continuous- Preprint submitted to Automatica Received February 16, 2015 05:56:13 PST design parameter θ to this value while considering a very small constant value for the sampling period e.g. Ts = 0.01h. As in the noise free case, the obtained estimates are quite similar, while being somewhat more noisier, to those obtained in the continuous outputs case confirming thereby the theoretical results. Another simulation has been carried out in this case by considering a lower value for the design parameter θ, i.e. θ = 3. The estimates of the reactions rates obtained with this value are smoother than those obtained with θ = 5 but they are less precise since this value does not allow a satisfactory tracking of the reactions unknown dynamics. This explains the phase-shift like behaviour between the provided estimates of the reactions rates and their true values. In order, to show the behaviour of the continuous-discrete time observers for more higher values of the sampling period, two values of the latter have been considered, Ts = 0.1h and Ts = 1h. In each case, the value of the design parameter θ has been chosen by a trial and error approach to get a good compromise between a satisfactory tracking of the kinetics unknown dynamics and a well behavior with respect to noise measurements . Indeed, the value of θ has been set to 3 for Ts = 0.1h and to 2 when Ts = 1h . The obtained estimates are given in figure 6 which clearly shows that the continuous-discrete time observer allows a good tracking of the reactions rates while performing well with respect to the noise measurements. Moreover and as expected from the theoretical analysis, the best estimates are obtained with smaller values of the sampling period.

Conclusion

We have derived an impulsive continuous-discrete time high gain observer for a class of nonlinear systems involving some uncertainties and subject to noisy sampled output measurements. The main characteristic of this observer lies in the fact that it provides continuous time estimates of the whole system state from the available output samples. The convergence of the underlying observation error has been established under a well defined condition on the observer, the system parameters (system dimension, Lipschitz constant) and the maximum allowable value of the sampling partition diameter. More specifically, it has been shown that the observation error remains confined in a ball centered at the origin with a radius proportional to the magnitudes of the uncertainties, the measurements noise and the maximum of the sampling partition diameter. The effectiveness of the proposed observers has been illustrated in simulation through an example dealing with an ethanolic fermentation. The obtained results are quite promising to conclude that the proposed observers are able to provide relatively accurate estimates of the reactions rates even in the case of relatively long sampling periods.

Fig. 1 .

 1 Fig. 1. Time evolution of the dilution rate

10 Fig. 2 .Fig. 3 .

 1023 Fig. 2. Estimation of r1 and r2 from noise-free continuous outputs

Fig. 4 .Fig. 5 .

 45 Fig. 4. Continuous noisy measurements of S and P