Seminar Theoretical Computer Science

Prof. Dr.-Ing. Franz Baader, Dr.-Ing. habil. Anni-Yasmin Turhan

Course Description

This seminar covers topics on Automata, logics and infinite games.

The seminar 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, it is recommended 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.

Prerequisites: Basic knowledge in automata theory. For computer scientist students: Pflichtvorlesung Formale Systeme

Organisation

Available topics are sketched and assigned to interested students in an initial meeting on Friday 5th of April 14:50–16:20, in room APB/3027. Further organisational matters are covered there as well. Students who cannot attend the initial meeting, but want to participate in the seminar, should contact Anni-Yasmin Turhan.

Each participant must get acquainted with the respective topic, write a report (ca. 12 pages) about it, and give a presentation (ca. 30 minutes) at the end of the semester (more specifically, in the two weeks before the lecture-free period). During the semester, every student gets individual help and guidance by a tutor (Prof. Dr.-Ing. Franz Baader) or (Anni-Yasmin Turhan. Furthermore, each student is expected to participate in the discussions after the talks given by her/his fellow students.

The students are expected to stick to the following schedule.

• April: mandatory meeting with the tutor
• end of May: first complete version of the report
• middle of June: first complete version of the presentation slides
• end of June: presentation and discussion

Topics

From the book by Erich Grädel, Wolfgang Thomas, Thomas Wilke (Editors) on Automata, Logics, and Infinite Games (Lecture Notes in Computer Science Volume 2500. Springer Verlag, 2002) we will cover the chapters on:

• Chapter 4:
  Complementation of Büchi Automata using Alternation
• Chapter 6:
  Memoryless Determinacy of Parity Games
• Chapter 8:
  Nondeterministic Tree Automata
• Chapter 9:
  Alternation Tree Automata and Parity Games
• Chapter 10:
  Modal μ-calculus and Alternating Tree Automata

SWS/Modules

SWS: 0/2/0
This course can be used in the following modules:

• Master Computational Logic: MCL-PS
• Master Informatik, Diplom Informatik: INF-04-HS, INF-AQUA, INF-D-940