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

Period: October 01, 1996 - September 30, 1997

This is the html-version of the annual report. Not all sections are present here. Math may not be displayed right. A postscript version is available as well.

0. Introduction

0.1. The network

1.1. Scientific results

1.2 Scientific highlights

1.3 Networking and coordination

1.3.1. General coordination

1.3.2. Management committee

1.3.3. Plenary meeting

1.3.5. Further networking

1.4. Researchers

1.4.1. Publication of vacant positions

1.4.2. Dissemination of applications

1.4.3. Researchers paid from the network

1.5. Interactions with industry

1.6. Researchers financed

2. Joint work

2.1 Joint publications

2.2. Collaboration

2.3. Conference visits by ALAPEDES-members

2.3.1. Waterford convention

2.3.3. External collaboration by ALAPEDES-members

Appendix A - Publications

0. Introduction

0.1. The network

ALAPEDES is an 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.

0.2. The report

This report describes the activities of the network ALAPEDES during the first 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 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, scientific highlights (1.2) for the general reader, reports on networking and coordination activities undertaken (1.3), introduces the researchers funded from 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 emerging 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 contact and coordination were sustained (3.2).

0.3. Legend

0.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;
scientific teamleader: G.J. Olsder; g.j.olsder@math.tudelft.nl
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;
scientific teamleader: G. Cohen; cohen@cas.ensmp.fr
INRIA: - Institut National de Recherche en Informatique et en Automatique) has two research teams involved in ALAPEDES:
INRIA-Sophia Antipolis (near Nice), France;
scientific teamleader: F. Baccelli; francois.baccelli@inria.fr
INRIA-Rocquencourt (near Paris), France;
scientific teamleader: J.-P. Quadrat; jean-pierre.quadrat@inria.fr
KUL: - Katholieke Universiteit Leuven, Leuven, België;
scientific teamleader: B. De Moor; bart.demoor@esat.kuleuven.ac.be
HP: - Hewlett Packard Limited, Basic Research Institute in the Mathematical Sciences (BRIMS), Bristol, United Kingdom;
scientific teamleader: J.H.C. Gunawardena; jhcg@hplb.hpl.hp.com
LIAFA: (formerly LITP) - Université Paris VII, Laboratoire d'Informatique Algorithmique: Fondements et Applications, Paris, France;
scientific teamleaders: J. Mairesse; mairesse@litp.ibp.fr and D. Krob; krob@litp.ibp.fr
RUG: - Rij ksuniversiteit Groningen, Groningen, Nederland;
scientific teamleader: R. Smedinga; rein@cs.rug.nl
ULG: - Université de Liège, Liege, Belgique;
scientific teamleader: V. Blondel; vblondel@ulg.ac.be

0.3.2. Subprojects

The ALAPEDES network is structured into ten closely related subprojects. Whenever possible activities and accomplishments in the sequel will be brought 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

0.3.3. Glossary

In the report the term (ALAPEDES) partner is used for the organizations that were listed in § 0.3.1; students preparing their graduation are called undergraduates, graduated students embarking 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 (most postdocs) who are paid by the network funds, and ALAPEDES member applies to (other) researchers working for some ALAPEDES partner.

1. Progress

After one year from its start, the ALAPEDES network activities are well on their way now, which, for the time being, culminated in a four days ALAPEDES workshop in Waterford (Ireland), September 7-10, 1997. For the next year of the ALAPEDES existence, new and similar activities are being planned.

1.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.

1.1.1. T-1

KUL has been working on the extension of previous results in connection with the minimal state space realization problem in the

(max,+)

algebra. More specifically the team has developed a heuristic procedure to compute a factorization of a matrix in the

(max,+)

algebra. This algorithm is used to determine the minimal system order (and to construct a minimal state space realization) of a max-linear time-invariant discrete event system.
Van der Woude (TUD) started independently with the problem of minimal state space realization in the

(max,+)

algebra setting along the lines of matrix factorizations, when it was realized that KUL had started earlier with the same problem and solution method. Some scientific discussions between the two took place, for instance during the European Control Conference in Brussels, July, 1997. A TUD undergraduate (Van der Bol) started recently his graduation project on relationships between the theory of nonnegative matrices and the

(max,+)

algebra.
Publications within ALAPEDES that are relevant to this part of the subproject are [16, 19, 24, 68].
Next the KUL team has studied sequences of consecutive powers of boolean matrices in the

(max,+)

algebra. Upper bounds have been derived for the length of the cycles of the ultimate periodic behaviour of a max-linear time-invariant discrete event system as a function of the size of the system matrix of the given discrete event system. The team has considered the transient part of the sequence of consecutive powers of

(max,+)

algebraic boolean matrices, and has derived upper bounds for the length of this transient part. This result has been used to prove 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, and to derive a lower bound for the minimal system order of a max-linear time-invariant boolean discrete event system.
Publications within ALAPEDES that are relevant to this part of the subproject are [18, 26].
ULG has been mostly involved in T-1 and T-2. Blondeel has investigated how complexity results obtained for the usual algebra extend to the

(max,+)

algebra. This work is in line with some previous joint work of Gaubert and Blondel (be aware that Blondel and Blondeel are different persons) and with an earlier undecidability result of Krob. Blondel has initiated with Gaubert and De Schutter an analysis of the realization problem from a decidability and complexity viewpoint. A ULG undergraduate (Cardol) has recently started his graduation project on the analyis of the algebraic properties of

(max,+)

matrices and their interrelation with analogous properties for positive matrices. At ULG Droesch is studying for an advanced degree. She is investigating the properties of rational series over non-associative variables.
Publications within ALAPEDES that are relevant to this part of the subproject are [6, 7, 17, 65, 66].

1.1.2. T-2

An important research item has been (and still is) the study on the existence of cycle time vectors for

(min, max,+)

systems, and various variations on this theme. The total system does not have to move with the same speed on the average; different subsystems can have time behaviours with different speeds. Hence the introduction of a cycle time vector rather than one cycle time (also referred to as eigenvalue). Both TUD (Perennes, Olsder) and HP/INRIA (Gunawardena, Gaubert) worked on this problem though the approaches are slightly different. The so-called duality-conjecture is also considered in both approaches.
The TUD approach can be seen as a (nontrivial) extension of properties, proofs, etc. known for

(max,+)

systems. Perennes started to work on stochastic extensions, for which the same train of thought is used.
Publications within ALAPEDES that are relevant to this part of the subproject are [57, 58].
The starting point of the HP/INRIA approach is the class of so-called topical functions (of which the

(min, max,+)

systems form a subclass -- in the latter the expectation operator is not included). Progress, jointly with Keane (Amsterdam) and Sparrow (Cambridge), is being made on dynamics of topical functions and non-expansive mappings generally. Deeper understanding is developing of a relationship with nonlinear Perron-Frobenius Theory. Katirtzoglou studies the relationship with so-called DAD theorems.
Subiono and Olsder continued the study of bipartite

