On Reversible Transducers

Ismael Jecker
ULB
Friday, 19 May, 2017 - 16:00
Salle P.OF2072

Deterministic two-way transducers define the robust class of regular functions which, among other good properties, is 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 talk, I will present 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 will see that any two-way transducer can be made reversible through a single exponential blow-up. As a consequence, we obtain that the composition of two-way transducers can be done with a single exponential blow-up in the number of states.