Which classes of origin graphs are generated by transducers?

11:00 30th November 2017 ( week 30/11/2017, Michaelmas Term 2017 )LTA, Wolfson Building
This talk is about transductions,
which are binary relations on words.
We are interested in various
models computing transductions (ie, transducers),
namely twoway automata with outputs, streaming
string transducers and stringtostring 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 righttoleft oneway 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.