@article{Filiot:2021uk,
    Abstract = {Copyless streaming string transducers (copyless SST) have been introduced by R. Alur and P. {\v C}ern{\'y}in 2010 as a one-way deterministic automata model to define transductions of finite strings. Copyless SST extend deterministic finite state automata with a set of variables in which to store intermediate output strings, and those variables can be combined and updated all along the run, in a linear manner, i.e., no variable content can be copied on transitions. It is known that copyless SST capture exactly the class of MSO-definable string-to-string transductions, and are as expressive as deterministic two-way transducers. They enjoy good algorithmic properties. Most notably, they have decidable equivalence problem (in PSpace ). On the other hand, HDT0L systems have been introduced for a while, the most prominent result being the decidability of the equivalence problem. In this paper, we propose a semantics of HDT0L systems in terms of transductions, and use it to study the class of deterministic copyful SST. Our contributions are as follows:(i) HDT0L systems and total deterministic copyful SST have the same expressive power, (ii) the equivalence problem for deterministic copyful SST and the equivalence problem for HDT0L systems are inter-reducible, in quadratic time. As a consequence, equivalence of deterministic SST is decidable, (iii) the functionality of non-deterministic copyful SST is decidable, (iv) determining whether a non-deterministic copyful SST can be transformed into an equivalent non-deterministic copyless SST is decidable in polynomial time. HDT0L systems and total deterministic copyful SST have the same expressive power, the equivalence problem for deterministic copyful SST and the equivalence problem for HDT0L systems are inter-reducible, in quadratic time. As a consequence, equivalence of deterministic SST is decidable, the functionality of non-deterministic copyful SST is decidable, determining whether a non-deterministic copyful SST can be transformed into an equivalent non-deterministic copyless SST is decidable in polynomial time.},
    Author = {Filiot, Emmanuel and Reynier, Pierre-Alain},
    BookTitle = {Fundamenta Informaticae},
    File = {Copyful Streaming String Transducers - copyful\_submitted - k.pdf},
    ISBN = {1875-8681},
    Keywords = {words; transducers; equivalence problem},
    Pages = {59--76},
    Publisher = {IOS Press},
    Title = {Copyful Streaming String Transducers},
    Volume = {178},
    Year = {2021},
    bdsk-url-1 = {https://doi.org/10.3233/FI-2021-1998},
    date-added = {2021-03-24 11:47:11 +0100},
    date-modified = {2021-03-24 11:47:11 +0100},
    m1 = {1-2},
    ty = {JOUR},
    doi = {10.3233/FI-2021-1998}
}

@article{Filiot:2021uk, Abstract = {Copyless streaming string transducers (copyless SST) have been introduced by R. Alur and P. {\v C}ern{\'y}in 2010 as a one-way deterministic automata model to define transductions of finite strings. Copyless SST extend deterministic finite state automata with a set of variables in which to store intermediate output strings, and those variables can be combined and updated all along the run, in a linear manner, i.e., no variable content can be copied on transitions. It is known that copyless SST capture exactly the class of MSO-definable string-to-string transductions, and are as expressive as deterministic two-way transducers. They enjoy good algorithmic properties. Most notably, they have decidable equivalence problem (in PSpace ). On the other hand, HDT0L systems have been introduced for a while, the most prominent result being the decidability of the equivalence problem. In this paper, we propose a semantics of HDT0L systems in terms of transductions, and use it to study the class of deterministic copyful SST. Our contributions are as follows:(i) HDT0L systems and total deterministic copyful SST have the same expressive power, (ii) the equivalence problem for deterministic copyful SST and the equivalence problem for HDT0L systems are inter-reducible, in quadratic time. As a consequence, equivalence of deterministic SST is decidable, (iii) the functionality of non-deterministic copyful SST is decidable, (iv) determining whether a non-deterministic copyful SST can be transformed into an equivalent non-deterministic copyless SST is decidable in polynomial time. HDT0L systems and total deterministic copyful SST have the same expressive power, the equivalence problem for deterministic copyful SST and the equivalence problem for HDT0L systems are inter-reducible, in quadratic time. As a consequence, equivalence of deterministic SST is decidable, the functionality of non-deterministic copyful SST is decidable, determining whether a non-deterministic copyful SST can be transformed into an equivalent non-deterministic copyless SST is decidable in polynomial time.}, Author = {Filiot, Emmanuel and Reynier, Pierre-Alain}, BookTitle = {Fundamenta Informaticae}, File = {Copyful Streaming String Transducers - copyful_submitted - k.pdf}, ISBN = {1875-8681}, Keywords = {words; transducers; equivalence problem}, Pages = {59--76}, Publisher = {IOS Press}, Title = {Copyful Streaming String Transducers}, Volume = {178}, Year = {2021}, bdsk-url-1 = {https://doi.org/10.3233/FI-2021-1998}, date-added = {2021-03-24 11:47:11 +0100}, date-modified = {2021-03-24 11:47:11 +0100}, m1 = {1-2}, ty = {JOUR}, doi = {10.3233/FI-2021-1998} }