T Boukhobza
email: taha.boukhobza@cran.uhp-nancy.fr

F Hamelin

Observability analysis for structured bilinear systems: a graph-theoretic approach

Keywords: Structured bilinear systems, generic observability, graph theory

This paper is devoted to the generic observability analysis for structured bilinear systems using a graph-theoretic approach. On the basis of a digraph representation, we express in graphic terms the necessary and sufficient conditions for the generic observability of structured bilinear systems. These conditions have an intuitive interpretation and are easy to check by hand for small systems and by means of well-known combinatorial techniques for large scale systems.

Introduction

The class of bilinear systems (BLS), representing particular nonlinear systems whose dynamics are jointly linear in the state and the input variables, was introduced in control theory in the 1960's. This kind of systems are simpler and better understood than most other nonlinear systems. Furthermore, industrial process control, economics and biology (switched circuits, mechanical brakes, controlled suspension systems, immunological systems, population growth, enzyme kinetics, . . . ) provide examples of BLS. Finally, the usual linearization of a nonlinear control system near an equilibrium point can be improved by using a bilinear approximation. For these reasons, many works deal with BLS. The observability of BLS was tackled in many works among which we can cite [START_REF] Grasselli | Deterministic state reconstruction and reachability of bilinear processes[END_REF][START_REF] Williamson | Observation of bilinear systems with application to biological control[END_REF]. The necessary and sufficient conditions to achieve this property are now very well known. These conditions have been established using essentially geometric or algebraic tools. However, the use of such tools assumes the exact knowledge of the state space matrices characterizing the system's model. In many modeling problems, these matrices have a number of fixed zero entries determined by the physical laws while the remaining entries are not known precisely. To study the properties of these systems in spite of the poor knowledge we have on them, the idea is that we only keep the zero/non-zero entries in the state space matrices. Thus, we consider models where the fixed zeros are conserved while the non-zero entries are replaced by free parameters. There is a huge amount of interesting works in the literature using this kind of models called structured models. These models are useful to describe the class of systems having the same structure and they capture most of the structural available information from physical laws. Moreover, their study requires a low computational burden which allows one to deal with large scale systems. Be-cause of these features, we think that structured systems are adapted to study a property like the observability and subsequently this paper deals with this kind of systems. Many results on structured systems are related to the graphtheoretic approach. This approach is mainly dedicated to linear systems for which many structural properties such as controllability, observability, solvability of several classical control problems including disturbance rejection, inputoutput decoupling, fault detection and isolation are studied. Survey paper [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF] reviews the most significant results in this area. From these studies, it follows that the graphtheoretic approach provides simple and elegant solutions and so is very well-suited to analyse large scale or/and uncertain systems. Unfortunately, not so many works based on graph-theoretic methods deal with nonlinear systems. Among them, [START_REF] Kasinski | A Fast Graph Theoretic Algorithm for the Feedback Decoupling Problem of Nonlinear Systems[END_REF][START_REF] Lévine | A graph-theoretic approach to input output decoupling and linearization[END_REF] give conditions to the input-output decoupling and linearization of a nonlinear system, [START_REF] Svaricek | A graph theoretic approach for the investigation of the observability of bilinear systems[END_REF] gives sufficient conditions to fulfill the observability of bilinear systems and recently, [START_REF] Bornard | A graph approach to uniform observability of linear multi output systems[END_REF] provides sufficient conditions for the uniform observability of some nonlinear systems. In this context, this paper is dedicated to the analysis of the observability for structured bilinear systems (SBLS). More precisely, for such class of systems, we give simple necessary and sufficient conditions to achieve the observability of the whole or of a given part of the state. These conditions, which are equivalent to the well-known observability criteria [START_REF] Grasselli | Deterministic state reconstruction and reachability of bilinear processes[END_REF][START_REF] Sen | On the choice of input for observability in bilinear systems[END_REF][START_REF] Williamson | Observation of bilinear systems with application to biological control[END_REF] are easier to check from a computational point of view. The paper is organised as follows: after section 2, which is devoted to the problem formulation, a digraph representation of SBLS is defined in section 3. The main results are given in section 4 and are illustrated with an example in section 5. Finally, some concluding remarks are made.

In this paper, we consider SBLS in the form:

(Σ Λ ) :              ẋ(t) = A 0 x(t) + m i=1 u i (t)A i x(t) + Bu(t) y(t) = Cx(t) (1)
where

x(t) = (x 1 (t), . . . , x n (t)) T ∈ R n , u(t) = (u 1 (t), . . . , u m (t)) T ∈ R m and y(t) = y 1 (t), . . . , y p (t) T ∈ R p
are respectively the state, the input and the output vectors.

For i = 0, . . . , m, A i ∈ R n×n , B ∈ R n×m and C ∈ R p×n are matrices which elements are either fixed to zero or assumed free non-zero parameters. We can parameterize these nonzero entries by scalar real (nonzero) parameters λ i , i = 1, . . . , h forming a parameter vector Λ = (λ 1 , λ 2 , . . . , λ h ) T ∈ R h . If all the parameters λ i are fixed, we obtain an admissible realization of structured system (Σ Λ ). Theoretic properties of each realization can be studied according to the values of λ i . We say that a property is true generically [START_REF] Davison | Properties of linear time-invariant multivariable systems subject to arbitrary output and state feedback[END_REF] if it is true for almost all the realizations of structured system (Σ Λ ). Here, " for almost all the realizations " is to be understood [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF][START_REF] Van Der Woude | The generic number of invariant zeros of a structured linear system[END_REF] as " for all parameter values (Λ ∈ R h ) except for those in some proper algebraic variety in the parameter space ". The proper algebraic variety for which the property is not true is the zero set of some nontrivial polynomial with real coefficients in the h system parameters, which can be written down explicitly. Recall that a proper algebraic variety is an algebraic variety which has Lebesgue measure zero.

Many studies deal with the observability of bilinear systems using generally either geometric tools or linear timevarying system theory [START_REF] Angelo | Linear time varying systems: Analysis and Synthesis[END_REF]. In these studies, the notions of u-indistinguishability, u-observability and u-unobservability subspaces are defined to characterize the ability of state reconstruction using the knowledge of the input and the output. In this respect, observability definition of BLS is given in [START_REF] Williamson | Observation of bilinear systems with application to biological control[END_REF]. We extend this definition to SBLS:

