Topics in Modal Logic (Fall 2018)
This page concerns the course `Topics in Modal Logic', taught at the University
of Amsterdam from October  December 2018.
(This course used to be called `Capita Selecta in Modal Logic, Algebra and
Coalgebra'.)
Contents of these pages
 About the exam:
 Look here for an overview of the course
content. There will no questions about Chapter 9 (expressive
completeness).
 To get an impression of what the exam will look like,
here is the version of 2016.
Note that the course content this year is not exactly the same as in
2016.
 The complete, final version of the
lecture notes is available.
 On Wednesday 19 December (14:00  16:00) there will be a question hour
in room F0.22 (ILLC building).
During this meeting I will answer questions about the course content, and/or
discuss solutions to the exercises in the homework sets 46.
 The sixth homework set is available. Deadline for submission is
Monday 17 December 17h00.
Collection and submission proceeds via Canvas (but you can find the
homework also here).
Staff
 Lecturer: Yde Venema (y dot venema at uva dot nl, phone: 525 5299)
Dates & location:

Classes run from 31 October until 14 December; there will be 14 classes
in total.

There are two classes weekly, on Wednesdays from 09.00  10.45, in
room (ILLC) F2.19 and on Fridays from 09.00  10.45 in room SP G2.13.

There is an exam on Thursday December 20, from 09.00  12.00, in room SP A1.04.
 All of these rooms are in the Science Park.

Grading is primarily through homework assignments, and a written exam at the
end 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
software.
More specifically, a large part of the course will focus on the modal
mucalculus, an extension of modal logic with explicit fixpoint operators, which
was introduced in the early 1980s.
The modal mucalculus 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 automatatheoretic tools to
understand and prove results about the modal mucalculus.
Indicatively, we will discuss the following topics:
 modal mucalculus: syntax and semantics
 equivalence of gametheoretical and algebraic semantics
 algebraic theory of fixpoint operators
 bisimulation invariance and bounded tree model property
 size matters in the modal mucalculus
 automata for infinite words: basic definitions, acceptance conditions,
determinization
 theory of infinite games
 parity games: positional determinacy, complexity issues
 cyclic formulas and modal automata
 simulation theorem
 finite model property, complexity of the satisfiability problem
 uniform interpolation
 expressive completeness
Prerequisites
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.11.3, 2.12.3 of the Modal Logic book.
Next to this, we assume that students possess some mathematical maturity.
Comments, complaints, questions: mail
Yde Venema