Course Description
This course considers finite automata that work on finite or infinite
words and trees. The course will concentrate on the connection between
these automata and certain logics that play an important role in many areas of
computer science (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 (which play an important role in many areas of computer science)
Prerequisites: Undergraduate course on Automata and Formal Languages;
Basic notions from logic would be helpful.
Organization
The lecture takes place twice a week in room GRU 350:
Tuesday 16:40-18:10 and Thursday 16:40-18:10.
Exercise Group
The exercise group takes place on Wednesday 11:10-12:40 also in room GRU
350 and is held by Barbara Morawska.
The exercises will be available
in Postscript format:
- exercises (for 13.10)
- exercises (for 20.10)
- exercises (for 27.10)
- exercises (for 3.11)
- exercises (for 10.11)
- The next tutorial will replace the lecture on 23.11,
(GRU 350, 16:40-18:10)
exercises (for 23.11)
- exercises (for 24.11)
- exercises (for 1.12)
- Next Wednesday there will be the lecture in the usual time
and place for the tutorial
and we will have the tutorial in place of the lecture on 9.12
(GRU 151, 16:40-18:10).
exercises (for 9.12)
- exercises (for 15.12)
- exercises (for 5.1)
- exercises (for 12.1)
- exercises (for 19.1)
- exercises (for 26.1)
- exercises (for 2.2)
Credits / Examinations
Computational logic students can earn 9 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
obligations:
- 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.
Computer Science students are not obliged to present exercises, but are invited
to do so.
Script
A complete script is available, both in german
and english language.
Literature
- 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.
Barbara Morawska
![[TU Dresden]](tu-logo.gif){kind=logo}