Difference between revisions of "Jobs/M2 AD 2014 minimisation-automates"
From LRDE
Line 6: | Line 6: | ||
|Related project=Vaucanson |
|Related project=Vaucanson |
||
|Advisor=Akim Demaille |
|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 (⟨B, ∨, ∧⟩, ⟨Z, +, ×⟩, ⟨Q, +, ×⟩, etc..), tropical (⟨Z min, +⟩, etc..), or yet of another |
+ | |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 Resaearch 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. |
Vaucanson 2 is a project with financial aid from ANR (National Resaearch 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. |
|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. |
||
Line 16: | Line 16: | ||
|Contact=<akim . demaille at lrde . epita . fr> |
|Contact=<akim . demaille at lrde . epita . fr> |
||
|Compensation=800 euros gross/month |
|Compensation=800 euros gross/month |
||
− | |Future work opportunities= |
+ | |Future work opportunities=If you have performed the internship satisfactorily, we would like it to be followed by a PhD thesis. |
|Type=Master Internship |
|Type=Master Internship |
||
|Language=en |
|Language=en |
Revision as of 18:47, 19 February 2014
Minimization of automata | |
---|---|
Reference id |
M2 AD 2014 minimisation-automates |
Dates |
5 - 6 months in 2014 |
Research field |
Automata |
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 Resaearch 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> |