Annual progress report ALAPEDES
Contract ERB-FMRX-CT96-0074

Alapedes is the acronym for ALgebraic Approach to Performance Evaluation of Discrete Event Systems. The theory of discrete event systems deals with dynamical systems that are event-driven as opposed to time-driven; usually their state variables take on only discrete values. Several approaches exist to study discrete event systems; of these the ``logical'' approach, where the ordering of the events is of interest, and the ``timed'' approach, where the timing of the events is also of interest for the mainstreams form the research within Alapedes. In both streams the structure of algebraic systems plays a dominant rôle.

In Alapedes eight partners from four different countries work together in ten strongly interrelated subprojects, to develop new theory, applications and software tools within the algebraic approach to discrete event systems. Alapedes is a network in the framework of the TMR programme, European Commission, Directorate General XII, network contract no. ERB-FMRX-CT96-0074.

1.2. The report

This report describes the activities of the network Alapedes during the second year of its official existence (the commencement date was October 1, 1996). The report is written to inform the European Union on the progress of the Alapedes network, but equally serves as an information source on Alapedes for the network partners (and maybe for interested outsiders as well).

The report consists of five parts. This first (Section 0) serves as an introduction to it; included are the acronyms of the partners and a list of the subprojects.

Section 1 describes the progress of the Alapedes network against the objectives set out in the work programme. It gives the scientific results (1.1) per subproject, relating them, whenever possible, to the text in the first annual report, gives scientific highlights (1.2) for the general reader, reports on networking and coordination activities undertaken (1.3), introduces the researchers funded by the network (1.4), gives information about contacts with industry (1.5), and lists difficulties experienced with environmental constraints (1.6).

Section 2 gives factual information on the network activities. The scientific specialities of the partners are listed (2.1), according to the codes that the European Union uses, the research staff involved is listed (2.2), introducing the researchers funded by the network (2.3), presents publications that have emerged or will emerge from the network activities (2.4) and acknowledges secondments between partners (2.5).

Section 3 stresses the collaboration within the Alapedes network. In it a list of joint publications is given (3.1) and a description of the way contacts and coordination were sustained (3.2).

The report has nine appendices. Appendix A lists the names of all (mostly) researchers involved in Alapedes in one way or another. Appendix B gives an extensive list of publications. Appendix C gives additional information about the network, that is not explicitly required according to the reporting guidelines. Similarly, one finds in Appendix D the programme of the Alapedes workshop held near Cagliari (Italy), in Appendix E the programme of the Alapedes software course at INRIA-Rocquencourt (France), in Appendix F the programme of the workshop on non-expansive systems in Bristol (United Kingdom), in Appendix G the programme of the Spring School in Noirmoutier (France), in Appendix H the contributions and the attendants from the Alapedes network to the WODES'98 near Cagliari (Italy), and, finally, in Appendix I the programme of a Tropical day in Paris (France).

1.3. Legend

1.3.1. Partners

The Alapedes network consists of eight partners (one of which comprises two locations). They are frequently referred to, in which the following acronyms are utilized.

TUD: - Technische Universiteit Delft, Delft, Nederland;
ARMINES: - Association pour la Recherche et le Développement des Méthodes et Processus Industriels, École Nationale Supérieure des Mines de Paris (ENSMP), Fontainebleau, France;
INRIA: - Institut National de Recherche en Informatique et en Automatique has two research teams involved in Alapedes:
KUL: - Katholieke Universiteit Leuven, Leuven, België;
HP: - Hewlett Packard Limited, Basic Research Institute in the Mathematical Sciences (BRIMS), Bristol, United Kingdom;
LIAFA: (formerly LITP) - Université Paris VII, Laboratoire d'Informatique Algorithmique: Fondements et Applications, Paris, France;
RUG: - Rij ksuniversiteit Groningen, Groningen, Nederland;
ULG: - Université de Liège, Liège, Belgique;

1.3.2. Subprojects

The Alapedes network is structured into ten closely related subprojects. Whenever possible activities and accomplishments in the sequel will be reported upon in relation with these subprojects; for ease of reference they are summarized below (the text utilizes the accompanying codes).


Cross-Fertilisation on the Theoretical Level
T-1	Representation problems
T-2	Stability problems
T-3	Optimisation problems
T-4	Control of automata
T-5	Large systems problems
Applications
A-1	Transportation systems
A-2	Manufacturing systems
A-3	Communication networks
Software
S-1	Investigation and critical analysis of existing software
S-2	Development of new software

1.3.3. Glossary

In the report the term (Alapedes) partner is used for the organizations that were listed in § 1.3.1; students preparing their graduation are called undergraduates, graduated students working for a doctoral degree are referred to as postgraduates, researchers having a doctoral degree are called postdocs; the term Alapedes researcher is reserved for those (mostly postdocs) who are paid by the network funds, and Alapedes member applies to researchers working for some Alapedes partner, but paid from other funds.

2. Progress

Various activities, in which Alapedes-researchers and -members were heavily involved, took place during the second year of the official existence of the Alapedes-network. The `École de Printemps' in Noirmoutier, the software course at INRIA-Rocquencourt, the HP-workshop in Bristol and the Alapedes-convention near Cagliari (glued to the WODES'98 workshop) can be mentioned here.

Essentially the only serious concern is attracting qualified post-docs. Many young researchers prefer a tenured job to temporary postdoc positions and and such tenured jobs are amply available, probably due to the general economic prosperity. Thus not all partners managed to fill their positions.

2.1. Scientific results

The description of the scientific results is structured according to the ten subprojects. Activities which belong to more than one subproject, have been mentioned under one of them and a reference from the other subproject(s) to that description is given. Frequently names are mentioned; names with an Alapedes connection appear in Appendix A where more particulars, such as home institution and the rôle in Alapedes can be found. Next to these descriptions, there is a separate one (§ 2.1.11) on milestones. Cross-references with the previous annual progress report, when appropriate, are given.

2.1.1. T-1

Last year the team at KUL has continued its research on the minimal state space realization problem in the (max,+)-algebra. First they have studied the sequence of matrix powers of boolean matrices in the (max,+)-algebra. The results have then been used to derive upper bounds for the length of the cycles of the ultimate periodic behaviour of a max-linear time-invariant discrete event system and to derive a lower bound for the minimal system order. Furthermore, in cooperation with the ULG team, the KUL team has proved that the boolean minimal realization problem in the (max,+)-algebra is decidable and can be solved in a time that is bounded from above by a function that is exponential in the minimal system order.

Finally, the KUL team also did some research on the connection between minimal realization and state space transformations in the (max,+) algebra.

Publications within Alapedes which are relevant to this part of the subproject are [42, 45, 65, 58, 64, 43, 147, 47].

The INRIA-Rocquencourt and ARMINES teams investigate the problem of state space representation of (max,+)-linear systems from a geometric point of view. This contribution is also relevant to T-5 (last year it was classified in §2.1.5, but T-1 (see §2.1.1) is now predominant). Last year, results where obtained for the projection on the image of a ((max,+)-)linear operator parallel to the `kernel' of another linear operator. This year, these results started being applied to controllability and observability matrices.

Preliminary results have been obtained which define a dynamic equation, (min,max,+) a priori rather than (max,+), but which `lives' on a minimal set, from the set-theoretic point of view. It remains to understand how minimality in the set-theoretic sense is related to minimality in terms of dimension of the state space, and when such an approach provides (max,+)-linear equations.

A publication within Alapedes which is relevant to this part of the subproject is [38].

A recent chapter of a long story is the quest for algebraic models of timed behaviours. In earlier work, timed behaviours of simple timed discrete event systems were represented by dater functions, which associate the number of occurrences of a repetitive event with its physical execution time, or dually, by counter functions, which are, in loose terms, the inverses of such maps.

More recently, some more general models, seeing a dater function as a map from a free monoid (set of event sequences) to the physical time were developed. This formalism with `noncommutative logical time' is well adapted to the modelling and analysis of systems with concurrent access to a set of shared resources, which are beyond the scope of older models. It allows us to reduce some performance evaluation problems to basic algebraic problems concerning semigroups of matrices and automata with coefficients over the max-plus semirings. What we loose by considering a `noncommutative logical time' is the symmetry between counting and dating.

To regain symmetry, a more general model was developed: a behaviour is just seen as a relation (or transduction) between two noncommutative monoids, whose elements represent event sequences, and time instants, respectively. Then, the inversion of time and events just amounts to the inversion of a rational transduction: one of the oldest and most elementary results of the field. But, to model the natural monotonicity features of physical behaviours, one has to consider special transductions which are closed under the division ordering.

Publications within Alapedes which are relevant to this part of the subproject are [14, 15]. The work has been presented at the WODES'98 meeting as well (see Appendix H).

Baccelli and Gaujal (with Simon (INRIA-Sophia Antipolis)) have worked on the modelling of on several tasks with preemption performed by a robot, using marked graphs. Then, with the help of the (max,+)-representation, they were able to derive simple tests to check real time constraints on those tasks.

Gaujal and Jean-Marie (with Siegel) have introduced a new class of Petri nets (non-ambiguous Petri nets) that combine a fairly high power of description with ease of simulation. This has been applied to the simulation of a ATM backbone model.

A publication within Alapedes which is relevant to this part of the subproject is [89].

Blondel has been working with De Schutter and De Vries on the minimal boolean realization problem for discrete event systems. This collaboration has lead to a joint publication in a journal and a presentation at a conference.

Related to this, Blondel with the postdoc Portier has started an investigation of the complexity of the realization problem for positive systems.

Publications within Alapedes which are relevant to this part of the subproject are [43, 47]. Van der Woude, together with Van der Bol (an undergraduate at TUD who did this research as his graduation project) studied the basic problem of the definition of (minimal) rank of a matrix in the (max,+)-algebra, which is basic to many realization approaches. Their work is related to the theory of nonnegative matrices. A similar approach had been taken by De Schutter.

Publications within Alapedes which are relevant to this part of the subproject are [25, 45].

2.1.2. T-2

The study on the existence of cycle time vectors, already mentioned in the previous annual report, has progressed very well.

Collaborative work in this phase of Alapedes led to the solution of the Duality Conjecture for min-max functions by Gaubert and Gunawardena, and its extension to a broader class of topical functions.

The cycle time vector of D-A-D functions was computed, using their combinatorial structure, by Katirtzoglou. It was not possible to apply the results obtained by Gaubert and Gunawardena to this class of non-expansive maps.

Future work will concentrate on going beyond the Duality Conjecture, in particular to understanding the higher-order asymptotics associated to the cycle time and their relationship to fixed points, and on extending the calculation of the cycle time to a larger class of topical functions.

Publications within Alapedes which are relevant to this part of the subproject are [81, 82, 112, 113].

Also work in this direction was done at TUD. Due to the early departure of the Alapedes researcher Perennes (who got a tenured position in France), this approach did not (yet?) lead to a publication.

Van der Woude and Subiono are studying the structural existence of eigenvalues in bipartite (min,max,+)-systems, under some mild conditions on the structure of the systems. They found simple proofs of algorithms (see § 2.1.6) to determine eigenvalues and corresponding eigenvectors in an iterative way.

Cardol has completed his graduate project on the spectral theory of matrices in (max,+) under the supervision of Blondel. Gaubert was part of the thesis committee.

Blondel has pursued his work with Gaubert on complexity of Lyapunov exponents computation. A joint paper is currently being written.

2.1.3. T-3

Akian, Bapat and Gaubert consider the asymptotics of the Perron eigenvalue and eigenvector of irreducible nonnegative matrices whose entries have a geometric dependence on a large parameter. The first term of the asymptotic expansion of these spectral elements can be seen as the solution of a spectral problem in a semifield of jets, which generalizes the (max,+)-algebra. They state a `Perron-Frobenius theorem' in this semifield, which allows them to characterize the first term of this expansion in some non-singular cases. The general case involves an aggregation procedure à la Wentzell-Freidlin.

Once more, this work shows the deep duality existing between probabilities and optimization theory and the interest to explore it more deeply.

A publication within Alapedes which is relevant to this part of the subproject is [2].

Heidergott introduced the concept of weak differentiability for random matrices and thereby obtained closed-form analytical expressions for derivatives of functions of random matrices. He developed a calculus of weak differentiation of random matrices which is similar to the standard calculus of differentiation. In particular, the formalism enables one to (algebraically) calculate derivatives of finite time horizon performance measures of stochastic event graphs, such as (max,+)-linear systems. The resulting derivatives provide unbiased estimators for the gradients of finite time horizon performance measures. For various types of (max,+)-linear systems, these estimators have been computed explicitly.

Further research is focused on the extensions of this approach to the study of analyticity of (max,+)-linear systems. As soon as one is able to compute a gradient, optimization can be undertaken.

Publications within Alapedes which are relevant to this part of the subproject are [104, 103, 106, 101, 100, 98, 102, 99].

The work of Hong at INRIA-Sophia Antipolis focuses on the analyticity of the limiting behaviour of a class of dynamical systems defined by iteration of non-expansive random operators. The analyticity is understood in function of the parameters which govern the law of the operators. The proofs are based on contraction with respect to certain projective semi-norms. As soon as the analytic development with respect to a parameter proves successful optimization with respect to this parameter becomes possible.

The INRIA-Sophia Antipolis team first concentrates on the analyticity of Lyapunov exponents. Such exponents can be seen as functionals of a Bernoulli process whenever each operator is sampled independently between two possible values. The main concern is then the domain of analyticity of these exponents seen as functions of the parameter of the Bernoulli law.

Several examples are considered, including Lyapunov exponents associated with products of random matrices both in the conventional algebra, and in the (max,+)\ semi-field, and Lyapunov exponents associated with non-linear dynamical systems arising in stochastic control. For the class of reducible operators, the team also addresses the issue of analyticity of the expectation of functionals of the limiting behaviour in function of the parameters of the law, and connects this with contraction properties with respect to the supremum norm.

Several applications are given to the analyticity of stationary response times in certain queueing networks in function of the intensity of the arrival process and the paramaters of the law of the service times.

A publication within Alapedes which is relevant to this part of the subproject is [12]. For related work on queues with time varying service times or labouring under cross traffic see [1, 7].

Gaujal (with Altman and Hordijk (Leiden)) has been working on optimal admission control in (max,+)-systems under sample information. Under rather general assumptions, they show monotonicity properties of the optimal policy.

Gaujal (with Altman, Hordijk and Bhulai) has been involved with computations of the optimal arrival process in a single buffer queue. This also includes some work on cases with redundancy or block arrivals.

Gaujal (with Altman and Hordijk) has been involved with ordering binary sequences in terms of regularity and their applications in control policies.

Publications within Alapedes which are relevant to this part of the subproject are [5, 6, 3, 86, 4].

Also work on optimal scheduling of a railway subnetwork has been done in collaboration with SNCF. For more details see § 2.1.6. See also §2.1.11.

Mairesse and Vuillon (LIAFA) have studied jointly the relation between heap models and Sturmian sequences. In a heap model, pieces pile up according to the Tetris game mechanism. The problem is to explicitly give an optimal sequence. That is to specify an infinite sequence of pieces minimizing the asymptotic average height of the heap.

In a heap model with two pieces, they prove that there always exists an optimal sequence which is either periodic or Sturmian. They completely characterize the cases where this optimal sequence is periodic and the ones where it is Sturmian. The proof is constructive, providing an explicit optimal sequence and uses fundamental tools introduced by Gaubert and Mairesse and reported in § 2.1.7. They show an application for a system of two processes sharing a resource, and prove that a greedy schedule is not always optimal.

At TUD, Van Egmond recently also started to investigate the heaps-of-pieces approach to train scheduling.

2.1.4. T-4

Klimann, undergraduate at LIAFA, worked on the following problem: find the supremum element

X

which verifies

AX<=X+B

, with constraint

X<=K

, where

A

B

and

K

are languages or, more generally, formal power series. This problem and its solution are formally inspired from retroaction in control theory. The aim of retroaction is to abolish some imperfections; for this, a part of the output is reinjected in the input. Then, one must find what is the best initial input. This amounts to finding the maximal vector space

X

which verifies

AX<=X+B

and

X<=K

, where

A

represents the link between the input and its variations with time,

B

a parameter which the user controls and

K

the link between input and output.

The problem is classical in the case of finite dimensional vector spaces and it can be easily solved by iteration on dimensions. It is natural to try to extend this result to the case of modules and semi-modules, and in particular to formal power series with coefficients over an idempotent semiring (like for instance the (max,+)-algebra).

Gastin has been working on formal power series in partially commuting variables. Some results, in direct continuation of the ones reported in the previous annual progress report, have been obtained. A celebrated theorem by Schützenberger states the equivalence between star-free and periodic formal power series in non-commuting variables. This result has been extended to the case of partially commuting variables. A research report on the subject is in preparation.

The relevance of this work to Alapedes is due to the central role of trace monoids in the study of a large class of DES: 1-bounded Petri nets, see Gaubert and Mairesse.

A publication within Alapedes which is relevant to this part of the subproject is [84].

2.1.5. T-5

Most of the effort towards subproject T-5 has been executed in combination with subproject T-1. The description given in § 2.1.1 is partly applicable to this subproject as well.

The INRIA-Rocquencourt team studies networks of storage systems having dynamic programming equations with the (max,+) product form property. Indeed, for such kind of system the number of states increases exponentially with the number of stocks (that is: the size of the network). It is crucial to obtain simple analytical results even for a oversimplified model. The team tries to adapt known results in probability to the (max,+)-situation.

One can associate to a network of $m$ queues a random walk on ^m. The (min,+)\ analogue of a random walk is a decision walk where to each transition -- which corresponds to a decision -- is associated a cost instead of a probability. In this (min,+) context, the dynamic programming equation plays the role of the Kolmogorov equation. It is well known that the invariant measure of a Jackson network can be computed explicitly. The (min,+)-analogue consists in computing the optimal cost to go from a node $x$ to a node $y$ in the state space. It is a kind of geodesic problem on ^m with a field of admissible displacements corresponding to the admissible routings of the network. It is shown that this geodesic problem can be solved by a standard flow problem under the hypothesis of shift invariance of the transition costs. Moreover, for some particular ends ( $x$ , $y$ ) of the geodesic, an explicit formula, analogous to the standard product form, giving the minimal distance between $x$ and $y$ , is obtained. The result has been presented in the `École de Printemps d'Informatique Théorique' in Noirmoutier.

