## Introduction to Automatic Structures |
Technische Universität Dresden |

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

- mathematical and algorithmic properties of automata,
- algorithmic and logical properties of automatic structures and
- typical mathematical structures that are described by automata, e.g. linear orders, Boolean algebras, graphs and groups.

- The course will use notions of automata theory, e.g. basic automata models.
- Solid knowledge of propositional and ideally also first order logic is helpful.

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

- 2011: 14.10, 28.10, 11.11, 25.11,
**5.12**, - 2012: 06.01, 20.01, 03.02

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.

- Exercise Sheet 1 for the 14. of October
- Exercise Sheet 2, Part 1 and Part 2 (October 28)
- Exercise Sheet 3 (November 11)
- Exercise Sheet 4 (November 25) (Solutions)
- Exercise Sheet 5 (December 5)
- Exercise Sheet 6 (January 6)
- Exercise Sheet 7 (January 20)
- Exercise Sheet 8 (February 3)

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

**Bachelor Informatik**program for the modules**INF-B-510**and**INF-B-520**,-
**Master Informatik**and**Diplom Informatik (Ordnung 2010)**programs for the modules**INF-BAS6**and**INF-VERT6**, and -
**Computational Logic**program for the modules**KR**and**TCSL**

In order to get the credits, students must pass an

*Three Lectures on Automatic Structures*by Bakhadyr Khoussainov and Mia Minnes; 2008-
*Automatic Structures*a course given by Dietrich Kuske at ESSLI 2010. The slides are available here.

Dr. Anni-Yasmin Turhan