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
Lecturer
SWS
- 2/2/0
Modules
Examination method
- Oral exam
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.
