BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SUMMARY:
Which classes of origin graphs are generated by transducers?
STATUS:CONFIRMED
ATTENDEE;CN="Bruno Guillon
":
MAILTO:no@spam.com
DESCRIPTION:
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 recogn
ized by deterministic 2-way finite automata with outputs or
deterministic streaming string transducers. We start from th
e observation that the various equivalent models of transduc
ers capturing the class\, actually provide more than a funct
ion from words to words. Indeed\, one can also reconstruct o
rigin information which says how positions of the output wor
d originate from positions of the input word. With this sema
ntics\, transductions are viewed as sets of particular graph
s\, called origin graphs. This allows us to express properti
es\, 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 ge
neral framework\, I will briefly show that MSO Logic is deci
dable on the origin semantics of regular transducers\, yield
ing procedures to check formulas such as given above. Then\,
I will characterize the families of origin graphs which cor
responds to the semantics of streaming string transducers. T
his is joint work with MikoÅaj BojaÅczyk\, Laure Daviaud a
nd Vincent Penelle\, which has been published at ICALP17.
DTSTART;TZID=Europe/Paris:20180313T110000
DURATION:PT1H
URL;VALUE=URI:http://www.lsv.ens-cachan.fr/Seminaires/?sem=201803131
100
UID:LSVsemLSV.201803131100@lsv.ens-cachan.fr
LOCATION:Salle de Conférence (Pavillon des Jardins)
END:VEVENT
END:VCALENDAR