Course Description
In this course we look at several automata formalisms on finite objects and analyse their expressive power in comparison to extensions
of First Order Logic.
Prerequisites: Undergraduate course on automata and formal languages.
Basic notions from logic also helpful.
Organization
The lecture takes place weekly in room E05:
Wednesdays 11:10-12:40
Announcements
- May 5 no lecture
- May 12 no lecture
- June 28 reposition lecture at 16:40
- July 5 reposition lecture at 16:40
- July 12 lecture at 13:00 (no tutorial)
- July 21 tutorial at 11:10 (no lecture)
Credits / Examinations
Computational Logic students can earn 3 credits for the modules TCSL and SV by attending this lecture.
In order to get the credits, students must pass an oral examination at the end of the semester.
Exercises
A weekly exercise session will be held by
Felix Distel on Mondays 13:00-14:30 in E05 (starting from April 19).
All students are encouraged to present their solutions to the exercises, as they are useful for a better understanding of the lecture material.
Exercise sheets will be available online approx. one week before the session.
Lecture Notes
A pdf version of the lecture notes is now available. Please notice that these are incomplete and may contain errors.
Use them with care.
Literature
The lecture material is taken from several different sources. However, students may find the following literature helpful, in particular to
recall basic automata-theoretic notions.
- 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.
- T. Wilke. Alternating Tree Automata, Parity Games, and Modal μ-Calculus.
Bull. Belg. Math. Soc., pages 359-391. 1993.
Rafael Peñaloza
![[TU Dresden]](tu-logo.gif){kind=logo}