Equivalence of finite-valued streaming string transducers is decidable

We show that the equivalence problem for finite-valued streaming string transducers is decidable, thus solving a question left open in an ICALP’11 paper by Alur and Deshmukh. We follow a proof idea due to Culik and Karhumäki, that uses Ehrenfeucht’s conjecture. Our proof is much more involved, because streaming string transducers produce their outputs piecewise, in contrast to one-way or two-way transducers, that produce their output linearly while reading the input. The solution is to come up with a suitable normalization procedure for SST, based on some (mild) word combinatorics and word equations. The paper will be presented at ICALP’19, and it is co-authored with Gabriele Puppis.

Authors

• Anca Muscholl.

Keywords

No keywords are indexed for this paper.