  Functional transductions realized by two-way transducers (or, equally, by
streaming transducers or MSO transductions) are the natural and standard notion
of "regular" mappings from words to words. It was shown in 2013 that it is
decidable if such a transduction can be implemented by some one-way transducer,
but the given algorithm has non-elementary complexity. We provide an algorithm
of different flavor solving the above question, that has doubly exponential
space complexity. In the special case of sweeping transducers the complexity is
one exponential less. We also show how to construct an equivalent one-way
transducer, whenever it exists, in doubly or triply exponential time, again
depending on whether the input transducer is sweeping or two-way. In the
sweeping case our construction is shown to be optimal.
