Determinacy and Subsumption of Single-Valued Bottom-Up Tree Transducers
Determinacy and Subsumption of Single-Valued Bottom-Up Tree Transducers
复制标题
DOI：
10.1587/transinf.2015fcp0015
复制
发表时间：
2016-03
期刊：
影响因子：
--
通讯作者：
Kenji Hashimoto;R. Sawada;Yasunori Ishihara;H. Seki;T. Fujiwara
中科院分区：
文献类型：
--
作者：
Kenji Hashimoto;R. Sawada;Yasunori Ishihara;H. Seki;T. Fujiwara
本文讨论了树型传感器的确定性和包容性的可判定性。对于两个树换能器T1和T2，如果T2的输出可以由T1的输出艾德，则T1确定T2，即存在部分函数f使得[[T2]] = f <$[[T1]]其中[[T1]]和[[T2]]分别是由T1和T2导出的树变换关系。此外，如果T 1确定T 2和部分函数f，使得[[ T 2 ]] = f <$[[ T 1 ]]可以由T 2所属的指定类别中的换能器定义，则T 1包含T 2。本文证明了单值线性扩展自底向上树变换器作为判定类和单值自底向上树变换器作为判定类的判定性是在coNEX-PTIME中。我们还表明，包容是在coNEXPITME为这些类，和一个自底向上的树转换器T3，使得[[T2]] = [[T3]][[T1]]可以构造，如果T1包含T2。
SUMMARY This paper discusses the decidability of determinacy and subsumption of tree transducers. For two tree transducers T 1 and T 2 , T 1 determines T 2 if the output of T 2 can be identified by the output of T 1 , that is, there is a partial function f such that [[ T 2 ]] = f ◦ [[ T 1 ]] where [[ T 1 ]] and [[ T 2 ]] are tree transformation relations induced by T 1 and T 2 , respectively. Also, T 1 subsumes T 2 if T 1 determines T 2 and the partial function f such that [[ T 2 ]] = f ◦ [[ T 1 ]] can be defined by a transducer in a designated class that T 2 belongs to. In this paper, we show that determinacy is in coNEX-PTIME for single-valued linear extended bottom-up tree transducers as the determiner class and single-valued bottom-up tree transducers as the deter-minee class. We also show that subsumption is in coNEXPITME for these classes, and a bottom-up tree transducer T 3 such that [[ T 2 ]] = [[ T 3 ]] ◦ [[ T 1 ]] can be constructed if T 1 subsumes T 2 .