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

Metadaten
Author:Laura Kallmeyer, Yannick Parmentier
URN:urn:nbn:de:hebis:30-1110362
DOI:http://dx.doi.org/10.1007/978-3-540-88282-4_25
ISBN:978-3-540-88281-7
ISBN:978-3-540-88282-4
Editor:Carlos Martín-Vide, Friedrich Otto, Henning Fernau
Document Type:Preprint
Language:English
Year of Completion:2008
Year of first Publication:2008
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2008/10/20
Tag:Multicomponent Tree Adjoining Grammar ; Range Concatenation Grammar
SWD-Keyword:Automatentheorie; Deutsch ; Formale Sprache; Kongress; Online-Publikation; Syntaktische Analyse; Tarragona <2008>
Pagenumber:12
Note:
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
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
Institutes:Extern
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
400 Sprache
Sammlungen:Linguistik
Linguistic-Classification:Linguistik-Klassifikation: Computerlinguistik / Computational linguistics
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $