About this course
Discrete event systems are systems whose behaviour is driven by the
occurrence of asynchronous, discrete events rather than by the steady
tick of continuous time — think of packets arriving at a router,
jobs entering a queue, or tokens moving through a workflow. This course
introduces the modeling frameworks, analysis techniques, and verification
tools used to reason about such systems rigorously.
By the end of the course you will be able to:
- describe families of languages and the abstract machines that recognise
them, and reason about what can and cannot be computed;
- model and analyse the long-run and average behaviour of stochastic
systems using Markov chains and queueing theory;
- specify desired properties of a system and verify them formally using
finite-automata techniques and Petri nets.
Course structure
The course is organised in three parts:
- Part 1 — Computability Models
(Prof. Vanbever): regular and non-regular languages, automata, and the
limits of computation.
- Part 2 — Analysis Methods
(Prof. Vanbever): Markov chains and queueing theory.
- Part 3 — Formal Verification
(Prof. Josipović): finite-automata verification and Petri nets.
Grading and organization
The course is graded entirely on a written final exam.
The exam is open book: all written material (script,
slides, your own notes, exercises, books) is allowed. No electronic
devices are permitted, except for a non-connected calculator.
The exam is in English, and you will not be tested on material that was not
covered during the lectures.
Weekly exercise sessions accompany the lectures. The exercises are
not graded, but working through them is the best way to
prepare for the exam — solutions are discussed in the session and
posted here.
Literature
The course is self-contained; the following references are recommended for
going deeper:
- M. Sipser, Introduction to the Theory of Computation, PWS/Cengage.
- C. Cassandras & S. Lafortune, Introduction to Discrete Event Systems, Springer.
- D. Bertsekas & R. Gallager, Data Networks, Prentice Hall.
- T. Schickinger & A. Steger, Diskrete Strukturen (Band 2), Springer.
The schedule below is tentative and may still be adjusted. Lecture
and exercise materials are posted here as the semester progresses.
Part 1
Computability Models
Week 1Sep 17
Lecture Introduction & Regular Languages
- What is a discrete event system?
- Languages and finite automata (DFA / NFA)
- Regular expressions
Materials
Week 2Sep 24
Lecture Regular Languages
- Equivalence of DFAs, NFAs, and regular expressions
- Closure properties
- Minimisation
Materials
Week 3Oct 01
Lecture Non-Regular Languages
- Limits of regular languages: the pumping lemma
- Context-free grammars and languages
Materials
Exercise
Materials
- Exercise sheet — coming soon
Week 4Oct 08
Lecture Non-Regular Languages
- Pushdown automata
- The tandem (pumping) lemma for context-free languages
Materials
Exercise
Materials
- Exercise sheet — coming soon
Week 5Oct 15
Lecture Non-Regular Languages
- Closure properties of context-free languages
- The Chomsky hierarchy
- Turing machines
Materials
Exercise
Materials
- Exercise sheet — coming soon
Week 6Oct 22
Lecture Markov Chains
- Discrete-time Markov chains
- Stationary distributions and convergence
- Application: PageRank
Materials
Exercise
Materials
- Exercise sheet — coming soon
Week 7Oct 29
Lecture Queueing
- Poisson processes and birth–death chains
- The M/M/1 queue
- Little's law
Materials
Exercise
Materials
- Exercise sheet — coming soon
Week 8Nov 05
Lecture Queueing
- More queueing models (M/M/k, M/G/1)
- Networks of queues
Materials
Exercise
Materials
- Exercise sheet — coming soon
Part 3
Formal Verification
Week 9Nov 12
Lecture Finite Automata Verification
- Modeling systems and specifications
- Safety and liveness properties
Materials
Exercise
Materials
- Exercise sheet — coming soon
Week 10Nov 19
Lecture Finite Automata Verification
- Temporal logic and model checking
- Automata-based verification
Materials
Exercise
Materials
- Exercise sheet — coming soon
Week 11Nov 26
Lecture Verification — topic TBD
Additional verification lecture — topic to be announced.
Materials
Exercise
Materials
- Exercise sheet — coming soon
Week 12Dec 03
Lecture Petri Nets
- Places, transitions, and tokens
- Modeling concurrency
Materials
Exercise
Materials
- Exercise sheet — coming soon
Week 13Dec 10
Lecture Petri Nets
- Reachability and behavioural properties
- Analysis techniques
Materials
Exercise
Materials
- Exercise sheet — coming soon
Week 14Dec 17
Lecture Recap & Exam Briefing
- Course review
- Exam format and Q&A
Materials
Q&A Exam preparation
Exam
The final exam is a written, open-book exam. All written
material (script, slides, your own notes, exercises, books) is allowed;
no electronic devices are permitted, except for a
non-connected calculator. The exam is in English, and you will not be tested
on material that was not covered during the lectures.
Previous exams
Heads up: the set of topics covered in this course has
changed over the years — lecturers, chapters, and emphasis differ
between editions (for example, the “Online algorithms” chapter
is not part of the 2026 edition). Use these past exams to practise,
but treat questions on topics we did not cover this year as out of scope,
and don't assume this year's exam will match their structure.
With solutions:
Without solutions:
