XML Type Checking for Macro Tree Transducers with Holes
XML Type Checking for Macro Tree Transducers with Holes
复制标题
带孔宏树传感器的 XML 类型检查
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Keisuke Nakano
中科院分区：
文献类型：
--
作者：
S. Maneth;Keisuke Nakano
宏森林传感器 (mfts) 将宏树传感器 (mtts) 从排序树扩展到未排序树。 Mfts 比 mtts（对二叉树编码进行操作）更强大，因为它们支持输出树的序列串联作为内置操作。令人惊讶的是，对于固定输出类型，mfts 的逆类型推断可以在与 mtts 相同的复杂度内完成。反向类型推断用于对 XML 转换进行精确类型检查的算法。带孔宏树传感器（hmtt）是本文提出的一个新概念。它将 mfts 的序列串联推广为任意树串联。 Hmtts 严格来说比 mfts 更强大，就像 mfts 比 mtts 更强大一样。同样，令人惊讶的是，逆向类型推断仍然保持在与 mfts 相同的复杂度范围内。 Hmtts 是 mtts 的自然而强大的扩展：任何 hmtt 都可以通过 mtt 模拟，然后是所谓的“YIELD 映射”，相反，具有 YIELD 映射的 mtt 的任何组合都可以通过 hmtt 模拟。这一特征意味着总确定性 mtts 的二重组合的逆类型推理可以在 2 指数时间内完成（高度为 2 的指数塔），而之前最知名的算法需要 3 指数时间。
Macro forest transducers (mfts) extend macro tree transducers (mtts) from ranked to unranked trees. Mfts are more powerful than mtts (operating on binary tree encodings) because they support sequence concatenation of output trees as build-in operation. Surprisingly, inverse type inference for mfts, for a fixed output type, can be done within the same complexity as for mtts. Inverse type inference is used in algorithms for exact type checking of XML transformations. The macro tree transducer with holes (hmtt) is a new concept that is introduced in this paper. It generalizes sequence concatenation of mfts to arbitrary tree concatenation. Hmtts are strictly more powerful than mfts, in a similar way as mfts are more powerful than mtts. Again, it comes as a surprise that inverse type inference remains within the same complexity bound as for mfts. Hmtts are a natural and robust extension of mtts: any hmtt can be simulated by an mtt, followed by a so called “YIELD-mapping”, and, conversely, any composition of an mtt with a YIELD-mapping can be simulated by an hmtt. This characterization implies that inverse type inference for two-fold compositions of total deterministic mtts can be done in 2-exponential time (a tower of exponents of height 2), while the previously best known algorithm takes 3-exponential time.