Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Gabriele Puppis Connect in order to contact the contributor
Submitted on : Tuesday, January 10, 2017 - 4:16:46 PM
Last modification on : Friday, January 21, 2022 - 3:10:02 AM
Long-term archiving on: : Tuesday, April 11, 2017 - 4:11:45 PM


STACS 2017.pdf
Files produced by the author(s)



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. ⟨10.4230/LIPIcs⟩. ⟨hal-01431250⟩



Les métriques sont temporairement indisponibles