Automata and Logic

Lecturer: Prof. Dr.-Ing. Franz Baader
Tutorials: Dr. Patrick Koopmann

OPAL course: https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/26604765185

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 be held online, but synchronous using a video conferencing tool. It takes place twice a week (Tuesdays and Thursdays 16:40–18:10), and is accompanied by weekly tutorials (Wednesdays 14:50–16:20). Exercise sheets will be made available approximately one week in advance of the respective tutorial.

To participate in the course, you need to register for the course in OPAL. Links for accessing the video conference and other material will be provided for registered participants within OPAL.

The exact organization of the lecture will be discussed in the first lecture, which starts on Tuesday, October 27, at 16:40.

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
Computational Modeling and Simulation: CMS‑LM‑MOC, CMS‑LM‑ADV

Lecture Notes

Lecture notes in German and English are available, but note that they are not necessarily complete.

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.