C E Lemke

BIMATRIX EQUILIBRIUM POINTS AND MATHEMATICAL PROGRAMMING*t

Some simple constructive proofs are given of solutions to the matric system Mz-tD = q;z;;:; O;w!!: O;e.ndz"w = O,forvariouskinds ofdataM,q,whlch embrace the quadratic programming problem and the problem of finding equilibrium points of bimatrix games.

The general scheme is, ass uming non-degeneracy, to generate an adjacent extreme point path leading to a solution. The scheme does not require that some functional be reduced.

A. Introduction

In this paper, simple constructive proofs are given of the existence of solutions for certain systems of the form: Mz-w = q; z � 0; w � 0, when such exist.

The quadratic programming problem and the problem of finding equilibrium points for bimatrix games may be posed in the given form, and thus a general algorithm is given for these problems.

The element of proof adapts the techniques used in the constructive proof of the existence of equilibrium points for bima.trix games [START_REF] Howson | Equilibrium Points of Bi-matrix Games[END_REF] to a wider class of problems. The main characteristic of the technique, combining the familiar concepts of non-degeneracy and extreme-point path, is the generation of an adjacent extreme-point path (which is not based upon a successive-approxima tion scheme) which terminates in an equilibrium point, when such exists. In somewhat more geometrical detail, visualizing the convex polyhedron in z-space of points satisfying: Mz � q; z � 0, the path of points generated consists wholly of points for which z"w = (z),(w),; that is, points for which the sum has at most one (non�negative) summan d (z),(w), positive, for fixed s. It is arranged that the path start on an unbounded edge, which thereafter uniquely defines the path to be traversed, and for particu lar kinds of data M and q the path will end in an equilibrium point.

