论文标题
无限有序单词的流式转换
Streaming Transformations of Infinite Ordered-Data Words
论文作者
论文摘要
在本文中，我们定义了流媒体寄存器换能器（SRT），这是一种单向，字母到字母的，转换的机器模型，用于无限数据域形成线性组的无限数据单词的转换。与现有数据单词传感器相比，SRT能够对寄存器执行两个额外的操作：基于线性订单的比较和一个加法更新。我们考虑SRT和SRT的几个子类可以定义的转换。我们研究这些语言的表现力和几个决策问题。我们的主要结果包括：1）SRT在联合和交点下关闭，并且在组成下也关闭了无添加的SRT； 2）可以在Monadic二阶（MSO）逻辑中定义SRT可定义转换，但与一阶（FO）可定义转换不可媲美； 3）功能问题对于无添加的SRT是可决定的，对于确定性无添加的SRT，反应性问题和包含问题是可决定的，但是对于SRT来说，这些问题通常都无法决定。
In this paper, we define streaming register transducer (SRT), a one-way, letter-to-letter, transductional machine model for transformations of infinite data words whose data domain forms a linear group. Comparing with existing data word transducers, SRT are able to perform two extra operations on the registers: a linear-order-based comparison and an additive update. We consider the transformations that can be defined by SRT and several subclasses of SRT. We investigate the expressiveness of these languages and several decision problems. Our main results include: 1) SRT are closed under union and intersection, and add-free SRT are also closed under composition; 2) SRT-definable transformations can be defined in monadic second-order (MSO) logic, but are not comparable with first-order (FO) definable transformations; 3) the functionality problem is decidable for add-free SRT, the reactivity problem and inclusion problem are decidable for deterministic add-free SRT, but none of these problems is decidable in general for SRT.
