Le séminaire du LSV

Le séminaire du LSV a lieu le mardi à 11h00. Le lieu habituel est la salle de conférences au Pavillon des Jardins (plan d'accès). Pour être informé par email des prochains séminaires, contacter Stéphane Le Roux and Matthias Fuegger.

Le séminaire du LSV est public et ne nécessite aucune inscription préalable.

Séminaires passés

Which classes of origin graphs are generated by transducers?

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

 Bruno Guillon
Le mardi 13 mars 2018 à 11:00
Salle de Conférence (Pavillon des Jardins)
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.

À propos du LSV

Agenda des séminaires

Exporter l'agenda au format iCalendar | Les séminaires précédents

mar. 19 février

Les séminaires précédents