Word transducers: from two-way to one-way

Regular word transductions extend the robust family of regular word languages, preserving many of its characterisations and algorithmic properties. Finite state transducers are a standard model for representing word transductions, and can be seen as automata extended with outputs. However, differently from automata, two-way transducers are strictly more expressive than one-way transducers. It has been recently shown how to decide if a two-way functional transducer has an equivalent one-way transducer, and the complexity of the algorithm is non-elementary. We will present an alternative and simpler characterisation that is decidable in EXPSPACE. In the positive case, the characterisation can be used to construct an equivalent one-way transducer of (worst-case optimal) doubly exponential size. We will finally discuss a generalisation of the result that characterises k-pass sweeping definability of transductions, and relate this to minimisation problems for registers of streaming transducers.