Definition 1 Structured bilinear system (Σ Λ ) is generically observable if, for almost all the realisations of (Σ Λ ), there exists an input u(t) such that any pair of initial states x 0 (0) and x 1 (0) are distinguishable by observation of the corresponding outputs y 0 (t) and y 1 (t) for t ≥ 0.

Directly, from results provided in [START_REF] Williamson | Observation of bilinear systems with application to biological control[END_REF], the generic observability of SBLS (Σ Λ ) is necessary and sufficient to ensure, for almost all the realizations of (Σ Λ ), the existence of an observer which provides an asymptotic estimate of the state. Moreover, Theorem 1 of [START_REF] Grasselli | Deterministic state reconstruction and reachability of bilinear processes[END_REF] states that for piecewise constant or continuous controls, a BLS is observable iff there exists an input u(t) for which it is u-observable. The proof is based on the construction of an universal input ū, which distinguishes all initial states x 1 (0) from x 0 (0) = 0 by concatenating at most n + 1 constant inputs: ū = u 0 • u 1 • . . . • u n . At the k th stage in the construction, the set of states indistinguishable from x(0) = 0 is reduced in dimension by well chosen input value u k . This leads to the following observability criterion for BLS. This criterion is based on the observability matrix rank conditions proposed in [START_REF] Grasselli | Deterministic state reconstruction and reachability of bilinear processes[END_REF] for BLS.

Theorem 2 For piecewise continuous input signals u(t), structured bilinear system (Σ Λ ) is generically observable iff

