Skip to main content

List of Theses

For advanced search options you can also view this in the Forschungsinformationssystem of the TU Dresden.

Expressing Context-Free Tree Languages by Regular Tree Grammars
Art der Abschlussarbeit
  • Teichmann, Markus
  • Prof. Dr.-Ing. habil. Heiko Vogler
In this thesis, three methods are investigated to express context-free tree languages by regular tree grammars. The first method is a characterization. We show restrictions to context-free tree grammars such that, for each restricted context-free tree grammar, a regular tree grammar can be constructed that induces the same tree language. The other two methods are approximations. An arbitrary context-free tree language can be approximated by a regular tree grammar with a restricted pushdown storage. Furthermore, we approximate weighted context-free tree languages, induced by weighted linear nondeleting context-free tree grammars, by showing how to approximate optimal weights for weighted regular tree grammars.
tree language, context-free, regular, formal grammar, weighted grammar, weighted tree language, approximation, training
Last modified: 2020-10-26 10:29am