Affiliations: [a] Université libre de Bruxelles (U.L.B.), Belgium. [email protected] | [b] Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France. [email protected]
Correspondence:
[*]
Associate researcher at F.R.S.-FNRS, and supported by the MIS project F451019F (F.R.S.-FNRS). Address for correspondence: Université libre de Bruxelles, Belgium.
Note: [†] Partly supported by the DeLTA project (ANR-16-CE40-0007).
Abstract: Copyless streaming string transducers (copyless SST) have been introduced by R. Alur and P. Černý 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.