(min, max,+)

systems (bipartite refers to a specific representation). Perennes and Olsder derived an upperbound on the period of non-expansive mappings.
Publications within ALAPEDES that are relevant to this part of the subproject are [59, 64].
In a joint effort of HP and INRIA-Rocquencourt Gaubert, Cochet-Terrasson and Gunawardena studied the standard multichain policy iteration algorithms (Howard), for stochastic or deterministic control and extend it to min-max functions. They obtained the following results.

In the min-max case, a new version of this policy iteration technique, coupled with the introduction of a semiring of germs of affine functions, allows them to prove the existence of the cycle time. The duality conjecture for min-max functions is obtained as a corollary.
The effective translation of the proof yields an efficient algorithm to compute the cycle time of min-max functions. One iteration of the algorithm essentially requires a) to evaluate the min-max function at a particular point, b) to solve a (reducible) $(max,+)$ spectral problem. The number of iterations of the algorithm is small, in practice (this quantity is difficult to estimate theoretically).
They show how the specialization of the (classical) multichain policy iteration to $(max,+)$ linear maps yields an algorithm which computes the cycle time in an almost linear time. By comparison with Karp's algorithm or linear programming, policy iteration is one order of magnitude faster. Numerical tests will be carried out.

Relevant publications in ALAPEDES on this part of the subproject are [10, 11, 34, 35, 36].
Activities by ULG under subproject T-2 are mentioned under § 1.1.1 (T-1).

1.1.3. T-3

The aim of this subproject is to optimize dynamic

(max,+)

systems such as deterministic or stochastic event graphs. The

(max,+)

algebra is well adapted to evaluate performance of a given system. But some parameters have to be optimized such as the number of resources of a given kind (number of tokens in a Petri net) or the schedule of the use of resources (the routing in a general Petri net).
Important conceptual progress has been achieved at INRIA-Rocquencourt and LIAFA by remarking that the schedule can be formulated in terms of heaps of pieces. This new point of view is under development.
Relevant publications in ALAPEDES on this part of the subproject are [37, 45, 53].
After an exploration phase of algorithms, as soon as the basic software will be available, a toolbox in SCILAB will be developed at INRIA and ARMINES including fast performance evaluation, resources optimisation and schedule optimization. Progress has been made on the problem of fast performance evaluation by using the Howard algorithm instead of the Karp algorithm.
In the case of stochastic event graphs the problem is still more complicated and new methods of perturbations analysis are explored at TUD (Heidergott). Analytic work allowing to compute explicitely the performance of some stochastic event graph done at INRIA-Sophia Antipolis is an important step towards optimization of such systems.
At TUD Heidergott optimizes stochastic

(max,+)

systems using weak derivatives techniques. He studies systems that can be described by the following recursion:

$x$ _µ (n+1) = A ( T , h ( x ( n ) , T , µ) ) × x_µ ( n ) , for n >= 0,

where

h

takes only finitely many values and, for given

h

A ( T , h )

is a matrix with random entries

T

and

µ in

µ in

R

. His aim is to maximize the given transient system performance index

L

, that is, to find

µ

such that

$E [ L (
x$ µ ( n ) : n <= m ) ] = max_µ in µ E [ L ( x_µ ( n ) : n <= m ) ] , for m >= 0 .

For example, $A$ may mimic a production system with several batch machines with dynamic batch-sizes and $h$ may represent the batch-size policy. Then the second equation refers to the problem of finding an optimal batch-size policy which maximises, say, the system throughput. The solution of it is well understood in case $µ$ is a parameter of the distribution of $T$ , however, it is an open question how to solve the problem in case $µ$ is a threshold parameter.
Relevant publications in ALAPEDES on this part of the subproject are [46, 48, 49].
INRIA-Sophia Antipolis has obtained various analytical representations and numerical algorithms for the expected value of any function of the stationary or transient state variables of an open stochastic $(max,+)$ linear system with a Poisson input point process.
First, Taylor expansions have been obtained in the intensity parameter $λ$ of the Poisson process. The coefficients of all orders are computed explicitly. Expressions for expected stationary waiting times of $(max,+)$ linear systems with deterministic services are deduced when the associated autonomous system has cyclicity 1.
In the deterministic case, use could be made of integral equations to characterize the distribution of the transient regime of the state variables, and to describe effective ways to evaluate it. From this, a representation is deduced of the stationary waiting time distribution in the case of general cyclicity.
Expansions for Laplace transforms, moments and distributions of these steady state variables are considered as specific instances of the main formula. Various examples are investigated, such as blocking (manufacturing and communication) queues, synchronized queueing networks and Kanban networks.
This research is based on the following papers: [3, 4, 5, 51].

1.1.4. T-4

The object of the subproject is to use automaton theory to study problems related to the control of discrete event systems. In LIAFA, some work has been done on the theoretical problems underlying T-4. Droste and Gastin have been working on formal power series in partially commuting variables.
Droste and Gastin chracterize in ([29]) the recognizable formal power series over arbitrary semi-rings and in partially commuting variables, i.e. over trace monoids. This provides a joint generalization of two very classical results: Schützenberger's and Ochmánski's theorems.
The relevance of this work to T-4 is due to the central rôle of trace monoids in the study of a large class of discrete event systems: safe Petri nets, see § 1.1.3 and [37].
As far as RUG is concerned, due to the fact that the ALAPEDES researcher (Lifsches) started only recently, research in ALAPEDES context is just starting, and specifically in the field of control of hybrid systems. Smedinga and Lifsches try to combine known results from the discrete event systems control area and from logics to obtain algorithms to find controllers in systems modelled by timed automata.

1.1.5. T-5

The purpose of this subproject is to study large event graphs or

(max,+)

linear systems possibly with a countable number of states, or systems with a continuous state space. Three main directions of research have been followed: 1) extending known results pertaining to

(max,+)

stochastic linear systems with finite state space to systems with a countable number of states; 2) putting the standard stochastic calculus and the

(max,+)

calculus into one common framework, thus generalizing all the limit theorems of probability in this way; 3) extending the notion of aggregation and reversibility to the

(max,+)

situation.
In the initial plan 6 months were allotted to this subproject. The effort done and the results obtained represent much more than what was initially scheduled. Nevertheless interesting work has still to be done and continued research in this domain is planned. The following fields of activity can be distinguished.

