M2 Course CR18, ENS-Lyon Short Description: 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.


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: 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.


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.