Jing Zhou
email: zhoujing@cuc.edu.cn

Zhongzhi Shi

Unstructured P2P-Enabled Service Discovery in the Cloud Environment

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Armbrust et al. defined in [START_REF] Armbrust | Above the clouds: A berkeley view of cloud computing[END_REF] that Cloud computing comprises the applications delivered as services over the Internet and the hardware and system software in the datacenters that offer those services. Typically, Cloud computing comes in three kinds: Software as a Service (SaaS), Platform as a Service (PaaS), and Infrastructure as a Service (IaaS) [START_REF] Buyya | Cloudbus toolkit for market-oriented cloud computing[END_REF]. The classification emphasizes the core concept of "X as a Service", that is, software, platform, and infrastructure all can be provided to end users on demand and on a subscription basis.

Cloud services are currently available from providers such as Amazon, Microsoft, Google App Engine, Eucalyptus, and GoGrid. Users can access Cloud services by visiting service provider's website, establishing a runtime environment in response to instructions, creating a user account, and configuring related tools. There is no complicated mechanism for service discovery involved. As the Cloud computing will soon become part of the mainstream computing in a few years, the number of the services it provides, its users, and the requests of these services will increase in orders of magnitude. To deliver satisfactory experience to Cloud users, highly scalable techniques for service discovery should be available.

We observed in distributed systems that service discovery mechanisms are primarily centralized in which a central index server (or several such servers) stores and maintains all information about services being offered. Centralized service discovery is prone to the following issues: 1) single point of failure; 2) lack of satisfactory scalability; 3) requirements for powerful computing capabilities to serve large amounts of service discovery and update queries on the central server; and 4) performance bottlenecks and network congestion. To overcome these obstacles so as to deliver a Cloud service discovery mechanism of high performance, we will rely on peer-to-peer (or P2P for short) computing [START_REF] Clark | Face-to-face with peer-to-peer networking[END_REF].

The popularity of P2P computing stems from its self-organization, fault tolerance, and scalability, which make P2P computing an obvious candidate for tackling large scale service discovery in the Cloud environment. Studies [START_REF] Ranjan | Peer-to-peer cloud provisioning: Service discovery and load-balancing[END_REF] showed that satisfactory scalability could be achieved if P2P techniques based on DHTs (distributed hash tables) were applied to service discovery in Cloud computing. We, however, argue that such structured P2P techniques place severe constrains on the network topology and the placement of services (or their indices), which makes structured P2P unable to better model the real world.

We aim to address the issue of service discovery in the Cloud computing by exploring the Semantic Web technology to describe Cloud services and to facilitate service discovery and service matching, and investigating unstructured P2P-based techniques that support highly efficient and scalable routing mechanisms for service requests.

The balance of the paper is structured as follows. Related work is reviewed in Sect. 2. We present and discuss the primary design issues in Sect. 3 in greater details. Finally, we conclude the paper by identifying open issues in Sect. 4.

Related Work

Unstructured P2P and structured P2P

Unstructured P2P systems including Gnutella, Freenet, and FastTrack carry out object lookup and downloading operations in the absence of a central index server. Each peer maintains indices for the resources it currently holds. A lookup operation in such systems will not necessarily be successful and there is no upper and lower bounds on the successful operation, that is, non-deterministric query performance is offered. In addition, unstructured P2P systems support one-dimensional and multi-dimensional point queries and range queries.

Similarly, there is no central index server in structured P2P built upon DHTs (such as CAN, Chord, Pastry, and Tapestry). Each peer maintains the indices of data items on another O(log n) peers where n is the number of peers in the system. The keys of the data items and nodes are mapped onto the overlay network in which each node is responsible for managing a small number of data items. Whenever a peer receives a lookup request, it is able to locate the data item of interest within O(log n) hops. Therefore, the query performance delivered by structured P2P is deterministic. One-dimensional point queries can be well supported but, in order to implement one-dimensional range queries and multidimensional point queries and range queries, the system needs to employ spatial indices [START_REF] Samet | The Design and Analysis of Spatial Data Structure[END_REF] such as the Space Filling Curve, kd-trees and MX-CIF quadtree, and carry out sufficient extension to the basic DHT mechanism [START_REF] Cai | Maan: A multi-attribute addressable network for grid information services[END_REF].

Note that each peer in structured P2P maintains the indices of data items of others (but not the data items of its own!) and reliance among peers exists. However, each Cloud service provider maintains its own services, describing the services, creating indices according to service description, and publishing service description to facilitate service discovery. Furthermore, service discovery in Cloud computing will regularly be performed based on multiple (instead of single) attributes of the service in most cases. We believe that the search mechanism enabled by unstructured P2P techniques can better resolve multidimensional queries by incorporating support for semantics, whereas the basic DHT technique delivers satisfactory performance in keyword search.

P2P-based Service Discovery

A robust, automatic, and reliable mechanism for service discovery is indispensable to distributed systems such as Grid computing, Web services, and pervasive computing because it helps users to locate services or resources required in such systems [START_REF] Toma | Discovery in grid and web services environments: A survey and evaluation[END_REF][START_REF] Bachlechner | Web service discovery -a reality check[END_REF][START_REF] Zhu | Service discovery in pervasive computing environments[END_REF][START_REF] Mokhtar | Easy: Efficient semantic service discovery in pervasive computing environments with qos and context support[END_REF]. To overcome the drawbacks and inefficiencies of centralized service discovery in terms of scalability, fault-tolerance, and network congestion, a number of fully decentralized solutions were proposed. Among others, the approach that adopts the P2P paradigm draws a great deal of attention (see [START_REF] Ranjan | Peer-to-peer-based resource discovery in global grids: A tutorial[END_REF] for details on P2P-based resource3 discovery in computational grids).

The first step towards implementing a P2P-based mechanism for service discovery is to design a decentralized index system in which the appropriate data structure is selected for building indices upon the service description. Since a service is typically characterized by both static and dynamic attributes, users can specify the requirement for multiple attributes in a query, that is, a multidimensional query is allowed. In unstructured P2P, each peer maintains its own services and service descriptions, hence simple indices, such as the two dimensional table, can be employed to faciliate resolving multi-dimensional queries.

The routing mechanism for multi-dimensional queries in the P2P paradigm should also be developed, which helps forward service requests to their destination peers efficiently. Flooding and its variants [START_REF] Lv | Search and replication in unstructured peer-to-peer systems[END_REF][START_REF] Iamnitchi | A peer-to-peer approach to resource location in grid environments[END_REF] are the widely used approaches to message routing in unstructured P2P. The main drawback of such techniques includes that excessive unnecessary query messages and traffic are generated. Vairous heuristics [START_REF] Chawathe | Making gnutella-like p2p systems scalable[END_REF][START_REF] Zhou | Supporting ad-hoc resource sharing on the web: A peer-to-peer approach to hypermedia link services[END_REF] were therefore developed to guide message routing as well as to increase system scalability.

When a query is eventually delivered to a potential destination peer, a matching scheme is needed to confirm a perfect match between the service description and the user requirement expressed in the query message. Currently, keywordbased methods widely used in structured P2P, due to their unsatisfactory search performance, have been gradually replaced by semantics-based solutions. This topic is however not the focus of our paper and we leave it to the future work.

Service Description and Discovery Using Semantics

When describing a service, elements such as the service properties, capabilities, and constraints should be taken into account. To service the request, the Semantic Web offers a number of powerful tools. The integration of the Semantic Web technologies is beneficial to the realization of efficient service discovery due to the following reasons: 1) Ontology can be used to describe concepts and the relationships among the concepts within a specific domain in a disambiguous way and hence, people often employ ontology to describe services and encode the description semantically; 2) Languages such as OWL can be used to describe ontologies in order to support semantic inference for relationships among various concepts; 3) A number of tools in the Semantic Web community have been developed for service (Web Services in particular) description purposes, including OWL-S [START_REF] Martin | Owl-s: Semantic markup for web services[END_REF], WSMO (Web Services Modeling Ontology) [START_REF] Roman | Web service modeling ontology[END_REF] and Web Service Semantics -WSDL-S [START_REF] Akkiraju | Web service semantics -wsdl-s[END_REF]; and 4) The semantic service description with powerful expresiveness is necessary to service matching based on semantics.

