Sarah Winter

(IRIF, Paris)

The notion of delay between finite transducers is a core element of numerous fundamental results of transducer theory.
In the first part of this talk we introduce an analogous notion for more complex machines: Streaming string transducers(SST) which strictly extend the expressiveness of finite transducers via additional registers that store partial outputs.

Our notion of delay is regular: a finite automaton can check whether the delay between any two SST executions falls within a specified bound. As a consequence, it enjoys good decidability properties. Furthermore, it has good completeness properties: two SSTs are equivalent if and only if they are equivalent up to some (computable) bounded delay.

In the second part of the talk we focus on finite-valuedness. A transducer is finite-valued if for some bound k, it maps any given input to at most k outputs. For classical, finite transducers, finite-valuedness ensures decidability of equivalence, contrasting with the undecidability in the general case. Moreover, for classical transducers, it is also known that finite-valuedness is decidable and that any k-valued finite transducer can be decomposed as a union of k single-valued finite transducers.

We address extensions of these results to SSTs, answering questions raised by Alur and Deshmukh in 2011. The main results are that any k-valued SST can be effectively decomposed as a union of k (single-valued) deterministic SSTs, and that finite-valuedness of SSTs is decidable. Our notion of delay is central to these results.