Seminar

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

Prerequisites

Basic knowledge in automata theory.

For computer scientist students: Pflichtvorlesung Grundlagen der Theoretischen Informatik.

Language

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

• a full version of their paper at least 4 weeks before their talk and
• a first version of the slides for their talk at least 2 weeks before the talk.

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
04.05.2009	All	Chapter 1: ω-Automata	-
11.05.2009	All	Chapter 2: Infinite Games	-
18.05.2009	All	Q & A: about Chapter1 and Chapter 2	-
06.07.2009	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
13.07.2009	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 announced	W. Fu	Chapter 8: Nondeterministic Tree Automata	A.-Y. Turhan

Contact

The seminar is coordinated by Anni-Y. Turhan.