T1: g_rank O(C, A 0 , A 1 , . . . , A m ) = n, where O(C, A 0 , A 1 , . . . , A m ) = col (C, CA 0 , CA 1 , . . . , CA m , CA 2 0 , CA 0 A 1 , . . . . . . , CA 0 A m , CA 1 A 0 , . . . , CA n-1 m
is the observability matrix of system (Σ Λ ) and where g_rank(M) denotes the generic rank of matrix M [START_REF] Murota | System Analysis by Graphs and Matroids[END_REF].

The aim of this paper is to provide graphic conditions equivalent to the one of Theorem 2. It turns out that these graphic conditions are easier to check and so more adapted to tackle large scale or uncertain systems. Indeed, the computation of g_rank O(C, A 0 , A 1 , . . . , A m ) is quite difficult particularly for large scale systems.

Graph representation of structured bilinear systems

This section is devoted, in a first stage, to the definition of a digraph which represents SBLS (Σ Λ ). Next, some useful notations and definitions are given.

Digraph definition for structured bilinear system

Not so many works use the graph-theoretic approach to study nonlinear systems. The digraph we use in this paper is quite close to the one presented in [START_REF] Lévine | A graph-theoretic approach to input output decoupling and linearization[END_REF]. The main differences are due to the fact that we adapt our representation to the context of observability analysis and to the fact that we deal with structured systems. The digraph we associate to (Σ Λ ) is noted G(Σ Λ ) and is constituted by a vertex set V and an edge set E i.e. G(Σ Λ ) = (V, E). The vertices are associated to the state and the output components of (Σ Λ ) and the directed edges represent links between these variables. More precisely, V = X∪Y, where X = {x 1 , . . . , x n } is the set of state vertices, Y = y 1 , . . . , y p is the set of output vertices. For sake of clarity, the state and the output vertices are written in bold fonts. The edge set is

E = m l=0 A l -edges∪C-edges, where, for l = 0, . . . , m, A l -edges = (x j , x i ) | A l (i, j) 0 and C-edges = (x j , y i ) | C(i, j) 0 . Here M(i, j) is the (i, j)th element of matrix M and (v 1 , v 2 ) denotes a directed edge from vertex v 1 ∈ V to vertex v 2 ∈ V.
Note that number i is indicated under each A i -edge in order to preserve the information about the belonging of the edges in the digraph representation. Moreover, for i ∈ {0, . . . , m}, to each edge e ∈ A i -edges we associate index i. Note that we associate several indexes to an edge e if it belongs to several subsets A i -edges. The following example illustrates the proposed digraph representation.

Example 3

In Figure 1, we represent the digraph associated to the SBLS defined by: As we can see, comparatively with the digraph presented in [START_REF] Lévine | A graph-theoretic approach to input output decoupling and linearization[END_REF], the input vertices are removed since we study the state observability. Moreover, due to this removal, the edges, which start in [START_REF] Lévine | A graph-theoretic approach to input output decoupling and linearization[END_REF] from the input vertices, start in our digraph from state vertices and constitute the A i -edges. Finally, as we are interested in structured systems, each edge represents a free parameter which has no numerical value. Thus, it is not necessary to indicate it on each edge of the digraph as in [START_REF] Lévine | A graph-theoretic approach to input output decoupling and linearization[END_REF].

A 0 =                                 λ 1 λ 2 λ 3 0 0 λ 4 0 λ 5 0 0 0 0 λ 6 0 0 0 0 0 0 λ 7 0 0 0 λ 8 0                                 , A 1 =                                 0 λ 9 0 0 0 0 0 0 0 0 0 0 λ 10 0 0 0 0 0 0 0 0 0 λ 11 λ 12 0                                 , A 2 =                                 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 λ 13 0 λ 14 0 0 0                                 and C =          λ 15 0 0 0 0 0 0 0 λ 16 0          . y 1 y 2 x 1 x 4 x 2 x 5 x 3 0 0,1 0 0 0 0,1 0,2 1 2 0,1 y 1 y 2 x 1 x 4 x 2 x 5 x 3 0 0,1 0 0 0 0,1 0,2 1 2 0,1

Definitions and notations

We present hereafter briefly some definitions concerning particular tools, we use in the paper. For the classical definitions related to the digraphs, the readers are referred to [START_REF] Andrë | Sparse Systems, Digraph Approach of Large-Scale Linear Systems Theory[END_REF][START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF][START_REF] Lévine | A graph-theoretic approach to input output decoupling and linearization[END_REF][START_REF] Murota | System Analysis by Graphs and Matroids[END_REF][START_REF] Reinschke | Multivariable Control. A Graph Theoretic Approach[END_REF].

• A path P is an Y-topped path if its end vertex is an ele- ment of Y. • Two edges e 1 = (v 1 , v ′ 1 ) and e 2 = (v 2 , v ′ 2 ), elements of E, are v-disjoint if v 1 v 2 and v ′ 1 v ′ 2 .
Note that e 1 and e 2 can be v-disjoint

even if v ′ 1 = v 2 or v 1 = v ′ 2 . k edges are v- disjoint if they are mutually v-disjoint. • Consider k edges e 1 = (v 1 , v ′ 1 ), e 2 = (v 2 , v ′ 2 ), . . . , e k = (v k , v ′ k ).
We define for i = 1, . . . , k, I i as the set of integers C2: for i = 1, . . . , k, I i = {i} or there exist r distinct integers i 1 , i 2 , . . . , i r such that e j 1 ∈ A i 1 -edges, e j 2 ∈ A i 2 -edges, . . . , e j r ∈ A i r -edges, where j 1 , j 2 , . . . , j r are all the elements of I i . Roughly speaking, k edges are A-disjoint if their begin vertices are all distinct and if all the edges which have the same end vertex can be associated to distinct indexes i.

j such that v ′ j = v ′ i i.e. I i de f = 1 ≤ j ≤ k | v ′ j = v ′ i . e 1 ,
To illustrate the latter definition, note that in Example 3, e 1 = (x 2 , x 1 ) and e 2 = (x 1 , x 1 ) are A-disjoint as well as e 1 = (x 2 , x 1 ) and e 3 = (x 3 , x 1 ). So, e 1 , e 2 and e 3 are mutually A-disjoint but they are not A-disjoint even if condition C1 is satisfied. Indeed, these three edges have the same end vertex i.e. I 1 = I 2 = I 3 = {1, 2, 3} and there do not exist three distinct integers i 1 , i 2 and i 3 such that e 1 ∈ A i 1 -edges, e 2 ∈ A i 2edges and e 3 ∈ A i 3 -edges. Thus, C2 is not satisfied. Otherwise, edges e 1 = (x 2 , x 5 ), e 2 = (x 3 , x 5 ) and e 3 = (x 4 , x 5 ) are A-disjoint. Indeed, as they have distinct begin edges, C1 is satisfied. Moreover, even if I 1 = I 2 = I 3 = {1, 2, 3}, as e 1 ∈ A 2 -edges, e 2 ∈ A 1 -edges and e 3 ∈ A 0 -edges, C2 is satisfied too.

Main results

We give hereafter a graphical criterion to characterize the generic-observability of system (Σ Λ ).

Proposition 4 Structured bilinear system (Σ Λ ) is generically observable iff in its associated digraph G(Σ Λ ) i. every state vertex is the begin vertex of an Y-topped path; ii. there exist n A-disjoint edges in G(Σ Λ ).

Proof:

Necessity: • Assume that Condition (i.) is not satisfied i.e. ∃ x j from which there does not exist an Y-topped path. Then, we can state that, ∀k > 0, ∀i 1 , i 2 , . . . , i k elements of {0, 1, . . . , m}, the j th column of CA i 1 A i 2 . . . A i k is equal to zero. Thus, condition T1 of Theorem 2 cannot be satisfied and the system is not generically observable.

• If structured bilinear system (Σ Λ ) is generically observable i.e. g_rank O(C, A 0 , A 1 , . . . , A m )

= n then

Im C T , A T 0 C T , A T 1 C T , . . . , A T m C T , (A T 0 ) 2 C T , A T 0 A T 1 C T , . . . , A T 0 A T m C T , A T 1 A T 0 C T , . . . (A T m ) n-1 C T = R n . Yet, since ∀M ∈ R n×p , Im(A T i M) ⊆ Im(A T i ), we have that Im C T , A T 0 C T , A T 1 C T , . . . , A T m C T , (A T 0 ) 2 C T , . . . , A T 0 A T m C T , A T 1 A T 0 C T , . . . (A T m ) n-1 C T ⊆ Im C T , A T 0 , . . . , A T m ⊆ R n . Thus, necessarily g_rank O(C, A 0 , A 1 , . . . , A m ) = n implies that Im C T , A T 0 , A T 1 , . . . , A T m = R n and so g_rank C T , A T 0 , A T 1 . . . , A T m = n which is equivalent to g_rank col (C, A 0 , A 1 , . . . , A m ) = n.
On the other hand, we can prove (Appendix A) using the results of [START_REF] Murota | System Analysis by Graphs and Matroids[END_REF][START_REF] Reinschke | Multivariable Control. A Graph Theoretic Approach[END_REF][START_REF] Van Der Woude | A graph theoretic characterization for the rank of the transfer matrix of a structured system[END_REF], that: Statement 1: The maximal number of A-disjoint edges in G(Σ Λ ) is equal to g_rank col (C, A 0 , A 1 , . . . , A m ) . Thus, immediately, the generic-observability of SBLS (Σ Λ ) implies that condition (ii.) is satisfied. Sufficiency: At first, let us recall some facts on linear systems. Consider a structured linear system,

Σ L,Λ :          ẋ(t) = Ax(t) + Bu(t) y(t) = Cx(t)
It is well known that the system is observable iff

g_rank         C sI -A         = n, ∀s ∈ C.
Otherwise, the PBH test [START_REF] Kailath | Linear systems. Prentice Hall Information and system science series[END_REF] states that (Σ L,Λ ) is unobservable iff there exists generically a vector q 0 such that Aq = s 0 q, s 0 ∈ C and Cq = 0.

On the one hand, if g_rank

        C sI -A         = n, ∀s ∈ C \ {0}
, then the unobservability of (Σ L,Λ ) implies necessarily that there exists generically a vector q 0 such that Aq = 0 and Cq = 0. On the other hand, Lemma 14.1 of [START_REF] Reinschke | Multivariable Control. A Graph Theoretic Approach[END_REF] states that, if in the digraph associated to (Σ L,Λ ), every state vertex is a begin vertex of an Y-topped path, then g_rank

        C sI -A         = n, ∀s ∈ C \ {0}.
Assume now that conditions of Proposition 4 are satisfied. On the one hand, using Lemma 14.1 of [START_REF] Reinschke | Multivariable Control. A Graph Theoretic Approach[END_REF], as all the parameters of matrices A 0 ,. . . , A m are assumed to be free, we can state that condition (i.) of Proposition 4 implies that, for almost all input values ū = (ū 1 , . . . , ūm ) T , we have g_rank col C, sI -(A 0 + ū1 A 1 + . . . + ūm A m ) = n, ∀s 0 . On the other hand, if SBLS (Σ Λ ) is generically unobservable, then for all input constant values, ū = (ū 1 , . . . , ūm ) T , linear systems defined by matrices (C, Ā) are also unobservable, where Ā = A 0 + m i=1 ūi A i . This is due to the fact that for all input constant values, ū, Im(O(C, Ā) ⊆ Im(O(C, A 0 , A 1 , . . . , A m )). Therefore, If (Σ Λ ) is unobservable, using the previous settings, we have that for each matrix Ā, there exists a nonzero vector q such that Āq = 0 and Cq = 0. Since this statement is true for almost all the input values ū = (ū 1 , . . . , ūm ) T , we have that for almost n(m + 1)-uple values of input noted ū j = (ū j 1 , . . . , ū j m ) T , j = 1, . . . , n(m + 1), we can find nonzero vectors q j such that the following system is satisfied:

             Cq j = 0 A 0 q j + m i=1 ū j i A i q j = 0 j = 1, . . . , n(m + 1) (2)
Obviously, there cannot exist more than n independent vectors q j . Let us note q 1 ,. . . , q n the vectors such that span(q 1 , q 2 , . . . , q n(m+1) ) ⊆ span(q 1 , q 2 , . . . , q n ) (we can renumber the vectors if necessary). All the vectors q j , j = n + 1, . . . , n(m + 1) are linear combinations of q 1 ,. . . , q n . Therefore, system (2) contains the following n(m + 1) + n equations

             Cq k = 0 k = 1, . . . , n n k=1 m i=0 a j i,k (ū)A i q k = 0 j = 1, . . . , n(m + 1) (3)
where a j i,k (ū) are linear functions of ū j , j = 1, . . . , n(m + 1). Since system (2) is satisfied for almost all the input values, we can generically find ū j , j = 1, . . . , n(m + 1) such that det

                        a 1 0,1 (ū) a 1 0,2 (ū) . . . a 1 m,n (ū) a 2 0,1 (ū) a 2 0,2 (ū) . . . a 2 m,n (ū) . . . . . . . . . . . . a n(m+1) 0,1 (ū) a n(m+1) 0,2 (ū) . . . a n(m+1) m,n (ū)                         0.
In this case, the only solution of system (3) is

         Cq k = 0 A 0 q k = A 1 q k = . . . = A m q k = 0 k = 1, . . . , n (4)
Obviously, if (Σ Λ ) is unobservable then at least one vector q k , k = 1, . . . , n is nonzero. Consequently, SBLS (Σ Λ ) is unobservable only if there exists at least a nonzero vector q such that Cq = 0 and A 0 q = A 1 q = . . . = A m q = 0. However, if condition (ii.) of Proposition 4 is satisfied, then g_rank col (C, A 0 , A 1 , . . . , A m ) = n and so there does not exist a vector q 0 such that Cq = 0 and A 0 q = A 1 q = . . . = A m q = 0. Hence, for almost all the realizations of SBLS (Σ Λ ), conditions of Proposition 4 are sufficient to ensure the observability. △

In the case of system described in Example 3, Figure 2 represents 5 A-disjoint edges extracted from digraph of Figure 1. Since all the state vertices are begin vertices of Y-topped paths, this system is generically observable. As in [START_REF] Murota | System Analysis by Graphs and Matroids[END_REF] (Theorem 14.1) for the linear case, we can give simpler graphic conditions based on bipartite graphs:

Corollary 5 Structured bilinear system (Σ Λ ) is generically observable iff in its associated digraph G(Σ Λ ) i. every state vertex is the begin vertex of an Y-topped path;

ii. g_rank col(C, A 0 , A 1 , . . . , A m ) = n or equivalently, the maximal matching of the bipartite graph associated to matrix col(C, A 0 , A 1 , . . . , A m ) is equal to n.

The main advantage of the previous corollary is its computational aspect. Indeed, the first condition can be checked using depth search algorithms. These algorithms have a complexity order O(M • N) where M is the number of edges in the digraph and N = n+p the number of vertices. For our digraphs, in the worst case M = (m + 1) • n 2 + n • p. Thus, the complexity of these algorithms, in our case, is O(m • n 3 ), (assuming without loss of generality that p ≤ n). To check the second condition of Corollary 5, we define the bipartite graph related to matrix col(C, A 0 , A 1 , . . . , A m ) [START_REF] Murota | System Analysis by Graphs and Matroids[END_REF]. Then, we use the Bipmatch method [START_REF] Micali | An O(|V 1/2 E|) algorithm for finding maximum matching in general graphs[END_REF], which allows to compute the cardinal of maximal matching into a bipartite graph. The complexity order of algorithms using this method is O(M • N 0.5 ),

where, M = (m + 1) • n 2 + n • p and N = n + p + (m + 1) • n. So, for checking the second condition of Corollary 5 we can use algorithms which have complexity order O(m 3/2 • n 5/2 ). The proposed solution has an acceptable computational burden and so is very well suited to large scale systems.

The previous result can be seen as a generalization of the results concerning linear structured systems recalled in [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF][START_REF] Murota | System Analysis by Graphs and Matroids[END_REF]:

Proposition 6 A structured linear system (Σ L,Λ ) :          ẋ(t) = Ax(t) + Bu(t) y(t) = Cx(t)
is generically observable iff in its associated graph G(Σ L,Λ ) i. every state vertex is the begin vertex of an Y-topped path;

ii. the maximal matching of the bipartite graph associated to matrix col(C, A) is equal to n.

The first condition of both Corollary 5 and Proposition 6 is exactly the same. Moreover, since for a linear system, there is no matrices A i , i = 1, . . . , m, the second condition of Proposition 4 is equivalent to the second one of Corollary 5 in the linear case. Thus, in the linear case, Proposition 4 is equivalent to the one presented in [START_REF] Murota | System Analysis by Graphs and Matroids[END_REF] or to the one based on paths and cycles [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF].

Example

In this section, we illustrate the results presented above with an example. This example is intentionally not very complicated. Nevertheless, it is clear that the observability criteria presented in Proposition 4 and Corollary 5 are very welladapted to more complex or large-scale systems using combinatorial programming techniques. Consider the SBLS represented in the digraph of Figure 3. This system has 19 state components. The matrix representation of this system is not given because of lack of place. Nevertheless, it can be easily deduced from the digraph. Our aim is to show the simplicity of the proposed method on a relatively large example. The proposed conditions can be checked easily by hand whereas the rank test of the observability matrix is quite difficult to do by hand. In fact, this system is observable as each state vertex is a be-

0,1 x 12 0 0 y 1 x 1 x 2 x 4 y 2 x 3
x 7

x 6

x 5

x 8 x 10 In this paper, we propose a new analysis tool to study the observability of structured bilinear systems. Using a new graph representation of this class of nonlinear systems, necessary and sufficient conditions for generic observability are given and expressed in graphic terms. These intrinsic conditions need few information about the system and are easy to check by means of combinatorial techniques or simply by hand for small systems. From a computational point of view, our approach is particularly suited for large-scale systems since it is free from numerical difficulties. Indeed, the proposed conditions can be easily implemented because they require simple computations based on finding edges in digraphs and on integer comparisons. Furthermore, the use of a graph-theoretic approach makes it easy to visualize the system structure. This may be very helpful for the optimisation of sensor placement to achieve the observability of the system. Indeed, starting from the above results, we can study, as in [START_REF] Commault | Observability recovering by additional sensor implementation in linear structured systems[END_REF] for linear systems, the sensor location problem in order to achieve the generic observability.

Figure 1 .

 1 Figure 1. Digraph for the study of observability for Example 3

Figure 2 .

 2 Figure 2. A set of 5 A-disjoint edges for example 3

Figure 3 .

 3 Figure 3. Illustrative example gin vertex of an Y-topped paths and there exist 19 A-disjoint edges as it is displayed in Figure 4.

Figure 4 .

 4 Figure 4. A set of 19 A-disjoint edges for the illustrative example 6 Conclusion

  e 2 , . . . , e k are A-disjoint if C1 and C2 are satisfied, where: C1: edges e 1 , e 2 , . . . , e k have distinct begin vertices.

Appendix A: Proof of Statement 1

We prove hereafter that the maximal number of A-disjoint edges ending with vertices of Y ∪ X is equal to g_rank(M), where M = col (C, A 0 , A 1 , . . . , A m ). To compute g_rank(M), let us define bipartite graph B M = (V + ; V -; E M ) associated to matrix M and where

From the results on the generic rank matrices [START_REF] Reinschke | Multivariable Control. A Graph Theoretic Approach[END_REF], since all the parameters of matrices A 0 ,. . . , A m and C are assumed to be free, we have that g_rank(M) is equal to the maximal number of disjoint edges in B M , which is called the maximum matching in B M . If, for i = 1, . . . , n, vertices x - 0,i , x - 1,i , . . . , x - m,i are joined to form an unique vertex x i and if x + i and y - i are noted respectively x i and y i , the number of disjoint edges in B M becomes the number of A-disjoint edges in G(Σ Λ ). Indeed, k edges are disjoint in B M iff their corresponding edges in the original graph satisfy condition C1 (to have distinct begin vertices in B M ) and condition C2 (to have distinct end vertices in B M ). Therefore, g_rank(M) is equal to the maximal number of A-disjoint edges ending with vertices in G(Σ Λ ) and Statement 1 is proved. △


S Martinez-Martinez

T Mader

T Boukhobza

F Hamelin

LISA: A LINEAR STRUCTURED SYSTEM ANALYSIS PROGRAM

Keywords: Structured systems, graph theory, observability, isolability

In this paper, the so-called software LISA is presented. LISA is a flexible and portable software, which has been developed to analyse structural properties of large scale linear and bilinear structured systems. More precisely, LISA contains programmed algorithms, which allow us to apply recent results in the analysis of structured systems.

INTRODUCTION

Structured systems have received much attention since the beginning of the 70's. Based on the work of [START_REF] Lin | Structural controllability[END_REF], where graphic conditions for the structural controllability are given, [START_REF] Reinschke | Multivariable Control. A Graph-Theoretic Approach[END_REF]) and [START_REF] Murota | Systems Analysis by Graphs and Matroids, Structural Stability and Controllability[END_REF] propose theoretic algorithms for studying the structural properties of multi-input linear systems, like controllability, observability. The main results concerning graph theoretic approach are summarized in [START_REF] Dion | Generic properties and control of linear structured systems: A survey[END_REF].

Recently, some algorithms have been proposed for the analysis of structured linear systems. In [START_REF] Hovelaque | Analysis of linear structured systems using a primal-dual algorithm[END_REF], for example, the primal-dual algorithm is proposed to derive the infinite structure of a structured system. Later, the authors have implemented the algorithm to analyse the solvability of disturbance decoupling problem [START_REF] Hovelaque | Decoupling Problem for Structured Systems Via a Primal Dual Algorithm[END_REF].

In this context, [START_REF] Blanke | SaTool -A software Tool for Structural Analysis of Complex Automation Systems[END_REF] present a Matlab toolbox called SaTool, in which are implemented some results concerning structural analysis theory like reachability, controllability and fault detectability. SaTool uses mainly the bipartite graph to represent structured systems.

In this article, a new tool for the analysis of structured linear and bilinear systems is presented. This tool is based on the representation of structured systems by directed graphs (or digraphs). In fact, it is possible to transform graphic conditions given in terms of digraphs into flow graph conditions. Implementation of flow graphs is relatively easy and mainly efficient (lower computational burden) because there already exist many optimized algorithms useful to analyse structured system properties. The first version of LISA program deals with some new results concerning generic unknown input and state observability and fault isolability of structured linear systems and observability of structured bilinear systems. In order to deal with such complex problems, basic tools have been developed, these basic tools can be used to solve many other structural proprieties as the optimization of sensor placement for observability and FDI, the socalled autonomy for the networked systems, etc.

The paper is organized as follows: in section 2, structured linear and bilinear systems are presented, as well as their graphical representation. In section 3, the LISA program is presented, different useful algorithms are summarized and explained. An estimation of their complexity orders is given. Finally, in section 4, we give the conclusion of the paper.

STRUCTURED LINEAR AND BILINEAR SYSTEMS

Before presenting LISA program, an introduction to structured systems and their graphical representation is exposed in the following section. In many problems, the matrices which characterize the system have a number of fixed zero entries determined by the physical laws, while the reminded entries are not precisely known. To study these systems, the idea is that we keep the zero/non-zero structure in the state space matrices. Thus, we consider models where the fixed zeros are conserved and while the non-zero entries are replaced by free parameters. These kind of models are called structured models. In such a models, theoretic properties can be studied according to the values of the free parameters. We say that a property is true generically if it is valid for almost all parameter values of the structured system (Van der Woude 1999). Moreover, the study of such systems requires a low computational burden which allows one to deal with large scale systems. Many studies on structured systems are related to the graph-theoretic approach to analyse some system properties such as controllability, observability or the solvability of several classical problems as disturbance rejection, input-output decoupling and so on. It results from these works that the graphic approach provides simple and elegant solutions. This is why we develop a software, which allows us to analyse such systems.

Structured linear systems

Let us consider structured linear system noted (Σ l Λ ):

(Σ l Λ ) :

ẋ(t) = Ax(t) + Bu(t) + E 1 w(t) + F 1 f (t) y(t) = Cx(t) + Du(t) + E 2 w(t) + F 2 f (t) (1)
where

x(t) ∈ R n , u(t) ∈ R m , w(t) ∈ R r , f (t) ∈ R q
and y(t) ∈ R p are respectively the state, control input, disturbance, fault and the measured output vector.

A, B, C, D, E 1 , E 2 , F 1 and F 2 are constant structured matrices of appropriate dimensions and each of their elements is either fixed to zero or a free non-zero parameter.

A structured linear system (Σ l Λ ) can be represented through digraph G(Σ l Λ ). The later is constituted by a vertex set V and an edge set E i.e. G(Σ l Λ ) = (V, E). The total number of vertices is denoted by N and the total number of edges by M . The vertices are associated to the state X , controlled input U, disturbance W, measured output Y and fault F of (Σ l Λ ) and the edges represent links between these variables. More precisely, V = X ∪ U ∪ W ∪ F ∪ Y, where X = {x 1 , . . . , x n } is the set of state vertices, U = {u 1 , . . . , u m } is the set of control input vertices, W = {w 1 , . . . , w r } is the set of disturbance vertices, F = {f 1 , . . . , f q } is the set of fault vertices and Y = {y 1 , . . . , y p } is the set of measured output vertices.

Hence, V consists of n + m + r + q + p vertices. The edge set is

E = A-edges ∪ B-edges ∪ C-edges ∪ D-edges∪E 1 -edges∪E 2 -edges∪F 1 -edges∪F 2 -edges, where A-edges = {(x j , x i ) | A(i, j) = 0}, B-edges = {(u j , x i ) | B(i, j) = 0}, C-edges = {(x j , y i ) | C(i, j) = 0}, D-edges = {(u j , y i ) | D(i, j) = 0}, E 1 -edges = {(w j , x i ) | E 1 (i, j) = 0}, E 2 -edges = {(w j , y i ) | E 2 (i, j) = 0}, F 1 -edges = {(f j , x i ) | F 1 (i, j) = 0}, F 2 -edges = {(f j , y i ) | F 2 (i, j) = 0}. Here M λ (i, j) is the (i, j)th element of matrix M λ and (v 1 , v 2 ) denotes a directed edge from vertex v 1 ∈ V to vertex v 2 ∈ V.
We denote a path P as a sequence of vertices v r0 , . . . , v r i , where (v r j , v r j+1 ) ∈ E for j = 0, . . . , i -1. A group of paths are called edge disjoint if they have no common edge and vertex disjoint if they have no common vertex. A set of disjoint paths is called a linking.

Example 1. In Figure 1 is represented the digraph associated to the following structured linear system:

A =      λ1 0 0 λ2 0 0 0 0 0 λ3 λ4 λ5 0 0 0 0 0 0 0 λ6 0 0 0 0 0 λ7 0 λ8 0 0 0 0 0 0 λ9 0 0 0 0 λ10 0 0 0 0 0 0 0 0 0      , B =      0 0 0 0 0 λ11 0      , F1 =      0 0 0 0 0 0 λ12     

Structured bilinear systems

In this part, we consider structured bilinear system

(Σ b Λ ) of the form:          ẋ(t) = A 0 x(t) + m i=1 u i (t)A i x(t) +Bu(t) + E 1 w(t) + F 1 f (t) y(t) = C 0 x(t) +Du(t) + E 2 w(t) + F 2 f (t) (2)
State variables and matrices are defined as in the linear case. A i is a valid matrix for i = 0, . . . , m. In addition, the digraph associated to

(Σ b Λ ) is noted G(Σ b Λ )
and is constituted by a vertex set V and an edge set E i.e.

G(Σ

b Λ ) = (V, E). Vertex set is defined identically as in the linear case. Edge set is E = m l=0 A l -edges ∪ B-edges∪C-edges∪D-edges∪E 1 -edges∪E 2 -edges∪ F 1 -edges ∪ F 2 -edges.
Note that, we indicate the number i under each A i -edge in order to preserve the information about the belonging of the edges in the digraph representation. With this aim, we define the following vertex subset

X ′ = {x ′ k,i } where 0 ≤ i ≤ n and 1 ≤ k ≤ m and the edge sets A ′ k -edges = {(x j , x ′ k,i )|A k (i, j) = 0)}.
Example 2. In Figure 2 is represented the digraph associated to the following structured bilinear system:

A0 =    λ1 λ2 λ3 0 0 λ4 0 λ5 0 0 0 0 λ6 0 0 0 0 0 0 λ7 0 0 0 λ8 0    , A1 =    0 λ9 0 0 0 0 0 0 0 0 0 0 λ10 0 0 0 0 0 0 0 0 0 λ11 λ12 0    , A2 =   
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 λ13 0 λ14 0 0 0    and C = λ15 0 0 0 0 0 0 0 λ16 0 .

Fig. 2. Digraph for example 2

According to the graphic representation of structured linear systems by means of digraphs, we will present in the next section the different tools and functions, which are programmed in LISA.

LISA PROGRAM

LISA was developed in C++, a high level programming language, in order to reduce the computational burden. For the graphical user interface (gui), the library QT 4.0 was chosen. All these features make for LISA a flexible and portable program, which is suitable for Windows as well as Linux environment.

Roughly speaking, the program is divided into two parts: the user interface and the storages and calculation (Graph, StateRecorder, MatrixExporter).

For the purpose of this paper, we will concentrate in only two classes: Graph and MatrixExporter. A very practical group of functions is programmed in Matrix-Exporter class. This class allows the user to export the graph into a state space representation, which can be read and used by Maple (version 10) and Mupad.

Most of the algorithms programmed in LISA are based on a flow graph approach. Digraph representation is suitable for the visual interpretation of some theoretical conditions, which have to be verified by the system to ensure its observability, controllability, etc. However, it is important to note that, from a computational point of view, flow graph representation is more suitable than digraph representation. In LISA, a translation algorithm is used to convert digraphs into flow graphs and/or bipartite graphs. FlowGraph class contains different routines useful to these transformations. Namely, several algorithms are dedicated to find the maximum flow, to solve the minimum cost -maximum flow problem and to find essential vertices in a flow graph.

In this part, we detail some of the most important algorithms programmed in LISA. For this presentation, algorithms are divided into two main classes: basic graph properties (disjoint paths, essential vertices, etc) and structured system properties (input and state observability and fault isolability). The complexity order of every algorithm is provided in function of the total number of vertices N and the total number of edges M .

User interface

In the user interface uiMainWindow, all the "visual effect" functions are programmed. The user must first choose if he works with a linear or bilinear system. Then, the user can create the digraph using the mouse to place vertices, edges and to choose the kind of vertices (state, output, input, fault or disturbance vertices). In the main window, several tools make possible copy, removing, and transformation of the existing vertices. The user can manipulate its graph very easily. Moreover, the digraph can be saved, printed into many formats. Finally, the structured matrices of the digraph can be extracted using Maple or Mupad formats.

Algorithms for basic graph properties

• Finding successors of a vertex subset: This algorithm returns the successor (predecessor) vertices of a given vertex subset. Note that, if directed edge (v 1 , v 2 ) belongs to E then, v 1 is a predecessor of v 2 and v 2 is a successor of v 1 . The algorithm used to accomplish this task is directly derived from the Boost Library (Boost C++ Libraries 2005).

•

Finding predecessors of a vertex subset: Finding predecessors in a graph is equivalent to determine successors in the reversed graph. According to the documentation, the complexity of the used algorithm is O(M ).

•

Finding the maximum number of disjoint paths between two vertex subsets: This algorithm returns the maximal number of disjoint paths between two selected vertex subsets or equivalently the size of the maximal linking between these vertex subsets. To cope with this problem, the digraph has to be transformed into a flow graph. This idea is inspired by the next two theorems (Bang-Jensen 2002): ⊲ Menger's theorem : the maximum number of edge disjoint paths in a graph is equal to the size of the minimum edge cut in that graph, and ⊲ max flow min cut theorem : the size of the minimum edge cut is equal to the value of the maximum flow in a network, where all edges have unit capacity. A direct consequence of the latter theorems is that the maximum flow is equal to the maximum number of edges disjoint paths in a graph. However, in our case, vertex disjoint paths instead of edge disjoint paths are searched. Therefore, we transform the digraph into a flow graph in order to convert the vertex disjoint problem into an edge disjoint problem. Transformation of the original digraph G(•) carries out into two steps: vertex splitting and residual network procedure. Both steps are done by routines in the FlowGraph class. Once the transformation is made, an algorithm to solve the minimum cost -maximum flow problem is implemented. This consists essentially in the Ford Fulkerson algorithm (Bang-Jensen 2002) with a shortest path search at each step. When all the paths are tested, the algorithm stops and the maximum flow is given. There can be a maximum of O(N ) disjoint paths and so path searches. The complexity order of each search is O(N √ M ). Hence the overall complexity order is O(N 2 √ M ).

• essential vertices between two vertex subsets:

The set of essential vertices between two vertex subsets V 1 (source) and V 2 (sink), noted V ess (V 1 , V 2 ), corresponds by definition to vertices present in all maximum V 1 -V 2 linkings. The used algorithm is based on the fact that a removal of an essential vertex causes a reduction in the number of disjoint paths. To determine the essential vertices in a digraph, each vertex is removed and the maximum flow between source and sink is calculated. If the new flow is smaller than the original flow, then the removed vertex is essential. The algorithm requires O(N ) flow calculations. As we have seen, the complexity order of every flow calculation is O(N 2 √ M ). Then, the overall complexity order is O(N 3 √ M ).

• and output minimum separators between two vertex subsets: This algorithm returns input and output separators. A separator is a vertex subset, which contains at least one vertex in every path of a linking. We call minimum separators between V 1 and V 2 any separator having smallest size. According to Menger's Theorem, the latter is equal to the number of dis-joint paths between V 1 and V 2 . There exist two uniquely determined minimum separators between V 1 and V 2 , called input and output separators.

-the minimum input separator is the set of the end vertices of all direct V 1 -V ess (V 1 , V 2 ) paths, -the minimum output separator is the set of the begin vertices of all direct

V ess (V 1 , V 2 )-V 2 paths.
As it is highlighted in [START_REF] Boukhobza | State and input observability analysis for structured linear systems: a graph theoretic approach[END_REF][START_REF] Dion | Generic properties and control of linear structured systems: A survey[END_REF][START_REF] Van Der Woude | The generic number of invariant zeros of a structured linear system[END_REF], these sets play an important role in the analysis of observability property and in the optimization of sensor location for observability and FDI. To find these separators, the maximal set of disjoint paths is firstly calculated. Next, the set of essential vertices is determined. Hence, to find the input (output) separator, it is sufficient to take the essential vertex closer to the source (sink) subset in each disjoint path. Essential vertices are found in O(N 3 √ M ). Finding the vertices on each path, which are also essential vertices, is done in O(N log 2 (N )), hence the overall asymptotic complexity order is O(N 3 √ M ).

• maximal matching between two vertex subsets:

The algorithm determines the size of the maximal matching between two selected vertex subsets (source and sink). A matching is a set of disjoint edges in a bipartite graph. For this algorithm, the equivalence between the maximum flow and the maximal matching in a bipartite graph is considered [START_REF] Murota | Systems Analysis by Graphs and Matroids, Structural Stability and Controllability[END_REF]. To this aim, an algorithm dedicated to the construction of a bipartite flow graph from a directed graph is used. Once the bipartite flow graph is built, the maximum flow algorithm is run over this bipartite flow graph. The conversion of digraph into bipartite flow graph has a complexity equal to O(M + N ) for linear case and O(M + M N ) for bilinear case. The complexity order of the computation of the maximum flow is O(N 2 √ M ), the overall complexity order is O(N 2 √ M ).

In the program's main window, to select the vertex subsets, which are arguments of the different presented functions, the user must use the command depending on whether the vertex subset is an input (in green) or an output (in red) to the algorithm. According to the used algorithm, the selection of one or two vertex subsets is necessary.

Algorithms for properties of structured system

Generic properties of structured systems related to control problems are considered in this section. Based on the works of [START_REF] Boukhobza | State and input observability analysis for structured linear systems: a graph theoretic approach[END_REF], we recall, in a first time, the graphic conditions for the generic input and state observability of structured linear systems. Next, according to the works of (Boukhobza and Hamelin 2006a), observability of structured bilinear systems is treated. Finally, FPRG (Fundamental Problem of Residual Generation) of structured linear systems is introduced. We will briefly discuss algorithms for checking these properties.

Generic input and state observability of structured linear systems

In this paragraph, the conditions for the input and state observability of structured linear systems are given and they are translated to an algorithm-based language.

Input and state observability of structured linear system Σ l Λ requires the definition of the following subsets:

• X 1 is defined as all vertices x i of X such that the number of disjoint paths from {x i } ∪ W ∪ F to Y is greater than the maximal number of disjoint edges from W ∪ F to Y. According to this, X 1 is determined with function disjoint paths presented in section 3.2. • X s contains all vertices in X of all output separators between F ∪ W and Y calculated with function separators and X 0 is the vertex subset defined by X \ (X 1 ∪ X s ).

• Ω 0 contains all vertices v i of F ∪ W such that the maximal matching from v i to X \ (X s ∪ X 0 ) equals zero. This subset is calculated by means of the maximal matching function of 3.2. • Y 0 consists in all essential vertices between W ∪ F ∪ Y and Y. Y 0 is then determined with essential vertices function of 3.2.

The different vertex subsets are computed using respectively the commands , , , , and . In addition, LISA derive the vertex subsets Ω 1 and Y 1 with commands and respectively. Ω 1 is defined as all vertices in W ∪ F \ Ω 0 and Y 1 as all vertices in Y \ Y 0 .

According to these definitions, input and state observability of structured linear systems can be verified if next three conditions are satisfied [START_REF] Boukhobza | State and input observability analysis for structured linear systems: a graph theoretic approach[END_REF]):

