On the decomposition of finite-valued streaming string transducers

Paul Gallot; Anca Muscholl; Gabriele Puppis; Sylvain Salvati

doi:10.4230/LIPIcs

On the decomposition of finite-valued streaming string transducers

Paul Gallot ¹ Anca Muscholl ¹ Gabriele Puppis ¹ Sylvain Salvati ^{2, 3}

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

3 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

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.

Keywords : equivalence finite valuedness 1998 ACM Subject Classification F11 Models of Computation Automata Keywords and phrases Streaming Transducers

Document type :

Conference papers

Domain :

Computer Science [cs] / Formal Languages and Automata Theory [cs.FL]

Complete list of metadatas

Cited literature [17 references] Display Hide Download

https://hal.archives-ouvertes.fr/hal-01431250
Contributor : Gabriele Puppis <>
Submitted on : Tuesday, January 10, 2017 - 4:16:46 PM
Last modification on : Tuesday, April 2, 2019 - 1:45:42 AM
Long-term archiving on: Tuesday, April 11, 2017 - 4:11:45 PM

STACS 2017.pdf

Files produced by the author(s)

On the decomposition of finite-valued streaming string transducers

File

Identifiers

Collections

Citation

Export

Metrics

319

94

Contact

On the decomposition of finite-valued streaming string transducers

File

Identifiers

Collections

Citation

Export

Share

Metrics

319

94

Contact