Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-20T06:22:56.147Z Has data issue: false hasContentIssue false
  • English
  • Français

Syntactic composition of top-down tree transducers is short cut fusion

Published online by Cambridge University Press:  17 March 2004

CLAUS JÜRGENSEN  and
HEIKO VOGLER
CLAUS JÜRGENSEN
Affiliation:
Faculty of Computer Science, Dresden University of Technology, Germany E-mail: [email protected]
HEIKO VOGLER
Affiliation:
Faculty of Computer Science, Dresden University of Technology, Germany E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 14 , Issue 2 , April 2004 , pp. 215 - 282
Copyright
2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)