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 SizeFormat 
5020a468.pdfMain article285.39 kBAdobe PDFView/Open
Show full item record

SCOPUSTM   
Citations

18
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

16
checked on May 22, 2022

Page view(s)

72
checked on May 23, 2022

Download(s)

198
checked on May 23, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.