On the Decomposition of Finite-Valued Streaming String Transducers
Paul Gallot, Anca Muscholl, Gabriele Puppis, Sylvain Salvati · Institutional Research Information System (University of Udine) · 2017
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.