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.
Metadaten
Author:Laura KallmeyerORCiDGND, Yannick Parmentier
URN:urn:nbn:de:hebis:30-1110362
DOI:https://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
GND Keyword:Deutsch; Syntaktische Analyse; Automatentheorie; Kongress; Tarragona <2008>; Formale Sprache; Online-Publikation
Page Number: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:keine Angabe Fachbereich / Extern
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
4 Sprache / 40 Sprache / 400 Sprache
Sammlungen:Linguistik
Linguistik-Klassifikation:Linguistik-Klassifikation: Computerlinguistik / Computational linguistics
Licence (German):License LogoDeutsches Urheberrecht