一句话：证明双向词转换器的单向可定义性可判定，给出双指数空间算法，并可构造等价单向转换器。
双向词转换器（等价于流式转换器或 MSO 转换）所实现的函数转换，是词到词“正则映射”的标准模型。此前已知可判定一个这样的转换能否由单向转换器实现，但算法复杂度为非初等。本文给出一种不同风格的判定算法，其空间复杂度为双指数；在 sweeping 转换器的特殊情形下，复杂度少一个指数。论文还进一步说明，当等价单向转换器存在时，如何构造它：一般双向情形需三指数时间，sweeping 情形需双指数时间，并证明 sweeping 情形下的构造是最优的。
Functional transductions realized by two-way transducers (or, equally, by streaming transducers or MSO transductions) are the natural and standard notion of "regular" mappings from words to words. It was shown in 2013 that it is decidable if such a transduction can be implemented by some one-way transducer, but the given algorithm has non-elementary complexity. We provide an algorithm of different flavor solving the above question, that has doubly exponential space complexity. In the special case of sweeping transducers the complexity is one exponential less. We also show how to construct an equivalent one-way transducer, whenever it exists, in doubly or triply exponential time, again depending on whether the input transducer is sweeping or two-way. In the sweeping case our construction is shown to be optimal.
@article{paperbot350,
title = {One-way definability of two-way word transducers},
author = {Félix Baschenis and Olivier Gauwin and Anca Muscholl and Gabriele Puppis},
journal = {Logical Methods in Computer Science},
volume = {Volume 14, Issue 4},
year = {2018},
doi = {10.23638/lmcs-14(4:22)2018}
}