Difference between revisions of "Jobs/M2 AD 2015 Syntactic Monoids"
From LRDE
| (7 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{Job |
{{Job |
||
|Reference id=M2 AD 2015 Syntactic Monoids |
|Reference id=M2 AD 2015 Syntactic Monoids |
||
| − | |Title= |
+ | |Title=Syntactic Monoids |
|Dates=5-6 months in 2015 |
|Dates=5-6 months in 2015 |
||
|Research field=Automata Theory |
|Research field=Automata Theory |
||
|Related project=Vaucanson |
|Related project=Vaucanson |
||
|Advisor=Akim Demaille |
|Advisor=Akim Demaille |
||
| + | |General presentation of the field=Many properties and characteristics of an automaton can be easily computed from its syntactic monoids. Such properties are of particular importance to theoreticians. |
||
| − | |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). |
||
| − | The field 𝔽₂ is a particular interest, and shows quite a few unique properties, as demonstrated by the current active research under various names (e.g., "Symmetric Difference Automata"). |
||
| − | |||
| ⚫ | 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 has a sound base of data structure and algorithms for automata and rational expressions. However, it offers no support for syntactic monoids at all. |
||
|Prerequisites=* good programmer in some language |
|Prerequisites=* good programmer in some language |
||
* acquaintance with C++ |
* acquaintance with C++ |
||
* facilities with theoretical matters |
* facilities with theoretical matters |
||
| − | |Objectives=The objective of this internship is |
+ | |Objectives=The objective of this internship is to develop support for syntactic monoids in Vcsn, and to implement recent research results in Automata Theory that use the syntactic monoid. |
| ⚫ | |||
| − | |References=Some references |
||
| ⚫ | |||
* [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://www.cs.sun.ac.za/~jaco/PUBS/index.html#vzg13 L. van Zijl, J. Geldenhuys, “ Symmetric Difference NFA: the state of the art”] |
||
| − | |||
|Contact=<akim at lrde . epita . fr> |
|Contact=<akim at lrde . epita . fr> |
||
|Compensation=1000 € gross/month |
|Compensation=1000 € 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 |
|Type=Master Internship |
||
|Language=en |
|Language=en |
||
Latest revision as of 16:13, 12 December 2014
| Syntactic Monoids | |
|---|---|
| Reference id |
M2 AD 2015 Syntactic Monoids |
| Dates |
5-6 months in 2015 |
| Research field |
Automata Theory |
| Related project | |
| Advisor | |
| General presentation of the field |
Many properties and characteristics of an automaton can be easily computed from its syntactic monoids. Such properties are of particular importance to theoreticians. 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 has a sound base of data structure and algorithms for automata and rational expressions. However, it offers no support for syntactic monoids at all. |
| Prerequisites |
|
| Objectives |
The objective of this internship is to develop support for syntactic monoids in Vcsn, and to implement recent research results in Automata Theory that use the syntactic monoid. |
| Benefit for the candidate | |
| References | |
| Place | LRDE: How to get to us |
| Compensation |
1000 € gross/month |
| Future work opportunities |
If you have performed the internship satisfactorily, we would like it to be followed by a PhD thesis. |
| Contact |