Jobs/M2 AD 2014 minimisation-automates

	Minimization of automata
Reference id	M2 AD 2014 minimisation-automates
Dates	5 - 6 months in 2014
Research field	Automata
Related project	Vaucanson
Advisor	Akim Demaille
General presentation of the field	La théorie classique des automates, des transducteurs et des expressions rationnelles, admet une extension très élégante et extrêmement utile (e.g., en traitement des langues naturelles) prenant en compte un concept de pondération. Les poids sont alors pris dans un semi-anneau, qu'il soit classique (⟨B,∨,∧⟩, ⟨Z,+,×⟩, ⟨Q,+,×⟩, etc.), tropical (⟨Z,min,+⟩, etc.), ou autre encore (par exemple des expressions rationnelles). Vaucanson 2 est un projet ANR développé en partenariat entre Télécom ParisTech (Jacques Sakarovitch), le LaBRI (Sylvain Lombardy) et le LRDE (Alexandre Duret-Lutz et Akim Demaille). Il s'agit d'une plate-forme de manipulation des automates, transducteurs et expressions rationnelles pondérés. Elle est écrite en C++11 en évitant la programmation orientée-objet classique, au profit de la programmation générique (template) pour les performances.
Prerequisites
Objectives	La minimisation d’un automate consiste à l’«optimiser» : construire le plus petit des automates équivalents. Il existe de nombreux algorithmes de minimisation d’automates, dont les domaines d’application et les performances varient. Il s’agira d’implémenter dans Vaucanson 2 certains de ces algorithmes, de les optimiser, et de mener une étude comparative de leurs performances. Ces résultats permettront de proposer une approche adaptative, qui choisisse l’algorithme à appliquer en fonction du profil de l’automate/transducteur.
Benefit for the candidate
References	Some 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. Jean Berstel, Luc Boasson, Olivier Carton, Isabelle Fagnot, “Minimization of automata.” Marie-Pierre Béal, Maxime Crochemore, “Minimizing incomplete automata.”
Place	LRDE: How to get to us
Compensation	800€ euros gross/month
Future work opportunities	If the internship is satisfactory, we would like it to be followed by a PhD.
Contact	<akim . demaille at lrde . epita . fr> <akim . demaille at lrde . epita . fr>