Automata and Logic

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 would also be helpful.

SWS: 4/2/–

This course can be used in the following modules:

• Bachelor-Studiengang Informatik: INF-B-520 (Vertiefung zur Bachelor-Arbeit)
• Master/Diplom-Studiengang Informatik: INF-BAS6 (Theoretische Informatik), INF-VERT6 (Theoretische Informatik)
• Master in Computational Logic: MCL-TCSL (Theoretical Computer Science and Logic), MCL-PI (Principles of Inference), MCL-KR (Knowledge Representation)
• Diplom-Studiengang Informatik (Studienordnung 2004): Fachgebiet Theorie der Programmierung, Fachgebiet Intelligente Systeme

The lecture takes place twice a week. Additionally, there is a weekly exercise session held by Dipl.-Math. Francesco Kriegel. Exercise sheets will be available approximately one week before the session.

The lectures and exercise sessions will take place in room E005 at the following times: Tuesdays 16.40–18.10, Wednesdays 14.50–16.20, and Thursdays 16.40–18.10. The exact distribution of lectures and exercise sessions can be found in the table below.

Announcements:

• The lecture will start on 14 April.
• The exercise sessions will start on 23 April.
• There will be no lecture on 24 June.
• The exercise session on 25 June will be held by Dr. Marcel Lippmann.

	Tuesday	Wednesday	Thursday
13 Apr to 17 Apr	Lecture	Lecture	Lecture
20 Apr to 24 Apr	Lecture	Lecture	Exercise session (Exercise sheet 1) (Exercise sheet 2)
27 Apr to 1 May	Lecture	Lecture	Exercise session (Exercise sheet 3)
4 May to 8 May	Lecture	Dies Academicus	Exercise session (Exercise sheet 4)
11 May to 15 May	Lecture	Lecture	Public Holiday
18 May to 22 May	Lecture	Lecture	Exercise session (Exercise sheet 5)
25 May to 29 May	—	—	—
1 Jun to 5 Jun	Lecture	Lecture	Exercise session (Exercise sheet 6)
8 Jun to 12 Jun	Lecture	Lecture	Exercise session (Exercise sheet 7)
15 Jun to 19 Jun	Lecture	Lecture	Exercise session (Exercise sheet 8)
22 Jun to 26 Jun	Lecture	—	Exercise session (Exercise sheet 9)
29 Jun to 3 Jul	Lecture	Lecture	Output DD
6 Jul to 10 Jul	Lecture	Lecture	Exercise session (Exercise sheet 10)
13 Jul to 17 Jul	Exercise session (Exercise sheet 11)	Lecture	Exercise session (Exercise sheet 12)
20 Jul to 24 Jul	Exercise Session	Consultation	—

A (not necessarily) complete script of this lecture is available in German language and a shorter script is available in English language.

There also exists a lecture log.

• J. Almeida. Finite Semigroups and Universal Algebra. World Scientific, 1994.
• H. Comon et al. Tree Automata Techniques and Applications. Available online at http://www.grappa.univ-lille3.fr/tata
• S. Eilenberg. Automata, Languages, and Machines. Academic Press, Orlando, 1974. (Volume A, Volume B; there is also a Volume C, but this volume never left the state of a collection of manuscripts.)
• F. Gecseg and M. Steinby. Tree Automata. Akademiai Kiado, Budapest, 1984.
• E. Grädel, W. Thomas, T. Wilke. Automata, Logics, and Infinite Games. Springer, New York, 2002. Available online at SpringerLink.
• G. Lallement. Semigroups and Combinatorial Applications. John Wiley & Sons, New York, 1979.
• 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.