In recent work images, kernels of $(max,+)$ linear operators, and projections on images parallel to a kernel have been studied in joint effort by INRIA-Rocquencourt and ARMINES. In particular necessary and sufficient conditions under which it is possible to build a $(max,+)$ linear projector on the image or the kernel of a $(max,+)$ linear operator have been obtained. The results have been presented in [12, 13].
With this projector it is quite easy to copy old results obtained on aggregation coherency and reversibility of Markov chains, in the $(max,+)$ context. Aggregation and coherency are defined for general $(max,+)$ linear systems. A particular case called lumpability is studied for normalized linear systems (called Bellman chains by analogy with Markov chains). Then reversibility and partial reversibility are introduced.
These results are given in a section of a survey paper (see [61]), in which an attempt is being made to establish some links between statistical mechanics and $(max,+)$ algebra.
In a previous paper Quadrat, Viot and Akian (INRIA-Rocquencourt) have developed a probability theory over $(min,+)$ algebra, which can be seen as a formalism for optimization. This previous work is extended to include in the same framework the standard probability calculus and this formalism for optimization.
More precisely, for all positive $µ$ , the one-to-one map $x -> -µ log x$ transports the classical semi-field structure of $R$ ⁺ to $R + {+infinity}$ . Taking the limit when $µ$ goes to $0$ , we obtain the $(min,+)$ semi-field. Probabilities over all these structures are particular cases of capacities, for which weak convergence is defined. This allows one to present probability limit theorems, $(min,+)$ limit theorems for optimization and large deviation principles in an unified way.
In collaboration LIAFA and INRIA-Sophia Antipolis have considered an infinite tandem queueing system consisting of $/GI/1$ stations with i.i.d. service times. Such a model can be viewed as stochastic $(max,+)$ systems in infinite dimension.
They investigated the asymptotic behaviour of $t(n,k)$ , the interarrival times between customers $n$ and $n+1$ at station $k$ , and of $w(n,k)$ , the waiting time of customer $n$ at station $k$ . two versions of the model were considered: the quadrant and the half-plane. Some ergodic results were obtained for both versions of the model. This research is based on [1, 52].

1.1.6. A-1

The relationship between the

(max,+)

algebra at the theory side and time-tables of railway systems at the applications side has been known to exist for some time. At TUD Subiono and Olsder continued this research by looking at the railway system of the Netherlands, including intercity, fast and local trains (in a TUD doctoral thesis of 1993 only the intercity trains were considered). This gave rise to a system with a dimension of several hundred state variables. This dimensionality required a research to efficient numerical algorithms.
In the beginning the emphasis was on the so-called power-algorithm in which sparse matrices techniques were used (see [64]). Very recently Gaubert (INRIA) developed another method, based on a policy iteration algorithm (see under § 1.1.2 (T-2)), which looks more promising. The corresponding software (in C) has been made available to TUD and will be used routinely. ARMINES will investigate the same set up for SNCF (the French railway company).
Heidergott's work focuses on optimization of stochastic

(max,+)

systems. The specific application studied has to do with the arrivals of two trains in one railway station (see [47]). According to the time-table, these trains should wait one for the other. However, if one train arrives much later than the other, it may be better for this first arriving train not to wait. Because of the stochastic nature and scheduling features, this work will be more extensively reported upon under § 1.1.3 (T-3).
Official collaboration started recently with the faculty of Civil Engineering of TUD, and with Railned, a subsidiary of NS, the Dutch railway company. This collaboration has resulted in three postgraduate positions which are being filled. For more details, see under § 1.1.11 (milestones). The collaboration lead to [8].
KUL has developed methods to compute optimal and suboptimal traffic light switching schemes for traffic-light-controlled intersections given the arrival and departure rates in each lane; see [27]. TUD has recently started research on the synchronization of traffic lights (``phasing of traffic lights'', ``grüne Welle'').

1.1.7. A-2

In a joint enterprise by LIAFA and INRIA-Rocquencourt Gaubert, Hautecloque Raysz and Mairesse have studied the job shop scheduling problem using heaps of pieces and semigroups of matrices in the

(max,+)

algebra. They have shown the link between heap models and safe timed Petri nets, on which the jobshop modelling is based. Using trace techniques they have reduced considerably the number of schedules to consider. They have implemented in C and SCILAB a program computing the optimal schedule. Some numerical experimentations have been done on academic examples.
The theory is being studied in [37]. The implementation and experimentation are given in [45].
Reasons why few real-life examples have been studied will be given in § 1.5.

1.1.8. A-3

A case study in the use of recurrence equations in the detailed modelling of ATM

switches was initiated by INRIA-Sophia Antipolis. This work was in part triggered by discussions with Alcatel, a major company in the field. The representation formalism is that of ``unambiguous'' discrete time Petri nets. The modelling methodology is based on the combination of basic blocks. Several issues connected with the nature of the evolution equations associated with the model have been partially solved: their constructivity and their efficient implementation in programs for rapid simulation purposes. This research is based on [40] and [39].
Model of heaps of pieces (or Tetris games) have a close connection with communication networks. In fact, some basic communication networks can be modelled using heaps of pieces (see [67]). These networks are telephone networks with links having capacity one (a piece in the Tetris game corresponds to a phone call).
Several members of LIAFA (Krob, Mairesse, Choffrut, Gastin) and INRIA-Rocquencourt (Gaubert) have been working on the problem of exact computation of Lyapunov exponents (growth rate of a heap built by choosing the pieces in a random (Bernouilli) way). The Lyapunov exponent is directly related with the performance evaluation of the network, when the phone calls are modelled as random processes.
Different methods have been studied and compared. They are based, respectively, on non-commutative formal series (Krob), Markov chains and context-free grammars. For the moment, only small and toy examples have been successfully treated.
The relevance of this work to ALAPEDES is due to the central rôle of trace monoids in the study of a large class of discrete event systems: safe Petri nets; see § 1.1.4 and [37].

1.1.9. S-1

