Capita Selecta in
Modal Logic, Algebra and Coalgebra (Fall 2011)
This page concerns the course `Capita Selecta in Modal Logic, Algebra and
Coalgebra', taught at the University of Amsterdam from September -
December 2011.
Contents of these pages
-
The exam is on December 22, from 13.00 - 16.00, in room D1.113.
This exam will be based on the material that was covered in the course, look
here for the details.
-
The material associated with the class of December 13 are the sections 6.7
and 7.4.
- We will make use of lecture notes, to be supplied at the beginning of
the course, and updated occasionally.
Here are updates of the files:
- Chapter 7, last version: December 13, 2011
- Chapter 6, last version: December 13, 2011
- Chapter 5, last version: October 18, 2011
- Chapter 4, last version: October 18, 2011
- Chapter 3, last version: September 28, 2011
- Chapter 2, last version: September 28, 2011
- Chapter 1, last version: September 28, 2011
- Appendix, last version: September 6, 2011
- Here is the version of the notes prepared at
the beginning of the class.
Staff
Dates & location:
-
Classes run from September 6 until December 13; there will be 14 classes
in total.
-
There is one class weekly, on Tuesdays from 13.00 - 15.00, in
room D1.160 (week 36-42) and room F1.24C (week 44-50).
-
There is an exam on December 22, from 13.00 - 16.00, in room D1.113.
- 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 special 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.
Aspects of this common mathematical backbone form the topic of this course.
This year, the course will be devoted entirely to connections between modal
fixoint 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
mu-calculus, an extension of modal logic with 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.
Concretely, we will discuss (at least) the following topics:
- modal mu-calculus: syntax and game-theoretical semantics;
- other modal fixpoint logics: PDL, CTL, CTL*;
- theory of fixpoint operators;
- automata for infinite words: basic definitions, acceptance conditions,
determinization;
- automata for infinite trees: alternation, Rabin's theorem;
- Kripke automata: alternation, Janin/Walukiewicz theorem;
- modal mu-calculus: finite model property, decidability;
- modal mu-calculus: expressiveness and other properties;
- modal fixpoint logics: 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.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
Yde Venema