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 linea
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.
show moreshow less

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Laura Kallmeyer, Yannick Parmentier
URN:urn:nbn:de:hebis:30-1110362
Document Type:Article
Language:English
Date of Publication (online):2008/10/20
Year of first Publication:2008
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2008/10/20
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
Linguistic-Classification:Linguistik-Klassifikation: Computerlinguistik / Computational linguistics
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $