## Automata and Logic |
Technische Universität Dresden |

This course considers finite automata that work on finite or infinite words and trees. The course concentrates on the connection between these automata and logics that play an important role in computer science, such as first-order logic, monadic second-order logic, and propositional dynamic logic; in particular, it will be shown how closure and decidability results for the automata can be used to obtain decidability results for these logics.

Prerequisites: Undergraduate course on automata and formal languages. Basic notions from logic also helpful.

The lecture takes place twice a week in room E05: Tuesday 16:40-18:10 and Thursday 16:40-18:10.

- On Wednesday October 14, there will be a lecture instead of the tutorial.
- On Wednesday November 4, there will be a lecture instead of the tutorial.
- On Thursday November 12, there will be a tutorial instead of the lecture.
- On Thursday November 26, there will be a tutorial instead of the lecture.
- On Wednesday January 13, there will be a lecture instead of the tutorial.
- On Tuesday January 19, there will be NO lecture.
- On Thursday January 21, there will be a tutorial instead of the lecture.
- On Wednesday January 27, there will be a lecture instead of the tutorial.
- On Thursday January 28, there will be a tutorial instead of the lecture.

The exercise group takes place on Wednesday 14:50-16:20 also in room E05 and is held by Rafael Peñaloza.

The exercises will be available in PDF format one week before the exercise session:

- Exercises 1
- Exercises 2
- Exercises 3
- Exercises 4
- Exercises 5
- Exercises 6
- Exercises 7
- Exercises 8
- Exercises 9
- Exercises 10
- Exercises 11
- Exercises 12
- Exercises 13
- Exercises 14

- present at least five exercises in front of the exercise group;

- pass an oral examination at the end of the term performed by Prof. Baader.

- W. Thomas. Automata on infinite objects. In J. van Leeuwen,
editor, Handbook of Theoretical Computer Science, volume B: Formal
Models and Semantics, pages 133-192. Elsevier Science Publishers,
Amsterdam, 1990.
- W. Thomas. Languages, automata, and logic. In G. Rozenberg and
A. Salomaa, editors, Handbook of Formal Languages, volume III, pages
389-455. Springer, New York, 1997.
- H. Comon et al. Tree Automata Techniques and Applications.
Online available at http://www.grappa.univ-lille3.fr/tata
- F. Gecseg and M. Steinby. Tree Automata. Akademiai Kiado, Budapest, 1984.

Rafael Peñaloza