Semantics-based service matching comes in two forms: signature matching [START_REF] Zaremski | Signature matching: a tool for using software libraries[END_REF] and specification matching [START_REF] Zaremski | Specification matching of software components[END_REF]. In signature matching, the subsumption relationship between concepts that are defined in ontologies and are used to describe the input capabilities (that is, the required services) and output capabilities (that is, the available service descriptions), is identified. Specification matching is, however, performed between the pre-conditions and post-conditions of the functional semantics of software components using automated theorem proving or query containment. Semantic matching has been applied to a number of distributed systems, including Grid computing [START_REF] Harth | A semantic matchmaker service on the grid[END_REF][START_REF] Ludwig | Introduction of semantic matchmaking to grid computing[END_REF], P2P computing [START_REF] Zhou | Scalable web service discovery on p2p overlay network[END_REF][START_REF] Li | Pwsd: A scalable web service discovery architecture based on peer-to-peer overlay network[END_REF], Web Services [START_REF] Paolucci | Semantic matching of web services capabilities[END_REF], and pervasive computing [START_REF] Mokhtar | Easy: Efficient semantic service discovery in pervasive computing environments with qos and context support[END_REF].

To address the issue of service matching in the Cloud environment in particular, Zeng et al. proposed a matching algorithm which extends the keywords that describe the input and output capabilities of services by using WordNet [START_REF] Zeng | Cloud computing service composition and search based on semantic[END_REF]. A function is employed to evaluate the semantic similarity between the concept sets (consisting of concepts extended from the keywords) of any two services. The primary drawback of the approach is lack of support for range queries.

System Design

System Overview

Our proposed system consists of Cloud service providers (peers in P2P terminology) that describe their own services, create indices according to service descriptions, and publishing service descriptions for sharing purposes. Each new peer or node, upon arrival, will exchange its service descriptions with others (and maintain the information in its local index) that are already in the network, that is, 1-step replication [START_REF] Gkantsidis | Hybrid search schemes for unstructured peer-to-peer networks[END_REF] is utilized, thus forming a neighboring relationship with those nodes. When a peer voluntarily leaves the system, or is lost due to topology re-organization, the index information for that neighbor gets flushed.

According to our previous work on unstructured P2P, flooding and random walk search techniques can hardly offer scalability comparable to that of DHTbased approaches. One efficient solution to the problem is to introduce a certain degree of centralized control in the P2P network, that is, supernodes [START_REF] Chawathe | Making gnutella-like p2p systems scalable[END_REF] [START_REF] Gkantsidis | Hybrid search schemes for unstructured peer-to-peer networks[END_REF]. We therefore allow a few number of peers with high capacity to act as supernodes as needed. For instance, when a peer finds its knowledge about services provided by other peers is rich enough 4 , it can elect itself to be a supernode by informing all neighbors of the decision. If the latter agree to accept the peer as a supernode, they will update their indices to reflect the change. The primary motive underlying the introduction of supernodes is to bias query messages towards nodes that provide a shortcut to the destination peers with a high probability.

Moreover, to avoid overburdening nodes with query messages from neighbors, we allow nodes to add links to more useful neighbors and drops links to useless ones, thus leading to reorganization of the P2P overlay topology. Topology reorganization is often used by P2P systems to faciliate resource/service discovery by shortening the distance (in the form of hops) between the potential destination peers and the resource/service requester based on predictions of future requests.

We elaborate on issues comprising service description, description indexing, and routing of service requests in the following sections.

Service Description

To describe Could services, we start by using WSDL-S-currently a W3C member submission that offers a lightweight solution to creation of semantic service description. In WSDL-S, the expressivity of WSDL was augmented with semantics by adopting concepts similar to those in OWL-S. We may gradually extend and enhance WSDL-S by means of the extensibility provided by WSDL itself according to the specific requirements for Cloud service descriptions.

In a nutshell, WSDL-S provides a few extensibility elements to realize the URI reference mechanism as follows [START_REF] Akkiraju | Web service semantics -wsdl-s[END_REF]. wssem:modelReference specifies the association between a WSDL entity and a concept in a semantic model. wssem:schemaMapping handles the structural difference between the schema elements of a Web service and their corresponding concepts in a semantic model. wssem:precondition and wssem:effect are specified as child elements of the element operation and describe the semantics of the operation. wssem:serviceCategorization comprises service categorization information that could be used when publishing a service in a Web Services registry.

A Cloud service can be semantically annotated by borrowing all these constructs from WSDL-S. Figure 1 presents an example Cloud service description. Note that a precondition is a set of statements that should be true before a service can be successfully invoked. Hence, we can describe part of a user's requirement for a service by means of preconditions. For instance, if a user is looking for a disk storage service, she can send out a "DiskStorage" request and specify the capacity should be 200GB and the transfer rate of the disk should be 50Mb/s. However, in proposal [START_REF] Akkiraju | Web service semantics -wsdl-s[END_REF] at most one precondition (as well as one effect) is allowed so multiple preconditions should be captured into one high level precondition. We can combine those two statements via "AND" into one precondition since WSSemantics.xsd defines an attribute "expression" of type "string" for wssem:precondition.

<?xml version="1.0" encoding="iso-8859-1"?> <definitions name="DiskStorage" targetNamespace="http://www.example. <xs:complexType name="processDiskStorageRequest"> <xs:all> <xs:element name="billingInfo" type="xsd1:DSBilling"/> <xs:element name="storageItem" type="xsd1:DSItem"/> </xs:all> </xs:complexType> <!-Semantic annotation is added directly to leaf element -> <xs:element name="processDiskStorageResponse" type="xs:string" wssem:modelReference="DSOntology#StorageConfirmation"/> </xs:schema> </types> <interface name="DiskStorage"> <operation name="processDiskStorage" pattern="wsdl:in-out" wssem:modelReference="DSOntology:RequestDiskStorage"> <input messageLabel ="processDiskStorageRequest" element="tns:processDiskStorageRequest"/> <output messageLabel ="processDiskStorageResponse" element="processDiskStorageResponse"/> <wssem:precondition name="AvailableStoragePrecond" wssem:modelReference="DSOntology#StroageAvailable" expression="DSOntology#Capacity=200GB&& DSOntology#Transferrate=50Mb/s"/> <wssem:effect name="StorageOccupiedEffect" wssem:modelReference="DSOntology#StorageOccupied"/> </operation> </interface> </definitions> Fig. 1. An example Cloud service description

Description Indexing

Among all the constructs used to describe a Cloud service, the precondition is the most important resource upon which we can build indices for all the services in a P2P network. Suppose a user issues a Cloud service request and we can then compile part of the request (which is specified in wssem:precondition) as (attri 1, value 1 ), (attri 2, value 2 ), . . . , (attri i, value i ).

As such, a user request can be converted to a multi-dimensional query by which the user specifies multiple conditions should be met on several attributes. We adapted one of the database approachs-the kd-tree-to establish a data space for all service descriptions. Once the data space is constructed, we set out to develop the routing strategy (in the following section) by which a multi-dimensional query can be efficiently forwarded to the relevant peers in such a space.

The kd-tree is a data structure that decomposes a multi-dimensional data space into hyperrectangles and each node corresponds to a hyperrectangle. The fields of a kd-tree node include the splitting dimension number, splitting value, left kd-tree, and right kd-tree. According to the first two fields, each node splits the space into two subspaces. Searching for a point in the dataset represented in a kd-tree can be carried out in a traversal of the tree from root to leaf (O(log n) if there are n data points). In the following, we demonstrate a kd-tree representation of 4 points (200GB, 50Mb/s), (300GB, 80Mb/s), (600GB, 30Mb/s), and (800GB, 90Mb/s). For simplicity, a 2-d space is used for illustration. In Fig. 2, the root node (200GB, 50Mb/s) splits the space in the y-axis into two subspaces. The point (600GB, 30Mb/s) lies in the lower space, that is, {(x, y)|y < 50} and hence is in the subtree of the root node. By traversing such a kd-tree, the hyperrectangle leave that potentially contains the target point can be located.

In our system, each new node locally creates an index in the form of a kdtree for all the service descriptions it is aware of. The index will gradually grow and evolve as nodes join and depart from the system. The description indices are therefore distributed among individual nodes and will be used for routing service requests.

Routing of Service Requests

Part of a user's service request (encoded in wssem:precondition) is used to formulate a multi-dimensional query. To execute the query over a P2P network, it must be routed to the set of nodes that contain data relevant to the query. We describe routing as follows.

1. According to the content of the query, the node issueing the query will first traverse its kd-tree to locate the set of potential target nodes and subsequently forward the query to those nodes. If no such nodes are found, the node simply sends the query to its associated supernodes, if any. Otherwise, it will flood the query message to all neighbors. 2. Upon receipt of an incoming query, the receiving node checks its local index to find the target service that might satisfy the user query5 and forwards the query to the potential targets. If no such nodes are found, the node routes the query to its associated supernodes, if any. Otherwise, it will flood the query message to all neighbors if the message was not flooded in its last hop.

A flooded message, in this case, will be sent to a randomly chosen neighbor.

This process is repeated until: 1) there are no other potential targets to which a query can be further routed, 2) the TTL (Time-To-Live) in the query message is decreased to zero, or 3) the service requester explicitly claims that enough results have been collected.

Discussions

-Decentralized indices: By locally creating a kd-tree to index all service descriptions that a peer node is aware of, we obtain a fully distributed index (consists of all the local indices) for service discovery in the proposed P2P system. Neighbors simply delete index information about services of a leaving node from their kd-tree, whereas in a DHT-based structured P2P system, node departure incurs much more operations. -Support for point and range queries: Thanks to the use of the kdtree, both a point query and a range query can be similarly handled in our system. This is in contrast to other approaches in which it is easy to resolve the point query but sufficient extensions should be made to the basic mechanism (DHTs for instance) if range queries are also supported. -Localized scheme: We proposed a localized scheme when constructing the kd-tree index for each peer node, that is, no global knowledge is required. However, in [START_REF] Ganesan | One torus to rule them all: multidimensional queries in p2p systems[END_REF] when "skip pointers" (shortcuts used for optimized routing based on kd-trees) are built, the set of all nodes should be known in advance.

Future Work

In our preliminary work on unstructured P2P-enabled service discovery in Cloud computing, much still is left to be investigated. For instance, we have yet to experimentally demonstrate the efficency and the scalability of the routing algorithm. Moreover, developing matching and sorting algorithms for semanticsbased service matching is also indispensable for realizing effective and efficient service discovery in the context of Cloud computing. We are currently exploring these issues and will report our onging work in a forthcoming paper soon.

Fig. 2 .

 2 Fig. 2. A k-d tree example

  com/wsdl-s/examples/diskstorage.wsdl" xmlns="http://www.w3.org/2004/08/wsdl" ...... xmlns:wssem="http://www.example.com/wsdl-s/examples/diskStorage.wsdl" xmlns:DSOntology="http://www.example.com/wsdl-s/ontologies/DiskStorage.owl" <types> ...... <xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema"

targetNamespace="http://www.example.com/wsdl-s/examples/diskStorage.wsdl" xmlns="http://www.example.com/wsdl-s/examples/diskStorage.wsdl">

The "resource" here may refer to clusters, supercomputers, and desktop computers and this concept has an overlap with that of the "service" in Cloud computing.

In related work such as[START_REF] Chawathe | Making gnutella-like p2p systems scalable[END_REF], supernodes refer to peers with higher bandwidth connectivity, whereas in our system in which service description is encoded with semantics (see Sect. 3.2) and we argue that nodes with richer knowledge should be able to better serve service requests and thus be elected as supernodes.

A perfect match is only confirmed after the semantics-based service matching has been carried out.

Acknowledgment

This work is funded by 382 Research Foundation for Talented Scholars (No. G08382320), the Engineering Disciplines Planning Project (No. XNG0921), and the Leading Academic Discipline Program (3rd phase of 211 Project for the Communication University of China). We also acknowledge the input of the National Natural Science Foundation of China (No. 60775035, No.60933004, No.60970088), the National High-Tech Research and Development Plan of China (No. 2007AA01Z132), National Basic Research Priorities Programme(No. 2007CB-311004) and National Science and Technology Support Plan (No.2006BAC08B06), Dean Foundation of Graduate University of Chinese Academy of Sciences(O85101-JM03).


P Bernard

L Praly

V Andrieu

H Hammouri

On the triangular canonical form for uniformly observable controlled systems

Keywords: uniform observability, differential observability, canonical observable form, uniform infinitesimal observability

We study controlled systems which are uniformly observable and differentially observable with an order larger than the system state dimension. We establish that they may be transformed into a (partial) triangular canonical form but with possibly non locally Lipschitz functions. We characterize the points where this Lipschitzness may be lost and investigate the link with uniform infinitesimal observability.

Introduction

Context

A lot of attention has been dedicated to the construction of nonlinear observers. Although a general theory has been obtained for linear systems, very few general approaches exist for nonlinear systems. In particular, the theory of high gain [START_REF] Khalil | High-gain observers in nonlinear feedback control[END_REF] and references therein) and Luenberger [START_REF] Andrieu | On the existence of a Kazantzis-Kravaris / Luenberger observer[END_REF]; [START_REF] Andrieu | Convergence speed of nonlinear Luenberger observers[END_REF]) observers have been developed for autonomous non linear systems but their extension to controlled systems is not straightforward.

For designing an observer for a system, a preliminary step is often required. It consists in finding a reversible coordinate transformation, allowing us to rewrite the system dynamics in a targeted form more favorable for writing and/or analyzing the observer. In presence of input, two tracks are possible depending on whether we consider the input as a simple time function, making the system time dependent or as a more involved infinite dimensional parameter, making the system a family of dynamical systems, indexed by the input. In the former case, the transformation mentioned above is considered time dependent, and thus may need to be redesigned for each input. In the latter case, the transformation can be input-dependent. Specifically : -in [START_REF] Jouan | Finite singularities of nonlinear systems. output stabilization, observability, and observers[END_REF] (see also [START_REF] Gauthier | Deterministic observation theory and applications[END_REF]), the transformation depends on the inputs Email addresses: pauline.bernard@mines-paristech.fr (P. Bernard), laurent.praly@mines-paristech.fr (L. Praly), vincent.andrieu@gmail.fr (V. Andrieu), hassan.hammouri@univ-lyon1.fr (H. Hammouri). and its derivatives. When the ACP(N) condition is verified (see Lemma [START_REF] Gauthier | Deterministic observation theory and applications[END_REF], Definition 5.2.1, Lemma 5.2.2)), it leads to the so called phase-variable representation as targeted form (see (Gauthier and Kupka, 2001, Definition 2.3.1)), for which a high gain observer can be built.

