Claire Gardent
email: claire.gardent@loria.fr

Eric Kow
email: eric.kow@loria.fr

Spotting Overgeneration Suspects

We present a method for quickly spotting overgeneration suspects (i.e., likely cause of overgeneration) in hand-coded grammars. The method is applied to a medium size Tree Adjoining Grammar (TAG) for French and is shown to help reduce the number of outputs by 70% almost all of it being overgeneration.

Introduction

A generative grammar should describe all and only the sentences of the language it describes. In practice however, most grammars both under-and overgenerate. They under-generate in that they fail to describe all the language sentences and they overgenerate in that they licence as grammatical, strings that are not.

In a computational setting, this theoretical shortcoming means that processing will yield either too many or too few sentence analyses. Undergeneration results in insufficient coverage (some sentences cannot be parsed). Conversely, overgeneration leads to an explosion of generated strings.

Here we focus on overgeneration. There are several reasons why grammars overgenerate.

First, as is now well-known, grammar engineering is a highly complex task. It is in particular, easy to omit or mistype a constraint thereby allowing for an illicit combination and indirectly, an illicit string.

Second, a computational grammar is a large object and predicting all the interactions described by even a medium size grammar is difficult, if not impossible. Indeed this is why a surface realiser that produces all the strings associated with a given semantics is a valuable tool: it permits checking these predictions on concrete cases.

Third, grammars are often compiled from more abstract specifications and this additional layer of abstraction introduces the risk of licensing an illicit elementary structure. This is the case in particular in our approach where the TAG used by the realiser is compiled from a so-called "metagrammar" (cf. section 2). As we shall see in section 4, this added level of abstraction means that elementary trees are present in the grammar that shouldn't. These trees may also induce overgeneration.

In this paper, we propose a method for reducing overgeneration in a computational grammar. We apply the proposed approach to a Tree Adjoining Grammar for French (SEMFRAG) and show that it results in a 70% decrease of the generation output on a graduated test suite of 140 input semantics.

The paper is structured as follows. We start (section 2) by presenting the computational framework in which our experiment is based namely SEM-FRAG, a tree adjoining grammar for French and GENI, a surface realiser. In section 3, we then go on to describe the methodology we propose to identify and eradicate sources of overgeneration. Section 4 presents the results of the evaluation. Section 5 concludes with pointers for further research.

The computational framework

We now briefly describes the GENI surface realiser and the SEMFRAG TAG on which we tested our debugging method.

SemFraG, a TAG for French integrating semantic information

SEMFRAG is a Feature-based lexicalised TAG (FTAG, (VSJ88)) for French extended with semantic information as described in (GK03).

A Feature-based TAG (FTAG, (VSJ88)) consists of a set of (auxiliary or initial) elementary trees and of two tree composition operations: substitution and adjunction. Initial trees are trees whose leaves are labelled with substitution nodes (marked with a downarrow) or terminal categories. Auxiliary trees are distinguished by a foot node (marked with a star) whose category must be the same as that of the root node. Substitution inserts a tree onto a substitution node of some other tree while adjunction inserts an auxiliary tree into a tree. In an FTAG, the tree nodes are furthermore decorated with two feature structures (called top and bottom) which are unified during derivation as follows. On substitution, the top of the substitution node is unified with the top of the root node of the tree being substituted in. On adjunction, the top of the root of the auxiliary tree is unified with the top of the node where adjunction takes place; and the bottom features of the foot node are unified with the bottom features of this node. At the end of a derivation, the top and bottom of all nodes in the derived tree are unified.

To associate semantic representations with natural language expressions, the FTAG is modified as proposed in (GK03). ⇒ name(j,john), run(r,j), often(r)

Figure 1: Flat semantics for "John often runs" Each elementary tree is associated with a flat semantic representation1 . For instance, in Figure 1, the trees2 for John, runs and often are associated with the semantics name(j,john), run(r,s) and often(x) respectively.

The arguments of a semantic functor are represented by unification variables which occur both in the semantic representation of this functor and on some nodes of the associated syntactic tree. In the same example, the semantic index s occurring in the semantic representation of runs also occurs on the subject substitution node of the associated elementary tree.

The value of semantic arguments is determined by the unifications resulting from adjunction and substitution. For instance, the semantic index s in the tree for runs is unified during substitution with the semantic indices labelling the root nodes of the tree for John. As a result, the semantics of John often runs is (1) {name(j,john),run(r,j),often(r)}

The grammar used describes a core fragment for French and contains around 6 000 elementary trees. It covers some 35 basic subcategorisation frames and for each of these frames, the set of argument redistributions (active, passive, middle, neuter, reflexivisation, impersonal, passive impersonal) and of argument realisations (cliticisation, extraction, omission, permutations, etc.) possible for this frame. As a result, it captures most grammatical paraphrases that is, paraphrases due to diverging argument realisations or to different meaning preserving alternation (e.g., active/passive or clefted/non clefted sentence).

SemFraG and XMG

SEMFRAG is compiled from a higher-level XMG (eXtensible MetaGrammar) specification (CD04). Briefly, the XMG formalism permits specifying basic classes and then combining them (by inheritance, conjunction and disjunction) to produce SEMFRAG elementary trees and their associated semantics (cf. (CD04; Gar06)). For instance, the tree for an active intransitive verb taking a nominal canonical subject will result from specifying and then conjoining classes for the canonical nominal subject, the active verb form and the unary relation.

Importantly, the compilation process keeps track of which classes are used to produce each elementary tree. As a result, each SEMFRAG elementary tree is associated with the set of classes used to produce that tree. For instance, in SEMFRAG, the tree for the active form of intransitive verbs taking a nominal canonical subject will be associated by the XMG compiler with the following set of properties: CanonicalSubject, n0Vn1, ActiveForm, UnaryRel, NonInvertedNominalSubject More generally, the set of classes associated by the XMG compilation process with each elementary tree (we will call this the tree properties) provides clear linguistic information about these trees. As we shall see in section 3, this information is extremely useful when seeking to identify overgeneration suspects i.e., elementary trees which are likely to cause overgeneration.

The GenI surface realiser

The basic surface realisation algorithm 3 used is a bottom up, tabular realisation algorithm (Kay96) optimised for TAGs. It follows a three step strategy which can be summarised as follows. Given an empty agenda, an empty chart and an input semantics φ:

Lexical selection. Select all elementary trees whose semantics subsumes (part of) φ. Store these trees in the agenda. Auxiliary trees devoid of substitution nodes are stored in a separate agenda called the auxiliary agenda.

Substitution phase. Retrieve a tree from the agenda, add it to the chart and try to combine it by substitution with trees present in the chart. Add any resulting derived tree to the agenda. Stop when the agenda is empty.

