Hauptregion der Seite anspringen

Liste der Abschlussarbeiten

Für erweiterte Suchoptionen können Sie diese Inhalte auch im Forschungsinformationssystem anzeigen lassen.

Categorical semantics and composition of tree transducers
Art der Abschlussarbeit
Dissertation
Autoren
  • Jürgensen, Claus
Betreuer
  • Prof. Dr.-Ing. habil. Heiko Vogler
Abstract
In this thesis we see two new approaches to compose tree transducers and more general to fuse functional programs. The first abroach is based on initial algebras. We prove a new variant of the acid rain theorem for mutually recursive functions where the build function is substituted by a concrete functor. Moreover, we give a symmetric form (i.e. consumer and producer have the same syntactic form) of our new acid rain theorem where fusion is composition in a category and thus in particular associative. Applying this to compose top-down tree transducers yields the same result (on a syntactic level) as the classical top-down tree transducer composition. The second approach is based on free monads and monad transformers. In the same way as monoids are used in the theory of character string automata, we use monads in the theory of tree transducers. We generalize the notion of a tree transducer defining the monadic transducer, and we prove an according fusion theorem. Moreover, we prove that homomorphic monadic transducers are semantically equivalent. The latter makes it possible to compose syntactic classes of tree transducers (or particular functional programs) by simply composing endofunctors.
Zugeordnete Forschungsschwerpunkte
  • Gewichtete Baumautomaten und Baumübersetzer
Zugeordnete Forschungsprojekte
  • Formale Modelle zur syntaxgesteuerten Semantik
Schlagwörter
tree transducers
Berichtsjahr
2004
Stand: 26.10.2020 10:29 Uhr