Introduction to Automatic Structures

From International Center for Computational Logic

Introduction to Automatic Structures

Course with SWS 2/2/0 (lecture/exercise/practical) in WS 2020

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.


All course material can be found on the OPAL page.