Topics in Modal Logic (Fall 2020)
This page concerns the course `Topics in Modal Logic', taught at the University
of Amsterdam from October - December 2020.
Contents of these pages
The lecture notes are now available in one
Here is some information on the online exam:
- It will be held on Wednesday December 16, from 15.00 - 18.00
via zoom (please enter at 14.45).
The zoom link will be made available on Canvas or sent to you.
- You can find information on the protocol for the online exam
Please read this document carefully.
- On Friday 11 December during the question hour we will hold a trial
- Here is the exam of 2018.
Note that this year there will be some differences since the exam is online.
The fifth homework set is available.
Its deadline has been extended to Wednesday, 23 December, 17:00.
Here is the final overview of the class.
- We will make use of lecture notes, to be provided (and updated if needed)
during the course.
Here is the complete version of the
lecture notes (version of 12 December).
Here are the versions of the notes distributed during class:
- Lecturer: Yde Venema (y dot venema at uva dot nl)
- Teaching assistant, grading: Jan Rooduijn (j dot m dot w dot rooduijn
at uva dot nl)
Dates & location:
Classes run from 27 October until 10 December; there will be 14 classes
There are two classes weekly, on Tuesdays from 13.00 - 14.45,
and on Thursdays from 15.00 - 16.45.
In addition, there is a weekly question hour on Fridays, from 13:00 to 14:00.
All classes are online via Zoom; the Zoom link of the classes will be available
on the Canvas pages of the course, or can be provided by the lecturer on
There is a written online exam on Wednesday December 16,
from 15.00 - 18.00 (entrance at 14.45).
Grading is primarily through homework assignments, and a written exam at the
end of the course.
Collection and submission proceeds via the Canvas pages of the course.
- For the later part of the course additional/alternative requirements may apply
(such as working out lecture notes).
See the separate page on grading for more details.
Modal languages are simple yet expressive and flexible tools for describing
all kinds of relational structures.
Thus modal logic finds applications in many disciplines such as computer
science, mathematics, linguistics or economics.
Notwithstanding this enormous diversity in appearance and application area,
modal logics have a great number of properties in common.
This common mathematical backbone form the content of this course, the exact
topics change from year to year.
This year, the course will be devoted entirely to connections between modal
fixpoint logic and automata theory.
This is a classic field in theoretical computer science, which has led to
both seminal theoretical results such as Rabin's decidability theorem, and
practical applications in the field of specification and verification of
More specifically, a large part of the course will focus on the modal
mu-calculus, an extension of modal logic with explicit fixpoint operators, which
was introduced in the early 1980s.
The modal mu-calculus shares many attractive properties with ordinary modal
logic, but has a much bigger expressive power.
A main theme of the course will be the use of automata-theoretic tools to
understand and prove results about the modal mu-calculus.
Indicatively, we will discuss the following topics:
- modal mu-calculus: syntax and semantics
- equivalence of game-theoretical and algebraic semantics
- algebraic theory of fixpoint operators
- bisimulation invariance and bounded tree model property
- size matters in the modal mu-calculus
- automata for infinite words: basic definitions, acceptance conditions,
- theory of infinite games
- parity games: positional determinacy, complexity issues
- parity formulas and modal automata
- simulation theorem
- finite model property, complexity of the satisfiability problem
- uniform interpolation
- expressive completeness
We presuppose some (but very little) basic background knowledge
on modal logic; roughly, what is needed is familiarity with the syntax and
semantics of modal languages, and the notion of bisimulation.
More precisely, we build on the basic material covered
in the course Introduction to Modal Logic, that is: the sections
1.1-1.3, 2.1-2.3 of the Modal Logic book.
Next to this, we assume that students possess some mathematical maturity.
Comments, complaints, questions: mail