Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/15354
Title: | From Two-Way to One-Way Finite State Transducers | Authors: | Filiot, Emmanuel Gauwin, Olivier Reynier, Pierre-Alain SERVAIS, Frederic |
Issue Date: | 2013 | Publisher: | IEEE | Source: | 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science, p. 468-477 | 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 paper, 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. | Keywords: | Formal Languages, Transducer, MSO | Document URI: | http://hdl.handle.net/1942/15354 | ISBN: | 9781479904136 | DOI: | 10.1109/LICS.2013.53 | Category: | C2 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
5020a468.pdf | Published version | 285.39 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.