Compositions of extended top-down tree transducers
Compositions of extended top-down tree transducers
复制标题
扩展的自顶向下树传感器的组合
DOI：
10.1016/j.ic.2008.03.019
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Maletti
中科院分区：
文献类型：
--
作者：
A. Maletti
不幸的是，由具有常规前瞻的线性扩展自上而下树传感器计算的变换类在组合下并不封闭。结果表明，由某些线性双态计算的变换类别与前面提到的类别一致。此外，还证明了每个具有规则前瞻的线性无ε扩展自上而下树传感器都可以通过线性多自下而上树传感器来实现。由后一设备计算的变换类被示出在合成下是封闭的，并且被包括在由自上而下的树换能器与其自身计算的变换类的合成中。更准确地说，它构成了由有限复制自顶向下树传感器计算的变换类的组合闭包。
Unfortunately, the class of transformations computed by linear extended top-down tree transducers with regular look-ahead is not closed under composition. It is shown that the class of transformations computed by certain linear bimorphisms coincides with the previously mentioned class. Moreover, it is demonstrated that every linear epsilon-free extended top-down tree transducer with regular look-ahead can be implemented by a linear multi bottom-up tree transducer. The class of transformations computed by the latter device is shown to be closed under composition, and to be included in the composition of the class of transformations computed by top-down tree transducers with itself. More precisely, it constitutes the composition closure of the class of transformations computed by finite-copying top-down tree transducers.