论文标题
寄存器换能器是大理石传感器
Register transducers are marble transducers
论文作者
论文摘要
确定性的双向传感器定义了从单词到单词的常规函数类别。 Alur和Cerný引入了一个等效模型的传感器模型，其寄存器称为无拷贝流串换能器。在本文中，我们在这些机器上删除了“无复制”限制，并表明它们等于双向传感器，并在输入上删除了名为“大理石”的能力。我们将使用的大理石的最大数量与流弦传感器执行的寄存器副本量相关联。最后，我们表明与这些模型相关的类成员资格问题是可决定的。我们的结果可以用程序优化来解释，以实现简单的递归和迭代程序。
Deterministic two-way transducers define the class of regular functions from words to words. Alur and Cerný introduced an equivalent model of transducers with registers called copyless streaming string transducers. In this paper, we drop the "copyless" restriction on these machines and show that they are equivalent to two-way transducers enhanced with the ability to drop marks, named "marbles", on the input. We relate the maximal number of marbles used with the amount of register copies performed by the streaming string transducer. Finally, we show that the class membership problems associated with these models are decidable. Our results can be interpreted in terms of program optimization for simple recursive and iterative programs.
