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

• 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 lecture takes place weekly on Mondays 13:00-14:30 (DS 4) in APB E005. All the material necessary for successfully approving 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 is accompanied by exercise sessions held by Dipl.-Math. Francesco Kriegel every second week on Tuesdays 09:20-10:50 (DS 2) in APB E005. 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.

Announcements:

• The lecture will start on 04 April.
• The exercise sessions will start on 12 April.

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

	Monday	Tuesday
04 April to 10 April	Lecture	–
11 April to 17 April	Lecture	Exercise session (exercise sheet 1)
18 April to 24 April	Lecture	–
25 April to 01 May	Lecture	Exercise session (exercise sheet 2)
02 May to 08 May	Lecture	–
09 May to 15 May	Lecture	Exercise session (exercise sheet 3)
16 May to 22 May	Whitsun	Whitsun
23 May to 29 May	Lecture	Exercise session (exercise sheet 4)
30 May to 05 June	Lecture	–
06 June to 12 June	Lecture	Exercise session (exercise sheet 5)
13 June to 19 June	Lecture	Exercise session (exercise sheet 5, continued)
20 June to 26 June	Lecture	–
27 June to 03 July	Lecture	Exercise session
04 July to 10 July	Lecture	–
11 July to 17 July	Lecture	Exercise session

SWS: 2/1/–

This course can be used in the following modules:

• Bachelor-Studiengang Informatik: INF-B-510 (Vertiefung), INF-B-520 (Vertiefung zur Bachelor-Arbeit)
• Master/Diplom-Studiengang Informatik: INF-BAS6 (Theoretische Informatik), INF-VERT6 (Theoretische Informatik)
• Master in Computational Logic: MCL-TCSL (Theoretical Computer Science and Logic), MCL-PI (Principles of Inference)
• European Master in Computational Logic: EMCL-A-TCSL (Theoretical Computer Science and Logic), EMCL-A-PI (Principles of Inference)

The lecture will be based on the following course material:

• Bakhadyr Khoussainov and Mia Minnes: Three Lectures on Automatic Structures, 2008.
• Dietrich Kuske: Automatic Structures (Lecture 1, Lecture 2, Lecture 3, Lecture 4, Lecture 5), ESSLI 2010.