This work is a part of the thesis work of Fall and will be continued by generalizing the hypotheses under which the result is true. For the time being, theses hypotheses are too restrictive in comparison with those of probabilities.

A publication within Alapedes which is relevant to this part of the subproject is [72].

2.1.6. A-1

The relationship between the (max,+)-algebra at the theory side and timetables of railway systems at the applications side, already mentioned in the previous annual progress report, has become very strong.

Subiono and Olsder, at TUD, have finished this study for the three train types (intercity, fast and local trains). This led to a model with a dimension of several hundreds. Initially, it was being thought that the numerical algorithms would need considerable time on a workstation, but now that the power algorithm has been refined (by Subiono), and another algorithm, referred to as the `Howard algorithm', has been developed by Gaubert et al., computation time does not seem to be an issue anymore. The power algorithm has been extended to (min,max,+)-systems by Subiono and Van der Woude jointly.

Van Egmond (TUD) started his graduate study in September, 1997. His first application concerned the question of how the (max,+)-algebra could be applied for the synchronization of traffic-lights. This work is different from the work done at KUL as described in the previous annual progress report: whereas KUL focuses on one intersection, Van Egmond considers the interconnections of all intersections in a city.

Van Egmond's main activities take place in the framework of the TUD `Seamless Multimodal Mobility' project. In this project all kinds of problems which arise when using different modes of transport are investigated, such as the design of transfer points, predicting mobility demand and, as in his project, synchronisation of operations. The goal of his research is to predict the consequences of decisions of traffic controllers, and to design optimal decision rules. Eventually this will be put together in a decision support system for traffic controllers. Some of the results obtained were presented in Göteborg.

Recently another postgraduate, Soto Y Koelemeij er, started May 15, 1998, within the same project `Seamless Multimodal Mobility'. Some recent contacts with the Netherlands air carrier KLM raised the belief that the (max,+)-algebra approach might also be useful to some aerospace problems. This will be investigated by Soto Y Koelemeij er.

Heidergott's work has been described in § 2.1.3; it is strongly influenced by the applications mentioned above. His fundamental contributions focus on stochastic extensions and sensitivity issues.

The fact that a consortium of Netherlands railway companies financially supports two new postgraduate positions (one for the faculty of Civil Engineering and one for the subfaculty of Technical Mathematics) within the context of the work done in subproject A-1, shows that the approach is regarded as useful to real users. Currently a postgraduate is sollicited to fulfill the new position.

Publications within Alapedes which are relevant to this part of the subproject are [105, 109, 108, 26, 70, 69, 139, 131, 132, 123]

The KUL team has derived a method to compute optimal control strategies for timetable-driven transportation networks in the presence of breakdowns. They developed a heuristic algorithm to devise a control policy that minimize the total delay on the one hand and that guarantees as many transfer connections as possible. Furthermore, the KUL team has also studied optimal control schemes for traffic-light controlled intersections.

Publications within Alapedes which are relevant to this part of the subproject are [50, 59, 62, 148].

Work in collaboration with SNCF, ARMINES and INRIA-Rocquencourt around application of (max,+)-modelling to railway systems has been done. The purpose of this work was to obtain indicators for robust functioning of a railway subsystem. A model, based on heaps of pieces, has been achieved. The possibility of computing the optimal schedule of departure of trains at each station has been explored. The railway system can be seen as a jobshop problem (the jobs are the routes of the trains, the resources are the train and the railway lines). The method developed by Gaubert, Hautecloque Raysz and Mairesse, described in the previous Alapedes report, has been used.

This work was done as the four months training course of Eydoux in the École Polytechnique. It should be continued to obtain a clear conclusion about the interest of the approach for railway systems.

A publication within Alapedes which is relevant to this part of the subproject is [71].

2.1.7. A-2

Cohen is still looking for industrial contacts that would provide an interesting application. For the time being, he has been busy with software developments and will anyway incorporate in Scilab -- see 2.1.10 below -- pieces of software which address generic problems of manufacturing, such as e.g.\ resource optimization.

In a joint effort by LIAFA and INRIA-Rocquencourt, Gaubert and Mairesse have continued their work on heaps of pieces. In previous work, finalised and accepted for publication this year, they showed that 1-bounded Petri nets (that include jobshops, one of the basic models in manufacturing) can be represented using heaps of pieces and (max,+)-automata. They have been working on the problem of exact computation of the worst case, optimal case and average case behaviour. In a research report currently in preparation, they show that the worst case problem is completely solvable for any heap model, that the optimal case problem is completely solvable for heap models with pieces of integer heights, and that the average case problem is completely solvable for heap models with pieces of integer heights and complete dependence alphabets.

Further work, on a closely related problem, is described in § 2.1.4.

A publication within Alapedes which is relevant to this part of the subproject is [84].

An internal working group has been functioning during the year within LIAFA. The group was meeting every three weeks and the topic was heap models. For details see § 2.3.4.

A publication within Alapedes which is relevant to this part of the subproject is [120].

2.1.8. A-3

Some basic communication networks can be modelled using heaps of pieces (see also § 2.1.3). These networks are telephone networks with links having capacity one (a piece in the Tetris game corresponds to a phone call). Hence the work carried out on heaps of pieces, and recalled in § 2.1.7, is also relevant for communication networks.

A publication within Alapedes which is relevant to this part of the subproject is [84].

2.1.9. S-1

The subproject S-1 (investigation and critical analysis of existing software) was completed during the first year of the network.

2.1.10. S-2

The developments on Scilab-

(max,+)

described in the last year's report have been pursued this year. In particular, it has been necessary to adapt the (max,+)\ extension to Scilab, version 2.4: this version has been especially designed to allow such extensions to be incorporated more easily in the future.

New algorithms have been added, e.g. Howard's algorithm to compute eigenvalues, which seems the fastest such algorithm at this moment.

A first version of this software -- and of Semigroupe and Ers as well - has been presented to Alapedes participants in a two-day software introductory course held at INRIA-Rocquencourt in June 1998. This course was also an opportunity for all contributors to examine the possibility of setting up interfaces to Semigroupe and Ers from within Scilab, which is a first step to integrating all packages in a unique graphical user interface.

The (max,+)-developments of Scilab have been somewhat slowed down by the fact that Michael Mc Gettrick , who held an Alapedes postdoc position with ARMINES, decided to leave the network at the end of May, 1998, while it was initially planned that he would continue with this project at INRIA-Rocquencourt for at least one year. At this moment, both teams -- INRIA-Rocquencourt and ARMINES -- are looking for new postdocs to take over.

Specifically, the work to add a toolbox, to Scilab, for performance evaluation, resource optimization and optimal scheduling, dedicated to production systems, has still not been started. This work will have to be taken up by a future researcher in the network.

A first preliminary version of a Scilab toolbox dedicated to numerical (max,+)\ computation works with the new version 2.4 of Scilab. The previous Michael Mc Gettrick version was experimental and done by modifying the version 2.2 of Scilab. The new version is an independent toolbox which can be linked to standard and future versions of Scilab.

In the course of the year, the Ers toolbox for modelling of discrete event systems has received a large number of improvements. All graphical user interfaces have been rewritten and now use the widely distributed public domain environment Tcl/Tk. Tools based on algebraic manipulations now use sparse matrix representations, resulting in improved performance. The bounds developed by M. Brilman (Université Grenoble) for (max,+)-systems have been incorporated, as well as bounds on (max,+) matrix products recently obtained by Alain Jean-Marie.

Collaboration between Heidergott and Jean-Marie led to the implementation of a gradient estimation algorithm in the Ers toolbox. Bridges have been built towards Scilab, and a stronger integration between the two tools is expected during next year. The first public release of the Ers package will take place during the month of October 1998.

Pin is currently developing a program called Semigroupe. Its specificity is to be able to deal with semigroups which are not necessarily defined as transformation semigroups (as opposed to Automate for instance). In Semigroupe, one can work as well with semigroups of relations, semigroups of matrices, etc. In particular, one can deal with matrices over commutative semirings such as the boolean semiring, $N$ _max, $N$ _min and $(N, + , )$ . One can also compute the syntactic semigroup and the ordered syntactic semigroup of a subset of the given semigroup.

The functionalities already implemented (with some original algorithms) are (given the generators of the semigroup): list of the elements, relations, idempotents, computation of the minimal ideal, Green's classes, semigroup inverses and weak inverses, local subsemigroups, Rhodes kernel, representative of an element, and numerous variety tests: commutativity, nilpotence, idempotence, aperiodicity, and so on.

This program was demonstrated during the `École de Printemps' in Noirmoutier and during the software course at INRIA-Rocquencourt. An informal meeting between Pin, Gaubert (INRIA), Quadrat (INRIA) and Gohen (ARMINES) was held in June, 1998 at INRIA. The purpose was to discuss the interfacing of Semigroupe with Scilab. Progress has been made in that respect. The interfacing is expected to be completed in 1998-1999.

It should be recalled that Scilab is a free program developed by INRIA and whose functionalities are close to those of the commercial program Matlab. Furthermore, there have been fruitful interactions with Jean-Marie (INRIA) who wrote a graphical interface for drawing Green classes. This interface will be incorporated to Semigroupe as well.

In connection with this program, Heam and Nicaud, both postgraduates, are respectively developing and analyzing new algorithms for semigroups and automata. Nicaud works on the average behaviour of automata. He tries to obtain some results about the average space complexity of basic operations, and average time complexity of some well-known algorithms (like Hopcroft's or Brzozowski's minimization algorithms). He has shown that the average case complexity of basic operations can be very different from their worst case complexity. Such an analysis can lead to new efficient algorithms. For example he has found a minimization algorithm for group automata which is linear in the average case (the worst case complexity is in O( $n log n$ )). He is also implementing in GAP the basic kernel of an automata package, using both new and classical algorithms.

They participated to the Lisboa GAP meeting. The purpose of this meeting was a general presentation of GAP (Groups, Algorithms, and Programming). Pfeiffer, one of the main GAP programmers, presented a package to deal with monoids. The meeting also contained several practical programming sessions conducted by experienced GAP programmers.

Pin presented a paper to ICALP, a general purpose conference in theoretical computer science. One of the papers presented in this conference, `On the determination of weighted finite automata' is of special interest for the Alapedes\ community, because it may give some important hints on the still open problem of minimizing (max,+)-automata.

2.1.11. Milestones

The book about idempotency [90], edited by one of the Alapedes teamleaders, Gunawardena, has appeared in 1998.

A book on open problems in mathematical systems theory [], edited by another Alapedes teamleader, Blondel, has appeared by the end op 1998; it contains two contributions on (max,+)-problems (written by Alapedes members).

The 26 0.7exth spring school of computer science has been organized by Pin, Mairesse and Gaubert. It was held on the Île de Noirmoutier, France, between May 4 and May 7, 1998. Its title was "Algèbres Max-Plus et applications en Informatique et Automatique". Almost every Alapedes partner was represented by 2 or 3 teammembers.

A two days workshop dedicated to software for algebraic evaluation of discrete event systems, developed inside the Alapedes program, has been organized at INRIA-Rocquencourt, 1998, June 18-19. The purpose of the meeting was the initiation to the three sofware tools: Scilab, Ers and Semigroupe. See further in § 2.3.4.

>From July 20 to July 22, 1998 a workshop `Nonexpansive Maps: Theory and Applications' was held in HP-BRIMS. The participants were leading experts from inside and outside the Alapedes network. During this workshop researchers from different viewpoints were brought together, in order to exchange ideas and to explore ways to develop a unified approach to the theory of non-expansive maps.

