What Are Discrete Event Systems?

Discrete event systems are dynamical systems in which state changes occur in response to the occurrence of discrete, asynchronous events rather than unfolding continuously over time. The system occupies a state that remains constant until an event triggers a transition to a new state; the sequence and timing of events, not a continuous flow of time, drives the system's evolution. Discrete event systems theory provides a formal framework for modeling, analyzing, and designing systems of this kind, drawing on automata theory, formal language theory, and queuing theory. The field covers both theoretical foundations and practical design problems that arise in manufacturing automation, communication networks, logistics, and embedded control systems.

The discipline was given a unified theoretical footing by P. J. Ramadge and W. M. Wonham in a landmark 1987 paper in SIAM Journal on Control and Optimization, which formulated the supervisory control problem for discrete event processes using formal language models and established the concept of controllable languages.

Formal Models and Language Theory

The primary formal model in discrete event systems theory is the finite automaton, or labeled transition system, in which states represent conditions of the system and labeled edges represent events that cause state transitions. The language generated by an automaton is the set of all event sequences the system can produce, and specifications on desired system behavior are expressed as languages. A system satisfies a specification if its generated language is a subset of the specified language.

This language-theoretic viewpoint allows specification problems to be cast as language containment and synthesis problems that can be solved algorithmically. Regular languages, accepted by finite automata, correspond to specifications that can be verified by polynomial-time algorithms. The MIT lecture notes on discrete Fourier and control transforms illustrate how formal decomposition applies broadly to systems with event-driven dynamics, grounding the mathematical framework shared across signal processing and control.

Nondeterministic automata and partial observation models extend the framework to systems where the supervisor cannot observe every event, leading to problems of state estimation and diagnosis under uncertainty.

Supervisory Control Theory

Supervisory control theory addresses the problem of restricting the behavior of a plant (a discrete event system representing a physical process) to a legal sublanguage by enabling and disabling controllable events. A supervisor observes the sequence of events produced by the plant and responds by enabling or disabling the subset of events it can influence, while uncontrollable events such as machine failures or sensor triggers remain outside its authority.

The Ramadge-Wonham supervisory control framework showed that the supremal controllable sublanguage of a given legal language can be computed constructively, providing a systematic design procedure for supervisors that guarantee legal behavior while permitting as much plant activity as possible. This result has been extended to modular supervisory control, where a complex specification is decomposed into a set of simpler local specifications, and to timed discrete event systems, where event occurrence is constrained to time windows rather than being purely asynchronous.

Petri Nets and Timed Models

Petri nets offer an alternative graphical and mathematical model for discrete event systems, particularly well suited to systems with concurrent processes and shared resources. A Petri net consists of places, transitions, and directed arcs, with tokens on places representing the distribution of system state. Firing a transition consumes tokens from input places and deposits tokens on output places, modeling the occurrence of an event that requires and produces conditions. Petri nets explicitly represent concurrency, which finite automaton models capture only through parallel composition, and they have been used extensively to model flexible manufacturing systems, communication protocols, and workflow processes. The Springer volume on modular supervisory control describes how Petri net and automaton models interact in compositional synthesis methods.

Timed extensions of both automata and Petri nets associate time bounds with transitions, enabling performance analysis of throughput, cycle time, and deadline satisfaction alongside the logical correctness properties addressed by untimed models.

Applications

Discrete event systems have applications in a range of fields, including:

• Flexible manufacturing cell sequencing and deadlock avoidance
• Communication network protocol verification and admission control
• Railway and air traffic control scheduling
• Workflow management in enterprise and business process systems
• Fault diagnosis and reconfiguration in automated production systems