Automata and Logic

Lecturer: PD Dr.-Ing. habil. Anni-Yasmin Turhan
Tutorials: Dipl.-Math. Francesco Kriegel

Course Description

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.

Organisation

The lecture will take place in room APB/E005 twice a week on Tuesdays and Thursdays, and is accompanied by weekly tutorials in room APB/E005 on Wednesdays. Exercise sheets will be available approximately one week in advance. The exact distribution of lectures and tutorials can be found in the table below.

Announcements

• As requested, no replacement tutorial is offered in compensation for the Reformation Day.
• As requested, there is a replacement tutorial offered in compensation for the Day of Prayer and Repentance. It takes place on Thursday, 22 November, 11:10–12:40, in room APB/3027.
• The lecture on 29 November will be exchanged with the tutorial on 28 November.
• There are no lectures on 4 December and on 6 December. As requested, no tutorial or Q&A session will be offered instead.
• The replacement tutorial for those students who were not able to attend the tutorial on 12 December will take place on Friday, 14 December, 7:30–9:00, in room APB/3027.
• On 19 December, there will be a lecture instead of the tutorial.
• The lecture on 10 January will be exchanged with the tutorial on 9 January.
• The lecture on 31 January will be exchanged with the tutorial on 30 January.

Schedule

	Tuesday 16:40–18:10	Wednesday 14:50–16:20	Thursday 16:40–18:10
9 October — 11 October	Lecture	Tutorial Exercise Sheet 1	Lecture
16 October — 18 October	Lecture	Tutorial Exercise Sheet 2	Lecture
23 October — 25 October	Lecture	Tutorial Exercise Sheet 3	Lecture
30 October — 1 November	Lecture	Reformation Day	Lecture
6 November — 8 November	Lecture	Tutorial Exercise Sheet 4	Lecture
13 November — 15 November	Lecture	Tutorial Exercise Sheet 5	Lecture
20 November — 22 November	Lecture	Day of Prayer and Repentance	Lecture & Tutorial (11:10–12:40) Exercise Sheet 6
27 November — 29 November	Lecture	Lecture	Tutorial Exercise Sheet 7
4 December — 6 December	—	Tutorial Exercise Sheet 8	—
11 December — 13 December	Lecture	Tutorial Exercise Sheet 9	Lecture
18 December — 20 December	Lecture	Lecture	Lecture
25 December — 27 December	Turn of the Year	Turn of the Year	Turn of the Year
1 January — 3 January	Turn of the Year	Turn of the Year	Turn of the Year
8 January — 10 January	Lecture	Lecture	Tutorial Exercise Sheet 10
15 January — 17 January	Lecture	Tutorial Exercise Sheet 11	Lecture
22 January — 24 January	Lecture	Tutorial Exercise Sheet 12	Lecture
29 January — 31 January	Lecture	Lecture	Tutorial Exercise Sheet 13

SWS/Modules

SWS: 4/2/–
This course can be used in the following modules:

• Master Computational Logic: MCL-KR, MCL-PI, MCL-TCSL
• Master Informatik, Diplom Informatik: INF-BAS6, INF-VERT6
• Bachelor Informatik: INF-B-520

Literature

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