-in [START_REF] Besançon | Further results on high gain observers for nonlinear suystems[END_REF], the transformation does not depend on the input, and leads to a block triangular form when the system verifies the observability rank condition (see [START_REF] Hermann | Nonlinear controllability and observability[END_REF]). However, afterwards, an extra condition on the input is needed for the observer design. -in [START_REF] Gauthier | Observability for any u(t) of a class of nonlinear systems[END_REF]; [START_REF] Gauthier | A simple observer for nonlinear systems application to bioreactors[END_REF], the transformation does not depend on the input, and leads to a triangular form when the system is a) uniformly observable (see (Gauthier and Kupka, 2001, Definition I.2.1.2) or Definition 2 below), and b) strongly differentially observable of order equal to the system state dimension (see Definition 1 below). This so-called observable canonical form allows the design of a high gain observer.

In this paper, we complete and detail the results announced in [START_REF] Bernard | Non lipschitz triangular canonical form for uniformly observable controlled systems[END_REF]. We work within the third context (of the second track), but going beyond [START_REF] Gauthier | Deterministic observation theory and applications[END_REF] with allowing the strong differential observability order to be larger than the system state dimension. We shall see that, in this case, the system dynamics may still be described by a (partial) triangular canonical form (see (3)) but with functions which may be non locally Lipschitz.

Definitions and problem statement

We consider a controlled system of the form :

ẋ = f (x) + g(x)u , y = h(x) (1)
where x is the state in R dx , u is an input in R du , y is a measured output in R and the functions f , g and h are sufficiently many times differentiable, f being a column d x -dimensional vector field and g a (d x ×d u )-dimensional matrix field. In the following, for a scalar function α, L f α denotes its Lie derivative in the direction of f . It has scalar values. We denote

H i (x) = (h(x), L f h(x), ..., L i-1 f h(x)) ∈ R i . (2)
It is a column i-dimensional vector. Similarly L g α denotes the Lie derivative along each of the d u columns of g. It has row d u -dimensional vector values.

Given an input time function t → u(t) taking values in a compact subset U of R du , we denote X u (x, t) a solution of (1) going through x at time 0. We are interested in solving :

Problem P : Given a compact subset C of R dx , under which condition do there exist integers T and d z , a continuous injective function Ψ : C → R dz , and continuous functions ϕ dz : R dz → R and g i : R i (or R dz ) → R du such that, when x is in C and satisfies (1) and u is in

U, z = Ψ(x) satisfies ż1 = z 2 + g 1 (z 1 ) u . . . żT = z T+1 + g T (z 1 , . . . , z T ) u żT+1 = z T+2 + g T+1 (z) u . . . żdz = ϕ dz (z) + g dz (z) u , y = x 1 (3)
Because g i depends only on z 1 to z i , for i ≤ T, but potentially on all the components of z for i > T, we call this particular form up-to-T-triangular canonical form and T is called the order of triangularity. When d z = T + 1, we say full triangular canonical form. When the functions ϕ dz and g j are locally Lipschitz we say Lipschitz up-to-T-triangular canonical form.

We are interested in addressing the Problem P because, when the functions are Lipschitz and d z = T + 1, we get the nominal form for which high gain observers can be designed and therefore X u (x, t) can be estimated knowing y and u as long as (X u (x, t), u(t)) is in the given compact set C × U.

We will use the following two notions of observability defined in [START_REF] Gauthier | Deterministic observation theory and applications[END_REF] :

Definition 1 (Differential observability 1 ) System (1) is weakly differentially observable of order O on an open subset S of R dx if the function H O (see (2)) is injective on S.
If it is also an immersion, the system is called strongly differentially observable of order O.

Definition 2 (Uniform observability) (See (Gauthier and Kupk 2001, Definition I.2.1.2).) System ( 1) is uniformly observable on an open subset S of R dx if, for any pair (x a , x b ) in S 2 with x a = x b , any strictly positive number T , and any C1 function u defined on [0, T ), there exists a time t < T such that h(X u (x a , t)) = h(X u (x b , t)) and (X u (x a , s), X u (x b , s)) ∈ S 2 for all s ≤ t.

Note that this notion is a matter of instantaneous observability since T can be arbitrarily small. In the case where H dx is a diffeomorphism, we have In general, it is possible for the system not to be strongly differentially observable of order d x everywhere. This motivates our interest in the case where the system is strongly differentially observable of order O > d x , i-e H O is an injective immersion and not a diffeomorphism.

As we shall see in Section 2, in this case, we may still have an at least up-to-(d x + 1)-triangular form, but the Lipschitzness of its nonlinearities can be lost. Since this property is crucial for the implementation of high gain observers (see [START_REF] Ciccarella | A luenbergerlike observer for nonlinear systems[END_REF]), we give in Section 3 some sufficient conditions under which the Lipschitzness is preserved.

2 Immersion case (O > d x )
The specificity of the triangular canonical form (3) is not so much in its structure but more in the dependence of its functions g i and ϕ dz . Indeed, by choosing Ψ = H dz , we obtain:

˙ H dz (x) =        0 1 0 . . . 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 0 . . . . . . 0 1 0 . . . . . . . . . 0        H dz (x) +        0 . . . . . . 0 L dz f h(x)        + L g H dz (x)u
To get (3), we need further the existence of a function ϕ dz satisfying

L dz f h(x) = ϕ dz (H dz (x)) ∀x ∈ C (4)
and, for i ≤ T, of functions g i satisfying

L g L i-1 f h(x) = g i (h(x), . . . , L i-1 f h(x)) ∀x ∈ C .
(5) Let us illustrate via the following elementary example what can occur.

Example 1 Consider the system defined as

ẋ1 = x 2 , ẋ2 = x 3 3 , ẋ3 = 1 + u , y = x 1 We get H 3 (x) = (h(x), L f h(x), L 2 f h(x)) = (x 1 , x 2 , x 3 3 ) H 5 (x) = (H 3 (x), L 3 f h(x), L 4 f h(x)) = (H 3 (x), 3x 2
3 , 6x 3 ) Hence H 3 is a bijection and H 5 is an injective immersion on R 3 . So this system is weakly differentially observable of order 3 on R 3 and strongly differentially observable of order 5 on R 3 . Also the function (x 1 , x 2 , x 3 ) → (y, ẏ, ÿ) being injective for all u, it is uniformly observable on R 3 . From this we could be tempted to pick d z = 3 or 5 and the compact set C arbitrary in R 3 . Unfortunately, if we choose d z = 3, we have

L 3 f h(x) = 3x 2 3 = 3(L 2 f h(x)
) 2/3 and there is no locally Lipschitz function ϕ 3 satisfying (4) if the given compact set C contains a point satisfying x 3 = 0. If we choose d z = 5, we have

L g L 2 f h(x) = 3x 2 3 = L 3 f h(x) = 3(L 2 f h(x)) 2/3
and there is no locally Lipschitz function g 3 satisfying (5) if the given compact set C contains a point satisfying x 3 = 0.

Leaving aside the Lipschitzness requirement for the time being, we focus on the existence of continuous functions ϕ dz and g i verifying (4) and (5) respectively.

Existence of ϕ dz satisfying (4)

Proposition 2 Suppose System (1) is weakly differentially observable of order O on an open set S containing the given compact set C. For any d z ≥ O, there exists a continuous function ϕ dz : R dz → R satisfying (4). If System (1) is strongly differentially observable of order O on S, the function ϕ dz can be chosen Lipschitz on R dz .

PROOF. There is nothing really new in this result. It is a direct consequence of the fact that a continuous injective function defined on a compact set admits a continuous left inverse defined on the image (see (Bartle, 1964, §16.9)) and that this left inverse can be extended to the full space (e.g. Tietze extension theorem). In the case where H dz is also an immersion, according to (Andrieu, 2014, Lemma 3.2), there exists a real number

L H > 0 such that |x a -x b | ≤ L H |H dz (x a ) -H dz (x b )| ∀(x a , x b ) ∈ C 2 .
Therefore, the previously mentioned continuous leftinverse of H dz defined on H dz (C) is Lipschitz on H dz (C).