Adjunction phase. Move the chart trees to the agenda and the auxiliary agenda trees to the chart. Retrieve a tree from the agenda, add it to the chart and try to combine it by adjunction with trees present in the chart. Add any resulting derived tree to the agenda. Stop when the agenda is empty.

When processing stops, the yield of any syntactically complete tree whose semantics is φ yields an output i.e., a sentence.

The workings of this algorithm can be illustrated by the following example. Suppose that the input semantics is (1). In a first step (lexical selection), the elementary trees selected are the ones for John, runs, often. Their semantics subsumes part of the input semantics. The trees for John and runs are placed on the agenda, the one for often is placed on the auxiliary agenda.

The second step (the substitution phase) consists in systematically exploring the possibility of combining two trees by substitution. Here, the tree for John is substituted into the one for runs, and the resulting derived tree for John runs is placed on the 3 See (GK05) for more details.

agenda. Trees on the agenda are processed one by one in this fashion. When the agenda is empty, indicating that all combinations have been tried, we prepare for the next phase.

All items containing an empty substitution node are erased from the chart (here, the tree anchored by runs). The agenda is then reinitialised to the content of the chart and the chart to the content of the auxiliary agenda (here often). The adjunction phase proceeds much like the previous phase, except that now all possible adjunctions are performed. When the agenda is empty once more, the items in the chart whose semantics matches the input semantics are selected, and their strings printed out, yielding in this case the sentence John often runs.

Reducing overgeneration

We now present the methodology we developed for identifying and eradicating sources of overgeneration. In essence, the idea is to first, manually annotate the realiser output as either PASS or OVERGEN-ERATION and to then use the annotated data to: automatically spot the items ((sets of) TAG elementary trees, pairs of combined trees) which systematically occur only in overgeneration cases.

More specifically, the procedure we defined to reduce overgeneration can be sketched as follows (cf. also Figure 2).

1. Surface realisation is applied to a graduated test suite of input semantics thus producing a (detailed) derivation log of all the derivations associated with each input in the testsuite 2. The outputs given by the derivation log are (manually) classified into PASS or OVERGEN-ERATION sentences, the overgeneration mark indicating strings that either do not actually belong in the target language, or should not be associated to the input semantics.

3. The annotated output is used to automatically produced a suspects report which identifies a list of suspects i.e., a list of TAG trees or derivation steps which are likely to cause the overgeneration because they only occur in overgeneration cases.

4. The grammar is debugged and re-executed on the data 5. The derivations results are compared with the previous ones and any discrepancy (less or more sentences generated) signalled.

In a sense, this is an approach that might already be widespread in generation: produce some output, and correct the grammar possibly with the aid of a derivation log. Our contributions are a systematic, incremental approach; a high level of automation, which increases our throughput by focusing human attention on correcting the grammar rather than the unrelated details; and research into summarisation of the operations log so that we can more easily identify the source of error.

An incremental approach

First experiments with SEMFRAG showed that the grammar strongly overgenerates both because it was initially developed for parsing and because it is automatically compiled from an abstract specification (cf. section 1). Indeed for some inputs, the realiser produced over 4000 paraphrases, a large portion of them being overgeneration. More generally, Figure 3 shows that the number of outputs for a given input varies between 0 and 4908 with an average of 201 outputs per input (the median being 25).

To avoid having to manually annotate large amounts of data, we relied on a graduated test suite and proceeded through the data from simplest to more complex. Concretely, this means that we first eliminated overgeneration in input corresponding to sentences with one finite verb (INPUT1) before moving on to inputs corresponding to sentences with two (INPUT2) and three (INPUT3) finite verbs. This means that as we moved from the simplest to the more complex data, overgeneration was incrementally reduced thereby diminishing the number of output to be annotated.

Indeed this worked very well as by simply looking at INPUT1 we achieved a 70% decrease in the number of outputs for the total testsuite (cf. section 4).

Semi-automated grammar debugging

The debugging procedure described above was implemented through a test harness interleaving manual annotations with machine-generated output. Three points are worth stressing. First, the suspects report is produced automatically from the annotated derivation log. That is, except for the derivation log manual annotation, the identification of the suspects information is fully automated. Second, regression testing is used to verify that corrections made to the grammar do not affect its coverage (all PASS remains PASS). Third, the harness provides a linguist friendly environment for visualising, modifying and running the grammar on the inputs being examined.

Listing the suspects

The derivation log produced by GENI contains detailed information about each of the derivations associated with a given input. More specifically, for each generated string, the derivation log will show the associated derivation tree together with the tree family, tree identifier and tree properties associated with each elementary tree composing that derivation tree. However, the derivation log can be both very long and very redundant. To extract from it information that points more directly to the likely causes of overgeneration, we first manually annotate each string as pass or overgeneration. We then automatically extract from the annotated derivation log, a much shorter "suspects report" which identifies suspects i.e., likely causes for overgeneration.

In essence, this suspects report lists trees, sets of trees or derivation items that only occur in overgeneration cases (i.e., strings that have manually been annotated as OVERGENERATION). Moreover, information about the suspects is displayed in a compact and informative way. Specifically, for a given generation input, the suspects report will consist of a (possibly empty) list of items of the following form 4 : 1. Lemma 2. TreeFamily ?(all) -?(∧ tree-property) 3. ?( TreeId * ? (∧ tree-property))

?( TreeId

i :nodeId j Op ←-TreeId k )
That is, a suspect report item (SR-ITEM) indicates, for a given lemma (line 1), the tree family (line 2), the specific trees (line 3), the specific tree properties (lines 2 and 3) and/or the specific derivation items 5 (line 4) that consistently occur only in overgeneration cases.

The suspects report is compact in that it only outputs information about likely suspects i.e., trees, tree family, tree properties and/or derivation items which consistently occur only in overgeneration cases. Furthermore, it groups together overgeneration sources which share a common feature (same tree family, same tree family and same tree properties, same derivation items). As we shall see, displaying the commonalities between suspects makes it easier for the linguist to understand the likely cause of overgeneration (for instance, if all the trees of a given family lead to overgeneration, then it is likely that the grammar is not sufficiently constrained to block the use of this family in the particular context considered).

It is informative in that it gives detailed information about the likely cause of overgeneration. In particular, tree properties can be extremely useful in understanding the commonalities between the trees involved and thereby the likely cause of overgeneration. 4 The * is the Kleene star, ? indicates optionality. To better illustrate the type of information contained in a suspects report, we now go through a few examples.

Example 1: "il faut partir/? devoir partir" Given the input semantics for e.g., il faut partir (we must go), the suspects report tells us that the presence in a derivation of any trees of the family SemiAux leads to overgeneration. consistent overgeneration for devoir TSemiAux (all) -SemiAux [506] Indeed, in this context (i.e., given the input semantics considered), the use of a SemiAux tree results in the production of such strings as devoir partir which are grammatical but do not yield a finite sentence as output. If desired, this particular overgeneration bug can be fixed by constraining the generator output to be a finite sentence.

