joint work with Mikołaj Bojańczyk, Laure Daviaud and Vincent Penelle

This talk is about transductions, which are binary relations on
words. We are interested in various models computing transductions
(ie, transducers), namely two-way automata with outputs, streaming
string transducers and string-to-string MSO transductions. We observe
that each of these formalisms provides more than just a function from
words to words. Indeed, one can also reconstruct origin information,
which says how positions of the output string originate from positions
of the input string. It is also possible to provide any
string-to-string function with an origin semantic, indicating an
origin input position for each output position, in a similar way. This
defines a general object, that extends functions and which we call
origin graph. We characterise the families of origin graphs which
corresponds to the semantics of the classical transducer models.