[TU Dresden]


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

Hauptseminar "Automata, logics and infinite games" in Summer Term 2009

Position in Curriculum
Informatik (both diploma and bachelors degree), starting from 5. semester, Wahlpflichtveranstaltung (-/-/2)
Computational Logic: Modules TCSL and IT, 3 credit points

Basic knowledge in automata theory.
For computer scientist students: Pflichtvorlesung Grundlagen der Theoretischen Informatik.

The language of the initial meeting is English.

Topic of the Hauptseminar

The Hauptseminar is concerned with the close connection between automata, logic, and infinite games. In particular, we will be concerned with non-deterministic and alternating automata on infinite trees, the mu-calculus, and parity games. The seminar will be based on the book

Erich Grädel, Wolfgang Thomas, Thomas Wilke (Editors). Automata, Logics, and Infinite Games. Lecture Notes in Computer Science Volume 2500. Springer Verlag, 2002.

Each seminar topic will be based on a chapter from this book. In addition, every participant is supposed to read and understand the following paper:

Thomas Wilke. Alternating tree automata, parity games, and modal mu-calculus. Bulletin of the Belgian Mathematical Society, 8(2):359-391, 2002.

Goal of the Hauptseminar
Apart from learning about the main topic, students should learn how to get acquainted with a relevant body of literature, how to produce a well-structured paper, and how to give an understandable scientific talk.

Duties of Participants
In the initial meeting, students choose a topic to work on and are assigned a tutor. During the seminar, the student has to understand the relevant literature and writes a paper about the chosen topic (~12 pages). In doing this, he/she receives individual support by the tutor. The produced paper is required to conform to the standards of scientific writing. Finally, each student presents his/her work in a talk to the other participants.

It is also the duty of the participants to reserve enough time for performing the seminar. It is the obligation of the participant to start working in time, and to make appointments with their tutors for regular meetings during the semester. In particular, students must present to their tutors

Preliminary schedule
The seminar takes place Mondays 9:20 o'clock (2.DS) in room INF 3027. The first two meetings are fixed now. However, the dates for the participants' talks might be subject to change.

When Speaker Topic Tutor
All Chapter 1:
All Chapter 2:
Infinite Games
All Q & A:
about Chapter1 and Chapter 2
E. Sherkhonov Chapter 4:
Complementation of Büchi Automata using Alternation
A.-Y. Turhan
M. Hutagalung Chapter 6:
Memoryless Determinacy of Parity Games
B. Morawska
M. Raitza Chapter 9:
Alternation Tree Automata and Parity Games
R. Penaloza
M. F. Arif Chapter 10:
Modal μ-calculus and Alternating Tree Automata
F. Distel
date to be
W. Fu Chapter 8:
Nondeterministic Tree Automata
A.-Y. Turhan

The seminar is coordinated by Anni-Y. Turhan.

Last modified: Mon Jul 13 11:56:38 CEST 2009