According to (McShane, 1934, Theorem 1), it admits a Lipschitz extension defined on R dz .

Existence of g i satisfying (5)

Concerning the functions g i , we will prove the following result :

Proposition 3 Suppose System (1) is uniformly observable on an open set S containing the given compact set C.

-There exists a continuous function g 1 : R → R du satisfying ( 5). -If, for some i in {2, . . . , d x }, H 2 , . . . , H i defined in

(2) are open maps, then, for all j ≤ i, there exists a continuous function g j : R j → R du satisfying (5).

The rest of this section is dedicated to the proof of this result through a series of lemmas, the proof of which can be found in appendix.

A first important thing to notice is that the following property must be satisfied for the identity ( 5) to be satisfied (on S).

Property A(i):

L g L i-1 f h(x a ) = L g L i-1 f h(x b ) ∀(x a , x b ) ∈ S 2 : H i (x a ) = H i (x b )
Actually the converse is true and is a direct consequence from Lemma 7 proved in Appendix B :

Lemma 1 If Property A(i) is satisfied with S containing the given compact set C, then there exists a continuous function g i : R i → R du satisfying (5).

Property A(i) being sufficient to obtain the existence of a function g i satisfying (5), we study now under which conditions it holds. Clearly A(i) is satisfied for all i ≥ O if H O is injective. If we do not have this injectivity property the situation is more complex. To overcome the difficulty we introduce the following assumption for 2

≤ i ≤ d x +1. Property B(i) : (6) For any (x a , x b ) in S 2 such that x a = x b , verifying H i (x a ) = H i (x b ) , there exists a sequence (x a,k , x b,k ) of points in S 2 converging to (x a , x b ) such that for all k, H i (x a,k ) = H i (x b,k ) and ∂Hi-1 ∂x is full-rank at x a,k or x b,k . As in this Property, let x a = x b be such that H i (x a ) = H i (x b ). If ∂Hi-1
∂x is full-rank at either x a or x b , then we can take (x a,k , x b,k ) constant equal to (x a , x b ). Thus, it is sufficient to check B(i) around points where neither ∂Hi-1 ∂x (x a ) nor ∂Hi-1 ∂x (x b ) is full-rank. But according to (Gauthier and Kupka, 2001, Theorem 4.1), the set of points where ∂H dx ∂x is not full-rank is of codimension at least one for a uniformly observable system. Thus, it is always possible to find points x a,k as close to x a as we want such that ∂Hi-1 ∂x (x a,k ) is full-rank. The difficulty of B(i) thus rather lies in ensuring that we have also

H i (x a,k ) = H i (x b,k ).
In Appendix A, we prove Lemma 2 Suppose System (1) is uniformly observable on a set S.

-Property A(1) is satisfied.

-If, for some i in {2, . . . , d x + 1}, Property B(i) holds and Property A(j) is satisfied for all j in {1, . . . , i -1}, then Property A(i) holds.

Thus, the first point in Proposition 3 is proved. Besides, a direct consequence of Lemmas 1 and 2 is that a sufficient condition to have the existence of the functions g i for i in {2, . . . , d x + 1} is to have B(j) for j in {2, . . . , i}. The following lemma finishes the proof of Proposition 3 by showing that B(j) is in fact satisfied when H j is an open map.

Lemma 3 Suppose that for some j in {2, . . . , d x }, H j is an open map on S. Then, B(j) is satisfied. ) \ H j (Π) is non-empty and contains a point y p . We conclude that there exist (x a,p , x b,p ) in B p (x a ) × B p (x b ) such that H j (x a,p ) = H j (x b,p ) = y p and ∂Hj ∂x (and thus ∂Hj-1 ∂x ) is full-rank at x a,p and x b,p . Besides (x a,p , x b,p ) converges to (x a , x b ), and B(j) is satisfied.

PROOF. Take (x a , x b ) in S 2 such that x a = x b and H j (x a ) = H j (x b ) = y 0 . Let Π be
Note that the assumption that H j is an open map is stronger that B(j) since it leads to the full rank of ∂Hj ∂x , while, in B(j), we only need the full-rank for ∂Hj-1 ∂x . We show in the following example that the openness of H j is not necessary.

Example 2 Consider the system defined as

ẋ1 = x 2 , ẋ2 = x 3 3 x 1 , ẋ3 = 1 + u , y = x 1 (7) On S = x ∈ R 3 : x 2 1 + x 2 2 = 0
, and whatever u is, the knowledge of the function t → y(t) = X 1 (x, t) and therefore of its three first derivatives

ẏ = x 2 , ÿ = x 3 3 x 1 , ... y = 3x 2 3 x 1 (1 + u) + x 3 3
x 2 gives us x 1 , x 2 and x 3 . Thus, the system is uniformly observable on S. Besides, the function

H 4 (x) = x 1 , x 2 , x 3 3 x 1 , 3x 2 3 x 1 + x 3 3
x 2 is injective on S and the system is weakly differentially observable of order 4 on S. Now, although H 2 is trivially an open map on S, H 3 is not. Indeed, consider for instance the open ball B in R 3 with radius 1 2 and centered at (0, x 2 , 0) for some x 2 such that |x 2 | > 1 2 . B is contained in S. Suppose its image by H 3 is an open set of R 3 . It contains H 3 (0, x 2 , 0) = (0, x 2 , 0) and thus (ε, x 2 , ε) for any sufficiently small ε. This means that there exist x in B such that (ε, x 2 , ε) = H 3 (x), i-e necessarily x 1 = ε and x 3 = 1. But this point is not in B, and we have a contradiction. Therefore, H 3 is not open. However, B(3) trivially holds because H 2 is full-rank everywhere. PROOF. In each case, the function ϕ dz is obtained from Proposition 2. Functions g i for i ≤ T are obtained from Proposition 3. Finally, it is possible to construct the functions g i , for i > T, in the same way as ϕ dz in Proposition 2.

Three remarks :

-As seen in Example 2, the openness of the functions H j is sufficient but not necessary. We may ask only for B(j) for any j in {2, . . . , i} with i ≤ d x + 1. Besides, this weaker assumption allows to obtain the existence of g i up to the order d x + 1.

-Consider the case where B(j) is satisfied for all j ≤ d x + 1 and O = d x + 2. Then we have T = d x + 1 and it is possible to obtain a full triangular form of dimension -If P is solved with d z = T + 1, we have a full triangular canonical form of dimension d z . But, at this point we know nothing about the regularity of the functions g i , besides continuity. As we saw in Example 1, even the usual assumption of strong differential observability is not sufficient to make it Lipschitz everywhere. This may impede (see for instance [START_REF] Ciccarella | A luenbergerlike observer for nonlinear systems[END_REF]) the convergence of the high gain observer proposed in [START_REF] Gauthier | A simple observer for nonlinear systems application to bioreactors[END_REF]. That is why, in the next section, we look for conditions under which the Lipschitzness is ensured. -As mentioned in the introduction, another way of solving Problem P is to allow the transformation Ψ to depend on the control u and its derivatives. In particular, if d z > T + 1, a full triangular form may still be obtained with Ψ = (H T , Ψ) where the components Ψi of Ψ are defined recursively as

d z = T + 1 = O = d x + 2.
Ψ1 = L T f h , Ψi+1 = L f +gu Ψi + i-2 j=0 ∂ Ψi ∂u (j) u (j+1)
until (if possible) the map x → Ψ(x, u, u, ...) becomes injective for all (u, u, ...).

Example 3 Coming back to Example 2, we have seen that H 2 is open and that H 3 is not but B(3) is satisfied. Besides, the system is weakly differentially observable of order 4. We deduce that there exists a full-triangular form of order 4. Indeed, we have