By way of background, the quadratic programming problem (which includes the linear programming problem) in the well-known "Kuhn-Tucker format" takes the above form. Indeed, the majority of published solution techniques may be described in tenns of the formulation. The bimatrix (or non-zero-sum two-person matrix) game may be cast in the given fonn, as may other "quadratic l ike" types of problems (see , for example, those discusse d in [61). The results t Thi.e work was supported by the Air Force Office of Scientific Research Grant No. AF -A.FOSR-339-63.

given below extend somewhat the class of problems for which an adjacent extreme point path scheme will lead to a solution. Also, additional light (Theorem 5 ) is shed on the results of Chames, Cooper, and Thompson [3 ] touching on the boundedness of the constraint sets of linear programming problems. In pSBSing, the results generalize those contained in a report [START_REF] Dantzig | Positive (Semi-definite) Matrices and Mathematical Progrwnm[END_REF] of Dantzig and Cattle, and a similar scheme of Gomory and Balinski developed for the assignment and transportation problems, [START_REF] Ballnbki | A Primal Method for The Assignment and Trans portation Problems[END_REF] . From the computational point of view, it is supposed that adjacent extreme point algorithms are sufficiently well-known, 1 so that details of computation may be omitted .

B. Existence Proofs

We shall consider sets of the form:

(1) Z = { z: M z -w = q; z > 0; w > 0} c Rn ,
where M is a square matrix of order n, and q, z, and ware columns. Rn is the space of columns of numbers with n components. The notation A > 0 for a matrix means that all components are positive; and A > 0 means that all com ponents are non-negative.

We shall use the notation A r to denote the transpose of A. (A)i denotes the ''t.h column of matrix A ; and (a) • denotes the ith component of column a. We shall use the columns e, and e defined by: (e)i = 1, for all i, and (e,)i = 1;

(ei); = 0, for j � i.

Referring to system ( 1), given z , w = M zq serves always to define w. Dej. 1. A point of Z which satisfies:

(2)

z r w = ( z h(w)l + ( z) 2( w) 2

+ • • • + ( z )n(w),. = 0
is called an equil£brium point.

Since z and ware non-negative, (2) is equivalent to:

(3) (z) , (w) , = 0, for 1 � i < n.

For each i, the pair (z ) ; , ( w) , is a complementary pair, and each is the complement of the other. We shall summarize the relevant well-known facts concerning Z, and conse quences of the ass umption of non-degeneracy.

For each z eRn one obtains a unique matrix N(z) obtained from the matrix (Mr, I) by deleting, for each i, (Mr ) , if and only if (w) , � 0, and (I), if and only if ( z ) , � 0. (Possibly N(z) has no columns.) Dej. 2. A point z e R, is an extreme point of Z if and only if z e Z, and rank N(z) = n. A point z lies on an open edge of Z if and only if z e Z and rank N(z) = n-1. Dej. 3. Z is non-degenerate if and only if whenever A is a matrix obtained from (Mr, I) by deleting some (but not all ) columns, and there is a z eR, such that A = N(z) , then the number of columns of A equals its rank.

a For a description of adjacent extreme point algorithms see (2J, pp. 269-348, Vol. I.

Concerning the existence of equilibrium points, it may be shown (see, for example, [START_REF] Howson | Equilibrium Points of Bi-matrix Games[END_REF]) that z may be perturbed to a set z' :::> z' such that z' is non degenerate and in such a way that if z' has an equilibrium point then Z does.

In any case, non-degeneracy will be explicitly assumed where required.

If Z is non-degenerate, the following holds: if z is an extreme point of Z, then N(z) is non-singular, and if z is a point on an open edge of Z, then N(z) has n-1 columns. It further follows that an extreme point is an end-point of exactly n edges of Z. More precisely, if z is an extreme point of Z, and N = N(z), let N, be obtained from N by deleting its ith column. Then the set of points z e Z for which N, = N(z) is a (non-empty) open edge of Z having z as end point. Otherwise put, in terms of the components of w and z, moving from z along an edge of Z exactly one of those n of the 2n variables (z), and (w), which are zero at z is increased from zero (the other n -1 remaining at zero value), and that edge may be associated with that variable.

Finally, if z is an equilibrium point, by ( 3) N ( z) has at least n columns; hence, by non-degeneracy, has just n columns, and hence is an extreme point.

Hence, if Z is non-degenerate it has a finite nwnber of equilibrium points.

An edge of Z having two end-points is bounded. Its two end-points are adjacent extreme points. (If Z is non-degenerate, two extreme points z1 and z2 of Z are adjacent if and only if N(z1) and N(z,) have just n -1 columns in common).

An edge having just one end-point is unbounded, and will be called a ray of Z. Since z � 0 (i) Z cannot contain an entire line, and (ii) if Z is non-empty it has an extreme point.

Dej. 4. A non-empty connected set consisting of a non-empty class of closed

edges of Z such that no three edges of the class intersect is called an adjacent extreme-point path or more briefly an adjacency path.

Thus, an extreme point contained in an adjacency path of Z meets just one or two edges of the path. If such a point meets just one such edge it will be called an end-point of the path. Thus, an adjacency path has 0, 1, or 2 end-points, and contains 0, 1, or 2 rays of Z. It has 0 end-points if and only if it contains either 0 rays (a closed path) or 2 rays; it has 2 end-points if and only if it has 0 rays; and has 1 end-point if and only if it has 1 ray. Dej. 5. For fixed i, the set z, is the set:

Z,={z:zeZ and z T w=(z),(w)i}.

Hence, Z, is the set of points of Z for which (z) ;( w); = 0, for J . � i; and hence the setS of all equilibrium points of Z is contained in the set z, for each i, and is in fact the intersect over i of these sets.

Theorem 1. For fixed s, if Z is non-degenerate, Z, is either empty or is the union of disjoint adjacency paths of Z. The set S of equilibrium points of Z is precisely the set of end-points of the adjacency paths comprising Z,.

Proof. H z e Z,, then (z),(w), = 0; for i � s. Hence N(z) has n or n-1 columns. Hence z is either an extreme point of Z or lies on an open edge of Z.

H z is on an open edge of Z, then N(z) = N(z) for a.ll points z of that edge, and hence the entire edge is contained in Z,. Since at an end-point of such an edge, just one additional variable is made 0, such end-point is also a point of Z,. Hence, if z. is non-empty, it contains at least one extreme point of Z.

H z is an extreme point of Z, then either (Case I) (z),(w), = 0, or (Case 11)

(z),(w), > 0. In Case I z is an equilibrium point. In this case, for each i, precisely one of the pair (z).:, (w).: is equal to 0. Hence, that edge along which, from z, the zero member of the pair (z),, (w). is increased from 0, is the one and only edge from z contained in Z, . In Case 11, for just one value of i, say i = r � 8, N(z) contains as columns both (MT)r and (l)r ; that is: tOr = Zr = 0. An edge of Z (with end-point z) along which just one of these variables is increased from 0 is contained in z . . The two such edges are the only edges of Z with end-point z contained in Z, .

It remains to point out that an extreme point z in z. lies on one and only one adjacency path of Z of points of Z •.

If an extreme point z in z. is incident with just one edge of points of Z,, that edge is either a ray (in which case it constitutes the desired adjacency path), or is not. If not the other end-point is either an equilibrium point (in which case the edge constitutes the desired path) or is not. If not, there is just one other edge of points of Z, along which one may continue. Continuing in this manner the process terminates either in a ray, or at an equilibrium point, yielding the desired path.

If an extreme point z in Z, is incident with two edges of points of Z,, selecting one of these edges to start, a path is described as in the preceding paragraph, except that the path may return to z, in which case it terminates. If not, a similar portion of the desired adjacency path is swept out starting from the other edge coincident with i, and the two portions constitute the desired path. This concludes the proof.

Existence of E([Uilibrium Poinu

The technique which furnished a constructive proof of the existence of equilib rium points of non-zero sum matrix games [START_REF] Howson | Equilibrium Points of Bi-matrix Games[END_REF] will be adapted, in what follows, to certain other types of sets Z. A main result is contained in Theorem 4.

In the case of the game example, the resultant Z was clearly non-empty. An example similar to this case will illustrate the technique there applied. In other cases, one needs to take account of the possibility that Z is empty. We shall use the more obvious half of the following well-known result (see, for example, [START_REF] Charneb | Management Models and Industrial[END_REF]):

Lemma 2. Z is empty if and only if there exists a u � 0 satisfying:

(5)
MTu � 0; and uTq > 0.

We shall also use the following property of the sets Z, , which is an immediate corollary of Theorem 1 : Theorem 2. Let Z be non-degenerate and have the property that for some s, Z, contains precisely one ray of Z. Then Z has an odd number of equilibrium points.

Proof. Label as Eo the single ray of Z,. The adjacency path of Z of points of z. which contains Eo must terminate in an equilibrium point.

If an adjacency path contained in z. does not contain Eo it is either a closed path (containing no equilibrium points) or has two end-points (which are dis tinct equilibrium points). This concludes the proof.

AB an example, similar to the game case:

Corollary. Let Z be non-degenerate. If q = e, and M> 0, then Z has an odd number of equilibrium points.

Proof. For fixed s, we need merely point out that z. contains only one ray of Z. Consider the non-negative orlhant of points satisfying z � 0. Z is obtained from it by intersecting it with n half-spaces of the form a T z > 1, where a > 0 represents any row of M > 0. The hyperplane aT z = 1 therefore cuts each co ordinate axis, and points of the form:

(6) z = kei' k > 0,
are in Z for k large enough, and in fact, for some k0 > 0, points ( 6) are in Z

for k � ko , and not in Z for k < ko . The ray of points for which k � k0 lies in z, (for each i) and not in Z 1 for j � i. Since that part of Z satisfying aTz = 1 is bounded these are the only rays, and in particular, for fixed s, z. ha.s one and only one ray, completing the proof.

Regarding the number of equilibrium points, there is a general class for which, if Z is non-degenerate, an equilibrium point is unique. Theorem 3. If Z is non-degenerate and M satisfies z�'Mz > 0 (that is, if M is non-negative definite) there is at most one equilibriwn point.

Proof. Let z1 and Z2 be equilibrium points. Set w, = Mz,q, so that w,�'z, = 0, fori = 1, 2. Then:

(7) 0::5 (z,-zl)TM(Zt-Zt) = (%2-Zt)T(tl11-W1) = -(ZtTWl + ZtTW2).

Since all variables are non-negative, this implies:

(8)

Since z, is an equilibrium point, by non-degeneracy each pair (z1 , w1) and

(Zt, Wt) has precisely n zero components. Now the pair (zt + Zt , W t + w2) has at least n positive components. But (8) implies: (zt + z2)�'(w1 + WJ) = 0.

Hence the pair has at most n positive components. Hence, precisely n positive components. Hence the pairs (z1 , Wt) and (z2, w2) have the same components positive. Hence N(z1) = N(z,). Hence Z t = z2, completing the proof.

To attack a wider class of problems, consider the following device.

Let? = (�) where Zo is a scalar variable. Define the set:

(9) z* = {z*: Mz + zoe-w = q; w, z > 0; Zo � 0} c R,.+l.

Define the set:

(10) Z0* = {z* in Z*: z�'w = 0}.

Note that z• is non-empty. In fact, the set Eo* of points satisfying:

point z *. Then ZoWo = 0. If the path were to end in Wo = 0 (hence in Zo > 0), the choice of k would ensure that the equilibrium point lies on a ray of z*. We seek (Theorem 4) conditions on M which will ensure that if this occurs it must be that Z is empty. We shall therefore, from now on, disregard the artificial con• straint (12) and examine the possibility of rays of z* other than Eo* contained in Zo* (i. e., satisfying zrw = 0). Any ray of z* is a set of points satisfying (15), ( 16), and (17), where now z* is an extreme point of z*. we have:

(18) Mu + uoe -v = 0.
Now, if zo = 0, then z is already an equilibrium point of Z. If 2o > 0, then uTq > 0. In this case, a u has been found satisfying the conditions of Lemma 1, and Z is empty. This concludes the proof.

It may be observed that it has not been shown that the conditions (i) and (ii) on M ensure that Eo* is the only ray of z* contained in Z0 * (as in the case of the game example). But the conditions do ensure that, starting from the ray Eo*; one terminates an adjacency path in Zo = 0; that is, in an equilibrium point of Z. This latter statement embodies the suggested computational scheme.

C. Discussion

With regard to Theorem 4, we note that the case for which M satisfies zTMz � 0 for all z, most recently considered by Dantzig and Cottle, is included.

To show that this condition implies (ii) of the statement of Theorem 4, we need only observe that zTMz = !zT(M + MT)z; that M+ MT is therefore symmetric and non-negative definite; and hence that zT(M + MT)z = 0 implies (M + MT)z = 0. We have extended this result to, for example, the case for which M > 0, which evidently satisfies (i) and (ii) of Theorem 4. The hi-matrix game case does not satisfy ( ii) of the theorem.

Rega.rding the computational aspects, we have implied a computational scheme by the specification of a definite adjacency path, and have given no consideration to the question of how this might duplicate previous results. We shall compare our formulation briefly with that of Dantzig and Cottle [START_REF] Dantzig | Positive (Semi-definite) Matrices and Mathematical Progrwnm[END_REF], which we take the liberty of describing in our terms. Our constraints read:

Mz + zoe -w = q; Let w ' = w -�-Dantzig and Cottle apply themselves to the form:

Mz-w' = q; and w ' > -ZQe,

where Zo is taken fixed and Zo > ma.x, ( q) i • tD � 0.

Starting with z = 0 and w' = -q, they proceed to describe an adjacency path retaining z � 0 and w'T z = 0, and aim at success ively reducing the number of negative components of w ' to zero.

In conclusion, we may observe the following result:

Theorem 5. Let Z be non-empty and non-degenerate, and let M be non negative definite. Then Z has at least n rays. Proof. By Theorem 2, Z has a unique equilibrium point. Hence that point is the intersect of the sets z, . For fixed i, that adjacency path of the set z, which contains the equilibrium point must end in a ray belonging to Z, and not to Z 1 for j � i. Since this holds for each i, there are at least n rays.

As an example of Theorem 5, consider the case of linear programming. The matrix A of order m by r is given. Then Z is the set of points • = C) satisfy• mg:

A:e �a;

x � 0, and -A!' y � -b; y � 0.

The 888 ertion of the theorem is that when both of these sets are non-empty, then the number of rays, each of which is a ray either of one set or of the other, is at least m + r. In particular, if one of the sets, say Ax ;;;: :: a; x ;;;: :: 0, is bounded, then the dual set AT y S b; y ;;;: :: 0 has at least m + r rays. This extends the results of Clark 14] and of Charm�, Cooper and Thompson.2

If it is next supposed that the ray is in Z0 *, then ( i + Ou) r ( w + Ov) = 0. Since all quantities are non•negative, this is equivalent to:

(11) z = 0• , zo > Max, (q), ; and w = zoeq, is a ray of z* which is further contained in Zo *.

To apply Theorem 2, we shall add a single constraint. Let z** be the set of points of z* satisfying:

where k is taken large enough so that any extreme point of z* satisfies eTz < k (that is, Wo > 0). The equality constraints for z** in block form become:

(13 )

; where w * = (w);

-e 0 -k Wo so that z** has the form [START_REF] Ballnbki | A Primal Method for The Assignment and Trans portation Problems[END_REF]. Let Zci* be the set of points of Zo * which are con tained in z**. Letting wo play the role of complement of Zo , we are concerned with equilibrium points of z**. z�• is then the set of points of z** satisfying:

If it is ass umed that z* is non-degenerate, the choice of k ensures that z•• is non-degenerate. It may be remarked that if z* is non-degenerate, then Z is, and that if z is non-degenerate, z* may be perturbed so that z* is non-degenerate.

From the computational point of view, the constraint ( 12) is artificial and unnecessary.

Note that Eo* is still a ray of z**. The additional constraint (12) ensures that it is the only ray of z** contained in Z�*. To see this, we proceed as follows:

Points on any ray of z* or of z** will have the form:

(15) z* = t + ()u*• for() ;::: : 0• where t = (�)

and where z* is an extreme point of z* or of z** (whichever is being discussed) ; u* ;e 0; and 8 and Uo are scalar quantities. Setting w = Mz + Zoeq; and v = Mu+ u.oe, we may write:

(16)

M(z + Ou) + (Zo + lhlo)e-(w + 9v) = q.

The conditions f + lhl > 0; fo + 9uo > 0; and w + 8v ;::: : 0 for all 8 � 0 require that:

Then, if the ray is a ray of z**, the condition that eTz < k requires that u = 0. Then u * ;t. 0 requires that Uo > 0. Hence, for ()large enough, one must have that w = w + 8v > 0. Then the condition ZTW = Z T W = 0 for zt * requires that z = 0, and hence that the ray is Eo •.

Hence:

Lemma 2. z•• has an equilibrium point.

Proof. z** satisfies the requirements of Theorem 2.

Next, consider the path of points of Zri, * which terminates in an equilibrium

There are two cases: Case I: u = 0 and Case II: u r6-0. If u = 0, then Uo > 0. As before, we may conclude that the ray is Eo*. Hence, (Case II) we shall suppose that u r! 0. We may then take u so that e"u = 1. Then ( 18) and (19) yield: Lemma 3. A ray of z* contained in Zo * which is not the ray Eo* satisfies:

(20)

We next place conditions on M: Theorem 4. Let Z be non-degenerate. Let M have the property that if u � 0, then:

implies that:

Then, if Z is non-empty, it has an equilibrium point.

Proof. We need only show that, with the conditions of the theorem, the co nditions (20) imply that Z is empty, unless io = 0.

By (i) and ( 20


Michel Batteux
email: michel.batteux@irt-systemx.fr

Tatiana Prosvirnova
email: tatiana.prosvirnova@centralesupelec.fr

MTP Antoine Rauzy
email: antoine.rauzy@ntnu.no

From Models of Structures to Structures of Models

Keywords:

published or not. The documents may come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

The complexity of industrial systems is steadily increasing. To face this complexity the different engineering disciplines have virtualized their contents to a large extent. The design and operation of any modern system involve dozens if not hundreds of models [START_REF] Blanchard | Systems Engineering and Analysis[END_REF]. As systems are complex, one cannot expect models of these systems to be simple. They are complex. Therefore, they need to be organized and structured. The main purpose of this article is to study how to structure models.

Designing models has much to do with designing computer programs. To model, one needs a modeling language; just as to program, one needs a programming language. According to [START_REF] Wirth | Algorithms + Data Structures = Programs[END_REF]: "Algorithms + Data Structures = Programs". We revisited this sentence and applied it to models: "Behaviors + Structures = Models" Most of modeling languages are actually the combination of a mathematical framework, e.g. differential equations (as for Modelica [START_REF] Fritzson | Principles of Object-Oriented Modeling and Simulation with Modelica 2.1[END_REF]) or Mealy machines (as for Lustre [START_REF] Halbwachs | The synchronous dataflow programming language lustre[END_REF]), and constructs to structure models, e.g. a tree-like hierarchy of components. The structure of a model is in general close to the functional or physical architecture of the system it describes. There is however no such a thing as a one-toone correspondence between system and model structures, for different reasons. On one hand, a model is always a specific point of view on the system. It aims at capturing a particular aspect or at evaluating a particular property of that system. Therefore, it abstracts away irrelevant parts of the system and is useful only because it does so. On the other hand, the organization of a model has its own logic that can be quite different from the architecture of the system. It is clear that the choice of the right mathematical framework is of paramount importance to capture this or that physical aspect of the system, and to do it at the suitable level of abstraction. Our thesis is that the productivity of the modeling process stands also in the way models are structured. It is actually thanks to their structures that models can be versioned and configured throughout their life cycle and that knowledge can be capitalized throughout successive projects.

Constructs to structure models derive from those to structure computer programs. In this article we introduce a small modeling language, the so-called S2ML for System Structure Modeling Language, which provides constructs to structure models. The behavioral part is left unspecified, i.e. just represented by terms that are left un-interpreted. The particular syntax of the language has no much importance. What is truly important is to ensure a one-to-one correspondence between the concepts and the syntactic constructs of the language. A large class of actual modeling languages can be (re)constructed by plugging their behavioral constructs into S2ML, i.e. by interpreting these terms.

Our contribution is therefore multiple. First, it studies model structuring at a conceptual level, i.e. independently of any concrete modeling formalism. Second, it gives an overview of structural constructs of modeling languages used in systems engineering. Third, it introduces S2ML that can be seen as the skeleton for many particular modeling languages. Finally, it illustrates the syntax, semantics and pragmatics of the different constructs of the language rather than to give a formal and complete definition of these constructs. The reader interested in a detailed specification can refer to [START_REF] Batteux | System Structure Modeling Language (S2ML)[END_REF].

The remainder of this article is organized as follows. Section II presents an example used throughout the article to illustrate S2ML constructs. Section III introduces basic elements of S2ML: blocks, ports and connections, and shows how they can be interpreted by different system engineering modeling languages. Section IV gives an overview of structural constructs and discusses the reuse of modeling components via blocks, classes and the associated mechanisms. Section V concludes the article by carrying out a general discussion about model design process and the role of languages such as S2ML in this process.

II. ILLUSTRATIVE EXAMPLE

To illustrate S2ML concepts and notions presented throughout this article, we shall use an illustrative example inspired from safety engineering. The considered system is a simplified reactor cooling system. It consists of a reactor whose temperature and pressure must be maintained within acceptable limits thanks to a cooling system.

Fig. 1 gives a partial view of the physical architecture of this system. The main function of this system is to maintain the temperature of the reactor in a given range [T min , T max ]. The temperature sensors measure the temperature of the reactor and provide the value to the controller.

The cooling water comes from a tank and is provided to the reactor via two different lines: a main one and a backup one, which can be used in case of failures. These two lines are composed of three actuators: a pump and two valves.

If the temperature gets lower than T min , the controller commands the closing of the valve "ValveM1". If it gets higher than T max then the controller commands the opening of this valve. If the valve "ValveM1" fails to open (or if the pump "PumpM" is failed), the temperature and the pressure in the reactor increase. Pressure sensors detect the excessive pressure and send the value to the controller which switches to the backup line and commands the opening of the valve "ValveS1".

The view is simplified and only partial because it does not show other classical elements of such systems, for instance, steam generator or pressurizer. Nevertheless, it is a good view of a classical system with strong safety requirements to take into account: the system should be designed so that no single failure could lead to the loss of the capability to cool the reactor.

III. BASIC ELEMENTS: BLOCKS, PORTS AND CONNECTIONS

The block is the basic S2ML modeling unit. A block has a name and may contain ports and connections (and several other modeling elements).

The three terms "block", "port" and "connection" are borrowed to the SysML terminology [START_REF] Friedenthal | A Practical Guide to SysML: The Systems Modeling Language[END_REF], although they are used with a slightly different meaning. In the S2ML context, a port is something that has a name and that holds some atomic information. It is similar to variables in programming languages, but also of modeling languages such as Modelica, Lustre or AltaRica. A connection is a relation between ports (we shall come back to this issue later).

A. Graphical Representation

In Fig. 1, ports are represented by black filled squares, connections by bold lines and blocks are delimited with light lines and are usually represented by rectangles. For instance, the rectangle "ValveM1" represents a block with three ports. Names of ports are not indicated on the figure so not to overload the graphics. Ports of the block "ValveM1" are connected to ports of the blocks "Tank", "Controller" and "PumpM". The represented model contains several other blocks, with some of them containing others (explained later c.f. Section IV-A).

In Fig. 1, all ports are represented on the border of blocks. This is by no means mandatory. Ports can be internal to a block. Fig. 2 shows for instance an internal view of the block "ValveM1". The port "state" is internal.

B. Textual Representation

Graphical representations, as those of Fig. 1 and Fig. 2, are excellent communication means. However, they quickly reach their limit: as soon as the model ceases to be simple, they can only represent it partially. In other words, the model exists independently of its graphical representation. Moreover, there may be several graphical representations of the same concept, each having its own interest, depending on the context. That is the reason why S2ML is primarily a textual language. As previously pointed out, the particular syntax for this language is not important. What is really important is to ensure a oneto-one correspondence between the concepts and the syntactic constructs of the language.

The S2ML code for the block "ValveM1" is described in Fig. 3. It declares a block with four ports and two connections. The first connection is anonymous whereas the second is named. Blocks, ports and connections can carry information via lists of attributes. An attribute is a pair (name, value), where value is a string.

C. Interpretation

In S2ML, ports and connections are interpreted by themselves, i.e. a connection has no other meaning than "there is a relation between these ports". In other words, S2ML is a purely syntactic language. A language that would use S2ML as a structuring paradigm would redefine the syntax of ports and connections and more importantly would assign them a semantics. For instance, a S2ML version of Modelica would define connections as differential equations. A S2ML version of Petri nets (see e.g. [START_REF] Murata | Petri Nets: Properties, Analysis and Applications[END_REF] for an introduction) would define ports as places and connections as transitions. A S2ML version of AltaRica [START_REF] Prosvirnova | The AltaRica 3.0 project for model-based safety assessment[END_REF] would define ports as variables and events, and connections as transitions and assertions. As an illustration, Table I summarizes how different modeling languages can interprete blocks, ports and connections.

IV. MODELS OF STRUCTURES

In this section we give an overview of stuctural constructs of modeling languages used in systems engineering and show how these constructs can be represented in S2ML.

A. Composition

The simpliest structuring relation is the composition: a system composes a component means that the component "ispart-of" the system.

Fig. 1 shows a hierarchical description: the block "Reactor-CoolantSystem" is composed of the blocks "Reactor", "Controller", "MainLine" and "BackupLine". The block "Main-Line" contains the blocks "Tank", "ValveM1", "PumpM" and "ValveM2".

Many modeling languages implement composition. For example, it is the case of SysML [START_REF] Friedenthal | A Practical Guide to SysML: The Systems Modeling Language[END_REF], AADL [START_REF] Feiler | The Architecture Analysis & Design Language (AADL): An Introduction[END_REF], Modelica [START_REF] Fritzson | Principles of Object-Oriented Modeling and Simulation with Modelica 2.1[END_REF] and all the versions of AltaRica [START_REF] Arnold | The AltaRica language and its semantics[END_REF], [START_REF] Prosvirnova | The AltaRica 3.0 project for model-based safety assessment[END_REF].

In S2ML, to compose a block in another block, it is sufficient to declare the former inside the latter.

The declaration of the block "ReactorCoolantSystem" could be as presented Fig. 4: the block "ReactorCoolantSystem" composes the blocks as well as the connections. The port "p" of block "B" is referred to as "B.p" as in most of the object-oriented languages (it is prefixed by the name of its parent).

In S2ML, it is possible to refer to a port (and more generally any modeling element) of a block nested at any hierarchical level, therefore "crossing the wall" of composing blocks. As connections represent any relations, there is actually no reason to limit the reference mechanism as if ports were physical interfaces. Note finally that each block is a name space: the blocks "ValveM1" and "PumpM" can both declare a port "input".

B. Component reuse via classes

S2ML blocks are prototypes, in the sense of object and prototype oriented programming languages ( [START_REF] Abadi | A Theory of Objects[END_REF], [START_REF] Noble | Prototype-Based Programming: Concepts, Languages and Applications[END_REF]). A block has normally a unique occurrence. There are cases however where the system under study embeds several identical components. In our illustrative example, pumps "PumpM" and "PumpS" may be identical. It would be of course possible to duplicate the code of the two pumps, but this would be both error prone and confusing. A first solution to address this problem is to create a class for pumps and to instantiate it twice in the model.

A class is a separate "on-the-shelf" block (with possibly a full hierarchy of blocks underneath) that can be reused in models via the instantiation mechanism. The code of the reactor coolant system could be as depicted in Fig. 5. This code is equivalent to the one that would declare two identical blocks for pumps "PumpM" and "PumpS".

C. Component reuse via cloning

In addition to the class/instance mechanism to reuse components, S2ML provides another way to automatically duplicate code (a part of a model). It is called cloning. For instance, the code for the block "Reactor" could be as follows.

block Reactor block TemperatureSensors // body of the TemperatureSensors end clones TemperatureSensors as PressureSensors; // remainder of the body of Reactor end

In the above code, the block "Reactor" defines a block named "TemperatureSensors" and clones it to get the block "PressureSensors". In this example, both blocks are local to the model and thus do not require any genericity.

The cloning directive is extremely powerful in conjunction with aggregation (discussed later). The S2ML specification document [START_REF] Batteux | System Structure Modeling Language (S2ML)[END_REF] provides a graphical representation for cloning.

D. Inheritance

In some cases it is necessary to modify or extend the characteristics of a modeling component/class without changing its nature. In these cases, composition is not really suitable because we would like to be able to substitute the modified/extended component for any occurrence of the original one.

It can be achieved using the inheritance mechanism. Inheritance describes a "is-a" relation between modeling units.

As an illustration, consider the valves of our illustrative example. The actual implementation for these valves could derive from an abstract description of what is the interface of a modeling component for a valve. This inheritance mechanism makes it possible to build step wisely the model.

As any object-oriented language, S2ML provides a construct to implement the inheritance mechanism: the "extends" directive. The code to model the valves of our illustrative example could thus be as follows. In the context of modeling languages, inheritance can be seen as a particular type of composition, where no prefix is added to the composed/inherited class or block. S2ML allows multiple inheritance, with all the usual warnings about it.

Object-oriented languages, such as AADL, SysML, Modelica and the new version of AltaRica, AltaRica 3.0, implement the inheritance mechanism.

E. Aggregation

We have seen that composition describes a "is-part-of" relation. This relation assumes that a component cannot belong to two different super-components (parents). There are cases however where the same component is used in several places or to contribute to different functions of the system. This kind of "uses" relations can be described by means of aggregation.

As an illustration, Fig. 1 shows a physical breakdown of the system: it is made of four sub-systems and some connections; these sub-systems are further decomposed, and so on. This structural breakdown is correct, although it mixes physical and functional descriptions. It is probably not the only decomposition of the system that would be used. The two lines for instance are more functional groupings than physical groupings. The first is the main and the second is the backup. Usually for such parts, failures occur on actuators (pumps or valves). The tank can be assumed as a passive component. Thus, only one tank exists and is shared by the two lines. Therefore, we need to be able to describe hierarchical breakdowns with branches sharing components. This is the very purpose of the notion of aggregation. The S2ML construct for aggregation is the "embeds-as" directive.

The code describing the "Reactor Coolant System" could be as follows. In the code above, the block "ReactorCoolantSystem" defines a block "Tank", which is then aggregated by the blocks "MainLine" and "BackupLine".

The aggregation mechanism is extremely powerful. It makes it possible to embed into the same model different views, including functional and physical views. It can also be used to share universal objects (e.g. physical constants) in a clean way.

Very few modeling languages implement aggregation. For instance, it is the case of SysML, where aggregation relation between blocks is represented as a white filled diamond. The new version of AltaRica, AltaRica 3.0, also implements aggregation by means of the "embeds-as" directive.

F. Blocks/Prototypes versus Classes

As we have seen earlier, S2ML provides two types of containers: blocks, which are prototypes in the sense of prototypeoriented programming, and classes (see e.g. [START_REF] Abadi | A Theory of Objects[END_REF] and [START_REF] Noble | Prototype-Based Programming: Concepts, Languages and Applications[END_REF] for discussions about these paradigms). Classes are well suited for "on-the-shelf", generic, stabilized knowledge. Prototypes are well suited for the "on-going" work.

The C-K theory of Hatchuel and Weill (see e.g. [START_REF] Hatchuel | C-k design theory: an advanced formulation[END_REF]) formalizes this idea in the context of engineering design. Their dialectic applies to the model engineering as well: the model (made of blocks/prototypes) is the space C of concepts, i.e. a sandbox in which new knowledge is maturing. Classes are the space K of stabilized knowledge.

The class/instance mechanism is without any doubt interesting to define "on-the-shelf", re-useable modeling components such as those for valves or pumps in our illustrative example. The fantastic richness of modeling languages such as Modelica or Matlab/Simulink stands for a great part in the wide choices of dedicated libraries.

However, when authoring a model (graphically or not), we may want to modify the code for the cooling coil while editing the entire model. With a pure object-oriented language, this is not possible. Classes are flat: one cannot modify a class via its instance, even if this instance is unique. We may call that the "a box in a box in a box" issue.

Moreover, what can be re-used depends on the level of abstraction of the model. On the one hand, models designed with simulation languages such as Modelica or Matlab/Simulink, stand at physical component level. For these models, re-use means mainly re-use of modeling components. On the other hand, models standing at system level, typically designed with modeling languages such as SysML or AltaRica [START_REF] Prosvirnova | The AltaRica 3.0 project for model-based safety assessment[END_REF] shows a rather different picture. At system level, each model is unique. Re-use can be however obtained by cloning and adjusting models. In other words, there are prototypical systems/models, in the sense of [START_REF] Lakoff | Women, Fire, and Dangerous Things: What Categories Reveal About the Mind[END_REF], but no generic system model from which other system/model could be derived just by setting some parameters. What can be re-used is thus modeling patterns (in the sense of design patterns [START_REF] Gamma | Design Patterns : Elements of Reusable Object-Oriented Software. Addison-Wesley professional computing series[END_REF]) rather than modeling components.

The above discussion explains why S2ML provides both prototypes and classes. The comparison between classes and blocks is summarized in Table II.

G. Unfolding and Flattening

Any S2ML model is semantically equivalent to an unfolded one, i.e. a model made of a hierarchy of nested/aggregated blocks, connections and ports. In the unfolded model all the instantiated/inherited classes and "clones" directives are transformed into blocks and all the references/paths to model elements are resolved according to the rewriting rules, the socalled unfolding rules.

Any hierarchical S2ML model is also semantically equivalent to a flat one, i.e. a model made of a unique block with ports and connections. As in languages such as Modelica, Lustre or AltaRica, this flat model is obtained by applying recursively rewriting rules, the so-called flattening rules. These rules "remove the walls" of containers (blocks and instances of classes). In the S2ML specification document, they are formally defined in a Structural Operational Semantics style (see e.g. [START_REF] Plotkin | The origins of structural operational semantics[END_REF]).

H. Summary

As we have seen in this section, prototypes, classes, composition ("is-part-of" relation), inheritance ("is-a" relation) and aggregation ("uses" relation) are the fundamental concepts of model structuring. They originate from mechanisms to structure programs.

Table III presents an overview of structural constructs of some modeling languages used in systems engineering.

V. CONCLUSION

In this article, we introduced the domain specific language S2ML. S2ML provides a minimal, yet extremely powerful, set of concepts to describe functional and physical breakdowns of systems on the one hand, and to structure models on the other hand. The design of S2ML obeys the rule: "concepts should come first". S2ML is an object-oriented language that embeds some prototype-oriented features as well. The authors strongly believe that prototype orientation is the most suitable structuring paradigm for models at system level of abstraction. As a future work, it would be interesting to see how to embed S2ML to the Eclipse Modeling Framework [START_REF] Merks | EMF: Eclipse Modeling Framework (2nd Edition)[END_REF]. Developments around S2ML can be useful in two different ways. First, they can contribute to increase the awareness of the systems engineering community on the topics of model structuring. They can inspire system modeling language designers and provide them with conceptual tools to ensure the convergence of the structuring part of modeling languages. Second, S2ML can be used directly to support the model synchronization process, i.e. the process by which one can ensure that two possibly heterogeneous models are "speaking" about the same system. Two models, possibly written into two different languages, cannot in general be compared directly. The idea is thus to abstract them into a pivot language, e.g. S2ML, and to compare their abstractions. The development of a full S2ML modeling and simulation environment, including libraries of comparators and abstractors for different modeling languages is, at the time we write these lines, under specification.

S2ML is already used as a structuring paradigm for modeling formalisms dedicated to safety analyses. The future version of the Open-PSA model exchange format (see e.g. [START_REF] Epstein | Open-PSA Model Exchange format[END_REF] for the previous version) relies on S2ML to define the meta-model of classical modeling formalisms such as Fault Trees, Reliability Block Diagrams, Event Trees and Markov chains (see e.g. [START_REF] Rausand | System Reliability Theory: Models, Statistical Methods, and Applications[END_REF] for an introductory book). In addition, the high-level modeling language AltaRica 3.0 (see e.g. [START_REF] Prosvirnova | The AltaRica 3.0 project for model-based safety assessment[END_REF]) makes a full use of S2ML as a structuring paradigm while Stochastic Guarded Transition Systems [START_REF] Rauzy | Guarded transition systems: a new states/events formalism for reliability studies[END_REF] provide the underlying mathematical framework of the language. As of today, AltaRica 3.0 is probably the most advanced language to support Model-Based Safety Assessment, the declension of Model-Based System Engineering for Reliability, Availability, Maintainability and Safety (RAMS) studies. At the time we write these lines, both Open-PSA and AltaRica 3.0 are still under development. However, both projects are sufficiently mature to draw preliminary conclusions that show the pertinence of S2ML.

S2ML is a very powerful formalism to describe systems breakdowns as well as structures of models. Many widely used modeling languages could be re-casted so to adopt S2ML as a structuring paradigm. There is however an intrinsic limitation to S2ML expressive power: S2ML assumes that the architecture of the system (and/or of the model) does not change (significantly) throughout the mission time. Systems with evolving architecture, i.e. systems whose number of components and interactions between components change through the mission time, in other words systems of systems (see e.g. [START_REF] Maier | Architecting principles for systems-of-systems[END_REF]), are much more difficult to model. Extending S2ML ideas and principles to this kind of systems would be an extremely important step forward.

Fig. 1 .

 1 Fig. 1. A simplified reactor coolant system (partial view).

Fig. 2 .

 2 Fig. 2. Internal view of the block "ValveM1".

Fig. 3 .

 3 Fig. 3. S2ML code for the block "ValveM1".

Fig. 4 .

 4 Fig. 4. S2ML code for composition.

Fig. 5 .

 5 Fig. 5. S2ML code for class declaration and instantiation.