| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [17 references]
https://hal.archives-ouvertes.fr/hal-01431250
Contributor : Gabriele Puppis <>
Submitted on : Tuesday, January 10, 2017 - 4:16:46 PM
Last modification on : Wednesday, March 18, 2020 - 6:08:04 PM
Document(s) archivé(s) le : Tuesday, April 11, 2017 - 4:11:45 PM
Contributor : Gabriele Puppis <>
Submitted on : Tuesday, January 10, 2017 - 4:16:46 PM
Last modification on : Wednesday, March 18, 2020 - 6:08:04 PM
Document(s) archivé(s) le : Tuesday, April 11, 2017 - 4:11:45 PM
File
STACS 2017.pdf
Files produced by the author(s)