Streaming ranked-tree-to-string transducers
Streaming ranked-tree-to-string transducers
复制标题
流式排列的树到串传感器
DOI：
10.1016/j.tcs.2020.12.033
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Nakano Keisuke
中科院分区：
文献类型：
--
作者：
Takahashi Yuta;Asada Kazuyuki;Nakano Keisuke
Alur和D'Antoni引入了具有一次性限制（STT sur）的流树换能器，作为一种可分析、可执行和表达的模型，用于在单次传递中转换未排序的有序树。STT向量的等价问题是可确定的，因为它们的类与mso可定义的树变换类一样具有表达性。在本文中，我们提出了基于STT规则的流排序树到字符串换能器（SRTSTs）： SRTSTs从一次性使用限制中释放出来，而它们的输入和输出分别被限制为排序树和字符串。我们发现SRTSTs的表达性与具有规则前视（yDT R s）的确定性自顶向下树形换能器的表达性一致，其等效问题已知是可确定的。我们的证明是通过在两个方向上构造等效换能器来完成的。
Streaming tree transducers with single-use restriction (STT sur s) were introduced by Alur and D'Antoni as an analyzable, executable, and expressive model for transforming unranked ordered trees in a single pass. The equivalence problem of STT sur s is decidable because their class is as expressive as the class of MSO-definable tree transformations. In this paper, we present streaming ranked-tree-to-string transducers (SRTSTs), based on STT sur s: SRTSTs are released from the single-use restriction while their input and output are restricted to ranked trees and strings, respectively. We show that the expressiveness of SRTSTs coincides with that of deterministic top-down tree transducers with regular look-ahead (yDT R s), whose equivalence problem is known to be decidable. Our proof is done by constructing equivalent transducers in both directions.