On the relation between multicomponent tree adjoining grammars with tree tuples (TT-MCTAG) and range concatenation grammars (RCG)
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.
Download full text files
Export metadata
Additional Services
| Author: | Laura Kallmeyer, Yannick Parmentier |
|---|---|
| URN: | urn:nbn:de:hebis:30-1110362 |
| Document Type: | Article |
| Language: | English |
| Date of Publication (online): | 20.10.2008 |
| Year of first Publication: | 2008 |
| Publishing Institution: | Univ.-Bibliothek Frankfurt am Main |
| Tag: | Multicomponent Tree Adjoining Grammar ; Range Concatenation Grammar |
| SWD-Keyword: | Deutsch ; Syntaktische Analyse |
| Source: | http://www.springerlink.com/content/0k3414u71l15r911/fulltext.pdf ; Language and Automata Theory and Applications. Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers, Lecture Notes in Computer Science (Berlin 2 |
| HeBIS PPN: | 206714637 |
| Dewey Decimal Classification: | 400 Sprache |
| Sammlungen: | Linguistik |
| Linguistik-Klassifikation: | Linguistik-Klassifikation: Computerlinguistik / Computational linguistics |
| Licence (German): |  Veröffentlichungsvertrag für Publikationen ohne Print on Demand |
