TU Dresden
Institut für Theoretische Informatik
Lehrstuhl für Automatentheorie

Hauptseminar "Automata, Logics and Infinite Games" in Winter Term 2007/2008

Initial Meeting
The initial meeting will take place on 12.10.2007 (Friday), at 14:50 in room E05. Attending the initial meeting is mandatory for participation in the seminar. People who want to participate in the seminar, but have serious reasons to not attend the initial meeting, please send an email.

The presentations will take place at the final meeting.
Final Meeting The final meeting will take place on 1.02.2003, DS5: 14.50 - 16.20 in INF E05.
Attending all of the talks is mandatory for all participants

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

Basic knowledge in automata theory.
For computer scientists: 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 concerened 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 talk.

Hints on how to prepare a paper and how to give a talk are available (in German).

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. The sharp deadline for finishing is the end of the semester. Failure to finish the project in time will result in no credits to be given. It is the obligation of the participant to start working in time, and to make appointments with the supervisor for regular meetings during the semester.

The seminar is coordinated by Barbara Morawska.