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

Speaker(s)

Bruno Guillon

Affiliation

Uniwersytet Warszawski

Date

Feb. 15, 2017, 2:15 p.m.

Room

room 5870

Title in Polish

Regular transductions with origin semantics

Seminar

Seminar Automata Theory

---

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.

---