Cond1: each vertex in X ∪ F ∪ W is predecessor of vertex set Y. Cond2: all vertices in X 0 and Ω 0 are essential for the linking between Ω 0 and X s ∪ Y 0 . Cond3: the maximal matching in the bipartite graph X ∪ F ∪ W → X ∪ Y is equal to n + q + r.

Command

Observable checks conditions Cond1, Cond2 and Cond3 as follows: To verify condition Cond1, algorithm predecessors is used and then all vertices of X , F and W are searched in the result list of predecessors of Y 0 .

According to the complexity orders associated to the basic graph functions, it results that the complexity order on calculating Cond1 is O(M + N log 2 (N )).

The two main steps for the verification of Cond2 are recapitulated as follows:

(1) Essential vertices between Ω 0 and X s ∪ Y 0 are calculated, (2) If all vertices in X s and Ω 0 are in the previously calculated set, then Cond2 is satisfied.

According to the complexity orders associated to the basic graph functions, it results that the complexity order on calculating Cond2 is O(N 3 √ M ).

To check condition Cond3, it is sufficient to compute the maximal matching between X ∪F ∪W and X ∪Y.

That is, the complexity order of Cond3 is O(N 2 √ M ).

Observability for structured bilinear systems

Graphic conditions for the observability of structured bilinear systems can be found in (Boukhobza and Hamelin 2006a). We can summarize these conditions as follows:

