Introduction to Discrete Event Systems 2nd Edition

Introduction to Discrete Event SystemsIntroduction to Discrete Event Systems 2Introduction to Discrete Event Systems, 1st and 2nd Editions
Christos G. Cassandras and Stephane Lafortune

The rapid evolution of computing, communication, and sensor technologies has brought about the proliferation of new dynamic systems, mostly technological and often highly complex. Examples are all around us: computer and communication networks; automated manufacturing systems; air traffic control systems; and distributed software systems. The “activity” in these systems is governed by operational rules designed by humans; their dynamics are therefore characterized by asynchronous occurrences of discrete events. These features lend themselves to the term discrete event system for this class of dynamic systems.
A substantial portion of this book is a revised version of Discrete Event Systems: Modeling and Performance Analysis (1993), written by the first author, which received the 1999 HAROLD CHESTNUT PRIZE awarded by the International Federation of Automatic Control for best control engineering textbook. This new expanded book is intended to be a comprehensive introduction to the field of discrete event systems, emphasizing breadth of coverage and accessibility of the material to readers with possibly different backgrounds. Its key feature is the emphasis placed on a unified modeling framework that transcends specific application areas and allows linking of the following topics in a coherent manner: language and automata theory, supervisory control, Petri net theory, (max,+) algebra, Markov chains and queuEing theory, discrete-event simulation, perturbation analysis, and concurrent estimation techniques. Until now, these topics had been treated in separate books or in research literature only.
Introduction to Discrete Event Systems is written as a textbook for courses at the senior undergraduate level or the first-year graduate level. It will be of interest to students in a variety of disciplines where the study of discrete event systems is relevant: control, communications, computer engineering, computer science, manufacturing engineering, operations research, and industrial engineering.

Table of Contents


1. Systems and Models

System and Control Basics
Discrete Event Systems
Summary of System Classifications
The Goals of System Theory
Summary & Problems
Selected References

2. Languages and Automata

The Concepts of Languages and Automata
Operations on Automata
Finite-State Automata
Analysis of Discrete-Event Systems
Summary & Problems
Selected References

3. Supervisory Control

Feedback Control with Supervisors
Specifications on Controlled System
Dealing with Uncontrollability
Dealing with Blocking
Modular Control
Dealing with Unobservability
Decentralized Control
Summary & Problems
Selected Reference

4. Petri Nets

Petri Net Basics
Comparison of Petri Nets and Automata
Analysis of Petri Nets
Summary & Problems
Selected References

5. Timed Models

Timed Automata
Timed Petri Nets
Dioid Algebras
Concluding Comments
Summary & Problems
Selected References

6. Stochastic Timed Automata

Stochastic Process Basics
Stochastic Clock Structures
Stochastic Timed Automata
The Generalized Semi-Markov Process
The Poisson Counting Process
Properties of the Poisson Process
Automata with Poisson Clock Structure
Extensions of the GSMP
Summary & Problems
Selected References

7. Markov Chains

Discrete-Time Markov Chains
Continuous-Time Markov Chains
Birth-Death Chains
Uniformization of Markov Chains
Summary & Problems
Selected References

8. Introduction to Queueing Theory

Specification of Queueing Models
Performance of a Queueing System
Queueing System Dynamics
Little’s Law
Simple Markovian Queueing Systems
Markovian Queueing Networks
Non-Markovian Queueing Systems
Summary & Problems
Selected References

9. Controlled Markov Chains

Applying “Control” in Markov Chains
Markov Decision Processes
Solving Markov Decision Problems
Control of Queuing Systems
Summary & Problems
Selected References

10.Introduction to Discrete-Event Simulation

The Event Scheduling Scheme
The Process-Oriented Simulation Scheme
Discrete-Event Simulation Languages
Random Number Generation
Random Variate Generation
Output Analysis
Summary & Problems
Selected References

11. Sensitivity Analysis & Concurrent Estimation

Sample Functions and Their Derivatives
Perturbation Analysis: Some Key Ideas
PA of GI/G/ 1 Queuing Systems
IPA for Stochastic Timed Automata
Sensitivity Estimation Revisited
Extensions of IPA
Smoothed Perturbation Analysis (SPA)
PA for Finite Parameter Changes
Concurrent Estimation
Summary & Problems
Selected References


I. Review of Probability Theory
II. IPA Estimator


PDF file of Errata in the book: errata.pdf

If you find a typographical error or have any questions regarding any part of the book, please contact either author:
Christos G. Cassandras, cgc AT
Stephane Lafortune, stephane AT

– Solutions to all problems are available directly from the authors.
– Additional software, interactive web sites, animated presentations on special topics related to Discrete Event Systems are listed in Related Web Sites.

The authors would appreciate to hear your comments on the book, suggestions, specific questions, or any issue related to Discrete Event Systems.