Example 2: "Jean dit accepter/*C'est par Jean qui accepte qu'être dit". In the previous example, the SR-ITEM indicates that all trees of a given family lead to overgeneration but there is only one tree in that family. A more interesting case is when there are several such trees. For instance, the SR-ITEM below indicates that all derivations involving an n0Vn1 tree anchored with dire lead to overgeneration and that there are 6 such trees (trees 699 . . . 750). Moreover the tree properties information indicates that all these trees share the InfinitiveSubject Passive tree properties. Inspection of the data shows that these trees combine with a finite form of accepter to yield highly agrammatical strings such as c'est par Jean qui accepte qu'être dire (instead of e.g., Jean dit accepter. In short, the SR-ITEM indicates that the grammar is not sufficiently constrained to block the combination of the infinitive passive form of the n0Vn1 trees anchored with dire with some of the trees associated by the grammar with accepter. Example 3: "Jean doit partir/*C'est Jean il faut que qui part" Sometimes overgeneration will only occur with some of a family trees and in this case the third line of the SR-ITEM indicates which are those trees and which are their distinguishing properties (i.e. the properties that always result in overgeneration). For instance, the suspects report for the input semantics of Jean doit partir (Jean must leave), contains the following single SR-ITEM: Input t30 consistent overgeneration for partir This indicates that all derivations including tree 604 of the n0V family anchored with partir lead to overgeneration. Indeed such derivations license highly ungrammatical sentences such as C'est Jean il faut que qui part where a cleft subject tree for partir combines with the canonical tree for il faut. This overgeneration bug can be fixed by constraining n0V cleft subject trees to block such illicit combinations.

Example 4: "L'homme riche part/* riche l'homme part" Finally, overgeneration may sometimes be traced back to a specific derivation item i.e., to a specific tree combination. This will then be indicated in the last line of the trace item. For instance, the following SR-ITEM indicates that adjoining the adjective auxiliary tree Tn0vA-90 to the root of a determiner tree always lead to overgeneration. Indeed such an adjunction results in sentences where the adjective precedes the determiner which in French is agrammatical.

Before and after figures

We have used the test harness over a period of one week, roughly 12 consecutive man hours. Over that period we have run over ten iterations of the test harness, making 13 modifications to the grammar as a result. In the process of revising this grammar, we have studied 40 cases (under one third of the whole suite) and manually annotated 1389 outputs with pass/overgeneration judgements. On the whole 140 cases of the test suite, the original grammar produced 28 167 outputs (4908 for the worst case, 201 The revised grammar produces 70% fewer likely agramatical outputs, leaving behind 8434 sentences (201 worst case, 60 mean, 12 median). We believe that this reduction is especially noteworthy given the little time we have spent in this process.

It is very well to be cutting out overgeneration, but only so long as we are not cutting out linguistically valid sentences along the way. The test suite had been built semi-automatically, by parsing some sentences and hand-picking the valid semantic representations among the proposed outputs. As a basic sanity check, we reparsed the original sentences with the new grammar and found that 136 out of 140 sentences were parsed successfully, 4 less than with the original grammar. The difference was due to an over-restrictive constraint and was easily corrected.

Typing the suspects

As mentioned above, the overall 70% overgeneration reduction was achieved by a total of 13 modifications to the (meta)-grammar. Two points are worth stressing here.

First, the small number of modification is due to the fact that the metagrammar is a very compact description of the grammar where in particular, shared tree fragments are factored out and used in the production of several trees. As a result, one change to the metagrammar usually induces a change in not one but several (sometime hundred of) TAG trees. For instance, a modification stated in the fragment describing the verb spine of the active verb form will affect all trees in the grammar that realise an active verb form i.e., several hundreds of trees.

Second, the drastic reduction in overgeneration is made possible by a combination of 3 factors. First, the suspects report allows for a quick identification of the overgeneration sources. Second, the metagrammar architecture makes it possible to generalise. Suppose for instance, that a given SR-ITEM indicates that the grammar incorrectly allows the adjunction of a given type of auxiliary tree β to a subject cleft tree. It might be the case that in fact, the grammar should be modified to block the combination of β with all cleft trees (not just the subject ones). Then the metagrammar architecture makes it possible to state the required modification at the level of the cleft description so that in effect, all cleft trees will be modified. In this way, the identification of an overgeneration cause linked to a specific example can be generalised to a larger class of examples. Third, the input data was organised in a graduated testsuite where first simple (basic) sentences where considered then sentences of complexity 2 (cases whose canonical verbalisation involve two finite verbs), then sentences of complexity 3 (three finite verbs). By proceeding incrementally through the testsuite, we ensured that early modifications propagate to more complex cases.

Let us now look at the types of errors which, we found, induce overgeneration.

Missing constraints Unsurprisingly, the main source of overgeneration was the lack of sufficient constraints to block illicit tree combinations. For instance, the grammar overgenerated the string devoir c'est Jean qui part (instead of c'est Jean qui doit partir) because the tree for devoir was not sufficiently constrained to block adjunction on the VP node of cleft trees. In such cases, adding the relevant constraints (e.g., CEST = -on the foot node of the devoir-tree and CEST = + on the VP node of the cleft-tree for partir) eliminates the overgeneration.

Incomplete constraints and incorrect feature percolation

In some cases, we found that the constraint was only partially encoded by the grammar in that it was correctly stated in one of the combining trees but incorrectly or not at all in the other. Thus for instance, the adjective tree was correctly constrained to adjoin to DET = -N-trees but the corresponding DET = + constraint on the root node of determiner trees was missing. In other cases, the feature was present but incorrectly percolated. In both cases, the partial implementation of the constraint lead to a lack of unification clash and thereby to an overgenerating combination of trees.

Illicit elementary trees A third type of errors was linked to the fact that the grammar was produced semi-automatically from an abstract grammar description. In some cases, the linguist had failed to correctly foresee the implications of her description so that an elementary tree was produced by the compiler that was in fact incorrect. For instance, we had to introduce an additional constraint in the metagrammar to rule out the formation of trees describing a transitive verb with impersonal subject (in French, transitive verb cannot take an impersonal subject).

Incorrect semantics A more complex type of error to deal with concern cases where the semantics is insufficiently constrained thereby allowing for illicit combinations. For instance, in the imperative form, the grammar failed to constrain the first semantic argument to be YOU i.e., the hearer denotation. As a result, the input for sentences such as Jean demande si Paul part incorrectly generated strings such as demande à Jean si Paul part. In such cases thus, it is the semantics associated by the metagrammar with the elementary tree that needs to be modified.

Lexical exceptions

As is well known, grammatical generalisation often are subject to lexical exceptions. For instance, transitive verbs are generally assumed to passivise but verbs of measure such as to weigh are transitive and do not. As is usual in TAG, in GENI, such exceptions are stated in the lexicon thereby blocking the selection of certain trees (in this case, all the passive trees) for the lexical items creating the exception (here the measure type verbs). Relatedly, some of the overgeneration cases stem from insufficient lexical information.

Conclusion

Debugging grammars for overgeneration need not be slow and tedious. We have found that with a certain dose of automation -a test harness to mechanise the regression-testing parts of the process, and computer-generated summaries to identify trouble spots -we can obtain major reductions in overgeneration with little effort.

Whilst these initial results are encouraging, a more sophisticated approach should help to detect more errors more efficiently. One shortcoming of our current approach is that we focus mostly on unitary sources of overgeneration: a single lexical item, tree property or derivation operation that consistently occurs in overgenerated strings. However, grammar flaws essentially consist of unexpected interactions between (at least) two items, so it would seem that the most sensible place to look for mistakes would be where they interact. For example, instead of identifying single items that fail, we could look for pairs of items that consistently overgenerate when they co-occur. Note that this is not necessarily a subset of single-source failures. A given item X may consistently overgenerate in the presence of another item Y, but not with Z. If we were only looking for consistent single-source failures, we would ignore X altogether, whereas if we were looking for pairs, we would indeed detect (X,Y).

Another shortcoming of our approach is that it requires us to be disciplined in our pass/overgeneration annotations.

If we mismark a sentence as pass, the derivation summariser will neglect every tree property or derivation item that occurs in that sentence, as it is only looking for items that consistently overgenerate. Perhaps a more robust approach would be to instead return items that tend to occur with overgeneration. This would make it more tolerant to imperfect annotations.

Producing these annotations is time-consuming. It would be worthwhile to explore some automatic means of making pass/overgeneration judgements on a large number of sentences, for example, using an n-gram based language model, like one that would be employed by a speech recogniser. We could then take the best N% of the sentences as passes or establish a threshold of improbability, below which sentences will be considered as overgeneration. We could also use more sophisticated tools, a statistical parser or a symbolic one with a wide coverage grammar in an alternate formalism. Even a relatively liberal parser which itself overgenerates might be useful in that (i) it may overgenerate in different areas than our grammar (ii) anything that it marks as a failure would be highly suspicious indeed.

The annotations do not need to be produced by a full-fledged parser either. Indeed, for each sentence that it produces, the surface realiser outputs its parse tree. So another way to classify the generated strings might be through assessing not the quality of the strings themselves but of their parses. For example, we could determine if the elementary trees that were used to build a sentence are likely to occur together in the same sentence. This kind of information can be extracted from a systemic functional grammar for instance. SFGs are largely generationoriented grammars which encode as a network, the motivations behind each linguistic choice and the linguistic choices they allow for. If we associated each choice in the SFG network with a set of tree properties from our TAG grammar, we would essentially have an encoding of what tree properties go together. If the sentence contains a set of tree properties for which there is no equivalent system network traversal, it should be flagged as suspicious.

Our use of this test harness has so far been limited to the syntactic aspects of surface realisation. It could also be applied to other realiser tasks such as, for instance, morphological generation. It would also be interesting to see to what extent the method used here to spot overgeneration suspects could be adapted to other linguistic formalisms such as HPSG, LFG or CCG.

Finally, it would be interesting to investigate in how much overgeneration reduction helps reduce parsing ambiguity. Given a large scale symbolic grammar, parsing will often yield several hundreds of parses many of them are probably incorrect. We believe that reducing overgeneration should help reduce the number of output parses and thereby improve both parsing efficiency and the quality of the output parses.

GENI is free (GPL) software and can be downloaded at http://trac.loria.fr/˜geni.

Figure 2 :

 2 Figure 2: Test harness

  Output: jean se demande si c'est paul qui vient demander:n8 <-(s)-venir demander:n1 <-(s)-jean venir:n4 <-(s)

  5 A derivation item of the form TreeIdi:nodeIdjOp ←-TreeId k :nodeId l indicates that TreeId k has been added to the node nodeIdj of TreeIdi using the operation Op where Op is either adjunction or substitution.

Figure 3 :

 3 Figure 3: Distribution of generation outputs before and after debugging

The examples given actually show a simplified version of the flat semantics used y GENI where in particular, so-called labels are omitted. A full specification is given in (GK03).

C x /Cx abbreviate a node with category C and a top/bottom feature structure including the feature-value pair { index : x}.


Ngoc-Tu Trinh
email: trinh@lagep.univ-lyon1.fr

Vincent Andrieu
email: vincent.andrieu@gmail.com

Cheng-Zhong Xu
email: xu@lagep.univ-lyon1.fr

Keywords: Control of hyperbolic systems and conservation laws, infinite-dimensional multi-agent systems and networks, stability of distributed parameter systems, output regulation for distributed parameter systems, Lyapunov methods

The paper is concerned with the PI control regulation of a star-shaped network of systems governed by hyperbolic partial differential equations. The control input and measured output are on the boundary. First, each system of the network is linearized and diagonalized with Riemann invariants. Then, by using Lyapunov direct method, the PI controller is proposed for a single system. Finally, we extend the PI control design for the star-shaped network of n subsystems. The exponential stability and output regulation of closed-loop systems are all proven with the aid of a strict Lyapunov functional.

Boundary PI controllers for a star-shaped network of 2 × 2 systems governed by hyperbolic partial differential equations (long version) ∂ t H(x, t) + ∂ x (H(x, t)V (x, t)) = 0,

∂ t V (x, t) + ∂ x V 2 (x, t) 2 + gH(x, t) = 0 (1)
where H denotes the water depth, V the water velocity, and g the gravitational acceleration. Here x ∈ [0, L] and t ∈ [0, ∞) are space and time coordinates, and ∂ t , ∂ x stand for the time and space partial derivative respectively. System (1) can be linearized around a set point H = H e , and Q = Q e to obtain the following equations:

∂ t h v + V e H e g V e ∂ x h v = 0, (2)
where h = H -H e and v = V -V e . System (2) has been regarded as a 2 × 2 linear hyperbolic system. Up to now, the topic of controlling hyperbolic systems on the boundary has led to numerous studies in the literature, for example [START_REF] Coron | A strict lyapunov function for boundary control of hyperbolic systems of conservation laws[END_REF]; [START_REF] Greenberg | The effect of boundary damping for the quasilinear wave equation[END_REF]. Furthermore, some networks of hyperbolic systems were studied, for the cascaded networks in [START_REF] De Halleux | Boundary control in networks of open channels[END_REF]; [START_REF] Bastin | On Lyapunov stability of linearised Saint-Venant equations for a sloping channel[END_REF], and for the tree-shaped ones in [START_REF] Gugat | Stabilization of the Gas Flow in Star-Shaped Networks by Feedback Controls with Varying Delay[END_REF]; [START_REF] Leugering | On the modelling and stabilization of flows in networks of open canals[END_REF]. Most of them apply static control laws to stabilize the closed-loop systems. Following this, dynamic control laws were developed to make the closed-loop systems more robust confronted by constant perturbations, see for instance in [START_REF] Pham | Contribution to predictive control for systems of conservation laws[END_REF]; [START_REF] Perrollaz | Finite time stabilization of 2×2 hyperbolic systems on tree-shaped networks[END_REF]; [START_REF] Bastin | Stability of linear density-flow hyperbolic systems under PI boundary control[END_REF]; Trinh et al. (2017). However, little research has been carried out in this direction because of the complexity of systems controlled by dynamic control laws, especially for network cases. Our motivation is therefore to design a dynamic control law in the form of PI (proportional integral) controllers to stabilize the closedloop system and regulate output measurement to desired reference, and afterward extend the control design result for a star-shaped network of hyperbolic systems. The applying PI controller for hyperbolic systems has also been studied in the literature. Many results are based on the frequency domain approach combined with Laplace transformation or operator and semi-group theory, see in [START_REF] Bastin | Stability of linear density-flow hyperbolic systems under PI boundary control[END_REF]; [START_REF] Xu | Multivariable boundary PI control and regulation of a fluid flow system[END_REF]. In other works of Dos [START_REF] Santos | Boundary control with integral action for hyperbolic systems of conservation laws: stability and experiments[END_REF][START_REF] Trinh | Multivariable PI controller design for 2 × 2 systems governed by hyperbolic partial differential equations with Lyapunov techniques[END_REF], the Lyapunov direct method is employed to prove the stability of the closed-loop system in L 2 norm. In this paper, our contribution is making use of Lyapunov techniques to prove the exponential stability of the closed-loop system controlled by PI controllers in H 1 norm, and then obtain the regulation of the output. In addition, our approach is also extended for a star-shaped network of hyperbolic systems, and it is novel to the best of our knowledge.

This paper is the long version of the paper published in Trinh et al. (2017) in which some proofs have been removed due to space constraints.

The paper is organized as follows. Section II is devoted to present the characteristic form and PI controller structure used for the next sections. In Section 3, our PI controller design for a single system and the mathematical proof based on Lyapunov method are given. The main contribution is presented in Section 4, in which we analyze how to generalize the PI control design from the single system to the the star-shaped network. Finally, the conclusions are addressed in Section 5.

CHARACTERISTIC FORM AND PI CONTROLLER STRUCTURE

We consider the linearised system (2) with the output measurement y(t) which is chosen as the water level at x = 0, i.e, y(t) = h(0, t) + y r where y r = H e . By using the Riemann coordinates, the equations in (2) can be transformed to the characteristic form as follows:

∂ t φ 1 φ 2 + λ 1 0 0 -λ 2 ∂ x φ 1 φ 2 = 0 , y(t) -y r = aφ 1 (0, t) + bφ 2 (0, t) (3)
where

φ 1 = h + v H e g , φ 2 = h -v H e g (4)
and

λ 1 = V e + √ gH e , λ 2 = -V e + √ gH e , a = 1 2 , b = 1 2 .
Here, we consider only the subcritical water flow, i.e λ 1 > 0 and λ 2 > 0. We are concerned in the paper the system (3) under the initial conditions

φ 1 (x, 0) = φ 0 1 (x), φ 2 (x, 0) = φ 0 2 (x), ∀x ∈ [0, L],
(5) and suppose two following boundary conditions

φ 1 (0, t) = R 1 φ 2 (0, t) + u(t), φ 2 (L, t) = R 2 φ 1 (L, t) (6)
where u(t) is control input and R 1 , R 2 are real constant parameters, computed from the adaptive gate openings controlled on the boundary (see for example in Section 4). Our control target is to propose a dynamic feedback control law u(t) by the PI controller form such that the closed-loop system is asymptotically stable and the output y(t) is regulated to the desired reference y r . Precisely, we need to design the PI controller on the boundary with the real gain parameters K P and K I ,

u(t) = K P (y(t) -y r ) + K I t 0 (y(s) -y r )ds (7)
to guarantee the exponential stability of the closed-loop system (3)-( 7) and the output regulation.

The results of control design is presented in the following: in Section 3 for a single channel and in Section 4 for network of multichannels.

PI CONTROLLER DESIGN FOR A SINGLE CHANNEL

In this section, we consider a single channel with the linearised characteristic model analyzed in (3) with boundary conditions in (6) and the PI control feedback in (7). The direct Lyapunov method is used to prove the exponential stability and the output regulation of the closed-loop system controlled by PI controller.

Let denote the new state variable ξ(t) where ∂ t ξ = y(t)y r , the closed-loop system (3), (6), and ( 7) is governed by

                       ∂ t φ 1 φ 2 = -λ 1 0 0 λ 2 ∂ x φ 1 φ 2 ∂ t ξ = aφ 1 (0, t) + bφ 2 (0, t) φ 1 (0, t) = R 1 φ 2 (0, t) + K p (y(t) -y r ) + K I ξ φ 2 (L, t) = R 2 φ 1 (L, t) y(t) -y r = aφ 1 (0, t) + bφ 2 (0, t). (8)
with the following initial condition:

(φ 0 1 (x), φ 0 2 (x), ξ 0 ) ∈ (H 1 (0, L)) 2 × R, ∀x ∈ [0, L] For each initial condition (φ 0 1 (x), φ 0 2 (x), ξ 0 ) in (H 1 (0, L)) 2 × R and satisfying C 0 and C 1 compatibility conditions, then there exits a unique solution (φ 1 (•, t), φ 2 (•, t), ξ(t)) of (8) in (C 0 ([0, +∞), H 1 (0, L)) 2 × R for all t.
In the paper, we study the stability of the closed-loop system and the regulation of the output to the desired reference. Let X = (H 1 (0, L)) 2 × R be the state space of the closedloop system (8) equipped with the following norm :

||Z|| 2 X = ||Z 1 (., t)|| 2 H 1 (0,L) + ||Z 2 (., t)|| 2 H 1 (0,L) + |Z 3 (t)| 2 where Z = (Z 1 , Z 2 , Z 3 ) ∈ X.
The PI controller is designed on the boundary at first for a single system as following Theorem 1. There exists µ * > 0 such that for each µ ∈ (0, µ * ), and for each PI controller with the following proportional gain K P and the integral gain K I :

K P = -R 1 b , K I = -µ (a + bR 2 e µL )(b + aR 1 ) b (9)
then the two following properties hold true :

• The closed-loop system (8) with the PI controller design in ( 9) is exponentially stable toward the origin in X. • The output y(t) is regulated to the desired reference y r , i.e:

lim t→∞ |y(t) -y r | = 0
Proof : Applying the PI controller design in ( 9), the closed-loop system ( 8) is described as follows

                       ∂ t φ 1 φ 2 = -λ 1 0 0 λ 2 ∂ x φ 1 φ 2 ∂ t ξ = aφ 1 (0, t) + bφ 2 (0, t) φ 1 (0, t) = -k i ξ φ 2 (L, t) = R 2 φ 1 (L, t) y(t) -y r = aφ 1 (0, t) + bφ 2 (0, t). ( 10
)
where

k i = µ(a + bR 2 e µL ) (11)
Let us put φ 1x = ∂ x φ 1 and φ 2x = ∂ x φ 2 . The dynamics of φ 1x (x, t) and φ 2x (x, t) are given by

∂ t φ 1x φ 2x + λ 1 0 0 -λ 2 ∂ x φ 1x φ 2x = 0 , (φ 1x (x, 0), φ 2x (x, 0)) ∈ (L 2 (0, L)) 2 , φ 1x (0, t) = k i λ 1 (aφ 1 (0, t) + bφ 2 (0, t)) φ 2x (L, t) = - R 2 λ 1 λ 2 φ 1x (L, t) (12)
We consider the following Lyapunov function candidate

V (φ 1 , φ 2 , ξ) = L 0 φ T P φdx (13) where φ =       φ 1 e -µx 2 φ 2 e µx 2 ξ φ 1x e -µx 2 φ 2x e µx 2       , P =     
1 0 q 3 0 0 0 q 1 q 4 0 0 q 3 q 4 q 2 0 0 0 0 0 q 5 0 0 0 0 0 q 6      , µ > 0, and q i ∈ R with i = 1, 6 are parameters that have to be designed. The following lemma shows our design for q i . Lemma 1. Let k i be defined in (11) and q 1 , q 2 , • • • , q 6 be defined by

q 1 = λ 1 e -2µL 2λ 2 R 2 2 , q 2 = µλ 1 , q 3 = µbR 2 e µL , q 4 = µ bλ 1 λ 2 , q 5 = γ 2e 2µL R 2 2 λ 1 λ 2 , q 6 = γ . ( 14
)
Then there exists γ > 0 and µ * > 0 such that for every µ ∈ (0, µ * ), we have :

(1) There exists

M > 0 such that ∀ (φ 1 , φ 2 , ξ) in X : 1 M V (φ 1 , φ 2 , ξ) ||(φ 1 , φ 2 , ξ)|| 2 X M V (φ 1 , φ 2 , ξ).
(15) (2) There exists β > 0 such that along the solution of (10), for all t at which the solution is well defined

V (t) -βV (t) -φ 2 1 (L, t) λ 1 e -µL 2 . ( 16
)
The proof of Lemma 1 is given in Appendix. Now applying the Lemma 1 and the Lyapunov candidate to prove the Theorem 1.

At first, we prove the exponential stability of the closedloop system (10) toward the origin in X. According to Lemma 1, there exists β > 0 such that: Moreover,using (15), one can find K > 0 such that for all initial conditions (φ 0 1 (x), φ 0 2 (x), ξ 0 ) ∈ (H 1 (0, L)) 2 × R and satisfies C 0 and C 1 compatibility conditions, the solution is defined for all positive time in X and satisfies:

V (φ 1 , φ 2 , ξ) V (φ 0 1 (x), φ 0 2 (x), ξ 0 )e -βt .
||(φ 1 , φ 2 , ξ)|| 2 X Ke -βt ||(φ 0 1 , φ 0 2 , ξ 0 )|| 2 X .
(17) This implies that the origin of the closed-loop system (10) is exponentially stable in X. Secondly, we prove the regulation part. Employing (17), it is easy to show that lim

t→∞ ||φ 1 (x, t)|| H 1 (0,L) = 0 , lim t→∞ ||φ 2 (x, t)|| H 1 (0,L) = 0.
(18) Now employing the Sobolev embedding theorem, see in [START_REF] Brezis | Analyse fonctionnelle : Théorie et applications[END_REF], one can find that for ∀x ∈ [0, L] lim In this section, we extend the PI control results acquired from the previous section to a star-shaped network of n channels (n 3). The connection between channels is depicted in Fig. 1, with n -1 inlet channels (1th to (n -1)th) and a outlet channel (nth channel).

t→∞ φ 1 (x, t) = 0, lim t→∞ φ 2 (x, t) = 0 .
Modeling Each channel of the network is modeled by two PDE hyperbolic equations (1). Without loss of generality, the lengths of channels are assumed identical and equal L.

The following notations are used for the next : i = 1, n and j = 1, n -1;

H i (x, t) is water level in the ith channel, H i0 (t) = H i (0, t) and H iL (t) = H i (L, t) ; V i (x, t) is water velocity in the ith channel, V i0 (t) = V i (0, t) and V iL (t) = V i (L, t).
The network is thus governed by 2n equations :

∂ t H i (x, t) + ∂ x (H i (x, t)V i (x, t)) = 0, ∂ t V i (x, t) + ∂ x V 2 i (x, t) 2 + gH i (x, t) = 0. ( 19
)
The 2n -1 online measured outputs at each time t are y j0 (t) = H j0 (t) , y iL (t) = H iL (t) (20) We assume that the network is controlled by 2n -1 input controls, in which each channel is controlled by an independent gate at x = L, i.e Note however that at the junction, the constraint of flowrate conservation is expressed by

H 2 iL (t)V 2 iL (t) -U iL (t)(H iL (t) -H di ) = 0, (21)
H n0 (t)V n0 (t) = n-1 j=1 H jL (t)V jL (t). ( 23
)
The equation ( 23) implies that, at the boundary x = 0 the outlet channel (nth channel) cannot be controlled, but its dynamic can be deduced from the conservation of the flow.

Equilibrium states

Each 2n constant values H * i , V * i satisfying the following conditions

• gH * i > (V * i ) 2 (subcritical conditions), • H uj > H * j > H dj , H * n > H dn and V * i > 0, • H * n V * n = n-1 j=1 H * j V * j ,
can be chosen as an equilibrium state with the appropriate constant controls U * j0 , U * iL .

Control and regulation problem

The objective is to stabilize the linearised model of the network ( 19)-( 23) to the set-points H * i , V * i and regulate the output measurements of each inlet channel y j (t) to the desired references y jr = H * j . Apply the similar Riemann coordinates in (4) for the linearized models around the set-point H * i , V * i , one obtains the characteristic forms as follows:

∂ t φ i1 (x, t) + λ i1 ∂ x φ i1 = 0, ∂ t φ i2 (x, t) -λ i2 ∂ x φ i2 = 0 (24)
and 2n -1 measured outputs y j0 (t) -y jr = aφ j1 (0, t)

+ j2 (0, t), y iL (t) -y ir = aφ n1 (L, t) + bφ n2 (L, t) (25)
where the characteristic variables are

φ i1 = (H i -H * i ) + (V -V * i ) H * i g , φ i2 = (H i -H * i ) -(V i -V * i ) H * i g (26)
and

λ i1 = V * i + gH * i > 0 , λ i2 = -V * i + gH * i > 0, a = 1 2 , b = 1 2 .
Inspired by the stability and regulation analysis in Section 3, we want to receive the following boundary conditions :

φ j1 (0, t) = R j1 φ j2 (0, t) + u j (t), φ i2 (L, t) = R i2 φ i1 (L, t), ( 27
)
where R j1 and R i2 are arbitrary constants, u j (t) is the dynamic feedback control law which we want to design by PI controller for jth channel. Hence, using ( 25), ( 26), ( 21) and ( 22), we can compute the adaptive control gate openings on the boundary to satisfy conditions ( 27) as follows

U j0 = y 2 j0 H uj -y j0 V * j + g H * j (R j1 -1)(y j0 -H * j ) + u j R j1 + 1 2 , U iL = y 2 iL y iL -H dn V * i + g H * i (1 -R i2 )(y iL -H * i ) R i2 + 1 2 . (28)
Remark : Here, to implement control inputs U iL and U j0 , we only need 2n -1 online measurements y j0 and y iL as water levels H j0 and H iL . It is practical because measure flow discharge in reality is difficult.

The condition at the junction ( 23) therefore becomes

φ n1 (0, t) = R n1 φ n2 (0, t) + n-1 j=1 α j φ j1 (L, t). ( 29
)
where

R n1 = λ n2 λ n1 , α j = λ j1 + R j2 λ j2 λ n1 .
To summarize, the control target is to design the dynamic feedback PI controllers u j (t),

u j (t) = K jP (y j (t) -y jr ) + K jI L 0
(y j (s) -y jr )ds ( 30) such that the network of closed-loop systems ( 24), ( 25), ( 27), ( 29) and ( 30) is stabilized toward the origin and the outputs y j (t) of inlet channels are regulated to the reference y jr (∀j = 1, n -1).

PI controller design

The ideal of control design is to extend from the results in Section 3, we propose for each inlet channel a PI controller motivated by Theorem 1 and guarantee the exponential stability and the output regulation for the network of closed-loop systems controlled by PI controllers.

Denoting the new state variables ξ j (t) where ∂ t ξ j = y j (t)y jr , the network of closed-loop systems ( 24), ( 25), ( 27), ( 29) and ( 30) is governed by :

                                     ∂ t φ i1 (x, t) = -λ i1 ∂ x φ i1 , ∂ t φ i2 (x, t) = λ i2 ∂ x φ i2 , ∂ t ξ j = aφ j1 (0, t) + bφ j2 (0, t) φ i2 (L, t) = R i2 φ i1 (L, t), φ j1 (0, t) = R j1 φ j2 (0, t) + K jP (y j (t) -y jr ) + K jI ξ j (t), φ n1 (0, t) = R n1 φ n2 (0, t) + n-1 j=1 α j φ j1 (L, t). y j (t) -y jr = aφ j1 (0, t) + bφ j2 (0, t). (31)
The closed-loop system (31) is completed by the following initial conditions

φ 0 11 (x), φ 0 12 (x), • • • , φ 0 n1 (x), φ 0 n2 (x), ξ 0 1 , • • • , ξ 0 n-1 ∈ (H 1 (0, L)) 2n-2 × (L 2 (0, L)) 2 × R n-1 . (32) Let E = (H 1 (0, L)) 2n-2 × (L 2 (0, L)) 2 × R n-1
be the state space of the closed-loop system (31) equipped with the following norm :

||Y || 2 E = 2n-2 i=1 ||Y i (., t)|| 2 H 1 (0,L) + ||Y 2n-1 (., t)|| 2 L 2 (0,L) + ||Y 2n (., t)|| 2 L 2 (0,L) + 3n-1 j=2n+1 |Y j (t)| 2 , where Y = (Y 1 , Y 2 , • • • , Y 3n-1 ) ∈ E.
The main result of this Section is given in the following theorem Theorem 2. There exists µ * > 0 such that for each µ ∈ (0, µ * ), each R n2 ∈ -λn1 λn2 , λn1 λn2 and for each PI controller with the following proportional gain K jP and the integral gain

K jI K jP = -R j1 b , K jI = -µ (a + bR j2 e µL )(b + aR j1 ) b (33)
then the two following properties hold true :

• The network of closed-loop systems (31) with the initial condition in ( 32) is exponentially stable toward the origin in E. • The measured outputs y j (t) of each inlet channel are regulated to the desired set-points y jr , i.e : lim t→∞ |y j (t) -y jr | = 0

Lyapunov method for the proof

Inspired from the proof of the Theorem 1, we construct the following Lyapunov candidate function for the closed-loop system (31):

S = n-1 j=1 V j + V n (34)
where V j has the same form in (13), i.e

V j = L 0 F T j P j F dx with F j =       φ j1 e -µx 2 φ j2 e µx 2 ξ j φ j1x e -µx 2 φ j2x e µx 2       , P j =      1 0 q j3 0 0 0 q j1 q j4 0 0 q j3 q j4 q j2 0 0 0 0 0 q j5 0 0 0 0 0 q j6      , V n = q n L 0 qφ 2 n1 e -µx + φ 2 n2 e µx dx
Employing the Lemma 1, we can design the parameters q j1 , • • • , q j6 for every j = 1, n -1 satisfying that

• There exists M j > 0 such that 1

M j V j ||(φ j1 , φ j2 , ξ j )|| 2 X M j V j . (35)
• There exists β j > 0 such that

Vj (t) -β j V j (t) -φ 2 j1 (L, t) λ j1 e -µL 2 . ( 36
)
Now analysis the time derivative of V n along the solution of the system (24),

Vn (t) = -µq n L 0 λ n1 qφ 2 n1 e -µx + λ n2 φ 2 n2 e µx dx -φ 2 n1 (L, t)e -µL q n (λ n1 q -λ n2 R 2 n2 ) -φ 2 n2 (0, t)λ 2n q n + λ n1 q n q   R n1 φ n2 (0, t) + n-1 j=1 α j φ j1 (L, t)   2 . (37) Since |R n2 | < λ n1 λ n2 , one can choose q such that R 2 n2 λ n2 λ n1 < q < λ n1 λ n2
, and take q n > 0 small enough, we have 36), ( 37) and ( 38), there exits δ > 0 such that 39) and ( 40), it leads to the exponential stability toward the origin of network closed-loop system (31) in E. Finally, the proof of the output regulation for n -1 inlet channels is similar to the one in Theorem 1.