Alapedes organized a two days workshop for its researchers in Chia, near Cagliari on Sardinia, Italy. Details are given in Appendix D. The reason for this location was that the Workshop on Discrete Event Systems, WODES'98, was organized there as well, and that therefore many Alapedes researchers and members would participate in this workshop. In fact part of WODES'98 is advocated as pertaining to the Alapedes convention. See further Appendix H.

Burbanks is employed on the EPSRC (UK) postdoctoral research grant, awarded jointly to BRIMS/HP (Gunawardena) and Cambridge (Sparrow), will work for three years (from July 1998) on `Dynamics of non-expansive maps: theory and application to discrete event systems'. See also the previous annual progress report.

In the framework of the TUD project `Seamless Multimodal Mobility', already mentioned in the previous annual progress report, two postgraduates (Van Egmond and Soto Y Koelemeij er) started their research. A consortium of railway companies in the Netherlands also financially supports one postgraduate position in the TUD team. Olsder is currently looking for a suitable candidate.

2.2. Scientific highlights

A substantial part of the applications sofar is centred around timetables of railway systems. In France and in the Netherlands this has led to an official collaboration in terms of contracts and user group meetings.

A new area of application, via traffic control through the synchronization of traffic-lights (in which `grüne Welle' plays a rôle), has been investigated. The examples considered sofar are somewhat academic and contain fewer realistic results due to the fact that traffic behaviour is harder to describe than movements of trains.

On the theoretical level, progress has been made on several fronts.

So far, most results on representation of $(max,+)$ linear systems, whether in the state space or in the input-output (transfer function) description, have been obtained by using algebraic techniques. In the last two years, we have tried to have another, more geometric oriented, view of these problems. In classical system theory, the geometric point of view, which directly considers such fundamental objects as the reachable states -- image of the reachability matrix --, the unobservable states -- kernel of the observability matrix --, etc., have proved useful to understand representation problems, but also control synthesis problems, such as disturbance rejection by feedback for example. It turns out that the geometry of $(max,+)$ -linear operators is much more involved than that of their counterparts in classical vector spaces. Some progress has however been made in understanding such structures and we have started applying this better knowledge to system theoretic problems.

The understanding of relationships between (max,+)-systems, (min,max,+)systems and the encompassing class of non-expansive systems is improving. New and improved algorithms have been obtained which can calculate eigenvalues, eigenvectors and related items of large-size systems very fast. Another result worthwhile mentioning is the solution of the Duality Conjecture for (min,max,+) functions by Gaubert and Gunawardena.

The visualisation of some (max,+)-problems by means of heaps of pieces -- compare the Tetris game -- has greatly improved our insight in such problems.

The work in studying suitable definitions of a derivative in a stochastic context for (max,+)-expressions in order to obtain sensitivity results, looks promising.

2.3. Networking and coordination

2.3.1. General coordination

2.3.1.1. E-mail

Day-to-day contact between Alapedes members within different partners is established by electronic mail. The medium is used evenly for scientific purposes (spreading knowledge and tools) and for coordination (preparation of meetings, reporting).

2.3.1.2. Database

A database has partly been set up (both in physical and in electronic form) with publications in the Alapedes subject field. It is managed by the coordinator's team and is aimed to mediate and spread knowledge gained in the Alapedes setting. More emphasis must be put on making the database complete.

2.3.1.3. Vacancies

Vacancies are a point of concern. It turns out to be difficult to find qualified candidates for all positions available. Quite often young postgraduates with a citizenship, which does not allow participation in the TMR programme, apply (for instance from Malta, Cyprus, the Ukraine and Bulgaria).

The coordinator played a rôle in the search for postdocs to fill in the positions available in the network. At some occasions positions were advertised for Alapedes as a whole, for instance during the WODES'98 at Cagliari, Italy. In several other cases the network partners advertised their own positions more specifically. The issue of what has been done in searching suitable candidates for vacant positions for Alapedes researchers is treated in § 2.4.1.

In the proposal it was written that Alapedes postdocs should be given the opportunity to work with at least two partners. We considered this issue in our management meeting during the Alapedes convention near Cagliari. Such switching homebases between partners have become kind of a non-issue because either some partners have not yet attracted a (or the) postdoc, or during the employment with the first partner, the postdoc leaves the project because he or she accepts a tenured job.

2.3.1.4. Formal contacts

Through the network coordinator (TUD) several questions were asked to the European Commission via its project officer. They concerned the switching of homebases by Alapedes researchers halfway the contract period, refunding of travelling costs outside Europe and the organization of the midterm review by the European Commission.

2.3.1.5. Sponsoring

The Alapedes network sponsored the École de Printemps in Noirmoutier. See also § 2.3.4.

2.3.2. Management committee

The management committee met once: on August 29, 1998 in Chia, near Cagliari. Progress within the subprojects, possibilities for joint publications, vacancies for Alapedes researchers and homebase exchanges for the postdocs were discussed, and plans were set out for the period to come. Minutes of such meetings become available for internal use.

2.3.3. Plenary meeting

In August, 1998, all Alapedes members met near Cagliari for a plenary meeting, annex subproject meetings for every subproject. The meeting was given the form of a scientific workshop with presentations by Alapedes members with ample time for discussions and was partially combined with the WODES conference, also held in Cagliari, on discrete event systems as well. The meeting was open to researchers from outside the network. One of the presentations -- by a researcher from Sankt-Peterburg -- was cancelled. The programme of and attendance with the workshop can be found in Appendix D.

The workshop grossly stimulated mutual contacts, showed the state of the art within the Alapedes research as a whole and made clear what connections exist between the subprojects and teams within Alapedes. The Alapedes convention, that comprised a management meeting (see under § 2.3.2) as well, has been successful and marked the end of the second Alapedes year.

The combination of the Alapedes convention with another scientific meeting on a neighbouring field -- though attractive from the outset -- will not be pursued in the future, as the progress within the Alapedes network is easier to experience without a tiring preceding workshop.

2.3.4. Subproject meetings

Many meetings have taken place. An overview of most of them can be found in Appendix C, while details on some specific ones have been included in further appendices. In the sequel they are summarized. Because of the frequency of bilateral, incidental and informal contacts, and of the workshops organized, further, separate and formal, subproject meetings are regarded as superfluous.

2.3.4.1. Software course

A two days workshop dedicated to software for algebraic evaluation of discrete event systems, developed inside the Alapedes program, has been organized at INRIA-Rocquencourt, June 18-19, 1998. The purpose of the meeting was the initiation to the three software tools: Scilab, Ers and Semigroupe. This initiation consisted of an introductory talk for each sofware tool, followed by practice on a computer in manipulations with the help of this software.

The workshop attracted quite a few researchers mainly from within the network and was quite successful, also because it stimulated further contacts. For a list of attendants and one of the presentations given the reader is referred to Appendix E.

2.3.4.2. Non-expansive maps

HP-BRIMS hosted a workshop `Nonexpansive Maps: Theory and Applications', from July 20 to July 22 in Bristol. The participants were leading experts from inside and outside the Alapedes network. During this workshop researchers from different viewpoints were brought together, in order to exchange ideas and to explore ways to develop a unified approach to the theory of non-expansive maps.

The workshop stimulated the participants greatly. For the programme and a list of attendants the reader is referred to Appendix F; abstracts of the presentations are available upon request.

2.3.4.3. Noirmoutier

The `French Spring Schools in Theoretical Computer Science' are organized each year on a different topic. The choice of the different subjects of the schools is made by Maurice Nivat (LIAFA). Each school has a specific scientific committee. The 1998 `26 0.7exme École de Printemps d'Informatique Théorique' was co-organised between LIAFA and INRIA. It was held in Île de Noirmoutier, France, between May 4 and May 7, 1998. The topic was `The (max,+) algebra and its applications in computer science and automatic control'. The scientific committee consisted of Gaubert (INRIA), Loiseau (Ircyn, Nantes), Mairesse (LIAFA) and Pin (LIAFA). To the best of our knowledge, it was the first summer school specifically dedicated to the (max,+)-algebra. It was oriented toward young researchers and non-specialist wanting to obtain a solid knowledge on this new area.

The school experienced a great success, with 65 participants, including many Alapedes members and postdocs. The involvement of Alapedes in the school is emphasized by the fact that 7 of the 12 speakers are members of the network. The school received a financial support from Alapedes (as well as from INRIA, CNRS, EDF, GDR-Automatique). All the information about this school is available on the net at address http://www.inria.fr/maxplus. The programme and a list of the speakers can be found in Appendix G.

2.3.4.4. WODES'98

Directly before the Alapedes convention the biannual Workshop on Discrete Event Systems (WODES'98) took place, at the same venue near Cagliari (Italy). The workshop attracted many researchers within the broader field of discrete event systems, of whom several from outside Europe, and presented a good platform for the exchange of questions, ideas, approaches and developments, not only from the algebraic point of view, but also featuring process algebras, Petri nets, formal languages as well as logic.

The opportunity was also used to make the Alapedes network better known in this wider research field. For a list of contributions by researchers from Alapedes see Appendix H.

2.3.4.5. Heap models

Close collaboration, in regard of the subprojects A-2 and A-3, took place between Gaubert (INRIA-Rocquencourt) and LIAFA, via the LIAFA working group on discrete event systems on heap models. The regular participants were Choffrut, Gastin, Kliman, Pin, Teodosiu, Mairesse, Vuillon (LIAFA), Sakarovitch (ENST) and Gaubert (INRIA). The meetings each consisted in the exposition of one or several open questions, followed by informal discussions on the latter. Among the topics which have been discussed, one can mention: Inverse free semigroups (Choffrut), Ring and complete heap models (Mairesse), Heap models and formal power series (Krob), Trace monoids (Teodosiu).

2.3.4.6. Software development

All the teams involved in subproject S-2 have worked in close contact, and very often jointly, with each other. In particular, meetings have been held between INRIA-Rocquencourt, ARMINES and LIAFA on the integration of Semigroupe in Scilab, see § 2.1.10.

2.3.4.7. Tropical Algebra

Several other opportunities for the teams to meet each other are being exploited, of which the sixth meeting of the French (CNRS) working group ``Tropical Algebra'' on December 3-4, 1997, in Paris, deserve to be acknowledged, where quite a few Alapedes members met. Gaubert is one of the organizers. Blondel also attended the meeting. For the programme see Appendix I. At http://amadeus.inria.fr/TROPICAL/ full information on this working group is accessible.

2.3.5. Further networking

2.3.5.1. Internet

At the address http://www.cs.rug.nl/~rein/alapedes/alapedes.html Alapedes presents itself on Internet. The pages contain the research objectives, approach and work plan, schedules and milestones, a list of participants, an overview of meetings and an advertisement for postdocs and postgraduates. Furthermore, the body of the previous annual progress report is available there. A brochure aiming at a general public is included as well.

2.3.5.2. Conferences

Alapedes members meet each other frequently at conferences outside the network. In this respect the Conference on Mathematical Theory of Networks and Systems (MTNS) in Padova, Italy, June, 1998, the Summer School on the Modelling and Verification of Parallel Processes (MOVEP) in Nantes, France, July 6-9, 1998, the IFAC Conference on System Structure and Control (SSC'98) in Nantes, France, July 8-9, 1998, and the Fourth Workshop on Discrete Event Systems (WODES'98) in Chia (near Cagliari), Italy, August 26-28, 1998, are worth mentioning. Not only costs are reduced by meeting this way, the combination of project meetings with other scientific events is more efficient; furthermore, doing so provides a better basis for dissemination of results and to promote the network. The Alapedes network will hence continue to schedule subproject meetings in combination with other events.

Cohen was invited as one of the three plenary speakers at the IFAC System Structure and Control Conference in Nantes, see [38], $(max,+)$ linear systems to an audience of experts of (classical) linear systems: this is another sign of the Alapedes network main topics being recognized as a new branch of system theory.

In parallel with this international conference in Nantes, there was another French event taking place more or less at the same time, but with an international participation of speakers: this event, called MOVEP (École d'Été de MOdélisation et VÉrification de processus Parallèles), is more oriented towards students. Gaubert was one of the speakers.

2.3.5.3. Theses

Several instances of co-supervised theses foster networking within Alapedes. Cohen was one of the referees of Menguy's thesis. Olsder was also in the jury. Also, the graduate thesis of Cardol (ULG) in September, 1998 on the spectral theory of matrices in the (max,+)-algebra (with Blondel as supervisor and Gaubert as member of the jury, and that of Van der Bol (TUD) the basic problem of the definition of (minimal) rank of a matrix in the (max,+)-algebra are worth mentioning.

2.4. Researchers

2.4.1. Publication of vacant positions

Vacancies related to the Alapedes project have been published or made known via:

http://www.cs.rug.nl/~rein/alapedes/alapedes.html;
Cordis http://www.cordis.lu/tmr/src/mat741.htm;
e-letter on Systems, Control and Signal processing;
e-letter on discrete event systems (echong@ecn.purdue.edu);
Ela-list (electronic newsletter in linear algebra);
The Times Educational Supplement;
mailing (by Blondel) to 200 mathematics departments of European universities;
posting at the conferences CDC 1997 and MTNS 1998 and discussion with prospective candidates at these conferences;
Blondel's web page: http://www.ulg.ac.be/mathsys/blondel/position.html;
LIAFA's web page: http://www.liafa.jussieu.fr/;
e-mail (by Mairesse) to about 2000 selected addresses;
letters (by Mairesse) to 50 selected laboratories;
Petri Net mailing list;
Discrete Mathematics (DMANET) mailing list;
Discrete Events newsletter (IEEE working goup on DES); and
announcement during the Noirmoutier Spring school.

Furthermore informal networks and accidental contacts are used to sollicit potential candidates on an individual basis.

2.4.2. Dissemination of applications

Applications were assembled by the coordinating partner. Some Alapedes partners (ULG, LIAFA, INRIA-Sophia Antipolis) sollicited specifically for vacancies they have and communicated relevant applications throughout the network.

The network has the intention to reallocate postdocs at least once during the duration of the network (thus after one or two years) over the Alapedes partners. Because of difficulties in solliciting (see § 2.6) and in tying postdocs with a temporary position to the network this intention has not been concretized yet. Moreover, two Alapedes reseachers (Perennes and De Vries) left the network for a tenured position, while the contact with a third (Mc Gettrick) ceased.

2.4.3. Researchers paid from the network

A list of Alapedes researchers can be found in § 3.3 and in Appendix A, where also a table of all other researchers involved in Alapedes can be found.

2.4.3.1. Integration

Alapedes researchers partly enter the network with a background that differs from the Alapedes theme. Integration in the network is quite successful. This is partly due to the local scientific environment, where they can usually participate in projects that the institutes where they are employed are involved in, but a good part also by the cooperation between the partners, of which Appendix C gives a good impression and by meetings such as that in Waterford (see § 2.3.3 and Appendix D).

2.4.3.2. Stéphane Perennes

Per October 1, 1997 Stéphane Perennes left TUD and the network. Contact with him still exists, though he also left the field of discrete event systems. He worked with Olsder on determination of a upperbound on the period of non-expansive mappings. This lead to a publication at the IFAC Conference on System Structure and Control in Nantes, France. Another joint topic was on iterations of (min,max,+)-functions, which unfortunately, due to the departure of Stéphane Perennes, never was finished.

A publication by Stéphane Perennes was [129].

2.4.3.3. Bernd Heidergott

Analysis of stochastic (max,plus)-systems is an active research area. Bernd Heidergott focuses on optimisation of stochastic (max,+)-systems where the optimisation is carried out to optimize a certain performance characteristic of a given (max,+)-system. He introduced the concept of weak differentiability for random matrices and thereby obtained closed-form analytical expressions for derivatives of functions of random matrices; he developed a calculus of weak differentiation of random matrices which is similar to the standard calculus of differentiation.

Further research is focused on extensions to the study of analyticity of (max,+)-linear systems. The emphasis of his contribution lies in subprojects T-3 and A-1. Bernd Heidergott will be active as Alapedes researcher till August 1, 1999.

Publications by Bernd Heidergott are [105, 104, 103, 106, 101, 100, 98, 102, 109, 99, 108].

2.4.3.4. Michael Mc Gettrick

Michael Mc Gettrick stayed with ARMINES from January 1, 1997 to May 31, 1998 (17 months). His activities were relevant to subprojects S-2 and T-1. Outcomes of his work concern a joint paper at the WODES'98 plus pieces of Scilab software.

Publications by Michael Mc Gettrick are [30, 132].

2.4.3.5. Remco de Vries

Remco de Vries did research on minimal realization and state space transformations in the (max,+)-algebra. Together with Blondel and De Schutter he participated in a joint research effort in connection with the boolean minimal realization problem. Furthermore, De Vries has also developed a heuristic algorithm for the optimal control of connections in train networks. At September 1, 1998, Remco de Vries left the network to take up a tenured position at an institution outside the network.

Publications by Remco de Vries are [147, 45, 148].

2.4.3.6. Eleni Katirtzoglou

Eleni Katirtzoglou joined BRIMS in November, 1996 in order to work within the framework of the Alapedes research network. Her research goal was and is to study the cycle time vector of non-expansive maps and to investigate its relation with fixed points. So far she has been able to compute the cycle time vector of a special class of non-expansive maps, called D-A-D functions, due to their relation to a matrix scaling problem.

Publications by Eleni Katirtzoglou are [112, 113].

2.4.3.7. Sam Lifshes

Since August 1, 1997, Sam Lifshes works at RUG on problems concerning control of hybrid systems. His approach is to use monadic logic in the search of appropriate control strategies that may be regarded as branches in a binary tree.

A publication by Sam Lifshes is [115].

2.4.3.8. vacancy ARMINES

After the prospect -- mentioned in the previous annual progress report -- to attract a suitable candidate (from Southampton) proved not to be materialized, ARMINES still was left with a vacancy. ARMINES is looking for another postdoc for 12 months to work on applications (manufacturing and transportation) and to contribute to the software.

2.4.3.9. vacancy INRIA-Sophia Antipolis

The team within INRIA-Sophia Antipolis expects to be reinforced by the appointment of one or even two Alapedes researchers shortly after the reporting period ends.

2.4.3.10. vacancy LIAFA

Applications are invited for a one or two years postdoc position beginning in October, 1998. At the end of the period reported upon the vacancy still exists.

2.4.3.11. vacancy ULG

ULG has interviewed five candidates. The interviews were linked with scientific exchanges and visits to other parts of the university (both in the mathematics institute and the electrical engineering department). The candidate Natacha Portier will start on November 1, 1998. It is likely that ULG will also make a second appointment.

2.4.3.12. vacancy KUL

The departure of Remco de Vries caused a vacancy in the KUL team. It is in contact with prospective candidates, and is confident to find a further Alapedes researcher.

2.5. Interactions with industry

The TUD is involved in a project called ``Seamless Multimodal Mobility'', a joint effort by various faculties among which the faculty of Information Technology and Systems (subfaculty of Mathematics, where the Alapedes researchers are employed). Thence two fully supported postgraduate positions have become available on topics that are closely related to Alapedes. An intensive interaction takes place.

One of the other faculties is the one of Civil Engineering and a joint contract has been signed with Railned, the scientific company directly related to the Netherlands railway company. This leads to one more postgraduate position. This third position has not yet been filled in. See further under § 2.1.11.

Contacts have been initiated between the INRIA-Rocquencourt and ARMINES teams on the one hand, and SNCF, the French National Railway Company, on the other hand. The contact is through Gauyacq, who is with the `Service de la Recherche de la SNCF'. They have tried to identify issues which are relevant to the techniques developed in the Alapedes project and which may be of interest for SNCF too. It turns out that the kind of problem tackled by the TUD team with the Netherlands' railway company, namely, the study and optimization of periodic timetables, is not directly of interest for SNCF. A undergraduate student, Eydoux of the École Polytechnique near Paris, in connection with the Alapedes partners spent three months at SNCF trying to formulate scheduling problems arising in the real-time operation of a railway line in the Paris suburbs and to look for possible resolution algorithms.

In the same effort to investigate this domain of application of railway systems, Mc Gettrick attended a workshop on railway problems in Braunschweig, Germany (FORMS'98: `Workshop on Formal Specification of Train Control Systems in Europe') on May 12-13, 1998. It turns out that the problems advocated there were more control-command than planning-scheduling oriented, and, as such, were somewhat out of the scope of our network.

Gaujal will present an application of the software developed in Sophia Antipolis at an INRIA-Industry meeting, in November, 1998. The application is a sequel of the work on ATM switches previously reported.

Krob and Morvan (LIAFA) are collaborating with Nortel Matra Cellular and Bouygues Telecom on cellular communication type of problems. A joint article with Dornstetter (Nortel Matra) has been written, see [66].

2.6. Difficulties encountered

In spite of the fact that both the network coordinator and the individual teamleaders published advertisements for postdoc positions, mainly trough E-mail and newsletters (see § 2.4.1) it remains difficult to attract qualified postdocs. Moreover, some postdocs working in the framework of Alapedes, found tenured positions.

At the recent management meeting (see § 2.3.2) all partners were stressed to be very flexible with respect to the scientific background of possible candidates. Most inquiries that reach the network coordinator are from young researchers whose nationality prevents them from joining Alapedes.

3. Factual information

3.1. Scientific speciality

All Alapedes partners are involved via a mathematics department; most of them have an information sciences department as well. Consequently, most mathematical subjects and many information sciences subjects are covered.

The following table presents the specialities of the partners that are most relevant for the Alapedes network expressed in the discipline classification codes for the mathematics, information and engineering sciences, issued and utilized by the European Union offices. As the list contains only a few broad subject categories the table does however not convey much detail. The disciplines which are referred to in the table are summarized in a second table.

Table 1: Specialities by partner.


partner	discipline codes
TUD	M-99	M-53	I-22
ARMINES	M-53	M-99	M-51
INRIA	M-41	M-53	I-26
KUL	M-53	M-49
HP	M-43	M-54	I-26
LIAFA	M-46	M-48	M-41
RUG	M-48	M-51	M-47
ULG	M-53	M-48


	code	description

mathematics and information sciences
	M-41	Statistics and Probability
	M-43	Geometry and Topology
	M-46	Discrete Mathematics and Computational Mathematics
	M-47	Logic and Semantics
	M-48	Algorithms and Complexity
	M-49	Signals, Speech and Image Processing
	M-51	Information Systems, Software Development and Databases
	M-53	Systems Control, Modelling and Neural Networks
	M-54	Parallel and Distributed Computing, Computer Architecture
	M-99	Other Mathematics and Information Sciences

engineering sciences
	I-22	Transport Engineering
	I-26	Telecommunications

3.2. Research staff

A list of all researchers within the Alapedes context can be found in Appendix A. It contains the teamleaders (scientists-in-charge) and further permanent research staff, Alapedes researchers, postgraduates employed with Alapedes partners, who study a subject in connection with the Alapedes field, undergraduates having contributed to the research within Alapedes and administrative staff involved. The table is not supposed to be exhaustive.

The research effort (in manmonths) spent to Alapedes by the different partners is estimated below; it is sorted out according to the source of payment (from Alapedes funds or not, respectively) and gives figures per partner.

Table 2: Research effort by partner and by category.


partner	manmonths			total
TUD	12	25	9	37
ARMINES	8	6	?	14
INRIA	--	49	?	49
KUL	11	6	0	17
HP	12	6	0	18
LIAFA	--	22	3	22
RUG	12	1	0	13
ULG	--	3	9	3
Alapedes	55	118	+21	173

Legend: in the table the first column indicates the partner, the second column gives the number of manmonths paid by the European Commission, the third column the same, but invested by the partners themselves, the fourth column applies to undergraduate students, and the fifth column gives totals (leaving out undergraduate students).

3.3. Researchers financed

In table 3 all Alapedes researchers have been listed; their nationality, date of birth, begin and prognosed end of their (present or past) appointment, the partner they are working at, and the specialities are given. See also Appendix A. For the meaning of the codes used for the specialities the reader is referred to the information in § 3.1. All Alapedes researchers fall in the postdoc category.

Note that end dates of appointments are unsure as they are subject to: 1) internal regulations within the partners (the contract may initially not extend beyond one year of duration), 2) the possibility that further funding (outside Alapedes, however) may be found, 3) the possibility that Alapedes researchers may want to leave earlier to fulfill a permanent position (this has occurred already thrice) and 4) the reallocation between partners that is strived at (Alapedes researchers are encouraged to change their ``homebase'' within the network).

