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 |
SCOPUSTM
Citations
18
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
20
checked on Sep 29, 2024
Page view(s)
86
checked on Sep 7, 2022
Download(s)
216
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.