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.

The lecture takes place twice a week in room E05: Tuesdays 16:40–18:10 and Thursdays 16:40–18:10.

Announcements:

• On 12th July, there will be no lecture.
• The lecture of Tuesday, 10th July will take place in room INF/3027.
• On 28th June, there will be no lecture.
• On 12th June, there will be an exercise session instead of a lecture.
• The exercise session of 6th June is shifted to 4th June (11:10–12:40) and will take place in room INF/3027.
• On 23rd May, there will be a lecture instead of an exercise session.
• On 9th May, there will be no exercise session because of Dies Academicus.
• The exercise sessions will start on 4th April.
• The lecture will start on 3rd April.

SWS: 4/2/–

This course can be used in the following modules:

• Bachelor-Studiengang Informatik: INF-B-510 (Vertiefung), 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

A complete script of this lecture is available, both in German and in English language.

A weekly exercise session will be held by Marcel Lippmann on Wednesdays 14:50–16:20 in room E05.

Exercise sheets will be available here approximately one week before the session.

• Exercise Sheet 1 (4th April)
• Exercise Sheet 2 (11th April)
• Exercise Sheet 3 (18th April)
• Exercise Sheet 4 (25th April)
• Exercise Sheet 5 (2nd May)
• Exercise Sheet 6 (16th May)
• Exercise Sheet 7 (4th June)
• Exercise Sheet 8 (12th June)
• Exercise Sheet 9 (13th June)
• Exercise Sheet 10 (20th June)
• Exercise Sheet 11 (27th June)
• Exercise Sheet 12 (4th July)
• Exercise Sheet 13 (11th July)

• 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.