- n-1 j=1 φ 2 j1 (L, t) λ j1 e -µL 2 -φ 2 n2 (0, t)λ n2 q n + λ n1 q n q   R n1 φ n2 (0, t) + n-1 j=1 α j φ j1 (L, t)   2 0 , -φ 2 n1 (L, t)e -µL (λ n1 q -λ n2 R 2 n2 )q n 0 . (38) From (
n-1 j=1 Vj + Vn -δ   n-1 j=1 V j + V n   This implies that Ṡ(t) -δS(t) (39) Moreover, one can find A > 0 such that 1 A S || (φ 11 , φ 12 , • • • , φ n1 , φ n2 , ξ 1 , • • • , ξ n-1 ) || E A S (40) From (

Numerical simulations

Because of the lack of space, in this Section, we give only the numerical simulations for a single channel with the following data:

• Length of channel L = 50 m with the outside level:

H d1 = 3 , H u1 = 1 m. • The state equilibrium: H * = 2 m , V * = 0.5 m/s.
Clearly, the above data satisfy the subcritical conditions and physical conditions. The tuning parameter µ is chosen 0.02 in the simulations.

The simulations are based on Preissmann schema, with weighting coefficient θ = 0.55, space discretization step ∆x = 1 m. Figure 3 and Figure 4 show the stability of the closed-loop system controlled by PI controller. One can see that the equilibrium state (H * = 2 m and V * = 0.5 m/s) is stable for the closed-loop system In Figure 5, we see that the output measurement H(0, t) converges to the desired reference H * = 2 m. Note also that with the big value of tuning parameter µ (bigger than 0.002) in simulations, the controlled system becomes unstable.

CONCLUSIONS

In the paper, we have studied PI control design for a star-shaped network of hydraulic systems governed by two hyperbolic partial differential equations. The boundary PI controller is proposed by using Lyapunov direct method not only for a single system, but also for a star-shaped network in which each inlet system is applied a PI controller at the free extremity. Here the stability analysis is in H 1 norm and used to prove the output regulation effect for the closed-loop system. In the future, the objective is to extend the control design for a tree-shaped network, and to consider the PI control design at the junctions.

q 1 = µ λ 1 -µb 2 R 2 2 e 2µL -µb 2 R 2 2 e 2µL 2λ 1 λ 2 .
It is clearly that if µ is small enough, q 2 -q 2 3 -

q 2 4 q 1 > 0.
It therefore yields that the matrix P is symmetric positive definite. Hence, there exits σ 1 , σ 2 > 0 such that

σ 1 L 0 T φ V (φ 1 , φ 2 , ξ) σ 2 L 0 φ T φ with φ = φ 1 e -µx 2 , φ 2 e µx 2 , ξ, φ 1x e -µx 2 , φ 2x e µx 2 T
As a result, there exists M > 0 such that (15) holds.

A.2 Proof of the second part

The time derivative of V along the solution of system (10) has the following form:

V = - L 0 Λ T QΛ -L(t) ,
where Λ = φ 1 e -

+ ξ 2 λ 1 k 2 i 2 - γk 2 i λ 1 (bφ 2 (0, t) -ak i ξ(t)) 2 , Q = 1 L            µλ 1 L 0 T φ 1 ,ξ T φ 1 ,φ 20 0 0 0 µq 1 λ 2 L T φ 2 ,ξ T φ 2 ,φ 20 0 0 T φ 1 ,ξ T φ 2 ,ξ T ξ 0 0 0 T φ 1 ,φ 20 T φ 2 ,φ 20 0 λ 2 q 1 2 0 0 0 0 0 0 λ 1 q 5 0 0 0 0 0 0 λ 2 q 6            with T ξ = µ 2 λ 1 c 2 2
, T φ1,φ20 = -µLb 2 R 2 e µL , T φ2,φ20 = -µL b 2 λ 1 λ 2 , T φ1,ξ = µ 2 LbR 2 e µL 2ac + λ 1 2 , T φ2,ξ = µ 2 Lbλ 1 2ac + λ 2 2λ 2 , c = a + bR 2 e µL .

At first, one can easily see that if taking γ small enough, we have L(t) φ 2 1 (L, t) λ1e -µL 2 . In the following, we prove that by picking µ small enough, matrix Q is symmetric positive definite. From the Sylvester criterion, Q is symmetric positive definite if and only if

D 1 = det     µλ 1 L 0 T φ1,ξ 0 µq 1 λ 2 L T φ2,ξ T φ1,ξ T φ2,ξ T ξ     > 0, D 2 = det         µλ 1 L 0 T φ1,ξ T φ1,φ20 0 µq 1 λ 2 L T φ2,ξ T φ2,φ20
T φ1,ξ T φ2,ξ T ξ 0 T φ1,φ20 T φ2,φ20 0

λ 2 q 1 2         > 0.
By the direct computing, we have that D 1 = µ 4 f 1 (µ) , D 2 = µ 4 f 2 (µ) with lim µ→0 f 1 (µ) = 1 2 L 2 λ 2 1 λ 2 c 2 q 1 > 0 and lim µ→0 f 2 (µ) = 1 4 L 2 λ 2 1 λ 2 2 c 2 q 2 1 > 0. Taking µ small enough, it yields that the two terms D 1 , D 2 are both positive. Consequently, the matrix Q is symmetric positive definite. Therefore, with the adaptive choice of γ and µ, there exists a positive real number K > 0 such that for all t at which the solution is well defined we have:

V (t) -K||(φ 1 , φ 2 , ξ)|| 2 X -φ 2 1 (L, t)
λ 1 e -µL 2 .

With (15) the former inequality implies that we can find β > 0 such that (16) holds. This completes the proof of Lemma 1.

  , we consider a star-shaped network of open channels described by two Saint-Venant equations of conservation laws, studied in[START_REF] De Halleux | Boundary control in networks of open channels[END_REF];[START_REF] Bastin | On Lyapunov stability of linearised Saint-Venant equations for a sloping channel[END_REF][START_REF] Trinh | PI regulation control of a fluid flow model governed by hyperbolic partial differential equations[END_REF]

Fig. 1 .

 1 Fig. 1. Star-shaped networks of n channels As a result, lim t→∞ ||y(t) -y r || 2 R 2 = 0. This completes the proof of the Theorem 1. 2

Fig. 2 .

 2 Fig. 2. Channel jth and n -1 inlet channels is actively controlled at x = 0 by H 2 j0 (t)V 2 j0 (t) -U j0 (t)(H uj -H j0 (t)) = 0. (22) where control inputs U iL and U j0 are gate openings at the boundary, the constants H di and H uj are water levels outside channels (see in Fig 2). Note however that at the junction, the constraint of flowrate conservation is expressed by

Fig. 3 .

 3 Fig. 3. Water level H(x, t)

Appendix A. PROOF OF LEMMA 1

A.1 Proof of the first part

To begin with, we prove that matrix P is definite positive. Applying the Sylvester criterion, matrix P is positive definite if and only if :

, q 5 > 0, q 6 > 0.

Employing ( 14), one can find that : q 1 > 0, q 5 > 0, q 6 > 0 , q 2 -q 2 3 -q 2