CondA: Each vertex in X is a predecessor of vertex set Y, CondB: The maximal matching in the bipartite graph X → X ′ ∪ Y is equal to n.

For condition CondA, function predecessors implemented in section 3.2 can be used.

To check condition CondB, it is sufficient to compute the maximal matching between X and X ′ ∪ Y. Thus, the complexity order of CondB is O(N M 3/2 ).

Fault Isolability of structured linear systems

An important property in diagnosis context is the fault isolability. LISA allows us to verify this property for the multiple fault case as well as for the single fault case. Conditions for the FPRG solvability are treated in detail in [START_REF] Commault | Fault detection and isolation: a graph approach[END_REF][START_REF] Commault | Observed-based fault detection and isolation for structured systems[END_REF].

Only one condition has to be verified for ensuring fault isolability in a multi-fault context:

Cond.I : a subset of faults F 0 , belonging to F set, is isolable if the number of disjoint paths between F ∪W and Y is equal to the number of disjoint paths between F \ (F 0 ∪ W) and Y and the cardinality of F 0 .

In the single fault context, the following condition must be satisfied to ensure the fault isolability:

Cond.II : a subset of faults F 0 belonging to F set, is isolable if, ∀f i , f j included in F 0 , the number of disjoint paths between {f i , f j } ∪ W ∪ (F \ F 0 ) and Y is greater than the number of disjoint paths between {f j } ∪ W ∪ (F \ F 0 ) and Y.