Table: Researchers financed within Alapedes.


name nationality			birth	appointment			partner	specialities
	Remco de Vries	NL	640328	961101	-	980831	KUL	M-53, M-41
	Stéphane Perennes	F	681206	961115	-	970930	TUD	M-99
	Eleni Katirtzoglou	GR	651016	961125	-	981125	HP	M-99
	Michael Mc Gettrick	IRL	641103	970101	-	980531	ARMINES	M-51
	Bernd Heidergott	D	630430	970401	-	990731	TUD	M-41
	Sam Lifshes	ISR	630411	970801	-	000731	RUG	M-47, M-53, M-99
	Natacha Portier			981101	-	990901	ULG

3.4. Publications

3.4.1. Publications by Alapedes researchers

Publications by Alapedes researchers have already been given in § 2.4.3. For convenience they are also listed in table 4. The table refers to the list of publications in Appendix B.

Table: Publications by researchers financed within Alapedes.


	name	references
	Remco de Vries	[47, 46, 109, 148, 147]
		[45, 146]
	Stéphane Perennes	[129]
		[73, 75, 110, 126, 128, 127]
	Eleni Katirtzoglou	[112, 113]
	Michael Mc Gettrick	[30, 131, 132]
	Bernd Heidergott	[105, 104, 103, 106, 101, 100, 98, 102, 109, 99, 107, 108]
		[97, 95, 96, 94]
	Sam Lifshes	[115]

Remark: publications that were mentioned in the previous Alapedes annual progress report are type-set in a smaller typeface on a separate line.

3.4.2. Publications by other Alapedes members

Publications by other members of the network are embodied in Appendix B.

3.5. Secondments

Within Alapedes there were no secondments in which expertise between institutes was mediated by a detachment lasting for a period longer than two weeks.

4. Joint work

4.1. Joint publications

Joint papers -- defined as publications in which authors from at least two Alapedes partners have contributed -- are [32, 30, 39, 38, 43, 44, 47, 46, 82, 84, 109, 124, 125, 132]. Publications in this category, that were mentioned in the previous Alapedes annual progress report are: [9, 8, 31, 35, 36, 40, 37, 45, 81, 80, 83, 85, 90, 117, 118, 149, 136, 135, 137]. All of them have been included in the publication list of Appendix B.

4.2. Collaboration

Many mutual visits have been paid by Alapedes members. In Appendix C an overview of such visits is attempted, that probably stayed incomplete. Furthermore, in § 2.3.4 some extra information has been included on some of these contacts.

4.3. Conference visits by Alapedes-members

4.3.1. Cagliari convention

The plenary meeting near Cagliari brought together nearly all Alapedes members. Most of them presented (part) of their achievements of the second Alapedes year, either during the preceding WODES conference or during the Alapedes convention. Appendix D contains the programme and a list of attendants. Abstracts of the presentations are available upon request.

4.3.2. Other conferences and workshops

Appendix C contains an overview of visits by Alapedes members to other conferences, workshops and courses, that are related to Alapedes. Probably the overview is incomplete.

4.3.3. External collaboration by Alapedes-members

The TUD Alapedes team has established a cooperation with the faculty of Civil Engineering. In particular, Heidergott and Van Egmond are working together with A. de Kort, a postgraduate of the civil engineering faculty, and with G. Hooghiemstra of the stochastics laboratory within the subfaculty of Technical Mathematics, on issues in queuing theory. See [108].

One of the prominent interests is the application of stochastic (max,+)-theory to queueing systems and to elaborate on its use for optimisation of these systems.

Here, N. Krivulin from the University of Sankt Peterburg, Russia, is an expert. Heidergott is in permanent discussion with him and hopes to start on some joint work soon. Unfortunately, N. Krivulin didn't manage to attend the Alapedes\ convention near Cagliari, where a presentation of his work was scheduled (see Appendix D).

Further contact by the TUD team exists with M. Specovius from Paderborn, Germany; she visited Delft in June, 1998, who wanted to learn more about (max,+)-algebra and Alapedes activities.

Baccelli collaborates with Schmidt, Hasenfuss and Schlegel of the Universität Ulm, on the topics of Alapedes. See [10, 11].

Baccelli was an external reviewer of the thesis of F. Toomey at Trinity College Dublin. Toomey had been present during the first Alapedes convention in Waterford (Ireland).

Bruno Gaujal is involved in an European action Van Gogh; he has an active collaboration with the Universiteit Leiden and the Vrij e Universiteit Amsterdam. See [5, 6, 3, 86, 4].

Baccelli and Mairesse have a common paper in preparation with Borovkov. See [8].

Krob has collaborated with A.A. Mikhalev, of the Moscow State University, who is a specialist in combinatorics and formal calculus.

Krob is also collaborating with Grayson, of Columbia University, on problems in the interaction between automata and algebraic combinatorics.

Mairesse collaborated with Derrida (ENS Ulm, theoretical physics department), who is a well-known specialist in the physics of disordered systems.

A close collaboration is developing between LIAFA and the Laboratory `Traitement et Communication de l'Information', URA 820 ENST/CNRS. The participants on the ENST side are Sakarovitch, `Directeur de recherche au CNRS' and Lombardy, a postgraduate. The topic is automata with multiplicities in idempotent semirings. Sakorovitch and Lombardy participated to the Alapedes meeting in Cagliari, where Sakarovitch gave a talk on the `tropical semiring' (see Appendix D).

