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:

• Mathematical Foundations of Automata Theory, MPRI course, Jean Eric-Pin
• Mikołaj Bojańczyk's course on monoids, Green Relations, Schützenberger,...
• Finite Model Theory, Libkin: Ehrenfeucht-Fraïssé games

Probabilistic Automata:

• Probabilistic Automata, Seminal paper of Rabin 1963.
• Irregular Behaviours of Probabilistic Automata, Fijalkow and Skrzypczak.
• Probabilistic Automata on Finite words: Decidable and Undecidable Problems, Gimbert and Oualhadj.

Relation Algebras:

• HDR of Damien Pous

Coalgebra (with also a short introduction to category theory), including examples and exercises:

• The Method of Coalgebra: exercises in coinduction, Rutten (see in particular chapters 1-3, 5, 8, 10, 15)
• Algebras and Coalgebras, Venema (see in particular chapters 9-11)
• Introduction to Coalgebra: Towards Mathematics of States and Observation, Jacobs (more advanced)

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:

• Introduction to bisimulation and coinduction, Sangiorgi (for labelled transition systems ie NFA where all states are accepting, including examples and exercises. See in particular chapter 1)
• Checking NFA equivalence with bisimulations up to congruence, Bonchi, Pous (see in particular chapters 1-3)
• Exploring probabilistic bisimulations part I, Hennessy (see in particular chapters 1-3)

Infinite Words:

• Automata and semigroups recognizing infinite words, Carton, Perrin, Pin.
• Languages, Automata, and Logic,Thomas
• Automata, Logic and Games, Ong

Automatic Structures:

• Restricted Set-Theoretical Definitions in Arithmetic, Robinson
• Automatic Structures: Twenty Years Later, Grädel

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.