Command

Isolability checks condition Cond.I and Cond.II using the function disjoint paths presented in section 3.2. Thus, here also, the overall complexity order is O(N 2 √ M ).

Some other options are available as the computation of isolable fault components using command

CONCLUSION

LISA is a program used to display and manipulate linear/bilinear control systems. The systems are displayed in terms of graphs, which can be manipulated by the user. Important concepts, such as observability, fault isolability, etc. have been translated into graph theoretic terms, and were implemented with different graph algorithms.

Since many problems that needed to be solved here are rather expensive in terms of time complexity (i.e. finding disjoint paths), it was crucial to use a programming language with little overhead, close to the machine code level, C++ was chosen to benefit from a much great flexibility (e.g. classes, templates), with only little sacrifice of performance. For the graphical user interface (gui), the library QT 4.0 was chosen, since it is very flexible, portable and easy to use for creating graphical user interfaces.

An exhaustive description of the algorithms developed in LISA was done in this report. Some other properties can be studied using these graphic algorithms [START_REF] Dion | Generic properties and control of linear structured systems: A survey[END_REF][START_REF] Van Der Woude | The generic number of invariant zeros of a structured linear system[END_REF][START_REF] Van Der Woude | Disturbance decoupling with pole placement for structured systems: A graph-theoretic approach[END_REF]. Hence, LISA program is intended to expand its capabilities to analyze other structural properties as controllability, disturbance rejection, etc. Moreover, some specific properties related to Network Controlled Systems are currently in development. Algorithms to check the autonomy of distributed FDI nodes will be soon added as well as algorithms for sensor placement optimization.

  Fig. 1. Digraph for example 1