文章基本信息

标题：One-way definability of two-way word transducers
本地全文：下载
作者：Puppis, Gabriele ; Muscholl, Anca ; Gauwin, Olivier 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2018
卷号：14
期号：4
DOI：10.23638/LMCS-14(4:22)2018
语种：English
出版社：Technical University of Braunschweig
摘要：Functional transductions realized by two-way transducers (or, equally, bystreaming transducers or MSO transductions) are the natural and standard notionof "regular" mappings from words to words. It was shown in 2013 that it isdecidable if such a transduction can be implemented by some one-way transducer,but the given algorithm has non-elementary complexity. We provide an algorithmof different flavor solving the above question, that has doubly exponentialspace complexity. In the special case of sweeping transducers the complexity isone exponential less. We also show how to construct an equivalent one-waytransducer, whenever it exists, in doubly or triply exponential time, againdepending on whether the input transducer is sweeping or two-way. In thesweeping case our construction is shown to be optimal.
关键词：Computer Science - Formal Languages and Automata Theory;Computer Science - Logic in Computer Science