Instructors: Dr. Meghyn Bienvenu and Prof. Carsten Lutz

K4 (Vertiefung), Modulbereich Theorie

Di von 14:00 - 16:00, MZH Senatssaal (1400)

Do von 10:00 - 12:00, ~~GW2 B1400~~ IW3 0200

First lecture: 20.10

Course information sheet

List of topics:

- Preliminaries: Automata on finite words
- Automata on infinite words
- Definition of Büchi automata
- Closure properties for Büchi automata
- Deterministic Büchi automata
- Definition of Müller, Rabin, and Streett automata
- Relations between different types of automata
- Determinization of Büchi automata
- Decision problems (e.g. emptiness)

- Automata on finite trees
- Definition of (bottom-up) tree automata
- Equivalence of deterministic and non-deterministic tree automata
- Pumping lemma for recognizable tree languages
- Closure properties for tree automata
- Top-down tree automata
- Decision problems (e.g. emptiness)

- Automata on infinite trees
- Definition of Büchi, Müller, and parity tree automata
- Relations between different types of automata on infinite trees
- Closure properties
- Complementation problem for automata on infinite trees
- Determinacy of parity games

Oral exams will last between 30 and 45 minutes and may cover any material presented

in the lecture or in the homework. During the first five minutes of the exam, students

will have the option of discussing a subject of their choice.

Exams and Fachgespräch will both be held between March 9th and March 19th.

Students should contact Meghyn by email to set up an appointment for an exam.

Students must complete the evaluation form for the course (available here) and bring it

with them to their exam. I will only look at the form after assigning a grade, so please

answer honestly.

NOTE: In the last week of lecture, we discussed determinacy of parity games, which is

not covered in the notes. Students who missed these lectures may wish to consult Chapters

2 and 6 of the "Automata, Logics, and Infinite Games" book (see bibliography below).

- Homework 1. Due date: 27.10 at start of lecture.
- Homework 2. Due date: 10.11 at start of lecture.
- Homework 3. Due date: 24.11 at start of lecture.
- Homework 4. Due date: 15.12 at start of lecture.
- Homework 5. Due date: 12.01 at start of lecture.
- Homework 6. Due date: 26.01 at start of lecture.

- Automata Theory and its Applications. Khoussainov and Nerode, 2001.
- Automata, Logics, and Infinite Games. Grädel, Thomas, and Wilke (Eds.), 2002.
- Infinite Words: Automata, Semigroups, Logic, and Games. Perrin and Pin, 2004.
- Tree Automata Techniques and Applications. Available here.