UK Nonlinear News, May 1996


The Algebraic Approach to Performance Evaluation of Discrete Event Systems
an European Community Research Network

  • Introduction
  • Research Focus
  • Participants
  • Vacancies
  • Network Coordinator
  • Introduction

    The European Community has recently approved the Research Network ALAPEDES, under the Training and Mobility of Researchers scheme. It is expected that up to 8 postdoctoral or PhD positions will become available among the nodes of the network, which are located in Belgium, England, France, and Holland. Positions are likely to start in October 1996 and last for periods varying from 2 to 4 years.

    Research Focus

    Discrete event systems are systems whose behaviour consists of the repeated occurrence of collections of events. Examples include a digital circuit, in which an event might be a voltage transition on a wire, or a distributed computer system, in which an event might be the receipt of a message. From a mathematical standpoint, such systems may be modelled as deterministic or stochastic dynamical systems. Typically, they are extremely nonlinear in character. From a practical standpoint, one would like to understand the asymptotic behaviour of the system. Does it reach an equilibrium or settle into some periodic regime? Is this regime stable with respect to change of parameters? How quickly is equilibrium reached? What happens as the size of the system goes to infinity?

    The algebraic approach to discrete event systems, is based on the observation that certain basic systems can be regarded as linear over suitable semirings in which the addition operation is idempotent. Surprisingly, many of the classical results of linear algebra and analysis have analogues over these idempotent semirings, giving rise to the subject of "idempotent analysis". Many of the questions rasied above can now be solved by idempotent linear techniques. However, these have not yet been applied to industrial scale problems and have not yet been incorporated in design tools for engineering use.

    Idempotent analysis turns out to have important implications for a wide variety of subjects: algebric automata theory, particularly decision problems relating to distance automata; viscosity solutions of nonlinear partial differential equations, particularly the Hamilton-Jacobi-Bellman equation; optimisation theory, where an idempotent measure theory appears as the large deviation limit of classical probability theory; fixed point problems for mappings which are nonexpansive with respect to the supremum norm. These, and other, directions are under intensive investigation at the various nodes of this Research Network.

    The challenge for the algebraic approach is threefold:

  • to explore the many ramifications of idempotent analysis;
  • to make idempotent methods usable at an industrial scale;
  • to extend the existing theory beyond the linear regime to a wider class of systems.
  • The purpose of the Research Network is to address these challenges.


    The 8 nodes of the Research Network are listed below.
    1. Delft University of Technology, Delft, Holland
      Faculty of Technical Mathematics and Informatics
      Teamleader and Network Coordinator: Geert-Jan Olsder
    2. Ecole Nationale Supérieure des Mines de Paris, Fontainebleau, France
      Centre Automatique et Systèmes
      Teamleader: Guy Cohen
      [Synopsis of ENSMP research interests in Alapedes
    3. INRIA Sophia-Antipolis, Sophia-Antipolis, France
      Teamleader: Francois Baccelli
      INRIA Rocquencourt, Rocquencourt, France
      Teamleader: Jean-Pierre Quadrat
    4. Catholic University of Leuven, Leuven, Belgium
      Department of Electrical Engineering
      Teamleader: Bart de Moor
    5. Hewlett-Packard Laboratories, Bristol, England
      Basic Research Institute in the Mathematical Sciences (BRIMS)
      Teamleader: Jeremy Gunawardena
      [Synopsis of BRIMS research interests in Alapedes]
    6. Laboratoire Informatique Théorique et Programmation
      Université Pierre et Marie Curie, Paris, France
      Teamleader: Daniel Krob
    7. University of Groningen, Groningen, Holland
      Research Institute of Mathematics and Computing Science
      Teamleader: Reinder Smedinga
    8. Université de Liège, Liège, Belgium
      Institute de Mathématique
      Teamleader: Vincent Blondel


    It is expected that up to 8 postdoctoral or PhD positions will become available in October 1996 at the various nodes of ALAPEDES. Because of the multidisciplinary nature of this Network, the positions will be attractive to candidates from a wide range of backgrounds in mathematics, computer science or engineering. Candidates should take note of the following restrictions imposed by the European Commission.
  • A candidates must be a national of a member state of the EC or of an associated state.
  • A candidate must not be a national of the state in which he or she takes up an appointment.
  • To apply for a position, or to seek further information regarding ALAPEDES, please contact Geert-Jan Olsder, the Network Coordinator.

    Network Coordinator

    Geert-Jan Olsder
    Delft University of Technology
    Faculty of Technical mathematics and Informatics
    PO Box 5031, 2600 GA Delft, Holland

    Tel: +31 15 278 1912
    Fax: +31 15 278 7209

    << Move to UK Nonlinear News Issue 4 Index Page (May 1996).

    Last Updated: 1st May 1996.