- Authors
- Markus Teichmann
- title
- Expressing Context-Free Tree Languages by Regular Tree Grammars
- Please use the following URL when quoting:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa-224756
- Date of submission
- 28.10.2016
- Date of defense
- 12.04.2017
- Abstract (EN)
- 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.
- Keywords (DE)
- Baumsprache, kontextfrei, regulär, formale Sprache, gewichtete Grammatik, gewichtete Baumgrammatik, Approximation, Training
- Keywords (EN)
- tree language, context-free, regular, formal grammar, weighted grammar, weighted tree language, approximation, training
- Classification (DDC)
- 004
- Classification (RVK)
- ST 240
- Examiner
- Prof. Dr.‑Ing. habil. Dr. h.c./Univ. Szeged Heiko Vogler
- Prof. Dr. Frank Drewes
- Supervisor
- Prof. Dr.‑Ing. habil. Dr. h.c./Univ. Szeged Heiko Vogler
- Awarding institution
- Technische Universität Dresden, Dresden
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa-224756
- Qucosa date of publication
- 29.05.2017
- Document type
- doctoral_thesis
- Document language
- English
- licence