LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Past Seminars
Which classes of origin graphs are generated by transducers?
- Date
- Tuesday, March 13 2018 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Bruno Guillon (IRIF (Paris 7) and Universita degli Studi di Milano)
This talk is about regular word transductions, which form a robust class of (partial) functions from (finite) words to (finite) words. Regular transduction are for instance recognized by deterministic 2-way finite automata with outputs or deterministic streaming string transducers. We start from the observation that the various equivalent models of transducers capturing the class, actually provide more than a function from words to words. Indeed, one can also reconstruct origin information which says how positions of the output word originate from positions of the input word. With this semantics, transductions are viewed as sets of particular graphs, called origin graphs. This allows us to express properties, such as «the output is a permutation of the input» or «the transduction is a right-to-left one-way transduction», using MSO Logic. After an introduction presenting the general framework, I will briefly show that MSO Logic is decidable on the origin semantics of regular transducers, yielding procedures to check formulas such as given above. Then, I will characterize 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 at ICALP17.