Evènement pour le groupe Séminaire Méthodes Formelles

Date 2017-03-14  11:00-12:00
TitreOn the decomposition of finite-valued streaming string transducers 
RésuméI will present some preliminary results towards a proof of a decomposition theorem for streaming string transducers (SSTs). Roughly, the conjectured decomposition theorem states that every SST that associates at most k outputs to each input can be effectively decomposed as a finite union of functional SSTs. Such a result would imply, among other things, the decidability of the equivalence problem for the considered class of transducers as well as a correspondence with the classical two-way transducers. I will present a proof of this decomposition theorem in the special case of SSTs with 1 register. The proof heavily relies on a combinatorial result by Kortelainen concerning word equations with iterated factors. 
OrateurGabriele Puppis 

Aucun document lié à cet événement.

Retour à l'index