This subproject was of a specific nature. In fact, it did not involve any theoretical or applied research: the objective was to establish a review of all existing software at the beginning of the project. This goal has been accomplished, via the realization of a final document [54] Report on Subproject S-1: Existing software. The report has been made available on the web page (http://www.cs.rug.nlalapedes.html -- see § 1.3.5) of the ALAPEDES project. The document was prepared through a formal meeting which took place in Rocquencourt on November 8, 1996 (involving ARMINES, INRIA and LIAFA) and through several informal meetings and dicussions thereafter.
It appears that there exists a great number of available (free) software manipulating automata, Petri nets or queueing networks, i.e. the three basic modelling frameworks for discrete event systems.
On the other hand, there is a lack of software based on the algebraic representations of these objects. It is essential to try to develop such software within ALAPEDES. This effort has already started, as detailed in § 1.1.10 (S-2).

1.1.10. S-2

One letter rational series with multiplicities in the tropical semiring

(see [60]) have been studied by Kanta (LIAFA), and in particular the algorithmic issue of putting such series in a ``normal'' (or ``canonical'') form which allows to check equality of series (this problem is decidable for one-letter series only), of adding and multiplying such series and putting the result in the normal form again, etc.. A program in MAPLE (symbolic computation software) has been written by Kanta, which extends to the tropical semiring some of the functionalities already available in the MAX package of Gaubert (INRIA-Rocquencourt).
In prolongation of the work of Mairesse (LIAFA) and Gaubert (INRIA-Rocquencourt) on heaps of pieces, safe timed Petri nets, semigroups of matrices in the

(max,+)

algebra and trace monoids, a first ``SCILAB and C'' fast implementation of a scheduling algorithm (called Branch-and-Lex) has been contributed by Hautecloque Raysz (undergraduate at INRIA-Rocquencourt). It is based on a clever enumeration of possible schedules, given the precedence and competition constraints of tasks and resources, in order to avoid considering sequential schedules which differ only by the order in which tasks that are not competing for common resources are enumerated in a sequence.
Gaubert and an undergraduate at INRIA-Rocquencourt (Cochet-Terrasson) have been working on an efficient algorithm based on Howard's policy iteration algorithm to provide an alternative to Karp's algorithm for the computation of eigenvalues of

(max,+)

and other similar dynamic systems. This approach seems promising and the corresponding piece of software will be enhanced and ultimately incorporated in the ``SCILAB-Max-Plus'' package.
SCILAB is a freeware equivalent of MATLAB and it has been continuously developed at INRIA-Rocquencourt for years. With respect to MATLAB, it offers the additional feature of manipulating graphs and networks (graphically, algebraically, and in optimization problems) through the part called METANET. During this first year, Mc Gettrick (ARMINES), in close cooperation with INRIA, completed the first phase of adding

(max,+)

functionalities to this package: this includes most basic operations on matrices (addition, multiplication) and sparse matrices, computation of eigenvalues by Karp's algorithm, residuation, and so forth. Connections with METANET allow to represent graphs associated with matrices in the

(max,+)

algebra.
In addition to having to reconfigure the way data types are described in SCILAB in order to be able to introduce new algebras in a systematic manner now and in the future, it has been necessary to overcome the following difficulty: in the

(max,+)

algebra, it is common to manipulate values such as

-&inf;

and

+&inf;

as well as finite values, which becomes problematic when two infinite values of opposite sign are involved in the same (conventional) addition. This subsumes handling exceptions called NaN (Not A Number) in the proper way. Various solutions are possible but a universal solution which is both efficient in terms of execution time and robust on all platforms (UNIX, Linux, Windows, Mac OS) is still under study.
The software effort in the Mistral project has been oriented towards the development of simulators for Petri nets, based on algebraic evolution equations. This type of simulation is named ``equational simulation''. A class of timed Petri nets, called ``non-ambiguous Petri nets'' has been introduced, with the aim of broadening the modelling power of routed Petri nets, while keeping the same simulation algorithm. Nets in this class may have a general topology, and priority-based conflict resolution policies.
A set of tools implementing different simulation methods for non-ambiguous Petri nets has been developed. These methods include: translation into a queueing network simulated with the QNAP tool, interpreted simulation and compiled simulation in a stand-alone manner using the PROSIT simulation environment, which is being developed at INRIA. The simulation tools have been integrated to the modelling environment ERS.
Experiments are currently being carried out in order to assess the efficiency of the different simulation techniques. The target application of these tests concerns ATM communication networks (see under § 1.1.8 (A-3)).

1.1.11. Milestones

The book [41], edited by one of the ALAPEDES teamleaders, and describing the current developments in discrete event systems theory, will appear on the market in November, 1997.
The subproject S-1 has been concluded successfully; see the final report [54].
HP and the University of Cambridge has been awarded a 3 year EPSRC grant, entitled ``Dynamics of non-expansive maps: theory and application to discrete event systems'', to support a 3 year postdoc position in an area central to ALAPEDES (and specifically to T-2). Close collaboration is foreseen.
TUD approved a project about ``Seamless Multimodal Mobility''; see also [8]. This has resulted in several positions for postgraduates, two of which are closely related with discrete event systems. Van Egmond started September 1, 1997 on one of these positions, the other one is still vacant. Contacts with Railned (the scientific bureau of the Dutch railway campany) are intensified and this will lead to another opening at postgraduate level. The postgraduates on the three positions just mentioned will closely collaborate with ALAPEDES.
ALAPEDES organized a four days workshop for its researchers (and for some ``local'' researchers) in Waterford, Ireland.

1.2. Scientific highlights

As the number of vehicles and the need for transportation grow, cities around the world face serious road traffic congestion problems. Costs include lost work and leisure time, increased fuel consumption, air pollution, health problems, stress and discomfort. Furthermore, congestion slows the movement of goods and services, thereby increasing the price of products and reducing the competitiveness of business. ALAPEDES hopes to contribute to the solution of some of these problems in a modest way. In this way, applications to railway systems and time tables can be considered. The

(max,+)

algebra approach addresses, amongst others, questions related to departure times of trains at stations (how they should be scheduled) such as to have smooth change overs (passengers should not loose time by changing trains).
Contacts with railway companies exist (especially in the Netherlands, see under § 1.1.11 (milestones), but also in France and Belgium the contacts grow). Traffic control (the synchronization of traffic lights, grüne Welle) looks like a new promising field of application and ALAPEDES started research in this direction.

Realization theory

It is well known that an important class of discrete event systems can be described by a model that is linear in the $(max,+)$ algebra. Such a model can be characterized by a triple of so-called system matrices. The minimal realization problem -- the construction, given output of a system, of such a triple of matrices with dimensions that are as small as possible, but realize the observed behaviour of the system -- is one of the most important open problems. Research within ALAPEDES has resulted in a relatively fast heuristic procedure that can in many cases compute a (partial) minimal realization (see [24]). The complexity of the problem has also been investigated.
It has been realized only recently, by the ALAPEDES researchers, that the theory of timed discrete event systems based on the $(max,+)$ algebra can be incooperated in (and thus forms a subclass of) the theory of non-expansive mappings. There is a mutual benefit and fertilisation. The class of non-expansive mappings has less structure than the class of $(max,+)$ systems; its results are deeper (but fewer in number). For the class of $(max,+)$ systems more (technical) results are available.

Contributions by INRIA-Sophia Antipolis

New methods have been developed for computing statistics in stochastic $(max,+)$ linear systems. The problem of formulating stochastic discrete event systems in a theoretically sound way has been attacked as well. Structural results have been obtained on infinite dimensional stochastic $(max,+)$ systems.
In manufacturing emphasis has been laid on scheduling problems. As a first step to apply discrete event system in comunication networks novel simulation methods for Asynchronous Transfer Mode (ATM) switches were designed and implemented.
By means of the software developments one is able to study large scale systems (a few years ago systems of order 50 were considered to be very large, now it seems that systems up to an order of 1000 can be routinely studied). Especially INRIA-Rocquencourt, ARMINES and LIAFA are developing new promising software algorithms within the so-called SCILAB environment. The development of software tools fulfills two aims: at the theoretical level, the fact that they enable researchers to handle non-trivial examples fosters intuition for potential theoretical results; and at the more applied level -- and this mainly concerns software which uses numerical (rather than algebraic) programming languages -- dealing with real life applications makes the availability of such software an absolute necessity. This is the sense of the effort that is pursued under § 1.1.10 (S-2) and will be continued in the next years.
Another scientific highlight, though of a different nature, was the ALAPEDES workshop held in Waterford, Ireland. There the ALAPEDES researchers and some researchers from Ireland presented their latest results.

1.3. Networking and coordination

1.3.1. General coordination

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).

