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.0022 seconds