论文标题
从常规传感器表达式的有效构造可逆传感器
Efficient Construction of Reversible Transducers from Regular Transducer Expressions
论文作者
论文摘要
常规转换类别具有几种等效的特征，例如功能MSO转换，确定性的双向传感器，流弦换能器以及常规换能器表达式（RTE）。 对于算法应用程序，它对于将指定（在此，将RTE，机器）转换为换能器非常普遍且有用。在本文中，我们为相当于给定的RTE提供了有效的双向可逆传感器（2rft）。 2rfts是确定性和共同确定性的传感器类别（因此允许在线性时间\ wrt the Input Word中进行评估），并且组成仅具有多项式复杂性。 我们表明，对于完整的RTE，构造的2rft在表达式的大小上具有双重指数，而如果RTE不使用Hadamard产品或链式星，则构造的 2rft的大小在RTE的尺寸中。
The class of regular transformations has several equivalent characterizations such as functional MSO transductions, deterministic two-way transducers, streaming string transducers, as well as regular transducer expressions (RTE). For algorithmic applications, it is very common and useful to transform a specification, here, an RTE, to a machine, here, a transducer. In this paper, we give an efficient construction of a two-way reversible transducer (2RFT) equivalent to a given RTE. 2RFTs are a well behaved class of transducers which are deterministic and co-deterministic (hence allows evaluation in linear time \wrt the input word), and where composition has only polynomial complexity. We show that, for full RTE, the constructed 2RFT has size doubly exponential in the size of the expression, while, if the RTE does not use Hadamard product or chained-star, the constructed 2RFT has size exponential in the size of the RTE.
