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.
| Author: | Laura Kallmeyer, Giorgio Satta |
|---|---|
| URN: | urn:nbn:de:hebis:30-1135111 |
| Document Type: | Article |
| Language: | English |
| Date of Publication (online): | 27.10.2009 |
| Year of first Publication: | 2009 |
| Publishing Institution: | Univ.-Bibliothek Frankfurt am Main |
| 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 |
| Linguistik-Klassifikation: | Linguistik-Klassifikation: Computerlinguistik / Computational linguistics |
| Licence (German): |  Veröffentlichungsvertrag für Publikationen ohne Print on Demand |
