Tata Institute of Fundamental Research
From Two-Way to One-Way Finite State Transducers
Seminar
Speaker:
Emmanuel Filiot (Departement d'Informatique
Universite Libre de Bruxelles
Campus de la Plaine
CP 212 - 1050 Bruxelles
Belgium)
Organiser:
Paritosh K Pandya
Date:
Friday, 20 Dec 2013, 16:00 to 17:00
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
Any two-way finite state automaton is equivalent to some one-way finite state automaton. This well-known result, shown by Rabin and Scott and independently by Shepherdson, states that two-way finite state automata (even non-deterministic) characterize the class of regular languages. 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 particular deterministic two-way transducers capture exactly the class of MSO-transductions of finite strings. In this talk, we address the following definability problem: given a function defined by a two-way finite state transducer, is it definable by a one-way finite state transducer? By extending 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.
| Speaker: | Emmanuel Filiot (Departement d'Informatique Universite Libre de Bruxelles Campus de la Plaine CP 212 - 1050 Bruxelles Belgium) |
| Organiser: | Paritosh K Pandya |
| Date: | Friday, 20 Dec 2013, 16:00 to 17:00 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
Any two-way finite state automaton is equivalent to some one-way finite state automaton. This well-known result, shown by Rabin and Scott and independently by Shepherdson, states that two-way finite state automata (even non-deterministic) characterize the class of regular languages. 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 particular deterministic two-way transducers capture exactly the class of MSO-transductions of finite strings. In this talk, we address the following definability problem: given a function defined by a two-way finite state transducer, is it definable by a one-way finite state transducer? By extending 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.