[TU Dresden]

Automata and Logic

Technische Universität Dresden
Institut für Theoretische Informatik
Lehrstuhl für Automatentheorie

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 also helpful.


The lecture takes place twice a week in room E05: Tuesday 16:40-18:10 and Thursday 16:40-18:10.


Exercise Group

The exercise group takes place on Wednesday 14:50-16:20 also in room E05 and is held by Rafael Peñaloza.

The exercises will be available in PDF format one week before the exercise session:

Credits / Examinations

Computational logic students can earn 9 credits for the modules TCSL and IT by attending this lecture. In order to get the credits, CL students have to do meet both of the following two obligations:
  1. present at least five exercises in front of the exercise group;

  2. pass an oral examination at the end of the term performed by Prof. Baader.
Computer Science students are not obliged to present exercises, but are invited (and encouraged) to do so.


A complete script of this lecture is available, both in german and english language.


Rafael Peñaloza