Blondel is collaborating with J. Tsitsiklis (MIT, Cambridge, USA) on the analysis of the computational complexity of control problems. This collaboration between ULG and MIT is supported by a NATO grant and has recently produced results that have implications for discrete event systems. See [21, 19, 20, 16, 24, 23, 22, 143, 144].

Blondel is also collaborating with P. Koiran (ENS-Lyon, France) on the analysis of decidability questions for hybrid and discrete event systems. This collaboration was made possible thanks to a two-months visiting professor position occupied by Blondel at ENS-Lyon during the academic year 1997-1998. See [16].

A. Research effort

The next tables give the research effort by Alapedes researchers, and the same for other Alapedes members, arranged into the categories `teamleaders', `permanent staff', `postdocs', `postgraduates', `undergraduates' and `administrative staff'.

The share column contains percentages that apply to the period reported on (in some cases estimations had to be reverted to, which applies to the second column only); involvement planned in remaining years may be incomplete.

Table: Research effort by Alapedes researchers .


	name	nationality	period concerned			share		partner
				-
Alapedes researchers				-
	Bernd Heidergott	D	970401	-	990731	100	%	TUD
	Michael Mc Gettrick	IRL	970101	-	980531	100	%	ARMINES
	vacancy			-				INRIA - SA
	vacancy			-				INRIA-Rocq
	Remco de Vries	NL	961101	-	980831	100	%	KUL
	Eleni Katirtzoglou	GR	961125	-	981125	100	%	HP
	vacancy			-				LIAFA
	Shmuel Lifsches	ISR	970801	-	000731	100	%	RUG
	vacancy			-				ULG

Remark: only researchers and vacancies have been entered for whom the appointment overlaps the period reported on; for a complete list see Table 3.

Table: Research effort by other Alapedes members.


	name	period involved			share		partner
			-
scientific teamleaders
	Geert Jan Olsder	961001	-	..........	25	%	TUD
	Guy Cohen	961001	-	..........	50	%	ARMINES
	François Baccelli	961001	-	..........	50	%	INRIA - SA
	Jean-Pierre Quadrat	961001	-	..........	50	%	INRIA-Rocq
	Bart de Moor	961001	-	..........	5	%	KUL
	Jeremy Gunawardena	961001	-	..........	20	%	HP
	Daniel Krob	961001	-	..........	20	%	LIAFA
	Jean Mairesse	961001	-	..........	50	%	LIAFA
	Rein Smedinga	961001	-	..........	5	%	RUG
	Vincent Blondel	961001	-	..........	15	%	ULG
			-
permanent research staff
	Jacob van der Woude	961001	-	..........	25	%	TUD
	Alain Jean-Marie	961001	-	..........	40	%	INRIA - SA
	Bruno Gaujal	961001	-	..........	40	%	INRIA - SA
	Stéphane Gaubert	961001	-	..........	100	%	INRIA-Rocq
	Marianne Akian	961001	-	..........	100	%	INRIA-Rocq
	Bart De Schutter	961001	-	980930	40	%	KUL
	Colin Sparrow	961001	-	..........	10	%	HP
	P. Gastin	961001	-	..........	10	%	LIAFA
	Jean Éric Pin	961001	-	..........	10	%	LIAFA
	C. Choffrut	961001	-	..........	10	%	LIAFA
	M. Morvan	961001	-	..........	10	%	LIAFA
			-
postdocs
	Andrew Burbanks	980701	-	..........	100	%	HP
	Matthias Kanta	961115	-	971115	50	%	LIAFA
			-
postgraduates
	Subiono	961001	-	990901	65	%	TUD
	Robert Jan van Egmond	970901	-	010901	70	%	TUD
	Gerardo Soto Y Koelemeij er	980515	-	..........	100	%	TUD
	Hong Dohy		-		25	%	INRIA - SA
	Laurent Vuillon	970801	-		10	%	LIAFA
	O. Heam	no information					LIAFA
	Cyril Nicaud	970801	-		10	%	LIAFA
			-
undergraduates
	Maurice van der Bol	970801	-	980630	100	%	TUD
	Eydoux	no information					INRIA, ARMINES
	I. Klimann	970801	-		30	%	LIAFA
	H. Droesch	961001	-	980801	30	%	ULG
	G. Cardol	970801	-	981001	60	%	ULG
			-
administrative staff
	Niek Tholen	961001	-	..........	20	%	TUD
	Bart Motmans	961001	-	..........	5	%	KUL

B. Publications

