Jobs/M2 AD 2015 Syntactic Monoids


Syntactic Monoids
Reference id

M2 AD 2015 Syntactic Monoids


5-6 months in 2015

Research field

Automata Theory

Related project



Akim Demaille

General presentation of the field

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.

  • good programmer in some language
  • acquaintance with C++
  • facilities with theoretical matters

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.

Benefit for the candidate
Place LRDE: How to get to us

1000 € gross/month

Future work opportunities

If you have performed the internship satisfactorily, we would like it to be followed by a PhD thesis.


<akim at lrde . epita . fr> <akim at lrde . epita . fr>