Difference between revisions of "Jobs/M2 AD 2014 minimisation-automates"
From LRDE
(Created page with ";Thématique: Automates ;Laboratoire: Laboratoire de Recherche et Développement de l’EPITA (LRDE) ;Équipe: Projet Vaucanson (http://vaucanson.lrde.epita.fr) ;Directeur de ...") |
|||
| (26 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| + | {{Job |
||
| − | ;Thématique: |
||
| + | |Reference id=M2 AD 2014 minimisation-automates |
||
| − | Automates |
||
| + | |Title=Minimization of automata |
||
| − | ;Laboratoire: |
||
| + | |Dates=5 - 6 months in 2014 |
||
| − | Laboratoire de Recherche et Développement de l’EPITA (LRDE) |
||
| + | |Research field=Automata Theory |
||
| − | ;Équipe: |
||
| + | |Related project=Vaucanson |
||
| − | Projet Vaucanson (http://vaucanson.lrde.epita.fr) |
||
| + | |Advisor=Akim Demaille |
||
| − | ;Directeur de stage: |
||
| + | |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 (⟨B, ∨, ∧⟩, ⟨Z, +, ×⟩, ⟨Q, +, ×⟩, etc..), tropical (⟨Z min, +⟩, etc..), or yet of another type (eg rational expressions). |
||
| ⚫ | |||
| + | Vaucanson 2 is a project with financial aid from ANR (National Research Agency) developed in partnership between Telecom ParisTech (Jacques Sakarovitch), LaBRI (Sylvain Lombardy) and the LRDE (Alexandre Duret-Lutz and Akim Demaille). 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. |
||
| − | |||
| + | |Objectives=The minimization of an automaton consists of its "optimization": it means building the smallest equivalent automaton. There are many algorithms for the minimization of automata, whose fields of application and performance vary. The task of the intern will be to implement some of these algorithms in Vaucanson 2, to optimize them, and to conduct a comparative study of their performance. These results will provide an adaptive approach that selects the algorithm to be applied depending on the profile of the automaton / transducer. |
||
| − | === Présentation générale du domaine === |
||
| + | |References=Some references |
||
| − | 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=== |
||
* [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.”] |
||
| ⚫ | |||
| + | |Compensation=800 euros gross/month |
||
| + | |Future work opportunities=If you have performed the internship satisfactorily, we would like it to be followed by a PhD thesis. |
||
| + | |Type=Master Internship |
||
| + | |Language=en |
||
| + | }} |
||
Latest revision as of 17:40, 29 October 2014
| Minimization of automata | |
|---|---|
| Reference id |
M2 AD 2014 minimisation-automates |
| Dates |
5 - 6 months in 2014 |
| Research field |
Automata Theory |
| Related project | |
| Advisor | |
| 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 (⟨B, ∨, ∧⟩, ⟨Z, +, ×⟩, ⟨Q, +, ×⟩, etc..), tropical (⟨Z min, +⟩, etc..), or yet of another type (eg rational expressions). Vaucanson 2 is a project with financial aid from ANR (National Research Agency) developed in partnership between Telecom ParisTech (Jacques Sakarovitch), LaBRI (Sylvain Lombardy) and the LRDE (Alexandre Duret-Lutz and Akim Demaille). 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. |
| Prerequisites | |
| Objectives |
The minimization of an automaton consists of its "optimization": it means building the smallest equivalent automaton. There are many algorithms for the minimization of automata, whose fields of application and performance vary. The task of the intern will be to implement some of these algorithms in Vaucanson 2, to optimize them, and to conduct a comparative study of their performance. These results will provide an adaptive approach that selects the algorithm to be applied depending on the profile of the automaton / transducer. |
| Benefit for the candidate | |
| References |
Some references
|
| Place | LRDE: How to get to us |
| Compensation |
800 euros gross/month |
| Future work opportunities |
If you have performed the internship satisfactorily, we would like it to be followed by a PhD thesis. |
| Contact |
<akim . demaille at lrde . epita . fr> <akim . demaille at lrde . epita . fr> |