Undecidable Properties of Deterministic Top-Down Tree Transducers
Undecidable Properties of Deterministic Top-Down Tree Transducers
复制标题
确定性自顶向下树传感器的不可判定属性
DOI：
10.1016/0304-3975(94)90241-0
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Zoltán Fülöp
中科院分区：
文献类型：
--
作者：
Zoltán Fülöp
考虑有关确定性自上而下树传感器范围的可判定性问题。结果表明，对于任意两个确定性、不可删除和有限复制自顶向下树传感器的范围L1和L2，以下九个问题是不可判定的：L1∩L2是否为空（无限，可识别）？ L1 的补集是空的（无穷大，可识别）吗？ L1可以识别吗？ IsL1=L2(L1⊆L2)？确定性自顶向下树变换器是一种特殊的终止和汇合术语重写系统。因此，它的范围是从可识别的树语言（即从它的域）导出的不可约元素的集合。与上述九个问题相对应的问题被认为对于终止和汇合术语重写系统来说也是不可判定的。例如，“IsL1recognible?”的不可判定性对应的结果。如下。对于任意终止且汇合的术语重写系统R和可识别的树语言L，关于可从L导出的不可约元素集是否可识别是不可判定的。
Decidability questions concerning ranges of deterministic top-down tree transducers are considered. It is shown that the following nine problems are undecidable, for rangesL1andL2of arbitrary two deterministic, nondeleting and finite copying top-down tree transducers: IsL1∩L2empty (infinite, recognizable)? Is the complement ofL1empty (infinite, recognizable)? IsL1recognizable? IsL1=L2(L1⊆L2)?A deterministic top-down tree transducer is a special terminating and confluent term rewriting system. Hence, its range is the set of irreducible elements derivable from a recognizable tree language, namely from its domain. The questions corresponding to the above nine ones are considered and shown to be undecidable for terminating and confluent term rewriting systems as well. For example, the result corresponding to the undecidability of “IsL1recognizable?” is as follows. It is undecidable, for an arbitrary terminating and confluent term rewriting systemRand a recognizable tree languageL, whether the set of elements irreducible with respect toRderivable fromLis recognizable or not.