L g h(x) = L g L f h(x) = 0 and L g L 2 f h(x) = 3x 2 3 x 1 = 3(L 2 f h(x)) 2 3 (h(x))
1 3 so that we can take

g 1 = g 2 = 0 , g 3 (z 1 , z 2 , z 3 ) = 3z 2 3 3 z 1 3
1 . As for ϕ 4 and g 4 , they are obtained via inversion of H 4 i-e for instance on R 4 \ {(0, 0, z 3 ), z 3 ∈ R}

H -1 4 (z) =   z 1 , z 2 , (z 4 -3z 2 3 3 z 1 3 1 ) 2 + z 2 3 z 2 1 + z 2 2 1 6   .
3 Lipschitzness of the triangular form

A sufficient condition

We saw with Examples 1 and 2 that uniform observability is not sufficient for the functions g i to be Lipschitz. Nevertheless, we are going to see in this section that it is sufficient except maybe around the image of points where ∂H i ∂x is not full-rank (x 1 = 0 or x 3 = 0 in Example 2).

Consider the set R i of points in S where ∂H i ∂x has full rank. Note that according to (Leborgne, 1982, Corollaire p68-69), if

H i is an open map, R i is an open dense set.
Assume R dx ∩ C is non empty. Then there exists ε 0 > 0 such that, for all ε in (0, ε 0 ], the set

K i,ε = x ∈ R i ∩ C , d(x , R dx \R i ) ≥ ε .
is non-empty and compact, and such that its points are (ε)-away from singular points. The next proposition shows that the functions g i can be taken Lipschitz on the image of K i,ε , i-e everywhere except arbitrary close to the image of points where the rank of the Jacobian of H i drops. [START_REF] Mcshane | Extension of range of functions[END_REF], there exists a Lipschitz extension of g i to R i coinciding with g i on H i (K i,ε ), and thus verifying (5) for all x in K i,ε .

i (R i ) such that for all x in R i , g i (H i (x)) = L g L i-1 f h(x). Now, K i,ε being a compact set contained in R i , and H i be- ing continuous, H i (K i,ε ) is a compact set contained in H i (R i ). Thus, g i is Lipschitz on H i (K i,ε ). According to
For a strongly differentially observable system of order O = d x on S, the Jacobian of H i for any i in {1, ..., d x } has full rank on S. Thus, taking

d z = T + 1 = O = d x
(x a , x b ) in C 2 , |x 2 3,a x 1,a -x 2 3,b x 1,b | ≤ L(|x 1,a -x 1,b | +|x 3 3,a x 1,a -x 3 3,b x 1,b |) 2 If x1,a and x 1,b are both zero, the inequality is trivial. Suppose |x1,a| > |x 1,b | and denote ρ = x 1,b x 1,a . If ρ < 0, we have directly |x 2 3,a -ρ x 2 3,b | ≤ max{x 2 3,a , x 2 3,b }|1 -ρ|. If now ρ > 0, x 2 3,a -ρ x 2 3,b = (x 3 3,a -ρ 3 2 x 3 3,b )(x 3,a + √ ρx 3,b ) x 2 3,a + √ ρx 3,a x 3,b +ρx 2 3,b
and thus

|x 2 3,a -ρ x 2 3,b | ≤ 2 √ 2 x 2 3,a +ρx 2 3,a |x 3 3,a -ρ 2 3 x 3 3,b |. Besides, |x 3 3,a - ρ
Therefore, the continuous function g 3 found earlier in Example 3 such that g 3 (H 3 (x)) = L g L 2 f (x) = 3x 2 3 x 1 on S (and thus on C) verifies in fact

|g 3 (z a ) -g 3 (z b )| ≤ L|z a -z b |
on H 3 (C) and can be extended to a Lipschitz function on R 3 according to [START_REF] Mcshane | Extension of range of functions[END_REF], Theorem 1). We conclude that although H 3 does not have a full-rank Jacobian everywhere on C (singularities at x 1 = 0), it is possible to find a Lipschitz function g 3 solution to our problem on this set.

A necessary condition

We have just seen that the condition in Proposition 4 that the Jacobian of H i be full-rank, is sufficient but not necessary. In order to have locally Lipschitz functions g i satisfying ( 5), there must exist for all x a strictly positive number L such that for all (x a , x b ) in a neighborhood of x,

|L g L i-1 f h(x a )-L g L i-1 f h(x b )| ≤ L |H i (x a )-H i (x b )| . (8)
We have the following necessary condition : Lemma 4 Consider x in S such that (8) is satisfied in a neighborhood of x. Then, for any non zero vector v in R dx , and any k in {1, . . . , d u }, we have :

∂H i ∂x (x) v = 0 ⇒ ∂L g k L i-1 f h ∂x (x) v = 0 . (9)
PROOF. Assume there exists a non-zero vector v in

R dx such that ∂H i ∂x (x) v = 0 . Choose r > 0 such that
Inequality (8) holds on B r (x), the ball centered at x and of radius r. Consider for any integer p the vector x p in B r (x) defined by x p = x -1 p r |v| v. This gives a sequence converging to x when p tends to infinity. We have

0 ≤ |L g k L i-1 f h(x p ) -L g k L i-1 f h(x)| |x -x p | ≤ L |H i (x p ) -H i (x)| |x -x p | (10)
The sequence

x-xp |x-xp| tends to v, and thus,

Hi(xp)-Hi(x) |x-xp| tends to ∂Hi ∂x (x) v which by assumption is 0 . Sim- ilarly 1 |x-xp| (L g k L i-1 f h(x) -L g k L i-1 f h(x p )) tends to ∂L g k L i-1 f h ∂x (x) v
which is also 0 according to (10).

We conclude that when H i does not have a full-rank Jacobian, it must satisfy condition (9) to allow the existence of locally Lipschitz triangular functions g i . This condition is in fact about uniform infinitesimal observability.

Definition 3 (Uniform infinitesimal observability) (See (Gauthier and Kupka, 2001, Definition I.2.1.3).) Consider the system lifted to the tangent bundle (see [START_REF] Gauthier | Deterministic observation theory and applications[END_REF], page 10))

ẋ = f (x) + g(x)u v = ∂f ∂x (x) + ∂gu ∂x (x) v , y = h(x) w = ∂h ∂x (x)v (11)
with v in R dx and w in R and the solutions of which are denoted (X u (x, t), V u ((x, v), t)). System ( 1) is uniformly infinitesimally observable on S if, for any pair (x, v) in S × R dx \ {0}, any strictly positive number T , and any C 1 function u defined on an interval [0, T ), there exists a time t < T such that ∂h ∂x (X u (x, t)) V u ((x, v), t) = 0 and such that X u (x, s) ∈ S for all s ≤ t.

We have the following result.

Proposition 5 Suppose that System (1) is strongly differentially observable of order O (or at least that H O is an immersion on S) and that Inequality (8) is verified at least locally around any point x in S for any i in {1, . . . , O}. Then the system is uniformly infinitesimally observable on S.

PROOF. According to Lemma 4, we have (9) for all x in S and all non-zero v. Now take x in S and a nonzero vector v and suppose that there exists T > 0 such that for all t in [0, T ), X u (x, t) is in S and w(t) = ∂h ∂x (X u (x, t))V u ((x, v), t) = 0. To simplify the notations, we denote X(t) = X u (x, t) and V (t) = V u ((x, v), t). For all integer i, we denote

w i (t) = ∂L i-1 f h ∂x (X(t))V (t) .
We note that for any function h : R n → R, we have

˙ ∂h ∂x (X(t))V (t) = ∂L f h ∂x (X(t))V (t) + du k=1 u k ∂L g k h ∂x (X(t))V (t) .
We deduce for all integer i and all t in [0, T )

