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.
Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:14-qucosa-224756 |
Date | 29 May 2017 |
Creators | Teichmann, Markus |
Contributors | Technische Universität Dresden, Fakultät Informatik, Prof. Dr.‑Ing. habil. Dr. h.c./Univ. Szeged Heiko Vogler, Prof. Dr.‑Ing. habil. Dr. h.c./Univ. Szeged Heiko Vogler, Prof. Dr. Frank Drewes |
Publisher | Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden |
Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
Language | English |
Detected Language | English |
Type | doc-type:doctoralThesis |
Format | application/pdf |
Page generated in 0.018 seconds