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

*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: