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 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.
Verfasserangaben: | Laura KallmeyerORCiDGND, Giorgio Satta |
---|---|
URN: | urn:nbn:de:hebis:30-1135111 |
URL: | http://www.sfs.uni-tuebingen.de/~lk/papers/KallmSatta-ACL09.pdf |
ISBN: | 978-1-932432-46-6 |
Dokumentart: | Preprint |
Sprache: | Englisch |
Jahr der Fertigstellung: | 2009 |
Jahr der Erstveröffentlichung: | 2009 |
Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Datum der Freischaltung: | 27.10.2009 |
Freies Schlagwort / Tag: | Multicomponent Tree Adjoining Grammar |
GND-Schlagwort: | Syntaktische Analyse |
Seitenzahl: | 9 |
Bemerkung: | Erschienen in: Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, Volume 2, Stroudsburg, PA : Association for Computational Linguistics, 2009, S. 994–1002, ISBN: 978-1-932432-46-6 |
Quelle: | http://www.sfs.uni-tuebingen.de/~lk/papers/KallmSatta-ACL09.pdf ; (in:) Proceedings of ACL. - Singapore, 2009 |
HeBIS-PPN: | 219870004 |
Institute: | keine Angabe Fachbereich / Extern |
DDC-Klassifikation: | 4 Sprache / 40 Sprache / 400 Sprache |
Sammlungen: | Linguistik |
Linguistik-Klassifikation: | Linguistik-Klassifikation: Computerlinguistik / Computational linguistics |
Lizenz (Deutsch): | Deutsches Urheberrecht |