A discrete event system (DES) is a dynamic, asynchronous system, where the state transitions are initiated by events that occur at discrete instants of time. Typical examples of DESs are: flexible manufacturing systems, telecommunication networks, traffic control systems, multiprocessor operating systems and logistic systems.
Although DESs lead to a nonlinear description in linear algebra,
there exists a subclass of DESs for which this model becomes ``linear''
when we formulate it in the max-plus algebra.
The basic operations of this algebra are
maximization (represented by 
)and addition (represented by 
).
This leads to a kind of state space description for a certain class
of DESs:
We have defined a mathematical programming problem: the Extended Linear Complementarity Problem (ELCP) and shown that this problem can be used to describe and to compute the solution set of a system of multivariate max-plus-algebraic polynomial equalities and inequalities. This enables us to solve some important fundamental max-plus-algebraic problems such as: computing max-plus-algebraic matrix factorizations, constructing matrices with a given max-plus-algebraic characteristic polynomial, performing state space transformations and computing partial or minimal state space realizations. Currently we are investigating the computational complexity of the minimal state space realization problem, and the existence and characterization of state space transformations.
Hybrid systems arise from the interaction between DESs and continuous-variable systems (these are systems that can be modeled using difference or differential equations). We have shown that the ELCP arises in the modeling of certain classes of hybrid systems such as complementary-slackness systems (typical examples of which are electrical networks with diodes, or mechanical systems subject to geometric inequality constraints) and traffic systems.