Introduction to Automatic Structures
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
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:
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.
Students can earn 3 SWS (2/1/0) by attending this lecture.