TY  - INPR
A1  - Kallmeyer, Laura
A1  - Parmentier, Yannick
A2  - Martín-Vide, Carlos
A2  - Otto, Friedrich
A2  - Fernau, Henning
T1  - On the relation between multicomponent tree adjoining grammars with tree tuples (TT-MCTAG) and range concatenation grammars (RCG)
N2  - This paper investigates the relation between TT-MCTAG, a formalism used in computational linguistics, and RCG. RCGs are known to describe exactly the class PTIME; simple RCG even have been shown to be equivalent to linear context-free rewriting systems, i.e., to be mildly context-sensitive. TT-MCTAG has been proposed to model free word order languages. In general, it is NP-complete. In this paper, we will put an additional limitation on the derivations licensed in TT-MCTAG. We show that TT-MCTAG with this additional limitation can be transformed into equivalent simple RCGs. This result is interesting for theoretical reasons (since it shows that TT-MCTAG in this limited form is mildly context-sensitive) and, furthermore, even for practical reasons: We use the proposed transformation from TT-MCTAG to RCG in an actual parser that we have implemented.
KW  - Deutsch
KW  - Syntaktische Analyse
KW  - Multicomponent Tree Adjoining Grammar
KW  - Range Concatenation Grammar
KW  - Automatentheorie
KW  - Kongress
KW  - Tarragona <2008>
KW  - Formale Sprache
KW  - Online-Publikation
Y1  - 2008
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/9856
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-1110362
SN  - 978-3-540-88281-7
SN  - 978-3-540-88282-4
N1  - Erschienen in: Carlos Martín-Vide ; Friedrich Otto ; Henning Fernau (Hrsg.): International Conference on Language and Automata Theory and Applications, Berlin ; Heidelberg ; New York, NY : Springer, 2008, Lecture notes in computer science ; 5196, S. 263-274, ISBN: 978-3-540-88281-7, ISBN: 978-3-540-88282-4, doi:10.1007/978-3-540-88282-4_25
ER  -