Automata play an important role in computer science and its applications. As an example, finite state automata as introduced in introductory courses on theoretical computer science, are used in compiler construction and in pattern matching for strings.
In this course we systematically study the theoretical foundations of diverse automata models and establish connections of automata theory to other areas such as logic and algebra. Automata models have been developed for a plethora of applications, among other we will study
- w-Automata: Very similar to finite state automata, these automata work on infinite words. They are used in formal verification of hardware and software.
- Tree automata: Inputs for these automata are trees and they are used for instance in specification and querying of tree-shaped data, as for instance XML or JSON.
- Probabilistic automa: These automata accept their inputs with certain probabilities and can be used in pattern recognition and formal verification.
The focus of this course is on theoretical properties of automata, but we will also consider some applications.
Introductory literature for this course are the following books:
- Bakhadyr Khoussainov and Anil Nerode. Automata theory and its applications, volume 21. Springer Science & Business Media, 2012
- Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Christof Löding, Denis Lugiez, Sophie Tison, and Marc Tommasi. Tree automata techniques and applications, 1997
- Wolfgang Thomas, Thomas Wilke, et al. Automata, logics, and infinite games: a guide to current research, volume 2500. Springer Science & Business Media, 2002
Required prior knowledge: Introductory course on theoretical computer science
- Kursleiter/in: Thomas Zeume