On the decomposition of finite-valued streaming string transducers

Abstract : We prove the following decomposition theorem: every 1-register streaming string transducer that associates a uniformly bounded number of outputs with each input can be effectively decomposed as a finite union of functional 1-register streaming string transducers. This theorem relies on a combinatorial result by Kortelainen concerning word equations with iterated factors. Our result implies the decidability of the equivalence problem for the considered class of transducers. This can be seen as a first step towards proving a more general decomposition theorem for streaming string transducers with multiple registers.
Type de document :
Communication dans un congrès
34th International Symposium on Theoretical Aspects of Computer Science (STACS), Mar 2017, Hannover, Germany. 2017, 〈https://stacs2017.thi.uni-hannover.de/〉. 〈10.4230/LIPIcs〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-01431250
Contributeur : Gabriele Puppis <>
Soumis le : mardi 10 janvier 2017 - 16:16:46
Dernière modification le : jeudi 15 juin 2017 - 09:08:41
Document(s) archivé(s) le : mardi 11 avril 2017 - 16:11:45

Fichier

STACS 2017.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Paul Gallot, Anca Muscholl, Gabriele Puppis, Sylvain Salvati. On the decomposition of finite-valued streaming string transducers. 34th International Symposium on Theoretical Aspects of Computer Science (STACS), Mar 2017, Hannover, Germany. 2017, 〈https://stacs2017.thi.uni-hannover.de/〉. 〈10.4230/LIPIcs〉. 〈hal-01431250〉

Partager

Métriques

Consultations de
la notice

99

Téléchargements du document

29