M2 Course, ENS-Lyon
- Title: Mathematical aspects of automata theory
- Lecturers: Denis Kuperberg and Matteo Mio.
- Period: from September 2020 to December 2020.
- 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.
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 then show how this approach can generalize to several extensions of regular languages: weighted automata, probabilistic settings, infinite words, finite and infinite trees, graphs,...
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, and if time permits, the course will present recent research uncovering its links with set theory and category theory.
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.