1: R. Agrawal, F. Baccelli, and R. Rajan. An algebra for queueing networks with time varying service and its application to the analysis of integrated service networks. Research Report N^o 3435, INRIA, 1998. Submitted to Automatica.
2: M. Akian, R.B. Bapat, and S. Gaubert. Asymptotics of the Perron eigenvalue and eigenvector using max-algebra. Manuscript accepted for publication in Comptes Rendus à l'Académie des Sciences, July 1998. Also: INRIA Research Report N^o 3450, July 1998.
3: E. Altman, B. Gaujal, and A. Hordijk. Optimal open-loop control of vacations, polling and service assignment. Research Report N^o 3261, INRIA, 1998.
4: E. Altman, B. Gaujal, and A. Hordijk. Regular ordering and applications in control policies. In Proceedings of the IEEE Conference on Decision and Control (CDC,'98), Tampa Bay, USA, December 1998. To appear.
5: E. Altman, B. Gaujal, and A. Hordijk. Regular sequences and admission control in stochastic (max,+) systems. In Proceedings of the IFAC Conference on System Structure and Control (SSC'98), Nantes, France, July 1998.
6: E. Altman, B. Gaujal, A. Hordijk, and G. Koole. Optimal admission, routing and service assignment control: the case of single buffer queues. In Proceedings of the IEEE Conference on Decision and Control (CDC'98), Tampa Bay, USA, December 1998. To appear.
7: F. Baccelli and T. Bonald. Window flow control in fifo networks with cross traffic. Questa, 1998. To appear.
8: F. Baccelli, A. Borovkov, and J. Mairesse. On large tandem queueing systems, 1997. To appear.
9: F. Baccelli, S. Foss, and J. Mairesse. Stationary ergodic Jackson networks: Results and counter-examples. In Stochastic networks, pages 281-307. Oxford Univ. Press, 1996.
10: F. Baccelli, S. Hasenfuss, and V. Schmidt. Expansions for steady state characteristics in $(max,+)$ -linear systems. Research Report N^o 2785, INRIA, 1996.
11: F. Baccelli, S. Hasenfuss, and V. Schmidt. Transient and stationary waiting times in $(max,+)$ -linear systems with Poisson input. Research Report N^o 3022, INRIA, 1996.
12: F. Baccelli and D. Hong. Analytic expansions of (max,+) Lyapunov exponents. Research Report N^o 3427, INRIA, 1998. Submitted to Annals of Applied Probability.
13: F. Baccelli and V. Schmidt. Taylor series expansions for Poisson driven $(max,+)$ -linear systems. Annals of Applied Probability, No. 6-1:138-185, 1996.
14: A. Benveniste, S. Gaubert, and C. Jard. Monotone rational series and max-plus algebraic models of real-time systems. In Proceedings of the IEE Workshop on Discrete Event Systems (WODES'98), Cagliari, Italy, August 1998.
15: A. Benveniste, C. Jard, and S. Gaubert. Algebraic techniques for timed systems. In Proceedings of CONCUR'98, Nice, France, September 1998.
16: V.D. Blondel, O. Bournez, P. Koiran, and J.N. Tsitsiklis. Deciding stability and mortality of piecewise affine dynamical systems. Technical report, Insitute of Mathematics, ULg, Belgium, 1998. Submitted for publication.
17: V.D. Blondel, M. Gevers, and B. Bitmead. When is a model good for control design? In Proceedings of the IFAC Conference on Decision and Control (CDC'98), San Diego, USA, December 1997.
18: V.D. Blondel, E.D. Sontag, M. Vidyasagar, and J.C. Willems, editors. Open Problems in Mathematical Systems and Control Theory. Springer Verlag, Heidelberg, 1998.
19: V.D. Blondel and J.N. Tsitsiklis. Complexity of elementary nonlinear and hybrid systems. In Proceedings of the 4th European Control Conference (ECC'97), Brussels, July 1-4, 1997.
20: V.D. Blondel and J.N. Tsitsiklis. Complexity of stability and controllability of elementary hybrid systems. Technical Report LIDS-P 2388, Massachusetts Inhe of Technology, Cambridge, USA, 1997. To appear in Automatica.
21: V.D. Blondel and J.N. Tsitsiklis. When is a pair of matrices mortal? Information Processing Letters, 1997.
22: V.D. Blondel and J.N. Tsitsiklis. Decidability limits for low-dimensional piecewise linear systems. In Proceedings of the Conference on Mathematical Theory of Networks and Systems (MTNS), Padova, Italy, June 1998.
23: V.D. Blondel and J.N. Tsitsiklis. Overview of complexity and decidability results for three classes of elementary nonlinear systems. In V.D. Blondel, E.D. Sontag, M. Vidyasagar, and J.C. Willems, editors, Open Problems in Mathematical Systems and Control Theory. Springer Verlag, Heidelberg, 1998.
24: V.D. Blondel and J.N. Tsitsiklis. Three problems on the decidability and complexity of stability. In Y. Yamamoto, editor, Learning, Control and Hybrid Systems. Springer Verlag, Heidelberg, 1998.
25: M.H. van der Bol. Factorizations and rank in the positive algebra and the $(max,+)$ -algebra. Afstudeerverslag faculty of technical mathematics and informatics, Technische Universiteit Delft, 1998.
26: P.H.L. Bovy, R.M.P. Goverde, and G.J. Olsder. The max-plus algebra approach to transportation systems. Accepted for the 8th world conference on transport research, July 12-17 1998.
27: E. van Bracht. On production lines with blocking. Doctoral thesis, Delft University of Technology, 1996. Defense was on December 20.
28: C. Choffrut and F. D'Alessandro. Commutativity in free inverse monoids. Theoretical Computer Science, 204:35-54, 1998.
29: J. Cochet-Terrasson. Étude et mise en $œ$ uvre d'algorithmes de type Howard sous des hypothèses faibles d'accessibilité. Mémoire de stage de DES ``modélisation et méthodes mathématiques en économie'', Université de Paris I, 1996.
30: J. Cochet-Terrasson, G. Cohen, S. Gaubert, M. Mc Gettrick, and J.-P. Quadrat. Numerical computation of spectral elements in max-plus algebra. In Proceedings of the IFAC Conference on System Structure and Control (SSC'98), Nantes, France, July 1998.
31: J. Cochet-Terrasson, S. Gaubert, and J. Gunawardena. Dynamics of min-max functions. Technical Report HPL-BRIMS-97-13, HP Laboratories, August 1997. Submitted for publication.
32: J. Cochet-Terrasson, S. Gaubert, and J. Gunawardena. Dynamics of min-max functions. Accepted for publication in Dynamics and Stability of Systems, 1997. Also: Technical Report HPL-BRIMS-97-13.
33: G. Cohen. Residuation and applications. In Support de cours de la 26 ième École de Printemps d'Informatique Théorique, Noirmoutier, France, May 1998.
34: G. Cohen. Two-dimensional representation of timed event graphs. In Support de cours de la 26 ième École de Printemps d'Informatique Théorique, Noirmoutier, France, May 1998.
35: G. Cohen, S. Gaubert, and J.-P. Quadrat. Kernels, images and projections in dioids. In Proceedings of the International Workshop on Discrete Event Systems (WODES'96), pages 151-158, Edinburgh, Scotland, UK, August 1996.
36: G. Cohen, S. Gaubert, and J.-P. Quadrat. Linear projectors in the max-plus algebra. In Proceedings of the 5th IEEE Mediterranean Conference on Control and Systems, Paphos, Cyprus, July 21-23 1997.
37: G. Cohen, S. Gaubert, and J.-P. Quadrat. Timed event graphs with multipliers and homogeneous min-plus systems. Technical note. IEEE Transactions on Automatic Control, 1997. To appear.
38: G. Cohen, S. Gaubert, and J.-P. Quadrat. Max-plus algebra and system theory: where we are and where to go now. In Proceedings of the IFAC Conference on System Structure and Control (SSC'98), Nantes, France, July 1998.
39: G. Cohen, S. Gaubert, and J.-P. Quadrat. Time-event graph with multipliers and homogeneous min-plus systems. IEEE Transactions on Automatic Control, 43(9):1296-1302, September 1998.
40: G. Cohen and MAX PLUS working group. Vous changez de système, changez d'algèbre ! Colloque ``Voir, Entendre, Raisonner, Calculer'', Cité des Sciences et de l'Industrie, La Villette, Paris, June 10-13 1997.
41: B. De Schutter. Max-Algebraic System Theory for Discrete Event Systems. Doctoral thesis, Faculty of Applied Sciences, K.U. Leuven, Belgium, 1996.
42: B. De Schutter. On the ultimate behavior of the sequence of consecutive powers of a matrix in the max-plus algebra. Technical Report 98-32, ESAT-SISTA, K.U. Leuven, Belgium, July 1998. Submitted for publication.
43: B. De Schutter, V. Blondel, and B. De Moor. On the complexity of the boolean minimal realization problem in the max-plus algebra. Technical Report 98-41, ESAT-SISTA, K.U. Leuven, Belgium, May 1998.
44: B. De Schutter, V. Blondel, and B. De Moor. On the complexity of the boolean minimal realization problem in the max-plus algebra. In Proceedings of the International Conference on Systems, Signals, Control, Computers (SSCC'98), volume II of Advances in Systems, Signals, Control and Computers, pages 451-455, Durban, South Africa, September 1998.
45: B. De Schutter, V. Blondel, R. de Vries, and B. De Moor. On the boolean minimal realization problem in the max-plus algebra. Technical Report 97-68, ESAT-SISTA, K.U. Leuven, Belgium, August 1997.
46: B. De Schutter, V. Blondel, R. de Vries, and B. De Moor. On the boolean minimal realization problem in the max-plus algebra: Addendum. Technical Report 97-68a, ESAT-SISTA, K.U. Leuven, Belgium, December 1997.
47: B. De Schutter, V. Blondel, R. de Vries, and B. De Moor. On the boolean minimal realization problem in the max-plus algebra. Systems and Control Letters, 35(2):69-78, 1998.
48: B. De Schutter and B. De Moor. Generalized linear complementarity problems and the analysis of continuously variable systems and discrete event systems. Internal Report 96-71, ESAT-SISTA, K.U. Leuven, Belgium, 1996.
49: B. De Schutter and B. De Moor. A method to find all solutions of a system of multivariate polynomial equalities and inequalities in the max algebra. Discrete Event Dynamic Systems: Theory and Applications, 6(2):115-138, March 1996.
50: B. De Schutter and B. De Moor. Optimal traffic light control for a single intersection. Technical Report 96-90, ESAT-SISTA, K.U. Leuven, Belgium, 1996. Revised version, January 1998. Accepted for publication in European Journal of Control.
51: B. De Schutter and B. De Moor. The QR decomposition and the singular value decomposition in the symmetrized max-plus algebra. Internal Report 96-24, ESAT-SISTA, K.U. Leuven, Belgium, 1996.
52: B. De Schutter and B. De Moor. The extended linear complementarity problem and its applications in the analysis and control of discrete event systems and hybrid systems. In Proceedings of the IEEE Singapore International Symposium on Control Theory and Applications (SISCTA'97), pages 394-398, Singapore, July 29-30, 1997.
53: B. De Schutter and B. De Moor. The extended linear complementarity problem and the modeling and analysis of hybrid systems. In Book of extended abstracts of the Hybrid Systems V (HS'97) workshop, pages 15-20. Notre Dame (Indiana), USA, September 1997.
54: B. De Schutter and B. De Moor. Generalized linear complementarity problems and the analysis of continuously variable systems and discrete event systems. In Proceedings of the International Workshop on Hybrid and Real-Time Systems (HART'97), volume 1201 of Lecture Notes in Computer Science, pages 409-414, Grenoble, France, March 1997. Springer-Verlag.
55: B. De Schutter and B. De Moor. The linear dynamic complementarity problem is a special case of the extended linear complementarity problem. Technical Report 97-21, ESAT-SISTA, K.U. Leuven, Belgium, 1997.
56: B. De Schutter and B. De Moor. Matrix factorization and minimal state space realization in the max-plus algebra. In Proceedings of the 1997 American Control Conference (ACC'97), pages 3136-3140, Albuquerque, New Mexico, USA, June 1997.
57: B. De Schutter and B. De Moor. A note on the characteristic equation in the max-plus algebra. Linear Algebra and Its Applications, 261:237-250, 1997.
58: B. De Schutter and B. De Moor. On the sequence of consecutive powers of a matrix in a boolean algebra. Technical Report 97-67, ESAT-SISTA, K.U. Leuven, Belgium, 1997. Revised version, April 1998. Submitted for publication.
59: B. De Schutter and B. De Moor. Optimal traffic light control for a single intersection. In Proceedings of the 1997 International Symposium on Nonlinear Theory and its Applications (NOLTA'97), pages 1085-1088, Honolulu, Hawaii, November-December 1997.
60: B. De Schutter and B. De Moor. Optimal traffic signal control for a single intersection. Technical Report 97-10, ESAT-SISTA, K.U. Leuven, Belgium, Feb. 1997. Accepted for the International Symposium on Nonlinear Theory and its Applications (NOLTA'97), Hawaii, Nov. 29-Dec. 3, 1997.
61: B. De Schutter and B. De Moor. The QR decomposition and the singular value decomposition in the symmetrized max-plus algebra. In Proceedings of the 4th European Control Conference (ECC'97), Brussels, July 1-4, 1997.
62: B. De Schutter and B. De Moor. The extended linear complementarity problem and the modeling and analysis of hybrid systems. Technical Report 98-40, ESAT-SISTA, K.U. Leuven, Belgium, May 1998. Accepted for publication in Hybrid Systems V: Proceedings of the 5th International Workshop on Hybrid Systems.
63: B. De Schutter and B. De Moor. The linear dynamic complementarity problem is a special case of the extended linear complementarity problem. Systems and Control Letters, 34(1-2):63-75, 1998.
64: B. De Schutter and B. De Moor. On the sequence of consecutive matrix powers of boolean matrices in the max-plus algebra. Technical Report 98-20, ESAT-SISTA, K.U. Leuven, Belgium, March 1998. Accepted for publication in the Proceedings of the 6th IEEE Mediterranean Conference on Control and Systems, Alghero, Italy, June 1998.
65: B. De Schutter and B. De Moor. The QR decomposition and the singular value decomposition in the symmetrized max-plus algebra. SIAM Journal on Matrix Analysis and Applications, 19(2):378-406, April 1998.
66: J.L. Dornstetter, D. Krob, M. Morvan, and L. Viennot. Some algorithms for synchronizing clocks of base transceiver stations. LIAFA Research Report 13, Université Paris 7, 1997. Submitted to Discrete Applied Mathematics.
67: M. Droste and P. Gastin. On recognizable and rational formal power series in partially commuting variables. In LNCS, editor, Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP '97). Springer-Verlag, 1997. To appear. Submitted to IEEE Transaction on Automatic Control.
68: M. Droste and P. Gastin. The Kleene-Schützenberger theorem for formal power series in partially commuting variables. LIAFA Research Report 3, Université Paris 7, 1998.
69: R.J. van Egmond. Propagation of delays in public transport. Extended abstract, 6th EURO working group on transportation, Goteborg, 1998.
70: R.J. van Egmond and G.J. Olsder. The (max,+) algebra applied to synchronisation of traffic light processes. In Proceedings of the IEE International Workshop On Discrete Event Systems (WODES'98), Cagliari, Italy, August 1998.
71: Eydoux. Internal report, École Polytechnique.
72: O. Fall and J.-P. Quadrat. About min-plus product forms. Technical report, 1998.
73: M. Flammini and S. Perennes. Lower bounds on systolic gossiping. In Proceedings of IPPS '97, pages 517-521, Genève, April 1997.
74: V. Froidure and J.E. Pin. Algorithms for computing finite semigroups. In F. Cucker and M. Shub, editors, Foundations of Computational Mathematics, pages 112-126. Springer-Verlag, 1997.
75: L. Gargano, P. Hell, and S. Perennes. Coloring paths in directed symetric trees with applications to WDM routing, 1997. Accepted by ICALP '97. Longer version submitted to Journal of Graph Theory.
76: S. Gaubert. Exactly solvable models of timed discrete event systems: beyond max-plus algebra. In Proceedings of MOVEP'98, Nantes, July 1998.
77: S. Gaubert. Two lectures on max-plus algebra. In Support de cours de la 26 ième École de Printemps d'Informatique Théorique, Noirmoutier, France, May 1998.
78: S. Gaubert and A. Giua. Petri net languages with infinite sets of final markings. In Smedinga et al. [137].
79: S. Gaubert and A. Giua. Subsets of $N$ ^m and Petri net languages. Accepted for publication in J. of Computer and System Science, October 1997.
80: S. Gaubert and J. Gunawardena. The duality theorem for min-max functions. Technical Report HPL-BRIMS-97-16, HP Laboratories, August 1997.
81: S. Gaubert and J. Gunawardena. The duality theorem for min-max functions. Comptes Rendus à l'Académie des Sciences, 326:43-48, January 1998.
82: S. Gaubert and J. Gunawardena. A non-linear hierarchy for discrete event dynamical systems. In Proceedings of the IEE Workshop on Discrete Event Systems (WODES'98), Cagliari, Italy, August 1998.
83: S. Gaubert and J. Mairesse. Modeling and analysis of timed Petri nets using heaps of pieces. In Proceedings of the 4th European Control Conference (ECC'97), Brussels, July 1-4, 1997.
84: S. Gaubert and J. Mairesse. Modeling and analysis of timed Petri nets using heaps of pieces. IEEE Transactions on Automatic Control, April 1999. To appear.
85: S. Gaubert and MAX PLUS working group. Methods and applications of $(max,+)$ linear algebra. Invited paper. In Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 1997. To appear in Lecture Notes in Computer Science, Springer Verlag.
86: B. Gaujal and A. Hordijk. Regularity for admission control comparisons. In Proceedings of the IEE Workshop on Discrete Event Systems (WODES'98), Cagliari, Italy, August 1998.
87: B. Gaujal, A. Jean-Marie, P. Mussi, and G. Siegel. High speed simulation of discrete event systems by mixing process oriented and equational approaches. Parallel Computing, 23:219-233, 1997.
88: B. Gaujal, A. Jean-Marie, and G. Siegel. Modeling of ATM switches using non-ambiguous Petri nets, 1997. In preparation.
89: B. Gaujal, A. Jean-Marie, and G. Siegel. Non-ambiguous Petri nets and their application to the modeling of ATM switches. In Proceedings of the IEE Workshop on Discrete Event Systems (WODES'98), Cagliari, Italy, August 1998.
90: J. Gunawardena, editor. Idempotency. Cambridge University Press, Isaac Newton Institute, 1997.
91: J. Gunawardena. An introduction to idempotency. In Idempotency [90]. Technical Report HPL-BRIMS-96-24, September, 1996.
92: J. Gunawardena. Recent developments in the mathematics of reactive systems. In A. Mazurkiewicz and J. Winkowski, editors, CONCUR'97: Concurrency Theory, Springer Lecture Notes in Computer Science 1243. Springer-Verlag, 1997. Invited talk at the 8th International Conference on Concurrency Theory Warsaw, Poland, July 1997; Technical Report HPL-BRIMS-97-08, May 1997.
93: É. Hautecloque Raysz. Empilements de pièces, semi-anneau $(max,
+)$ et ordonnancement. Rapport de stage de DEA, INRIA, June 1997.
94: B. Heidergott. The Delft railway model. Working paper. 11 Pages, 1997.
95: B. Heidergott. Finite perturbation analysis for queuing networks. Journal of Discrete Event Dynamic Systems, 1997. Submitted. 31 Pages.
96: B. Heidergott. Infinitesimal perturbation analysis for queuing networks with general service time distributions. Technical Report 97-33, Technische Universiteit Delft, 1997.
97: B. Heidergott. On perturbation analysis. In INFORMS Conference on Applied Probability, Boston, USA, June 30 - July 1i 1997.
98: B. Heidergott. Analysing sojourn times in queueing networks: A structural approach. Mathematical Methods of Operations Research, 1998. Submitted.
99: B. Heidergott. A characterisation of (max,+)-linear queueing systems. Working paper, 1998.
100: B. Heidergott. Cost optimisation of a multi-component maintenance system using weak derivatives. Operations Research Letters, 1998. Submitted.
101: B. Heidergott. Customer-oriented finite perturbation analysis. Journal of Discrete Event Dynamic Systems, 1998. Submitted.
102: B. Heidergott. A differential calculus for random matrices with applications to (max,plus)-linear stochastic systems. Mathematics of Operations Research, 1998. Submitted.
103: B. Heidergott. Infinitesimal perturbation analysis for queueing networks with general service time distributions. Queueing Systems: Theory and Applications, 1998. To appear.
104: B. Heidergott. Optimisation of a single-component maintenance system: A smoothed perturbation analysis approach. European Journal of Control, 1998. To appear.
105: B. Heidergott. Optimisation of synchronisation constraints via weak derivatives. In Proceedings of the IEE International Workshop on Discrete Event Systems (WODES'98), pages 261-266, Cagliari, Italy, August 1998.
106: B. Heidergott. A weak derivative approach to optimisation of threshold parameters in a multi-component maintenance system. Journal of Applied Probability, 1998. Submitted.
107: B. Heidergott and G. Gürkan. Gradient estimation using simulation in option pricing: A weak derivative approach. Working paper, 1998.
108: B. Heidergott, A. de Kort, G. Hooghiemstra, and R.J. van Egmond. Queueing processes at railway stations: examining the approach by Wakob. Working paper, 1998.
109: B. Heidergott and R. de Vries. Towards a control theory of transportation networks. Working paper, 1998.
110: M.-C. Heydemann, N. Marlin, and S. Perennes. Complete rotations in Cayley graphs, 1997. Submitted to Discrete Applied Mathematics.
111: A. Jean-Marie. The waiting time distribution in Poisson-driven deterministic systems. Research Report N^o 3083, INRIA, 1997.
112: E. Katirtzoglou. The cycle time vector of D-A-D functions. Technical Report HPL-BRIMS-98-19, HP Liaboratories, 1998.
113: E. Katirtzoglou. The cycle time vector of D-A-D functions. Journal of Linear Algebra and its Applications, 1998. Submitted.
114: D. Krob. Some automata-theoretic aspects of min-max-plus semirings. In J. Gunawardena, editor, Idempotency, pages 70-79. Cambridge University Press, 1998.
115: S. Lifsches. Controlling hybrid systems by tree automata. In preparation, 1998.
116: J. Mairesse. Petri nets, (max,+) algebra and scheduling. In INRIA, editor, Support de cours de la 26 ième École de printemps d'informatique théorique, pages 329-357, 1998.
117: J. Mairesse and B. Prabhakar (HP). On the departure from ./GI/1 queues in tandem, 1997. In preparation.
118: J. Mairesse, B. Prabhakar (HP), and N. McKeown. Optimality of Tetris models for multicast switching. In Proceedings of CISS, Princeton, 1996.
119: J. Mairesse and LIAFA (LITP) team. report on subproject S-1: Existing software. Final report, 14 pages, LIAFA, 1997.
120: J. Mairesse and L. Vuillon. Optimal sequences in a heap model with two pieces. LIAFA Research Report, Université Paris 7, 1998.
121: G.J. Olsder. Dienstregelingen en de max-plus algebra. Euclides, jaargang 72, no. 4, 626:158-163, 1997.
122: G.J. Olsder. Max algebra approach to discrete event systems. In Support de cours de la 26 ième École de Printemps d'Informatique Thèorique, Noirmoutier, France, May 1998.
123: G.J. Olsder. Wiskunde in de beweging. Diesrede Technische Universiteit Delft, 9 januari 1998.
124: G.J. Olsder and B. De Schutter. The minimal realization problem in the max-plus algebra. In V. Blondel, editor, Open problems in systems and control. Springer, 1998. To appear.
125: G.J. Olsder and B. De Schutter. The minimal realization problem in the max-plus algebra. In Proceedings of the IEEE Conference on Decision and Control (CDC'98), Tampa Bay, USA, December 1998. To appear.
126: G.J. Olsder and S. Perennes. Iteration of Min-Max-Plus functions. Working paper, 1997.
127: G.J. Olsder and S. Perennes. On the long term behaviour of min-max-plus systems. Internal report, Technische Universiteit Delft, 1997.
128: G.J. Olsder and S. Perennes. The upperbound on the period of non-expansive mappings. Internal report, Technische Universiteit Delft, 1997. In preparation.
129: G.J. Olsder and S. Perennes. The upperbound on the period of non-expansive mappings. In Proceedings of the IFAC Conference on System Structure and Control (SSC'98), Nantes, France, July 1998.
130: G.J. Olsder and C. Roos. Eigenvalues in the max-plus algebra characterized by using LO duality. Linear Algebra and its Applications, July 1998. Submitted.
131: G.J. Olsder and Subiono. On large scale max-plus algebra model in railway systems. In Proceedings of the IEE International Workshop on Discrete Event Systems (WODES'98), Cagliari, Italy, August 1998.
132: G.J. Olsder, Subiono, and M. McGettrick. On time tables and allocation of trains. In Proceedings of the IEE International Workshop on Discrete Event Systems (WODES'98), Cagliari, Italy, August 1998.
133: J.E. Pin. Tropical semirings. In Gunawardena [90].
134: J.-P. Quadrat. Min-plus probability calculus. In Support de cours de la 26 ième École de Printemps d'Informatique Théorique, Noirmoutier, France, May 1998.
135: J.-P. Quadrat and MAX PLUS working group. Min-plus linearity and statistical mechanics. Séminaire sur la mécanique statistique des grands réseaux, INRIA, October 21-25 1996.
136: J.-P. Quadrat and MAX PLUS working group. Min-plus linearity and statistical mechanics. Markov Processes and Related Fields, 3(4):565-587, 1997.
137: R. Smedinga, M.P. Spathopoulos, and P. Kozák, editors. Proceedings of the International Workshop on Discrete Event Systems (WODES'96), Edinburgh, Scotland, UK, August 1996.
138: M.P. Spathopoulos and R. Smedinga. Some issues on control of discrete event systems using model specifications. In Smedinga et al. [137].
139: Subiono. On large scale max-plus algebra model in railway systems. In Proceedings of the IFAC Conference on System Structure and Control (SSC'98), Nantes, France, July 1998.
140: Subiono. Power algorithms for (max,+)- and bipartite (min,max,+)-systems. Submitted to Discrete Event Dynamic Systems, 1998.
141: Subiono and G.J. Olsder. On bipartite min-max-plus systems. In Proceedings of the 4th European Control Conference (ECC'97), Brussels, July 1-4, 1997. Technical Report 96-100 of the Faculty of Technical Mathematics and Informatics, Technische Uiniversiteit Delft.
142: Subiono and J. van der Woude. Power algorithms for $(max,+)$ - and bipartite $(min, max,+)$ -systems. Technical Report 98-29, Technische Universiteit Delft, 1998. Submitted to Discrete Event Dynamic Systems.
143: J.N. Tsitsiklis and V. Blondel. The spectral radius of a pair of matrices is NP-hard to compute. In Proceedings of the 35th Conference on Decision and Control (CDC'96), pages 3192-3197, Kobe, Japan, 1996.
144: J.N. Tsitsiklis and V. Blondel. Spectral quantities associated to pairs of matrices are hard - when not impossible - to compute and to approximate. Mathematics of Control, Signals, and Systems, 1997. To appear.
145: J.M. Vincent. Some ergodic results on stochastic iterative discrete events systems. In DEDS: Theory and Applications, volume 7, no. 2, pages 209-233, 1997.
146: R. de Vries and B. De Moor. Minimal realizations and state space transformations for discrete event systems. Internal report, ESAT-SISTA, K.U. Leuven, Belgium, 1997.
147: R. de Vries, B. De Schutter, and B. De Moor. Minimal realizations and state space transformations in the symmetrized max-algebra. In Proceedings of the IFAC Conference on System Structure and Control (SSC'98), pages 587-592, Nantes, France, July 1998.
148: R. de Vries, B. De Schutter, and B. De Moor. On max-algebraic models for transportation networks. In Proceedings of the IEE International Workshop on Discrete Event Systems (WODES'98), pages 457-462, Cagliari, Italy, August 1998.
149: MAX PLUS working group. Max-plus-times linear systems. Workshop on Open Problems in Mathematical Systems Theory and Control, Belgium, June 30 1997.

C. Contacts

The next table gives a summary of mutual visits by Alapedes members. Only such contacts are mentioned that did not take place at one in the meetings in § 2.3 (see there). Also, Cohen visited INRIA-Rocquencourt once a week, the whole year long for interaction with Gaubert and Quadrat. Baccelli and Mairesse have met regularly at LIAFA.


	name			from				till			destination	objective

1997
	Eleni Katirtzoglou	T-2	I		-	10	/		-	10	INRIA-Roc
	Michael Mc Gettrick	A-1,S-2	IC	24	-	11	/	28	-	11	TUD
	Guy Cohen		F	27	-	11	/	27	-	11	Angers	promotion

1998
	Bruno Gaujal		I		-	02	/		-	02	INRIA-Roc
	Bart De Schutter	T-1	I	01	-	04	/	01	-	04	TUD
	Stéphane Gaubert	T-2	I	16	-	09	/	17	-	09	ULG	collaboration
	several members		I	19	-	06	/	21	-	06	INRIA-Roc
	Bart De Schutter	A-1,T-1	IO	22	-	06	/	24	-	06	TUD	mini-workshop
	Remco de Vries	T-1	I	22	-	06	/	24	-	06	TUD	mini-workshop
	Eleni Katirtzoglou	T-2	I	23	-	06	/	23	-	06	TUD
	Stéphane Gaubert	T-2	I	15	-	07	/	23	-	07	HP
	Bernd Heidergott		I	18	-	07	/	20	-	07	HP
	management committee	***	M	29	-	08	/	29	-	08	Cagliari	formal meeting
	Jean Mairesse	***	IO	07	-	09	/	11	-	09	HP
	Stéphane Gaubert	T-1	I		-	09	/		-	09	ULG

Legend: in the tables in this appendix the following codes are used:
*** in the subproject column signal the whole project;
in the third column activities undertaken are signalled:
N = network presentation, S = subproject presentation, O = own work presentation, M = meeting, C = consultation, I = informal contact, A = attend, F = formal function.

The next table gives some information about visitors from outside to partners of the Alapedes network, having a strong relation with its subject. The information is bound to be incomplete.

name from till destination origin

1997

Rossella Fenu T-1 SC 23 - 10 / 24 - 10 ULG Cagliari

1998

Natacha Portier T-1 SC 17 - 06 / 17 - 06 ULG Lyon

Éric Menguy T-1 SC 22 - 06 / 24 - 06 ULG Angers

Maria Specovius 22 - 06 / 24 - 06 TUD

Flavio D'Alessandro T-1 SC 01 - 07 / 01 - 07 ULG Paris/Roma

	name			from	till	destination	origin

1997
	Rossella Fenu	T-1	SC	23	-	10	/	24	-	10	ULG	Cagliari

1998
	Natacha Portier	T-1	SC	17	-	06	/	17	-	06	ULG	Lyon
	Éric Menguy	T-1	SC	22	-	06	/	24	-	06	ULG	Angers
	Maria Specovius			22	-	06	/	24	-	06	TUD
	Flavio D'Alessandro	T-1	SC	01	-	07	/	01	-	07	ULG	Paris/Roma

The next table gives a summary of visits by Alapedes members to conferences, workshops and courses. More information on the Alapedes software course, the workshop on non-expansive maps, the spring school, and the meetings of the working group on tropical algebra, can be found in § 2.3.4, and furthermore in Appendices E, F, G, and I (on Internet at http://amadeus.inria.fr/TROPICAL/), respectively. More details on presentations by Alapedes members are available upon request.

name from till destination objective

1997

Subiono A-1 A 28 - 10 / 28 - 10 Rotterdam SMM-Researchprogr.

Subiono A-1 A 30 - 10 / 30 - 10 Scheveningen Trail Conference

Cyril Nicaud 15 - 11 / 22 - 11 Lisboa workshop GAP

O. Heam 15 - 11 / 22 - 11 Lisboa workshop GAP

Bart De Schutter 29 - 11 / 02 - 12 Hawaii NOLTA'97

Jean Mairesse 01 - 12 / 12 - 12 Tel-Aviv Bar-Ilan Univ.

Vincent Blondel T-1 OA 10 - 12 / 12 - 12 San Diego IEEE CDC

Bernd Heidergott T-3 O 12 - 12 / 12 - 12 Hamburg Universität

1998

Eleni Katirtzoglou T-2 I 07 - 01 / 08 - 01 New Jersey prof. Nussbaum

Bernd Heidergott T-3 A 13 - 01 / 15 - 01 Lunteren OR workshop

several members OAI 04 - 03 / 06 - 03 Mierlo 17 0.7exth Benelux

Vincent Blondel T-1 I 15 - 03 / 25 - 03 Berkeley Univ. California

Eleni Katirtzoglou T-2 O 22 - 03 / 05 - 04 Memphis Analysis Seminar

Bernd Heidergott T-3 O 24 - 03 / 27 - 03 München Stochastik Tage

Bart De Schutter 03 - 04 / 03 - 04 Gent SYSTeMS group

Sami Lifsches T-4 A 13 - 04 / 15 - 04 Berkeley hybrid systems

Colin Sparrow T-2 O 21 - 04 / 26 - 04 Amsterdam Stieltjes Colloq.

Bernd Heidergott A-1 A 27 - 04 / 27 - 04 Delft Verkeersregeling

Vincent Blondel T-1 I 01 - 04 / 30 - 05 Lyon École Nat. Sup.

Michael Mc Gettrick A-1 A 12 - 05 / 13 - 05 Braunschweig FORMS'98

Eleni Katirtzoglou T-2 O 31 - 05 / 02 - 06 Edinburgh Analysis Seminar

Bruno Gaujal T-1 A - 06 / - 06 Marseille 2-dim. sequences

Bart De Schutter O 08 - 06 / 11 - 06 Alghero 6 0.7exth IEEE Med.

Daniel Krob 10 - 06 / 19 - 06 Columbia Un. prof. Grayson

Remco de Vries A 11 - 06 / 15 - 06 Brussels Eur. Conf. on OR

Sami Lifsches T-4 O - 06 / - 06 Nij megen hybrid systems

Vincent Blondel T-1 O 07 - 07 / 12 - 07 Padova MTNS

Jean Éric Pin 11 - 07 / 17 - 07 Danmark ICALP98

Jeremy Gunawardena T-2 O 21 - 06 / 23 - 06 Indianapolis LICS98

Eleni Katirtzoglou T-2 I 21 - 06 / 27 - 06 Amsterdam CWI, Vrij e Univ.

Remco de Vries 12 - 07 / 15 - 07 Brussels EURO XVI

Bart De Schutter OF 13 - 07 / 17 - 07 Toronto SIAM / DiPrima

Guy Cohen 08 - 07 / 10 - 07 Nantes IFAC SSC98

Bruno Gaujal OA 08 - 07 / 10 - 07 Nantes IFAC SSC98

Remco de Vries 08 - 07 / 10 - 07 Nantes IFAC SSC98

Robert Jan van Egmond A-1 O 09 - 09 / 11 - 09 Gteborg WG Transportation

Bart De Schutter 22 - 09 / 24 - 09 Durban SSCC'98

Legend: in the destination column the acronym of the network partner, and name and place of conference etc. participated in is mentioned;
*** in the subproject column signal the whole project.

	name			from	till	destination	objective

1997
	Subiono	A-1	A	28	-	10	/	28	-	10	Rotterdam	SMM-Researchprogr.
	Subiono	A-1	A	30	-	10	/	30	-	10	Scheveningen	Trail Conference
	Cyril Nicaud			15	-	11	/	22	-	11	Lisboa	workshop GAP
	O. Heam			15	-	11	/	22	-	11	Lisboa	workshop GAP
	Bart De Schutter			29	-	11	/	02	-	12	Hawaii	NOLTA'97
	Jean Mairesse			01	-	12	/	12	-	12	Tel-Aviv	Bar-Ilan Univ.
	Vincent Blondel	T-1	OA	10	-	12	/	12	-	12	San Diego	IEEE CDC
	Bernd Heidergott	T-3	O	12	-	12	/	12	-	12	Hamburg	Universität

1998
	Eleni Katirtzoglou	T-2	I	07	-	01	/	08	-	01	New Jersey	prof. Nussbaum
	Bernd Heidergott	T-3	A	13	-	01	/	15	-	01	Lunteren	OR workshop
	several members		OAI	04	-	03	/	06	-	03	Mierlo	17 0.7exth Benelux
	Vincent Blondel	T-1	I	15	-	03	/	25	-	03	Berkeley	Univ. California
	Eleni Katirtzoglou	T-2	O	22	-	03	/	05	-	04	Memphis	Analysis Seminar
	Bernd Heidergott	T-3	O	24	-	03	/	27	-	03	München	Stochastik Tage
	Bart De Schutter			03	-	04	/	03	-	04	Gent	SYSTeMS group
	Sami Lifsches	T-4	A	13	-	04	/	15	-	04	Berkeley	hybrid systems
	Colin Sparrow	T-2	O	21	-	04	/	26	-	04	Amsterdam	Stieltjes Colloq.
	Bernd Heidergott	A-1	A	27	-	04	/	27	-	04	Delft	Verkeersregeling
	Vincent Blondel	T-1	I	01	-	04	/	30	-	05	Lyon	École Nat. Sup.
	Michael Mc Gettrick	A-1	A	12	-	05	/	13	-	05	Braunschweig	FORMS'98
	Eleni Katirtzoglou	T-2	O	31	-	05	/	02	-	06	Edinburgh	Analysis Seminar
	Bruno Gaujal	T-1	A		-	06	/		-	06	Marseille	2-dim. sequences
	Bart De Schutter		O	08	-	06	/	11	-	06	Alghero	6 0.7exth IEEE Med.
	Daniel Krob			10	-	06	/	19	-	06	Columbia Un.	prof. Grayson
	Remco de Vries		A	11	-	06	/	15	-	06	Brussels	Eur. Conf. on OR
	Sami Lifsches	T-4	O		-	06	/		-	06	Nij megen	hybrid systems
	Vincent Blondel	T-1	O	07	-	07	/	12	-	07	Padova	MTNS
	Jean Éric Pin			11	-	07	/	17	-	07	Danmark	ICALP98
	Jeremy Gunawardena	T-2	O	21	-	06	/	23	-	06	Indianapolis	LICS98
	Eleni Katirtzoglou	T-2	I	21	-	06	/	27	-	06	Amsterdam	CWI, Vrij e Univ.
	Remco de Vries			12	-	07	/	15	-	07	Brussels	EURO XVI
	Bart De Schutter		OF	13	-	07	/	17	-	07	Toronto	SIAM / DiPrima
	Guy Cohen			08	-	07	/	10	-	07	Nantes	IFAC SSC98
	Bruno Gaujal		OA	08	-	07	/	10	-	07	Nantes	IFAC SSC98
	Remco de Vries			08	-	07	/	10	-	07	Nantes	IFAC SSC98
	Robert Jan van Egmond	A-1	O	09	-	09	/	11	-	09	Gteborg	WG Transportation
	Bart De Schutter			22	-	09	/	24	-	09	Durban	SSCC'98

DiPrima prize

Bart De Schutter received the 1998 Richard C. DiPrima Prize for his doctoral thesis. It was presented to him on July 16, 1998 during the SIAM Annual Meeting in Toronto.

D. Cagliari convention

ALAPEDES convention Cagliari PROGRAMME

Saturday, August 29, 1998

Opening TUD

08:45-09:15 welcome, coffee, installation

09:15-09:30 Geert Jan Olsder, Niek Tholen Opening, announcements
T-1Representation problems KUL

09:30-10:15 Guy Cohen, Stéphane Gaubert, Jean-Pierre Quadrat Realization of max-plus linear systems from the geometric point of view

10:15-10:45 coffee break

T-5Large systems problems INRIA

10:45-11:30 Marianne Akian, Ravindra Bapat, Stéphane Gaubert Asymptotics of the Perron eigenvalue and eigenvector using max-algebra
T-2Stability problems TUD

11:30-12:15 Colin Sparrow Periods of non-expansive maps

12:30-13:45 lunch break

13:45-14:30 Eleni Katirtzoglou The cycle time vector of D-A-D functions

14:30-15:15 Subiono, Jacob van der Woude A power algorithm for bipartite $(min, max,+)$ systems

15:15-15:45 tea break
T-3Optimisation problems INRIA

15:45-16:30 Bart de Schutter, Bart de Moor The extended linear complementarity problem and the modelling and analysis of hybrid systems

16:30-17:15 Dohy Hong Series expansions of $(max,+)$ Lyapunov exponents - analyticity via contraction

17:15-18:00 Bernd Heidergott Analyticity of $(max,+)$ -linear stochastic systems

19:30-22:00 meeting of management committee (delegates only)
Sunday, August 30, 1998

08:45-09:30 Nikolai Krivulin CANCELLED On constructing bounds for mean cycle time in acyclic fork-join queueing networks

09:30-10:15 Jean Mairesse, Laurent Vuillon Optimal sequences in a heap model

10:15-10:45 coffee break
T-4Control of automata LIAFA

10:45-11:30 Jacques Sakarovitch How automata theory got interested in the $(min,+)$ semiring

11:30-12:15 Sam Lifsches Controlling hybrid systems by tree automata

12:15-13:00 Vincent Blondel Elementary systems that simulate Turing machines

13:00-14:00 lunch break

Closure TUD

14:00-14:30 Geert Jan Olsder Closure, announcements

LIST OF PARTICIPANTS


name	affiliation	E-mail
Geert Jan Olsder	TUD	`G.J.Olsder@math.tudelft.nl`
Niek Tholen	TUD	`N.Tholen@math.tudelft.nl`
Jacob van der Woude	TUD	`J.W.vanderWoude@math.tudelft.nl`
Bernd Heidergott	TUD	`B.Heidergott@math.tudelft.nl`
Robert Jan van Egmond	TUD	`R.J.vanEgmond@math.tudelft.nl`
Guy Cohen	ARMINES	`cohen@cas.ensmp.fr`
Jean-Pierre Quadrat	INRIA-Rocq	`Jean-Pierre.Quadrat@inria.fr`
Stéphane Gaubert	INRIA-Rocq	`Stephane.Gaubert@inria.fr`
Marianne Akian	INRIA-Rocq	`Marianne.Akian@inria.fr`
Alain Jean-Marie	INRIA - SA	`Alain.Jean-Marie@sophia.inria.fr`
Bruno Gaujal	INRIA - SA	`Bruno.Gaujal@sophia.inria.fr`
Dohy Hong	INRIA - SA	`Dohy.Hong@sophia.inria.fr`
Bart de Schutter	KUL	`Bart.DeSchutter@esat.kuleuven.ac.be`
Colin Sparrow	HP	`c.sparrow@newton.cam.ac.uk`
Eleni Katirtzoglou	HP	`ek@hplb.hpl.hp.com`
Jean Mairesse	LIAFA	`mairesse@litp.ibp.fr`
Rein Smedinga	RUG	`rein@cs.rug.nl`
Sami Lifsches	RUG	`sam@cs.rug.nl`
Vincent Blondel	ULG	`blondel@math.ulg.ac.be`

E. Software course

PROGRAMME

C. Gomez: General Presentation of Scilab\ (Introduction, General Functionalities, Introduction to Metanet),
J.-P. Quadrat: Basic Max-Plus Operators in Scilab,
S. Gaubert: Max-Plus Linear Algebra in Scilab,
A. Jean-Marie: General Presentation of Ers,
A. Jean-Marie: Basic Manipulation on Ers,
J.E. Pin: Semigroupe,
J.E. Pin: Exercises on Semigroupe,
A. Jean-Marie: Advanced Ers,
G. Cohen: Manipulation of Max-plus Linear Systems in Scilab (an example).

LIST OF PARTICIPANTS C. Gomez
R. De Vries
E. Katirtzoglou
J. Mairesse
G. Soto Y Koelemeij er
R.J. van Egmond
P. Lotito
S. Gaubert
G. Cohen
J.-E. Pin
A. Jean-Marie
J.-P. Quadrat

F. Workshop non-expansive maps

SCHEDULE

Monday 20 July 1998


10:00	"Periodic Points of Nonexpansive Maps and Nonlinear
	Generalizations of the Perron-Frobenius Theory, Part I"
	Michael Scheutzow, TU, Berlin
	(joint work with R.D. Nussbaum and S. Verduyn Lunel)
11:00	Coffee break
11:30	"Periodic Points of Nonexpansive Maps and Nonlinear
	Generalizations of the Perron-Frobenius Theory, Part II"
	Roger D. Nussbaum, Rutgers University
12:30	Lunch
14:00	"About the Cycle-Time Vector
	of some Nonexpansive Maps"
	Eleni Katirtzoglou, BRIMS
15:00	Coffee break
15:30	"Infinitely Dimensional Nonexpansive Maps
	and the Option Pricing Theory"
	Vassili Kolokoltsov, Nottingham Trent University
16:30-18:00	Discussions

Tuesday 21 July 1998


10:00	"Asymptotic Estimates for the Maximum Period
	of a Periodic Point of Nonexpansive Maps"
	Sjoerd M. Verduyn Lunel, Vrij e Universiteit Amsterdam
11:00	Coffee break
11:30	"Integral Rigid Sets in Finite Dimensional
	₁ and _&inf; Spaces"
	Bas Lemmens, Vrij e Universiteit Amsterdam
12:30	Lunch
14:00	"Analytic Expansions for Iterates of
	Random Non-Expansive Maps"
	Part 1: Expansions for Lyapunov Exponents
	François Baccelli, INRIA-Sophia
15:00	Coffee break
15:30	"Analytic Expansions for Iterates of
	Random Non-Expansive Maps"
	Part 2: Analyticity via Contraction
	Dohy Hong, INRIA-Sophia
16:30-18:00	Discussions

Wednesday 22 July 1998


10:00	"Periods for Nonexpansive Maps"
	Colin Sparrow, University of Cambridge
11:00	Coffee break
11:30	"Main Results and Methods of Idempotent Analysis"
	Vassili Kolokoltsov
	(monograph presentation)
12:00	Lunch
13:30	"Computing the Cycle Time of
	Finitely Generated Monotone Homogeneous Maps"
	Stéphane Gaubert, INRIA
14:30	Coffee break
15:00	"Nonexpansive Dynamics:
	some theorems and some conjectures"
	Jeremy Gunawardena, BRIMS
16:00-17:30	Discussions
17:30	Closure of the Workshop

LIST OF PARTICIPANTS

François Baccelli, INRIA-Sophia *

Andy Burbanks, University of Cambridge

Sean Collins, University of Bristol

Stephane Gaubert, INRIA-Rocquencourt *

Jeremy Gunawardena, HP

Bernd Heidergott, TUD *

Dohy Hong, INRIA-Sophia Antipolis *

Eleni Katirtzoglou, HP

Vassili Kolokoltsov, Nottingham Trent University

Bas Lemmens, Vrij e Universiteit Amsterdam

Roger Nussbaum, Rutgers University

Geert Jan Olsder, TUD

Antony Quas, University of Memphis

Michael Scheutzow, Technische Universität Berlin

Colin Sparrow, University of Cambridge

John Toland, University of Bath

Sjoerd Verduyn Lunel, Vrij e Universiteit Amsterdam

The participants indicated by * were funded by Alapedes.

G. Spring school

PROGRAMME

Lundi 4 mai

M. Nivat: Introduction

M. Gondran: Algèbre max-plus, semi-anneaux et dioïdes: le début d'une histoire

S. Gaubert: Semianneaux idempotents: résultats de base illustrés. Théorie spectrale (max,+)

G.J. Olsder: Introduction to timed discrete event systems

Exercices: Évaluation de performance de systèmes à événements discrets simples (exemples d'ateliers)

Mardi 5 mai

J. Berstel: Introduction aux séries rationnelles et aux automates

G.J. Olsder: Applications of the max-plus algebra to time tables of railway systems and to synchronization of traffic lights

G. Cohen: Résiduation et applications

P. Butkovi?: Regularity of matrices, assignment problems, time-complexity

Exercices: Automates et séries

Mercredi 6 mai

G. Cohen: Représentations externes des systèmes

F. Baccelli: Systèmes (max,+) linéaires aléatoires

J. Mairesse: Automates (max,+), réseaux de Petri 1-bornés et ordonnancement

Presentation of available software

Exercices: Représentation de systèmes à ressources partagées, ordonnancement

Jeudi 7 mai

I. Simon: The tropical semiring and decidable problems

I. Simon: The tropical semiring and undecidable problems

J.P. Quadrat: Dualité entre le calcul des probabilités et l'optimisation

L. Libeaut: Commande de SED - Théorie des langages commandables

J. Gunawardena: Max-plus algebra and non-expansive maps

LIST OF SPEAKERS F. Baccelli INRIA-Sophia Antipolis France
J. Berstel Marne-la-Vallée France
P. Butkovic Birmingham United Kingdom
G. Cohen ARMINES France
S. Gaubert INRIA-Rocquencourt France
M. Gondran EDF France
J. Gunawardena HP United Kingdom
L. Libeaut IRCyN Nantes France
J. Mairesse LIAFA France
G.J. Olsder TUD The Netherlands
J.P. Quadrat INRIA-Rocquencourt France
I. Simon Saõ Paulo Brasil

H. WODES'98

Below the contributions by, and then the names of, researchers belonging to the Alapedes network are inserted. Page http://bode.diee.unica.it/wodes98/wodes98.html on Internet gives full, and more complete, information on all events.

WODES'98 contributions 4 0.7exth Workshop on Discrete Event Systems August 26-28, 1998 - Cagliari ITALY LIST OF PRESENTATIONS Non-ambiguous Petri nets and their application to the modeling of ATM switches.
B. Gaujal, A. Jean-Marie and G. Siegel
Monotone rational series and (max,+) algebraic models of real-time systems.
A. Benveniste, C. Jard and S. Gaubert
On the Boolean minimal realisation problem in the (max,+) algebra.
B. De Schutter and B. De Moor
A non-linear hierarchy for discrete event dynamical systems.
S. Gaubert and J. Gunawardena
Optimisation of synchronisation constraints using weak derivatives.
B. Heidergott
Regular ordering and applications in control policies.
B. Gaujal
The (max,+) algebra applied to synchronisation of traffic light processes.
R.J. van Egmond and G.J. Olsder
On max-algebraic models for transportation networks.
R. de Vries, B. De Schutter and B. De Moor
On large scale max-plus algebra model in railway systems.
G.J. Olsder, Subiono and M. Mc Gettrick LIST OF PARTICIPANTS

Marianne Akian
Vincent Blondel
Guy Cohen
Robert Jan van Egmond
Stéphane Gaubert
Bruno Gaujal
Bernd Heidergott
Hong Dohy
Alain Jean-Marie
Eleni Katirtzoglou
Sam Lifshes
Jean Mairesse
Rein Smedinga
Colin Sparrow
Niek Tholen
Geert Jan Olsder
Jean-Pierre Quadrat
Bart De Schutter
Jacob van der Woude

I. Tropical Algebra

PROGRAMME Sixième réunion du groupe de travail ALGÈBRES TROPICALES ... GdR/PRC AMI et GdR/PRC Automatique

Mercredi 3 Décembre

09.30Bruno Gaujal Multimodularité, convexité et propriétés d'optimisation

11.00Pause

11.30Guy Cohen Projecteurs (max,+)-linéaires

12.30Déjeuner

14.30Stéphane Gaubert Algorithmes de Howard dans l'algèbre (max,+)

16.00Pause

16.30Dohy Hong Analytic expansions of (max,+) Lyapunov exponents

17.15Alain Jean-Marie Présentation d'Ers

18.00Fin de la journée

Jeudi 4 Décembre

09.00Jacques SakarovitchAutomates à multiplicité dans mnp et le problème de
l'étoile: une introduction

10.30Pause

11.00Edouard Wagneur Éléments de géometrie et d'algèbre max-linéaire

14.00Jean-Éric Pin Calcul de sémigroupes

15.00Michael Mc Gettrick Implementation of the (max,+)-algebra in Scilab

16.00Fin de réunion

Rein Smedinga rein@cs.rug.nl Mon Feb 1 13:29:00 MET 1999

Annual progress report ALAPEDES Contract ERB-FMRX-CT96-0074

Contents

1. Introduction

1.1. The network

1.2. The report

1.3. Legend

1.3.1. Partners

1.3.2. Subprojects

1.3.3. Glossary

2. Progress

2.1. Scientific results

2.1.1. T-1

2.1.2. T-2

2.1.3. T-3

2.1.4. T-4

2.1.5. T-5

2.1.6. A-1

2.1.7. A-2

2.1.8. A-3

2.1.9. S-1

2.1.10. S-2

2.1.11. Milestones

2.2. Scientific highlights

2.3. Networking and coordination

2.3.1. General coordination

2.3.1.1. E-mail

2.3.1.2. Database

2.3.1.3. Vacancies

2.3.1.4. Formal contacts

2.3.1.5. Sponsoring

2.3.2. Management committee

2.3.3. Plenary meeting

2.3.4. Subproject meetings

2.3.4.1. Software course

2.3.4.2. Non-expansive maps

2.3.4.3. Noirmoutier

2.3.4.4. WODES'98

2.3.4.5. Heap models

2.3.4.6. Software development

2.3.4.7. Tropical Algebra

2.3.5. Further networking

2.3.5.1. Internet

2.3.5.2. Conferences

2.3.5.3. Theses

2.4. Researchers

2.4.1. Publication of vacant positions

2.4.2. Dissemination of applications

2.4.3. Researchers paid from the network

2.4.3.1. Integration

2.4.3.2. Stéphane Perennes

2.4.3.3. Bernd Heidergott

2.4.3.4. Michael Mc Gettrick

2.4.3.5. Remco de Vries

2.4.3.6. Eleni Katirtzoglou

2.4.3.7. Sam Lifshes

2.4.3.8. vacancy ARMINES

2.4.3.9. vacancy INRIA-Sophia Antipolis

2.4.3.10. vacancy LIAFA

2.4.3.11. vacancy ULG

2.4.3.12. vacancy KUL

2.5. Interactions with industry

2.6. Difficulties encountered

3. Factual information

3.1. Scientific speciality

3.2. Research staff

3.3. Researchers financed

3.4. Publications

3.4.1. Publications by Alapedes researchers

3.4.2. Publications by other Alapedes members

3.5. Secondments

4. Joint work

4.1. Joint publications

4.2. Collaboration

4.3. Conference visits by Alapedes-members

4.3.1. Cagliari convention

4.3.2. Other conferences and workshops

4.3.3. External collaboration by Alapedes-members

A. Research effort

B. Publications

C. Contacts

Annual progress report ALAPEDES
Contract ERB-FMRX-CT96-0074

Rein Smedinga
rein@cs.rug.nl
Mon Feb 1 13:29:00 MET 1999