Database

A database is being set up (both in physical and in electronic form) with publications in the ALAPEDES subject field. It will be managed by the coordinator's partner and is aimed to mediate and spread knowledge gained in the ALAPEDES setting.

Vacancies

The issue of coordination in the quest for suitable candidates for vacant positions for ALAPEDES researchers is treated in § 1.4.1.

Formal contacts

Through the network coordinator (TUD) several questions were asked to the European Commission via its project officer. They concerned researchers above 35 years of age, refunding of travelling outside the European Union, publishing vacancies, the rule on previous employment in the same member state and requirements to reporting, amongst others. In some specific occasions there has been direct contact between other ALAPEDES partners and the European Commission project officer.

1.3.2. Management committee

The management committee meeted twice: on December 19, 1996 in Delft, and on September 10, 1997 in Waterford. Progress within the subprojects, filling in vacancies for ALAPEDES researchers and difficulties encountered were discussed and plans were set out for the period to come. Minutes of such meetings become available for internal use.

1.3.3. Plenary meeting

In September, 1997, all ALAPEDES members met in Waterford 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. The meeting was open to researchers from outside the network and attracted attendees from the Dublin Institute of Applied Statistics and from the Waterford Institute of Technology. One of the presentations was given by a researcher from Dublin.
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 § 1.3.2) as well, has been very successful and marked the end of the first ALAPEDES year.

T-1

In subproject T-1 mutual visits have been paid by members of TUD, KUL and ULG, in which mainly realization issues have been discussed (see under § 1.1.1).

T-4

A close collaboration on the problematic of T-4 has started between Blondel (ULG) and Krob (LIAFA). It has been materialized by two visits of Krob to Blondel in Liège.

A-1

In order to investigate potential applications of discrete event systems for the Belgian railway system De Schutter and De Vries brought a visit to Blondel.

A-2, A-3

Close collaboration took place between Gaubert (INRIA-Rocquencourt) and Mairesse (LIAFA), who met about every two weeks (on average) to work together. This collaboration was finalized by a joint publication (see [37]).

S-1

A formal meeting of subproject S-1 took place in Rocquencourt (involving ARMINES, INRIA and LIAFA). The document finalizing S-1 ([54]) was also prepared through several informal meetings and dicussions.

S-2

All the teams involved in subproject S-2 have worked in close contact, and very often jointly, with each other. The actions of the first year were prepared by two meetings at Rocquencourt (involving ARMINES, INRIA-Rocquencourt and LIAFA, and ARMINES, INRIA-Rocquencourt and INRIA-Sophia Antipolis, respectively). Moreover, a meeting is held every week between INRIA-Rocquencourt and ARMINES around the work done in SCILAB.
Several other opportunities for the teams to meet each other are being exploited, of which the meetings of the French (CNRS) working group ``Tropical Algebra'' every three months in Paris deserve to be acknowledged, where quite a few ALAPEDES members meet.
The meetings of this working group were organized in Paris; Gaubert served as one of their organizers. At http://amadeus.inria.fr/TROPICAL/ full information on this working group is accessible. The group met at June 6-7, 1996, October 21, 1996, December 2, 1996, March 17, 1997 and June 25, 1997. These meetings have concerned Cohen, Gaubert, Quadrat, Akian and several people from INRIA-Sophia Antipolis and LIAFA.

1.3.5. Further networking

Internet

At the address http://www.cs.rug.nlalapedes.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.

Brochure

A brochure aiming at a general public is included as well. The European Commission plans to issue brochures like this, for which this brochure was compiled. In the process of compilation the communication with the European Commission offices proved to be less fluent than anticipated, but joint action of TUD and ARMINES cleared the situation.

Conferences

ALAPEDES members meet each other frequently at conferences beyond the network. In this respect the European Control Conference, held in Brussels from July 1 up to July 4, 1997, is 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 continue to schedule its meetings in combination with other events; the second plenary meeting for instance will be coupled to WODES '98 in Cagliari, which promises to build a very fruitful combination.

Theses

Several instances of co-supervised theses foster networking within ALAPEDES. Under this category the doctoral theses of Van Bracht ([9]), Blondeel and Menguy should be mentioned, and the guidance of the graduation work of Hautecloque Raysz.

1.4. Researchers

1.4.1. Publication of vacant positions

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

