On Reversible Transducers
On Reversible Transducers
复制标题
关于可逆传感器
DOI：
10.4230/lipics.icalp.2017.113
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
N. Lhote
中科院分区：
文献类型：
--
作者：
L. Dartois;P. Fournier;Ismaël Jecker;N. Lhote
确定性双向传感器定义了常规函数的鲁棒类，除其他良好特性外，它在组合下是封闭的。然而，用于构成双向传感器的最著名的算法会导致输入大小呈双指数爆炸。在本文中，我们介绍了一类其组成具有多项式复杂性的换能器。它是一类可逆传感器，其计算步骤可以确定性地反转。虽然在单向设置中这一类的表现力不是很强，但我们证明任何双向传感器都可以通过单次指数爆炸实现可逆。因此，我们证明双向换能器的组成可以通过状态数量的单一指数爆炸来完成。关系的统一化是具有相同域并且包含在原始关系中的函数。我们的主要结果实际上表明，我们可以通过具有单次指数爆炸的可逆传感器来统一任何非确定性双向传感器，从而改进 de Souza 的已知结果，该结果具有四倍指数复杂度。作为一个附带结果，我们的构造还给出了从无复制流字符串传感器到双向传感器的二次变换，从而改善了指数先前的界限。
Deterministic two-way transducers define the robust class of regular functions which is, among other good properties, closed under composition. However, the best known algorithms for composing two-way transducers cause a double exponential blow-up in the size of the inputs. In this paper, we introduce a class of transducers for which the composition has polynomial complexity. It is the class of reversible transducers, for which the computation steps can be reversed determin-istically. While in the one-way setting this class is not very expressive, we prove that any two-way transducer can be made reversible through a single exponential blow-up. As a consequence, we prove that the composition of two-way transducers can be done with a single exponential blow-up in the number of states. A uniformization of a relation is a function with the same domain and which is included in the original relation. Our main result actually states that we can uniformize any non-deterministic two-way transducer by a reversible transducer with a single exponential blow-up, improving the known result by de Souza which has a quadruple exponential complexity. As a side result, our construction also gives a quadratic transformation from copyless streaming string transducers to two-way transducers, improving the exponential previous bound.