  Deterministic two-way transducers define the robust class of regular
functions which is, among other good properties, closed under composition.
However, the best known algorithms for composing two-way transducers cause a
double exponential blow-up in the size of the inputs. In this paper, we
introduce a class of transducers for which the composition has polynomial
complexity. It is the class of reversible transducers, for which the
computation steps can be reversed deterministically. While in the one-way
setting this class is not very expressive, we prove that any two-way transducer
can be made reversible through a single exponential blow-up. As a consequence,
we prove that the composition of two-way transducers can be done with a single
exponential blow-up in the number of states. A uniformization of a relation is
a function with the same domain and which is included in the original relation.
Our main result actually states that we can uniformize any non-deterministic
two-way transducer by a reversible transducer with a single exponential
blow-up, improving the known result by de Souza which has a quadruple
exponential complexity. As a side result, our construction also gives a
quadratic transformation from copyless streaming string transducers to two-way
transducers, improving the exponential previous bound.