e-letter on Systems, Control and Signal processing, issue no. 91, March 1, 1996, and issue no. 110, October 1, 1997;
e-letter on discrete event systems (echong@ecn.purdue.edu) (sent in March 4, 1996, October, 1997);
ilas-newsletter (ilas-net@math.technion.ac.il) (March 19, 1996, September, 1997);
scme@euler.cs.kuleuven.ac.be (sent March 19, 1996);
NA-NET News Digest (http://www.netlib.org/na-net/na_home.html) (sent March 19, 1996);
http://gauss.technion.ac.il/iic (sent March 19, 1996);
http://www5.informatik.tu-muenchen.de/sci-comp/home.html (sent March 19, 1996);
http://www.cs.rug.nlalapedes.html;
http://www-uk.hpl.hp.com/brims/;
e-letter on hybrid systems (lemmon@maddog.ee.nd.edu), October, 1997;
CORDIS http://www.cordis.lu/tmr/src/mat741.htm (sent in June 20, 1996); and
Sportello giovani (http://www.infm.it) (sent in June 28, 1996).

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

1.4.2. Dissemination of applications

Applications were assembled by the coordinating partner and distributed by regular and electronic mail within the network. Some ALAPEDES partners 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 the short existence of ALAPEDES, because of difficulties in solliciting and in tying postdocs with a temporary position to the network this intention has not been concretized yet.

1.4.3. Researchers paid from the network

A list of ALAPEDES researchers can be found in § 1.6. where also a table of all other researchers involved in ALAPEDES can be found.

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.

Stéphane Perennes

Mid-November, 1996 Stéphane Perennes started at TUD. Since then and progressively team meetings have been hold regularly, in which various issues were discussed between the team members (Olsder, Perennes, Heidergott, Subiono and Van der Woude) working in the ALAPEDES field.
Stéphane Perennes studies mainly additive topical functions by transforming them to the Hilbert projective space. Questions relating to the existence of cycle time vectors have been answered successfully in collaboration with Gunawardena (HP). Some of his contributions at the algorithmic aspect eased computations in for instance subproject A-1. Next deterministic convergence results have been generalized to the case of stochastic $(min, max,+)$ systems.
Publications by Stéphane Perennes are [57, 59, 58, 50, 30, 32]. The summary above is an abridged version of an activity report by Stéphane Perennes that is available upon request.
Perennes participated in postgraduate courses of DISC (Dutch Institute of Systems and Control) in Utrecht. Subjects studied were linear matrix inequalities and system design. he joined the appertaining monthly group seminar as well.

Bernd Heidergott

Bernd Heidergott started his work for ALAPEDES on April 1, 1997. He is focusing on stochastic $(max,+)$ systems, using the notion of weak derivatives as his main analysis tool. See § 1.1.3 for his approach to these systems. Another subject studied is the determination of the optimal waiting time in case of stochastic arrival times of trains. This part of his research falls under subproject A-1; see § 1.1.6. One of his prominent interests is the application of stochastic $(max,+)$ theory to queueing systems and to elaborate on optimization of these systems. Bernd Heidergott is in permanent discussion with N. Krivulin (St. Petersburg, Russia) and hopes to start to do joint work with him soon. Publications by Bernd Heidergott are [44, 46, 47, 48, 49]. The summary above is an abridged version of an activity report by Bernd Heidergott that is available upon request.

Michael Mc Gettrick

ARMINES has been hiring Michael Mc Gettrick (on leave from the Waterford Institute of Technology) since January 1, 1997 and plans to do so until end of May, 1998. At this date, Michael Mc Gettrick will move to INRIA-Rocquencourt to complete his work with the extensions of SCILAB towards the themes of interest in ALAPEDES.
As a consequence of the nature of his contribution to ALAPEDES (software development) Michael Mc Gettrick did not produce publications. A more elaborate description of his activities, however, can be obtained upon request.

Remco de Vries

At KUL Remco de Vries has been appointed as a postdoc in the framework of the ALAPEDES project. His appointment started on November 1, 1997 and will end on October 31, 1998. He is continuing some of the previous research of De Schutter in connection with the minimal state space realization problem in the $(max,+)$ algebra and, more specifically, state space transformations in the $(max,+)$ algebraic system theory. Publications by Remco de Vries are [17, 68].

Eleni Katirtzoglou

Eleni Katirtzoglou studies the relationship between topical functions and non-expansive mappings on the one hand and DAD theorems on the other.

Sam Lifshes

It was not until August 1, 1997, that RUG could appoint Sam Lifshes. He will try to combine known results from the discrete event systems control area and from logics to obtain algorithms to find controllers in systems modelled by timed automata, specifically related to the field of control of hybrid systems and thus contribute to the subprojects T-4 and A-3.

vacancy ARMINES

ARMINES presently considers the possibility of hiring another young researcher, indeed a postgraduate, by the end of 1997 and for three years. Contacts exist with a German postgraduate currently completing a MPhil in Southampton. The subject of his doctoral thesis is related to § 1.1.7 (A-2).

vacancy INRIA-Sophia Antipolis

INRIA-Sophia Antipolis is looking for a postdoc to contribute to subproject S-2.

vacancy LIAFA

LIAFA is looking for the replacement of Kanta who will leave soon.

vacancy ULG

Sébastien Blondeel has started a co-supervised doctoral study in January, 1997. He has since then been paid by his home university. The intended co-supervision is with Krob of LIAFA. Due to lack of financial support for the originally planned 1997-1998 year at LIAFA, Blondeel is likely to re-direct his research efforts. The doctoral position is open anew and has been advertised in September, 1997.

1.5 Interactions with industry

The TUD started a project called ``Seamless Multimodal Mobility'', a joint effort by various faculties among which the Faculty of Technical Mathematics and Informatics (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 is foreseen.
One of the other faculties is the one of Civil Engineering and a joint contract is about to be signed with Railned, the scientific company directly related to the Dutch railway company. This leads to one more postgraduate position. The contact persons with Civil Engineering are P. Bovy and I. Hansen; with Railned the contact persons are A. Schaafsma and A. Berger. See further under § 1.1.11 (milestones).
After a long investigation from their side ARMINES can mention recent contacts with SNCF

. The meeting with D. Gauyacq of the Research Department of this company took place in Rocquencourt on August 21, 1997, in the presence of the ARMINES and INRIA-Rocquencourt teams. It is hoped that such contacts will result in applications in the scheduling of trains (in particular the three main lines of TGV from West/South-West, South-East and North of France: they interact with each other in the Paris area, which requires some coordination).
Within subproject A-3 there are strong contacts with the French telecommunication firm Alcatel, especially on ATM switches. INRIA-Sophia Antipolis is currently discussing the simulation of ATM switches; this activity would pertain to subproject S-2.
The LIAFA team works on several problems related to cellular communication networks in relation with the research and developement departments of two important French companies (Nortel Matra Cellular and Bouygues Telecom). The problems that are addressed in the LIAFA team cover different aspects of the subject:

performance analysis of communication networks (a joint doctoral study with Nortel Matra Cellular is being set up);
routing optimization;
frequency allocation (a joint doctoral study with Bouygues Telecom is being carried out since one year);
optimal quantization; and
distributed synchronization algorithms for Base Transceiver Stations (a Nortel Matra Cellular patent with three members of LIAFA as authors will be made pending).

The LIAFA team organized also recently the workshop DialM '97 (Discrete Algorithms for Mobile Computing and Communications) that was the first issue of an IEEE/ACM workshop devoted to this subject.

HP attaches considerable importance to the problem of developing a mathematical infrastructure for studying computer systems. At the present time, however, fundamental breakthroughs in mathematical theory must be made before a significant impact can be made on engineering practice (for instance, in the area of timing analysis of digital circuits). The emphasis at present as part of ALAPEDES has been on the development of the theory and, in this respect, the team is delighted at the progress which has already been made.
At this moment of writing no specific contacts exist yet with manufacturing industry in relation with subproject A-2 because of the following reasons. First, it was necessary to make some progress with software before being in a position to address real-life problems. Second, we have difficulties in establishing fruitful contacts with people in this area. New efforts will be made in the direction of the French car manufacturer Renault. Third, a visit to Proth at INRIA-Lorraine, who is a leading expert in the domain of manufacturing systems, convinced the subproject leader that the emphasis in this field has to be laid on scheduling problems. Some of the work previously mentioned (see in particular the work by Gaubert, Mairesse and Hautecloque Raysz) is related to this general topic. Future efforts should also be oriented in the same direction of scheduling problems, even if not directly on manufacturing systems.

1.6. Researchers financed

In table 1 all ALAPEDES researchers have been listed; their nationality, date of birth, begin and prognosed end of their (present) appointment, the partner they are working at, and the specialities are given. 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 (Stéphane Perennes left actually this way by October 1, 1997) and 4) the reallocation between partners that is strived at (ALAPEDES researchers are encouraged to change their ``home base'' within the network).

name nationality appointment partner

Stéphane Perennes F 961115 - 970930 TUD

Bernd Heidergott D 970401 - 980331 TUD

Michael Mc Gettrick IRL 970101 - 980531 ARMINES

Remco de Vries NL 961101 - 981031 KUL

Eleni Katirtzoglou GR 961125 - 981125 HP

Sam Lifshes ISR 970801 - 990801 RUG

Table: Researchers financed within ALAPEDES.

**Table:** Researchers financed within ALAPEDES.
name nationality	appointment	partner
	Stéphane Perennes	F	961115	-	970930	TUD
	Bernd Heidergott	D	970401	-	980331	TUD
	Michael Mc Gettrick	IRL	970101	-	980531	ARMINES
	Remco de Vries	NL	961101	-	981031	KUL
	Eleni Katirtzoglou	GR	961125	-	981125	HP
	Sam Lifshes	ISR	970801	-	990801	RUG

2. Joint work

2.1 Joint publications

Joint papers -- defined as publications in which authors from at least two ALAPEDES partners have contributed -- are [1, 2, 11, 12, 13, 14, 15, 17, 34, 35, 36, 37, 38, 41, 52, 53, 55, 61, 62].

2.2. Collaboration

Many mutual visits have been paid by ALAPEDES members. In § 1.3.4 some extra information has been included on some of these contacts.

2.3. Conference visits by ALAPEDES-members

2.3.1. Waterford convention

The plenary meeting in Waterford brought together nearly all ALAPEDES members. Most of them presented (part) of their achievements of the first ALAPEDES year.

2.3.3. External collaboration by ALAPEDES-members

During the Waterford convention (the first plenary meeting of ALAPEDES; see § 1.3.3) several researchers from the DIAS (Dublin Institute of Advanced Studies) were welcomed. They are interested in stochastic aspects of discrete event systems. Fruitfull discussions have taken place and one presentation has been given.
In the framework of the establishment of DIOC's (Delft Interfaculty Research Centres), an official collaboration with the Faculty of Civil Engineering has been started. The name of the joined project is: ``Seamless Multimodal Mobility''. The subject areas are on mathematical applications towards transportation planning. See further in § 1.1.11.
L. Shue, postgraduate of prof. Anderson, Australian National University, Canberra, visited TUD during the period of June 26-28 and KUL from July 9 till July 10, 1997. He gave presentations with the title ``On steady-state properties of certain $(max,+)$ products''.
Prof. R. Nussbaum of Rutgers University (Princeton) paid a visit to Cambridge (funded by HP) during the period June 1-14, 1997 for discussions on periods of non-expansive maps, and DAD theorems. S. Verduyn Lunel also came from June 4 till June 6, 1997 for this subject.
M. Keane visited HP.
Santos Mendes (UNICAMP, Brasilia) visited INRIA-Rocquencourt on July 10, 1997, for discussions on $(max,+)$ algebra and discrete event systems.
D. Gauyacq of SNCF came on August 21, 1997 to INRIA-Rocquencourt for discussions about possible applications in railway systems.
É. Menguy, J. Boismond (and J.-L. Ferrier the second time) visited INRIA-Rocquencourt twice (one day in June, 1997, and the second time on August 28, 1997) for discussions around Menguy's thesis. Cohen is going to serve as a referee of this thesis.
Cohen, Gaubert and Quadrat visited J.-M. Proth of INRIA-Lorraine (Nancy, France) on April 2, 1997, for discussions of manufacturing systems applications.
Krob visited the Queen Mary College in London from January 6 till January 7, 1997. There P.M. Cohn and A. Watkinson work on a topic close to ALAPEDES: non-commutative formal series.
Krob visited the Athens University of Economics during the period April 10-21, 1997. He spoke with prof. Magirou about maritime transportation networks.
Pin visited the University of Porto, Portugal, from May 17 till May 22, 1997. He had contact with J. Almeida about finite semigroups.
During the INFORMS conference in Boston Heidergott had intensive discussions with M. Fu, who is an expert in the area of stochastic optimization (he published several articles on this topic and is author of a recent book on that topic). He showed interest in the optimization of stochastic $(max,+)$ -systems and Heidergott is optimistic to start some joined work with him.

Appendix A - Publications

References

1: F. Baccelli, A. Borovkov, and J. Mairesse. On large tandem queueing systems, 1997. To appear.
2: 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.
3: F. Baccelli, S. Hasenfuss, and V. Schmidt. Expansions for steady state characteristics in $(max,+)$ -linear systems. Report 2785, INRIA, 1996.
4: F. Baccelli, S. Hasenfuss, and V. Schmidt. Transient and stationary waiting times in $(max,+)$ -linear systems with Poisson input. Report 3022, INRIA, 1996.
5: F. Baccelli and V. Schmidt. Taylor series expansions for poisson driven $(max,+)$ -linear systems. Annals of Applied Probability, No. 6-1:138-185, 1996.
6: V. Blondel and J. Tsitsiklis. Complexity of elementary nonlinear and hybrid systems. In Proc. of the 4th European Control Conference (ECC'97), Brussels, July 1-4 1997. To appear.
7: V. Blondel and J. Tsitsiklis. When is a pair of matrices mortal? Information Processing Letters, 1997. To appear.
8: 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, Antwerp, July 12-17, 1998. Topic area: Travel and Shipper Behavior Approach.
9: E. van Bracht. On production lines with blocking. Doctoral thesis, Delft University of Technology, 1996. Defense was on December 20.
10: 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 DEA ``modélisation et méthodes mathématiques en économie'', Université de Paris I, 1996.
11: J. Cochet-Terrasson, S. Gaubert, and J. Gunawardena. Dynamics of min-max functions. Technical Report HPL-BRIMS-97-13, HPL-BRIMS, August 1997. Submitted for publication.
12: G. Cohen, S. Gaubert, and J.-P. Quadrat. Linear projectors in the max-plus algebra. Proceedings of the 5th IEEE Mediterranean Conference on Control and Systems, Paphos, Cyprus, July 21-23 1997.
13: 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 19-21 1996.
14: 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.
15: G. Cohen and MAX PLUS. 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.
16: B. De Schutter. Max-Algebraic System Theory for Discrete Event Systems. Doctoral thesis, Faculty of Applied Sciences, K.U. Leuven, Leuven, Belgium, 1996.
17: 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, Leuven, Belgium, August 1997.
18: 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, Leuven, Belgium, 1996.
19: 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.
20: 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, Leuven, Belgium, 1996. Accepted for publication in SIAM Journal on Matrix Analysis and Applications.
21: 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 Proc. of the IEEE Singapore International Symposium on Control Theory and Applications (SISCTA'97), pages 394-398, Singapore, July 29-30 1997.
22: 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, sep 1997.
23: B. De Schutter and B. De Moor. The linear dynamic complementarity problem is a special case of the extended linear complementarity problem. Internal Report 97-21, ESAT-SISTA, K.U. Leuven, Leuven, Belgium, 1997.
24: 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.
25: 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.
26: B. De Schutter and B. De Moor. On the sequence of consecutive matrix powers of boolean matrices in the max-plus algebra. Internal Report 97-67, ESAT-SISTA, K.U. Leuven, Leuven, Belgium, 1997.
27: B. De Schutter and B. De Moor. Optimal traffic signal control for a single intersection. Technical Report 97-10, ESAT-SISTA, K.U. Leuven, Leuven, Belgium, February 1997. Accepted for the 1997 International Symposium on Nonlinear Theory and its Applications (NOLTA'97), Hawaii, USA , Nov. 29-Dec. 3, 1997.
28: B. De Schutter and B. De Moor. The QR decomposition and the singular value decomposition in the symmetrized max-plus algebra. In Proc. of the 4th European Control Conference (ECC'97), Brussels, July 1-4 1997. Paper 295.
29: 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-TAC.
30: M. Flammini and S. Perennes. Lower bounds on systolic gossiping. In Proceedings of IPPS '97, pages 517-521, Genève, April 1997.
31: 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.
32: 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.
33: S. Gaubert and A. Giua. Petri net languages with infinite sets of final markings. In Smedinga et al. [62].
34: S. Gaubert and J. Gunawardena. The duality theorem for min-max functions, June 1997. Submitted to the C.R.A.S.
35: S. Gaubert and J. Gunawardena. The duality theorem for min-max functions. Technical Report HPL-BRIMS-97-16, HPL-BRIMS, August 1997. To appear in Comptes Rendus Acad Sci Paris.
36: S. Gaubert and J. Gunawardena. A proof of the duality conjecture for min-max functions. Draft, 1997.
37: S. Gaubert and J. Mairesse. Modeling and analysis of timed Petri nets using heaps of pieces. In Proc. of the 4th European Control Conference (ECC'97), Brussels, July 1-4 1997. Submitted to IEEE-TAC.
38: S. Gaubert and MAX PLUS. 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).
39: 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.
40: B. Gaujal, A. Jean-Marie, and G. Siegel. Modeling of ATM switches using non-ambiguous Petri nets, 1997. In preparation.
41: J. Gunawardena, editor. Idempotency. Cambridge University Press, Isaac Newton Institute, 1997.
42: J. Gunawardena. An introduction to idempotency. In Idempotency [41]. Technical Report HPL-BRIMS-96-24, September, 1996.
43: 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.
44: G. Gürkan and B. Heidergott. Weak derivative analysis of option pricing. Working paper, 1997. 6 Pages.
45: É. Hautecloque Raysz. Empilements de pièces, semi-anneau $(max, +)$ et ordonnancement. Rapport de stage de DEA, INRIA, June 1997.
46: B. Heidergott. On perturbation analysis. INFORMS Conference on Applied Probability, Boston, USA, June 30 - July 1 1997.
47: B. Heidergott. The Delft railway model. Working paper, 1997. 11 Pages.
48: B. Heidergott. Finite perturbation analysis for queuing networks. Journal of Discrete Event Dynamic Systems, 1997. Submitted. 31 Pages.
49: B. Heidergott. Infinitesimal perturbation analysis for queuing networks with general service time distributions. Report 97-33, Delft University of Technology, 1997. 30 Pages.
50: M.-C. Heydemann, N. Marlin, and S. Perennes. Complete rotations in Cayley graphs, 1997. Submitted to Discrete Applied Mathematics.
51: A. Jean-Marie. The waiting time distribution in Poisson-driven deterministic systems. Report 3083, INRIA, 1997.
52: J. Mairesse and B. Prabhakar (HP). On the departure from ./GI/1 queues in tandem, 1997. In preparation.
53: J. Mairesse, B. Prabhakar (HP), and N. McKeown. Optimality of Tetris models for multicast switching. Proceedings of CISS, Princeton, 1996.
54: J. Mairesse and LIAFA (LITP) team. Report on subproject S-1: Existing software. Final report, LIAFA, 1997. 14 pages.
55: MAX PLUS (collective name). Max-plus-times linear systems. Workshop on Open Problems in Mathematical Systems Theory and Control, Belgium, June 30 1997.
56: G.J. Olsder. Dienstregelingen en de max-plus algebra. Euclides, jaargang 72, no.4, 626 no. 4:158-163, 1997.
57: G.J. Olsder and S. Perennes. Iteration of min-max-plus functions.
58: G.J. Olsder and S. Perennes. On the long term behaviour of min-max-plus systems. Internal report.
59: G.J. Olsder and S. Perennes. The upperbound on the period of non-expansive mappings. internal report.
60: J.E. Pin. Tropical semirings. In Gunawardena [41].
61: J.-P. Quadrat and MAX PLUS. Min-plus linearity and statistical mechanics. Séminaire sur la mécanique statistique des grands réseaux, INRIA, October 21-25 1996. Submitted to Markov Processes and Related Fields, June, 1997.
62: R. Smedinga, M.P. Spathopoulos, and P. Kozák, editors. Proceedings on the International Workshop on Discrete Event Systems, WODES96, Edinburgh, Scotland, UK. Institute of Electronical Engineers, Computing and control division, August 19-21 1996.
63: M.P. Spathopoulos and R. Smedinga. Some issues on control of discrete event systems using model specifications. In Smedinga et al. [62].
64: Subiono and G.J. Olsder. On bipartite min-max-plus systems. In Proc. of the 4th European Control Conference (ECC'97), Brussels, July 1-4 1997. Report 96-100 of the faculty of Technical Mathematics and Informatics, T.U. Delft.
65: J. Tsitsiklis and V. Blondel. The spectral radius of a pair of matrices is NP-hard to compute. In Proc. of the 35th Conference on Decision and Control, pages 3192-3197, Kobe, Japan, 1996.
66: J. Tsitsiklis and V. Blondel. Spectral quantities associated to pairs of matrices are hard - when not impossible - to compute and to approximate. Math. of Control, Signals, and Systems, 1997. To appear.
67: 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.
68: R. de Vries and B. De Moor. Minimal realizations and state space transformations for discrete event systems. Internal report, ESAT-SISTA, K.U. Leuven, Leuven, Belgium, 1997.

...ATM

ATM stands for Asynchronous Transfer Mode

...tropical semiring

the set of integers with

max

as addition and

+

as multiplication

...SNCF

Société Nationale des Chemins de Fer Français

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

Rein Smedinga rein@cs.rug.nlTue Nov 25 10:24:09 MET 1997

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

Rein Smedinga
rein@cs.rug.nl
Tue Nov 25 10:24:09 MET 1997