Jobs/M2 2015 AD Faster, Faster, Faster

	Faster, Faster, Faster
Reference id	M2 2015 AD Faster, Faster, Faster
Dates	5-6 months in 2015
Research field	Automata Theory
Related project	Vaucanson
Advisor	Akim Demaille
General presentation of the field	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 (⟨𝔹, ∨, ∧⟩, ⟨ℤ, +, ×⟩, ⟨ℚ, +, ×⟩, etc..), tropical (⟨ℤ, min, +⟩, etc..), or yet of another type (e.g. rational expressions). 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 aims at speed and user friendliness. To achieve this goal, it is built in three layers: static: this is a templated C++ library with efficient data structures and algorithms dyn: this C++ API support type-erasure and shields the user from the complex API of static while preserving performances. It also support code-generation and linking on the fly Python: on top of dyn, a Python binding allows a pleasant use of Vcsn, without any C++ knowledge required.
Prerequisites	good programmer in some language acquaintance with C++ facilities with theoretical matters
Objectives	The objective of this internship is to improve the performances of Vcsn is every possible ways. This includes: design of a binary format to save and restore automata (possibly with mmap) improvements to the core data structures design of efficient alternatives to classical data structures such as found in the C++ library improvement of the existing algorithms taken from Automata Theory, such as epsilon-transition removal optimization of the dyn type-erased dynamic dispatch etc.
Benefit for the candidate
References	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. Akim Demaille, Alexandre Duret-Lutz, Sylvain Lombardy, Luca Saiu, Jacques Sakarovitch. “ A Type System for Weighted Automata and Rational Expressions,” CIAA’14.
Place	LRDE: How to get to us
Compensation	1000 € gross/month
Future work opportunities
Contact	<akim at lrde . epita . fr> <akim at lrde . epita . fr>