Skip to main content

Which classes of origin graphs are generated by transducers?

Bruno Guillon ( University of Milan )

This talk is about transductions,
which are binary relations on words.
We are interested in various models computing transductions (ietransducers),
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 set of pairs of words.
Indeed, one can also reconstruct origin information
which says how positions of the output string originate from positions of the input string.
On the other hand,
it is also possible to provide any pair of words in a relation with an origin mapping,
indicating an origin input position for each output position, in a similar way.
This defines a general object called origin graph.
We first show that MSO is decidable on the origin semantics of the main transducer models,
yielding procedures to check formulas such as
«the output is a permutation of the input» or «the transduction is a right-to-left one-way transduction».
We then characterise the families of origin graphs which corresponds to the semantics of streaming string transducers.

This is joint work with Mikołaj Bojańczyk, Laure Daviaud and Vincent Penelle,
which has been published to ICALP17.

Share this: