Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
From Two-Way to One-Way Finite State Transducers
du groupe Graphes et Logique

Date 2013-02-19  11:00-12:00
TitreFrom Two-Way to One-Way Finite State Transducers 
RésuméAny two-way finite state automaton is equivalent to some one-way finite state automaton. This well-known result, shown by Rabin and Scott and independently by Shepherdson, states that two-way finite state automata (even non-deterministic) characterize the class of regular languages. It is also known that this result does not extend to finite string transductions: (deterministic) two-way finite state transducers strictly extend the expressive power of (functional) one-way transducers. In particular deterministic two-way transducers capture exactly the class of MSO-transductions of finite strings. In this talk, I will address the following definability problem: given a function defined by a two-way finite state transducer, is it definable by a one-way finite state transducer? By extending Rabin and Scott's proof to transductions, we show that this problem is decidable. Our procedure builds a one-way transducer, which is equivalent to the two-way transducer, whenever one exists. This is a joint work with Emmanuel Filiot, Olivier Gauwin and Pierre-Alain Reynier. 
LieuSalle 076 
OrateurFrédéric Servais 
Emailfrederic.servais@gmail.com 
UrlUniversity of Hasselt 



Aucun document lié à cet événement.

Retour
Retour à l'index