A polynomial-time parsing algorithm for TT-MCTAG

This paper investigates the class of Tree-Tuple MCTAG with Shared Nodes, TT-MCTAG for short, an extension of Tree Adjoining Grammars that has been proposed for natural language processing, in particular for dealing with 
This paper investigates the class of Tree-Tuple MCTAG with Shared Nodes, TT-MCTAG for short, an extension of Tree Adjoining Grammars that has been proposed for natural language processing, in particular for dealing with discontinuities and word order variation in languages such as German. It has been shown that the universal recognition problem for this formalism is NP-hard, but so far it was not known whether the class of languages generated by TT-MCTAG is included in PTIME. We provide a positive answer to this question, using a new characterization of TT-MCTAG.
show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Laura Kallmeyer, Giorgio Satta
URN:urn:nbn:de:hebis:30-1135111
Document Type:Article
Language:English
Date of Publication (online):2009/10/27
Year of first Publication:2009
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2009/10/27
Tag:Multicomponent Tree Adjoining Grammar
SWD-Keyword:Syntaktische Analyse
Source:http://www.sfs.uni-tuebingen.de/~lk/papers/KallmSatta-ACL09.pdf ; (in:) Proceedings of ACL. - Singapore, 2009
HeBIS PPN:219870004
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 $