Finite Automata on Infinite Words and Trees

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 description

This course provides an introduction to automata on infinite words and finite and infinite trees.

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

Evaluation

Either an oral exam, or homework + Fachgespräch.

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.

Course notes

Course notes are available here. Last modification: January 27.

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

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.

Bibliography

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.