The time complexity of typechecking tree-walking tree transducers
The time complexity of typechecking tree-walking tree transducers
复制标题
树行走树传感器型式检查的时间复杂度
DOI：
10.1007/s00236-008-0087-y
复制
发表时间：
2009
期刊：
影响因子：
0.6
通讯作者：
J. Engelfriet
中科院分区：
文献类型：
--
作者：
J. Engelfriet
行树传感器可在双指数时间内完成检型。更一般地，k树行走的树换能器的组成可以在(k+1)倍的指数时间内进行类型检查。因此，k-鹅卵树换能器可以在(k+2)倍的指数时间内进行类型检查，它构成了XML转换和查询的模型。这一结果对已排名和未排名的树木都适用。
Tree-walking tree transducers can be typechecked in double exponential time. More generally, compositions ofktree-walking tree transducers can be typechecked in (k+ 1)-fold exponential time. Consequentlyk-pebble tree transducers, which form a model of XML transformations and XML queries, can be typechecked in (k+ 2)-fold exponential time. The results hold for both ranked and unranked trees.