M2 Course CR18, ENS-Lyon
- Title: Mathematical aspects of automata theory
- Lecturers: Denis Kuperberg, Matteo Mio, Valeria Vignudelli.
- Period: from November 2020 to January 2021.
- Number of lectures: 12, 2h long.
The goal of this course is to explore the rich connections between the theory of automata and regular languages, and various areas of mathematics.
Prerequisites: Nothing outside of the normal cursus, we hope the students will remember earlier courses on automata theory, and basic algebra such as group theory. We will anyway provide some notes during the course to refresh these notions.
In particular, we will develop the algebraic view on regular languages, and show how studying the properties of semigroups can bring a deep understanding of the phenomena at work in automata theory.
We will see how automata can be used to solve problems from other fields such as logic and relational algebra.
We will also give an overview of classical results and techniques in descriptive complexity: what is the topological complexity of sets that can be described with automata models ?
Finally, we will show how automata theory interacts with foundations of mathematics and computer science, such as category theory.