Jobs/M2 AD 2015 Symmetric Difference Automata

From LRDE

Revision as of 14:09, 29 October 2014 by Akim Demaille (talk | contribs)
Symmetric Difference Automata
Reference id

M2 AD 2015 Symmetric Difference Automata

Dates

5-6 months in 2015

Research field

Automata Theory

Related project

Vaucanson

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 (⟨𝔹, ∨, ∧⟩, ⟨ℤ, +, ×⟩, ⟨ℚ, +, ×⟩, etc..), tropical (⟨ℤ min, +⟩, etc..), or yet of another type (e.g. rational expressions).

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 5 LaBRI).

Prerequisites

- good programmer in some language - acquaintance with C++ - facilities with theoretical matters

Objectives

The objective of this internship is exploit the existing features of Vcsn to apply them to 𝔽₂ in a first step, and then, in a second step, to use Vcsn as a tool to explore novel results.

Benefit for the candidate
References
Place LRDE: How to get to us
Compensation

1000 € gross/month

Future work opportunities

PhD thesis.

Contact

<akim at lrde . epita . fr> <akim at lrde . epita . fr>