ẇi (t) = w i+1 (t) + du k=1 u k ∂L g k L i-1 f h ∂x (X(t))V (t) .
Let us show by induction that w i (t) = 0 for all integer i and all t in [0, T ). It is true for i = 1 by assumption. Now, take an integer i > 1, and suppose w j (t) = 0 for all t in [0, T ) and all j ≤ i, i-e ∂Hi ∂x (X u (x, t))V u ((x, v), t) = 0 for all t. In particular, ẇi (t) = 0 for all t. Besides, according to (9), ((x, v), t) = 0 for all k in {1, . . . , d u } and for all t. Thus, w i+1 (t) = 0 for all t. We conclude that w i is zero on [0, T [ for all i and in particular at time 0, ∂H O ∂x (x)v = (w 1 (0), . . . , w O (0)) = 0. But H O is an immersion on S, thus, necessarily v = 0 and we have a contradiction.

∂Lg k L i-1 f h ∂x (X u (x, t))V u
Example 5 We go on with Example 2. The linearization of the dynamics (7) yields

v1 = v 2 , v2 = x 3 3 v 1 + 3x 2 3 x 1 v 3 , v3 = 0 , w = v 1 (12) Consider x 0 = (x 1 , x 2 ,
0) in S and v 0 = (0, 0, v 3 ) with v 3 a nonzero real number. The solution to (7)-( 12) initialized at (x 0 , v 0 ) and with a constant input u = -1 is such that X(x 0 , t) remains in S in [0, T ) for some strictly positive T and w(t) = 0 for all t in [0, T ). Since v 0 is nonzero, System (7) is not uniformly infinitesimally observable on S. But, for System (7), H 7 is an immersion on S. We deduce from Proposition 5 that Inequality (8) is not satisfied for all i, i-e there does not exist Lipschitz triangular functions g i for all i on S. This is consistent with the conclusion of Example 4. However, on S, i-e when we remove the points where x 3 = 0, the system becomes uniformly infinitesimally observable. Indeed, it can be checked that for x in S, w = ẇ = ẅ = w (3) = 0, implies necessarily v = 0. Unfortunately, from our results, we cannot infer from this that the functions g i can be taken Lipschitz on S. Nevertheless, the conclusion of Example 4 is that g 3 can be taken Lipschitz even around points with x 1 = 0. All this suggests a possible tighter link between uniform infinitesimal observability and Lipschitzness of the triangular form.

We conclude from this section that uniform infinitesimal observability is required to have the Lipschitzness of the functions g i when they exist. However, we don't know if it is sufficient yet.

Conclusion

Like for strongly differentially observable systems of order d x (the system state dimension), uniform observability of weakly differentially observable systems of order O > d x , may still imply the existence of an at least upto-d x + 1-triangular canonical form of dimension O (see ( 3)). But -we have shown this under the additional assumption that the functions

H i (x) = (h(x), L f h(x), ..., L i-1 f h(x)
) are open maps. Actually it is sufficient that the properties B(2), . . . , B(d x + 1) hold (see ( 6)).

-the functions in the triangular form are possibly non

Lipschitz, but only close to points where the rank of the Jacobian of H i changes. Anyhow, uniform infinitesimal observability is necessary to have Lipschitz functions. -for a non Lipschitz triangular canonical form, convergence of the regular high gain observer may be lost, but, under certain regularity assumptions, it is still possible to design asymptotic observers (see [START_REF] Bernard | Observers for a nonlipschitz triangular form[END_REF]).

Although our result only gives a partial triangular form, we have no counter example showing that it cannot be a full triangular form.

A Proof of Lemma 2

Assume the system is uniformly observable on S. We first show that property A(1) holds. Suppose there exists (x * a , x * b ) in S 2 and k in {1, ..., d u } such that x * a = x * b and

h(x * a ) = h(x * b ) , L g k h(x * a ) = L g k h(x * b ) .
Then, the control law u with all its components zero except its kth one which is

u k = - L f h(x a ) -L f h(x b ) L g k h(x a ) -L g k h(x b ) .
is defined on a neighborhood of (x * a , x * b ). The corresponding solutions X u (x * a , t) and X u (x * b , t) are defined on some time interval [0, T ) and satisfy

h(X u (x * a , t)) = h(X u (x * b , t)) ∀t ∈ [0, T ) .
Since x * a is different from x * b , this contradicts the uniform observability. Thus A(1) holds.

Let now i in {2, . . . , d x + 1} be such that Property B(i) holds and A(j) is satisfied for all j in {1, . . . , i-1}. To establish by contradiction that A(i) holds, we assume this is not the case. This means that there exists (x * a,0 , x * b,0 ) in S 2 and k in {1, ..., d u } such that

H i (x * a,0 ) = H i (x * b,0 ) but L g k L i-1 f (x * a,0 ) = L g k L i-1 f (x * b,0
). This implies x * a,0 = x * b,0 . By continuity of L g k L i-1 f and according to B(i), there exists x * a (resp x * b ) in S sufficiently close to x * a,0

(resp x * b,0 ) satisfying x * a = x * b , H i (x * a ) = H i (x * b ) , L g k L i-1 f (x * a ) = L g k L i-1 f (x * b ) ,
and ∂Hi-1 ∂x is full-rank at x * a or x * b . Without loss of generality, we suppose it is full-rank at x * a . Thus, ∂Hj ∂x is fullrank at x * a for all j < i. We deduce that there exists an open neighborhood V a of x * a such that for all j < i, ∂Hj ∂x is full-rank on V a . Since A(j) holds for all j < i, according to Lemma 8, H j (V a ) is open for all j < i and there exist locally Lipschitz functions g j : H j (V a ) → R du such that, for all x α in V a ,

g j (H j (x α )) = L g L j-1 f h(x α ) . (1) Also, H j (x * a ) = H j (x * b ) implies that H j (x * b ) is in the open set H j (V a ). Continuity of each H j implies the exis- tence of an open neighborhood V b of x * b such that H j (V b ) is contained in H j (V a ) for all j < i. Thus, for any x β in V b , H j (x β ) is in H j (V a ), and there exists x α in V a such that H j (x α ) = H j (x β ). According to A(j) this implies that L g L j-1 f h(x β ) = L g L j-1 f h(x α ) and with (A.1), L g L j-1 f h(x β ) = L g L j-1 f h(x α ) = g j (H j (x α )) = g j (H j (x β )
) . Therefore, (A.1) holds on V a and V b .

Then, the control law u with all its components zero except its kth one which is

u k = - L i f h(x a ) -L i f h(x b ) L g k L i-1 f h(x a ) -L g k L i-1 f h(x b ) is defined on a neighborhood of (x * a , x * b )
. The corresponding solutions X u (x * a , t) and X u (x * b , t) are defined on some time interval [0, T ) where they remain in V a and V b respectively. Let Z a

(t) = H i (X u (x * a , t)), Z b (t) = H i (X u (x * b , t)) and W (t) = Z a (t)-Z b (t) on [0, T ).
Since, for all j < i, (A.1) holds on V a and V b , (W, Z a ) is solution to the system : ẇ1 =w 2 + (g 1 (z a,1 )g 1 (z a,1w 1 )) u . . . ẇj =w j+1 +(g j (z a,1 , ..., z a,j )g j (z a,1w 1 , ..., z a,jw j )) u . . . ẇi =0 ża,1 =z 2 + g 1 (z a,1 ) u . . . ża,j =z j+1 + g j (z a,1 , ..., z a,j ) u . . . ża,i =ũ with initial condition (0, H i (x * a )), where ũ is the time derivative of Z a,i (t). Note that the function (0, Z a ) is also a solution to this system with the same initial condition. Since the functions involved in this system are locally Lipschitz, it admits a unique solution. Hence, for all t in [0, T [, W (t) = 0, and thus Z a (t) = Z b (t), which implies h(X(x * a , t)) = h(X(x * b , t)). Since x * a is different from x * b , this contradicts the uniform observability. Thus A(i) holds.

B Technical lemmas

In this appendix, we consider two continuous functions Φ : R n → R r and γ : R n → R q and a subset S of R n such that Φ(x) = Φ(y) ∀(x, y) ∈ S 2 : γ(x) = γ(y) . This means that φ is uniformly continuous on the compact set γ(C). Thus, φ is also bounded on γ(C). We deduce from [START_REF] Mcshane | Extension of range of functions[END_REF], Corollary 2) (applied to each component of φ) that φ admits a uniformly continuous (and bounded) extension defined on R q .

Lemma 8 Assume that q ≤ n and consider an open subset V of S such that ∂γ ∂x is full-rank on V , namely γ is a submersion on V . Then, γ(V ) is open and there exists a C 1 function φ defined on γ(V ) such that Φ(x) = φ(γ(x)) ∀x ∈ V .

PROOF.

γ is an open map according to (Lee, 2013, Proposition 4.28), thus γ(V ) is open. Consider the function φ given by Lemma 5 and take any z * in γ(V ). There exists x * in V such that z * = γ(x * ). γ being full-rank at x * , according to the constant rank theorem, there exists an open neighborhood V * of x * and C 1 diffeomorphisms ψ 1 : R n → V * and ψ 2 : R q → γ(V * ) such that for all x in R n : γ(ψ 1 (x)) = ψ 2 (x 1 , . . . , xq ) . It follows that for all z in γ(V * ) γ(ψ 1 (ψ -1 2 (z), 0)) = z namely γ admits a C 1 right-inverse γ ri defined on γ(V * )

which is an open neighborhood of z * . Therefore, φ = Φ • γ ri and φ is C 1 at z * .

  the set of points of S such that ∂Hj ∂x is not full-rank. According to Sard's theorem, H j (Π) is of measure zero in R j . Now, take p > 0 and consider B p (x a ) and B p (x b ) the open balls of radius 1 p centered at x a and x b respectively. Since H j is open, H j (B p (x a )) and H j (B p (x b )) are open sets, both containing y 0 . Thus, H j (B p (x a )) ∩ H j (B p (x b )) is a non-empty open set. It follows that (H j (B p (x a )) ∩ H j (B p (x b ))

  2.3 A solution to Problem P With Propositions 2 and 3, we have the following solution to Problem P. Theorem 1 Suppose System (1) is weakly differentially observable of order O and uniformly observable on an open set S containing the given compact set C. With selecting Ψ = H O and d z = O, we have a solution to Problem P if we pick either T = 1, or T = i when H j is an open map for any j in {2, . . . , i} with i ≤ d x .

  a full Lipschitz triangular form of dimension d x exists, i.e. we recover the result of Proposition 1. Example 4 In Example 2, H 3 is full rank on S \ {x ∈ R 3 | x 1 = 0 or x 3 = 0}. Thus, according to Proposition 4, the only points where g 3 may not be Lipschitz, are the image of points where x 1 = 0 or x 3 = 0. Let us study more precisely what happens around those points. Take x a = (x 1,a , x 2,a , 0) in S. If there existed a locally Lipschitz function g 3 verifying (5) around x a , there would exist L > 0 such that for any x b = (x 1,b , x 2,a , x 3,b ) sufficiently close to x a with x 1,b = 0, |3x 2 3,b | ≤ L|x 3 3,b |, which we know is impossible. Therefore, there does not exist a function g 3 which is Lipschitz around the image of points where x 3 = 0. Let us now study what happens elsewhere, namely on S = S \ {x ∈ R 3 |x 3 = 0}. It turns out that on any compact set C of S, there exists 2 L such that we have for all

  There exists a function φ defined on γ(S) such that Φ(x) = φ(γ(x)) ∀x ∈ S . (B.2) PROOF. Define the map φ on γ(S) as φ(z) = x∈S γ(x)=z {Φ(x)} . For any z in γ(S), the set φ(z) is non-empty and singlevalued because according to (B.1), if z = γ(x a ) = γ(x b ), then Φ(x a ) = Φ(x b ). Therefore, we can consider φ as a function defined on γ(S) and it verifies (B.2).Lemma 6 Consider any compact subset C of S. There exists a class K function ρ such that for all(x a , x b ) in C 2 |Φ(x a ) -Φ(x b )| ≤ ρ (|γ(x a )γ(x b )|) . (B.3) PROOF. We denote D(x a , x b ) = |γ(x a )γ(x b )|. Let ρ 0 (s) = max (x a , x b ) ∈ C 2 D(x a , x b ) ≤ s |Φ(x a ) -Φ(x b )|This defines properly a non decreasing function with non negative values which satisfies :|Φ(x a ) -Φ(x b )| ≤ ρ 0 (D(x a , x b )) ∀(x a , x b ) ∈ C 2 .Also ρ 0 (0) = 0. Indeed if not there would exist (x a , x b ) in C 2 satisfying :D(x a , x b ) = 0 , |Φ(x a ) -Φ(x b )| > 0 .But this contradicts Equation (B.1). Moreover, it can be shown that this function is also continuous at s = 0. Indeed, let (s k ) k∈N be a sequence converging to 0. For each k, there exist(x a,k , x b,k ) in C 2 which satisfies D(x a,k , x b,k ) ≤ s k and ρ 0 (s k ) = |Φ(x a,k ) -Φ(x b,k )|.The sequence (x a,k , x b,k ) k∈N being in a compact set, it admits an accumulation point (x * a , x * b ) which, because of the continuity of D must satisfy D(x * a , x * b ) = 0 and therefore with (B.1) also Φ(x * a ) -Φ(x * b ) = 0 . It follows that ρ 0 (s k ) tends to 0 and ρ 0 is continuous at 0. Now, the function, defined by the Riemann integral ρstrictly increasing and we have :|Φ(x a ) -Φ(x b )| ≤ ρ(D(x a , x b )) ∀(x a , x b ) ∈ C 2 .Lemma 7 Consider any compact subset C of S. There exists a continuous function φ defined on R q such that Φ(x) = φ(γ(x)) ∀x ∈ C . PROOF. Consider φ and ρ given by Lemmas 5 and 6 respectively. For any (z a , z b ) in γ(C) 2 , there exists (x a , x b ) in C 2 such that z a = γ(x a ) and z b = γ(x b ). Applying (B.3) to (x a , x b ) and using (B.2), we have |φ(z a )φ(z b )| ≤ ρ(|z az b |) .

  Actually, we still have a full triangular form if we choose d z > O. Indeed, H O being injective, A(i) is satisfied for all i larger than O, thus there also exist continuous functions g i : R i → R du satisfying (5) for all i ≥ O. It follows that T can be taken larger than d x + 1 and d z = T + 1 larger than O.

  Proposition 4 Assume System (1) is uniformly observable on an open set S containing the compact set C. For all i in {1, ..., d x } and for any ε in (0, ε 0 ], there exists a Lipschitz function g i : R i → R du satisfying (5) for all x in K i,ε . holds on R i (i-e with R i replacing S in its statement). It follows from Lemma 2 that A(i) is satisfied on R i . Besides, according to Lemma 8, H i (R i ) is open and there exists a C 1 function g i defined on H

	PROOF. As noticed after the statement of Property
	B(i), since erty B(i)	∂H i ∂x	has full rank in the open set R i , Prop-

This notion is weaker than the usual differential observability defined for instance in(Gauthier and Kupka

, 2001, Definition I.2.4.2) for controlled systems, because it is a differential observability of the drift system only, namely when u ≡ 0.

x

3,b | = |x 3 3,aρx 3 3,b + ρ(1 -√ ρ) x 3 3,b | ≤ |x 3 3,aρx 3 3,b | + ρ|x 3 3,b | 1+ √ ρ |1 -ρ| which gives L on compact sets.