Syntactic composition of top-down tree transducers is short cut fusion
Syntactic composition of top-down tree transducers is short cut fusion
复制标题
自顶向下树变换器的句法组成是捷径融合
DOI：
10.1017/s0960129503004109
复制
发表时间：
2004
影响因子：
0.5
通讯作者：
H. Vogler
中科院分区：
文献类型：
--
作者：
Claus Jürgensen;H. Vogler
我们比较了两种森林砍伐技术：范式论中形式化的短路融合和树木换能器的句法组成。前者强烈依赖于类型，并使用参数性质或自由定理，而后者根本不使用类型，并允许更通用的组合。我们引入了范畴换能器的概念，它是一个变形论的推广，并给出了相应的融合结果，它是“酸雨定理”的推广。我们证明了以下主要定理：(I)所有范畴转移器的类别建立了一个合成是融合的范畴；(Ii)范畴转移器的语义是一个函子。(3)自上而下分类换能器的子类是一个子类。(4)自上而下树形结构的句法组合相当于自上而下范畴结构的融合。
We compare two deforestation techniques: short cut fusion formalised in category theory and the syntactic composition of tree transducers. The former strongly depends on types and uses the parametricity property or free theorem, whereas the latter makes no use of types at all and allows more general compositions. We introduce the notion of a categorical transducer, which is a generalisation of a catamorphism, and show a corresponding fusion result, which is a generalisation of the ‘acid rain theorem’. We prove the following main theorems: (i) The class of all categorical transducers builds a category where composition is fusion; (ii) The semantics of categorical transducers is a functor. (iii) The subclass of top-down categorical transducers is a subcategory. (iv) Syntactic composition of top-down tree transducers is equivalent to the fusion of top-down categorical transducers.