  Copyless streaming string transducers (copyless SST) have been introduced by
R. Alur and P. Cerny in 2010 as a one-way deterministic automata model to
define transformations of finite strings. Copyless SST extend deterministic
finite state automata with a set of registers in which to store intermediate
output strings, and those registers can be combined and updated all along the
run, in a linear manner, i.e., no register content can be copied on
transitions. It is known that copyless SST capture exactly the class of
MSO-definable string-to-string transformations, as defined by B. Courcelle, and
are equi-expressive to deterministic two-way transducers. They enjoy good
algorithmic properties. Most notably, they have decidable equivalence problem
(in PSpace). In this paper, we show that they still have decidable equivalence
problem even without the copyless restriction. The proof reduces to the HDT0L
sequence equivalence problem, which is known to be decidable. We also show that
this latter problem is as difficult as the SST equivalence problem, modulo
linear time reduction.
