Master 2014 2015
Stages de la spécialité SAR
Syntactic Monoids

Site :Syntactic Monoids
Lieu :Laboratoire de Recherche & Développement de l'EPITA (LRDE) 14 - 16 rue Voltaire 94276 Le Kremlin-Bicêtre Cedex
Encadrant : Akim Demaille
Dates :01/03/2015 au 31/08/2015
Rémunération :1000 Euros brut/mois
Mots-clés : Master SAR, autre qu’ATIAM


Many properties and characteristics of an automaton can be easily computed from its syntactic monoids. Such properties are of particular importance to theoreticians. Vcsn is a project led by Alexandre Duret-Lutz and Akim Demaille (LRDE). It is a platform for the manipulation of automata, transducers and weighted rational expressions. It is written in C++11 avoiding the classical object-oriented programming in favor of generic programming (template) for more performance. Vcsn is an heir of the Vaucanson 2 project which was developed in partnership with Jacques Sakarovitch (Telecom ParisTech) and Sylvain Lombardy (LaBRI). Vcsn has a sound base of data structure and algorithms for automata and rational expressions. However, it offers no support for syntactic monoids at all. The objective of this internship is to develop support for syntactic monoids in Vcsn, and to implement recent research results in Automata Theory that use the syntactic monoid.


Jacques Sakarovitch, “Elements of Automata Theory,” Cambridge University Press.

Akim Demaille, Alexandre Duret-Lutz, Sylvain Lombardy, Jacques Sakarovitch. “Implementation Concepts in Vaucanson 2,” CIAA’13.