Difference between revisions of "Jobs/M2 AD 2014 minimisation-automates"
From LRDE
| Line 3: | Line 3: | ||
;Thématique: |
;Thématique: |
||
Automates |
Automates |
||
| ⚫ | |||
| − | ;Laboratoire: |
||
| ⚫ | |||
;Équipe: |
;Équipe: |
||
Projet Vaucanson (http://vaucanson.lrde.epita.fr) |
Projet Vaucanson (http://vaucanson.lrde.epita.fr) |
||
| Line 10: | Line 9: | ||
Akim Demaille <akim . demaille at lrde . epita . fr> |
Akim Demaille <akim . demaille at lrde . epita . fr> |
||
| − | + | ;Présentation générale du domaine |
|
La théorie classique des automates, des transducteurs et des |
La théorie classique des automates, des transducteurs et des |
||
expressions rationnelles, admet une extension très élégante et |
expressions rationnelles, admet une extension très élégante et |
||
| Line 26: | Line 25: | ||
générique (\texttt{template}) pour les performances. |
générique (\texttt{template}) pour les performances. |
||
| − | + | ;Objectifs du stage |
|
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. |
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. |
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. |
||
| − | + | ;Quelques références bibliographiques |
|
* [http://www.amazon.com/Elements-Automata-Theory-Jacques-Sakarovitch/dp/0521844258 Jacques Sakarovitch, “Elements of Automata Theory,” Cambridge University Press.] |
* [http://www.amazon.com/Elements-Automata-Theory-Jacques-Sakarovitch/dp/0521844258 Jacques Sakarovitch, “Elements of Automata Theory,” Cambridge University Press.] |
||
* [http://publications.lrde.epita.fr/201307-CIAA Akim Demaille, Alexandre Duret-Lutz, Sylvain Lombardy, Jacques Sakarovitch. “Implementation Concepts in Vaucanson 2,” CIAA’13.] |
* [http://publications.lrde.epita.fr/201307-CIAA Akim Demaille, Alexandre Duret-Lutz, Sylvain Lombardy, Jacques Sakarovitch. “Implementation Concepts in Vaucanson 2,” CIAA’13.] |
||
* [http://arxiv.org/abs/1010.5318 Jean Berstel, Luc Boasson, Olivier Carton, Isabelle Fagnot, “Minimization of automata.”] |
* [http://arxiv.org/abs/1010.5318 Jean Berstel, Luc Boasson, Olivier Carton, Isabelle Fagnot, “Minimization of automata.”] |
||
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.8177 Marie-Pierre Béal, Maxime Crochemore, “Minimizing incomplete automata.”] |
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.8177 Marie-Pierre Béal, Maxime Crochemore, “Minimizing incomplete automata.”] |
||
| + | |||
| + | ;Rémunération : environ 800 € brut/mois |
||
| + | |||
| + | ;Débouchés : Si le déroulement du stage est satisfaisant, nous souhaiterions qu'il soit suivi d'une thèse de doctorat. |
||
Revision as of 15:00, 12 November 2013
Minimisation d'automates
- Thématique
Automates
- Lieu
- Laboratoire de Recherche et Développement de l’EPITA (LRDE), 18, rue Pasteur, 94270 Le Kremlin-Bicêtre, (Porte d'Italie)
- Équipe
Projet Vaucanson (http://vaucanson.lrde.epita.fr)
- Directeur de stage
Akim Demaille <akim . demaille at lrde . epita . fr>
- Présentation générale du domaine
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 (\texttt{template}) pour les performances.
- Objectifs du stage
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.
- Quelques références bibliographiques
- 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.”
- Rémunération
- environ 800 € brut/mois
- Débouchés
- Si le déroulement du stage est satisfaisant, nous souhaiterions qu'il soit suivi d'une thèse de doctorat.