Bottom-up and top-down tree transformations— a comparison
Bottom-up and top-down tree transformations— a comparison
复制标题
自下而上和自上而下的树变换——比较
DOI：
--
复制
发表时间：
1975
期刊：
影响因子：
--
通讯作者：
J. Engelfriet
中科院分区：
文献类型：
--
作者：
J. Engelfriet
自上而下和自下而上的树传感器相对于它们的转换功率无与伦比。它们之间的区别主要是由他们使用复制和非确定性设施的不同顺序引起的。但是，可以定义某些独立于自上而下/自下而上的区别的简单树转换，从而使每个树的转换（自上而下或自下而上）可以分解为许多这些简单的转换。该分解结果用于给出有关自下而上树转化的组成结果的简单证明。引入了新的树转换模型，可以概括自上而下的树和自下而上的树换能器。
The top-down and bottom-up tree transducer are incomparable with respect to their transformation power. The difference between them is mainly caused by the different order in which they use the facilities of copying and nondeterminism. One can however define certain simple tree transformations, independent of the top-down/bottom-up distinction, such that each tree transformation, top-down or bottom-up, can be decomposed into a number of these simple transformations. This decomposition result is used to give simple proofs of composition results concerning bottom-up tree transformations.A new tree transformation model is introduced which generalizes both the top-down and the bottom-up tree transducer.