Automata and Logic

Prof. Dr.-Ing. Franz Baader

Course Description

This course considers finite automata that work on finite or infinite words and trees. The course concentrates on the connection between these automata and logics that play an important role in computer science, such as first-order logic, monadic second-order logic, and propositional dynamic logic; in particular, it will be shown how closure and decidability results for the automata can be used to obtain decidability results for these logics.

Prerequisites: Undergraduate course on automata and formal languages. Basic notions from logic would also be helpful.


The lecture takes place twice a week in room E05: Tuesdays 16:40–18:10 and Thursdays 16:40–18:10.



SWS: 4/2/–

This course can be used in the following modules:

Lecture Material

A complete script of this lecture is available, both in German and in English language.


A weekly exercise session will be held by Marcel Lippmann on Wednesdays 14:50–16:20 in room E05.

Exercise sheets will be available here approximately one week before the session.