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: 15, 2h long.
Short Description:
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 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.
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.
References:
Semigroups:
Probabilistic Automata:
Relation Algebras:
Coalgebra (with also a short introduction to category theory), including examples and exercises:
Basics of category theory, including examples and exercises:
- Basic Category Theory for Computer Scientists, Pierce (see in particular chapters 1.1, 1.4, 2.1)
- Category Theory: Awodey (more advanced)
Bisimulation:
Infinite Words:
Automatic Structures:
The course will happen on BBB from Portail des etudes, an ENS login is needed.
If not everybody is able to access it, we will switch to ENT Visio, room M2IF - CR18, see the pad for detailed information.
For any question, email denis.kuperberg@ens-lyon.fr.
Midterm Exam
For the midterm, each student has to choose a paper from the following list, via this interface, now Framadate instead of Doodle. At most 2 students can choose the same paper.
The task is to write a report, where you summarize the content of the paper, highlight the results you found interesting, state the most relevant contributions. You should also write if some parts of the papers are not clear, or if you would have questions for the author. Finally, you can suggest lines of research that continue this work.
The report should be from 1 to 2 pages long, in english.
For some of the papers which are longer or more technical, we specify a relevant subset of the paper, the rest can be ignored.
Reports are due before 18th of January, to send by email at denis.kuperberg@ens-lyon.fr.
Finally, each student will be interviewed for about 10mn, also in english, so that his/her understanding of the paper can be checked.
LIST OF PAPERS
Factorization Forests, Mikołaj Bojańczyk
Checking NFA equivalence with bisimulations up to congruence, Filippo Bonchi, Damien Pous
On the star-height of regular languages, Sylvain Lombardy, Jacques Sakarovitch
Logics for Reversible Regular Languages and Semigroups with Involution, Paul Gastin, Amaldev Manuel, Govind R
Uniformisation Gives the Full Strength of Regular Languages, Nathan Lhote, Vincent Michielini, Michał Skrzypczak
Unary Prime Languages, Ismaël Jecker, Orna Kupferman, Nicolas Mazzocchi
Powers of Regular Languages, Szilárd Zsolt Fazekas
Undecidability results for probabilistic automata, Nathanaël Fijalkow
Probabilistic automata, Michael O. Rabin
It is enough to go up to section VI included.
Separating Regular Languages with First-Order Logic, Thomas Place, Marc Zeitoun
Automata Minimization: a Functorial Approach, Thomas Colcombet, Daniela Petrisan.
Recognisable Languages over Monads, Mikołaj Bojańczyk
On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection, Mateus de Oliveira Oliveira, Michael Wehar
Enhanced Coalgebraic Bisimulation, Jurriaan Rot, Filippo Bonchi, Marcello Bonsangue, Damien Pous, Jan Rutten, Alexandra Silva
Section 7 can be skipped.
Generalizing determinization from automata to coalgebras, Alexandra Silva, Filippo Bonchi, Marcello Bonsangue, Jan Rutten
Technical proofs and details in section 4 and 5 can be skipped.