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.
There is no lecture on December 20!
The exercise group takes place on Wednesday 14:50-16:20 also in room
E05 and is held by Barbara Morawska.
The exercises will be available
in Postscript format:
Credits / Examinations
Computational logic students can earn 10 credits for the modules TCSL and IT by attending this lecture.
In order to get the credits, CL students have to do meet both of the following two
Computer Science students are not obliged to present exercises, but are invited
to do so.
- present at least five exercises in front of the exercise group;
- pass an oral examination at the end of the term performed by Carsten Lutz.
A complete script is available, both in german
and english language.
- 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,
- 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.