BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/428
DTSTAMP:20230914T125924Z
SUMMARY:From Two-Way to One-Way Finite State Transducers
DESCRIPTION:Speaker: Emmanuel Filiot (Departement d'Informatique\nUniversit
 e Libre de Bruxelles\nCampus de la Plaine\nCP 212 - 1050 Bruxelles\nBelgiu
 m)\n\nAbstract: \nAny two-way finite state automaton is equivalent to some
  one-way finite state automaton. This well-known result\, shown by Rabin a
 nd Scott and independently by Shepherdson\, states that two-way finite sta
 te automata (even non-deterministic) characterize the class of regular lan
 guages. It is also known that this result does not extend to finite string
  transductions: (deterministic) two-way finite state transducers strictly 
 extend the expressive power of (functional) one-way transducers. In partic
 ular deterministic two-way transducers capture exactly the class of MSO-tr
 ansductions of finite strings. In this talk\, we address the following def
 inability problem: given a function defined by a two-way finite state tran
 sducer\, is it definable by a one-way finite state transducer? By extendin
 g Rabin and Scott's proof to transductions\, we show that this problem is 
 decidable. Our procedure builds a one-way transducer\, which is equivalent
  to the two-way transducer\, whenever one exists.\n
URL:https://www.tcs.tifr.res.in/web/events/428
DTSTART;TZID=Asia/Kolkata:20131220T160000
DTEND;TZID=Asia/Kolkata:20131220T170000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR