[TU Dresden]

Introduction to Automatic Structures

Technische Universität Dresden
Institut für Theoretische Informatik
Lehrstuhl für Automatentheorie

Dr. Anni-Yasmin Turhan

Course Description

An automatic structure is one whose domain and atomic relations are computable by finite-state automata. The type of automata considered are those that operate synchronously on their inputs, which can be finite or infinite words or trees. The fundamental property of every automatic structure is that the first order definable relations are computable by automata.

The course will be devoted to the study of (mathematical) structures that can be described by finite state machines such as finite automata, tree automata and omega automata. In particular, we study

Prerequisites:

Organization

The lecture takes place weekly in room E05: Mondays 13:00-14:30 (DS 4)

The lecture is accompanied by a exercise sessions given every second week by Dr. Felix Distel. These sessions will be given on the following dates:

Exercises

Exercise sessions will be held by Dr. Felix Distel every second week on Fridays 07:30-09:00 (DS 1) in E05 (starting from October 14). All students are encouraged to present their solutions to the exercises, as they are useful for better understanding of the lecture material. Exercise sheets will be available online about a week before the session.

Credits / Examinations

Students can earn 3 SWS (2/1/0) by attending this lecture.

Modules

This lecture can be used for students from the
In order to get the credits, students must pass an oral examination at the end of the semester.

Literature

All the material necessary for successfully aproving the course will be presented during the lecture. Students are strongly recommended to copy the material written on the blackboard during lecture time. The lecture will be based on following course material on Automatic Structures:

Dr. Anni-Yasmin Turhan