Master 2014 2015
Stages de la spécialité SAR
Symmetric Difference Automata

Site :Symmetric Difference Automata
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


The classical theory of automata, of transducers and of rational expressions, admits a very elegant and extremely useful extension (eg, in natural language processing) taking into account the concept of weighting. The weights are then taken in a semi-ring, which can be classical, tropical, or yet of another type (e.g. rational expressions). The field F2 is a particular interest, and shows quite a few unique properties, as demonstrated by the current active research under various names. 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). The objective of this internship is to exploit the existing features of Vcsn to apply them to F2 in a first step, and then, in a second step, to use Vcsn as a tool to explore novel results.


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.

L. van Zijl, J. Geldenhuys, “ Symmetric Difference NFA : the state of the art”