文章基本信息

标题：One-way Definability of Sweeping Transducer
本地全文：下载
作者：F{\'e}lix Baschenis ; Olivier Gauwin ; Anca Muscholl 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：45
页码：178-191
DOI：10.4230/LIPIcs.FSTTCS.2015.178
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Two-way finite-state transducers on words are strictly more expressive than one-way transducers. It has been shown recently how to decide if a two-way functional transducer has an equivalent one-way transducer, and the complexity of the algorithm is non-elementary. We propose an alternative and simpler characterization for sweeping functional transducers, namely, for transducers that can only reverse their head direction at the extremities of the input. Our algorithm works in 2EXPSPACE and, in the positive case, produces an equivalent one-way transducer of doubly exponential size. We also show that the bound on the size of the transducer is tight, and that the one-way definability problem is undecidable for (sweeping) non-functional transducers.
关键词：Regular word transductions; sweeping transducers; one-way definability