Lexicalized Non-Local MCTAG with Dominance Links is NP-Complete


Authors
Lucas Champollion
New York University
Abstract
An NP-hardness proof for non-local Multicomponent Tree Adjoining Grammar (MCTAG) by Rambow and Satta (1st International Workshop on Tree Adjoining Grammers 1992 ), based on Dahlhaus and Warmuth (in J Comput Syst Sci 33:456–472, 1986 ), is extended to some linguistically relevant restrictions of that formalism. It is found that there are NP-hard grammars among non-local MCTAGs even if any or all of the following restrictions are imposed: (i) lexicalization: every tree in the grammar contains a terminal; (ii) dominance links: every tree set contains at most two trees, and in every such tree set, there is a link between the foot node of one tree and the root node of the other tree, indicating that the former node must dominate the latter in the derived tree. This is the version of MCTAG proposed in Becker et al. (Proceedings of the 5th conference of the European chapter of the Association for Computational Linguistics 1991 ) to account for German long-distance scrambling. This result restricts the field of possible candidates for an extension of Tree Adjoining Grammar that would be both mildly context-sensitive and linguistically adequate
Keywords Tree Adjoining Grammar  MCTAG  NP-complete  Dominance links  Lexicalization  Mildly context-sensitive  Scrambling
Categories (categorize this paper)
DOI 10.1007/s10849-011-9133-1
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 47,395
Through your library

References found in this work BETA

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Second-Order Abstract Categorial Grammars as Hyperedge Replacement Grammars.Makoto Kanazawa - 2010 - Journal of Logic, Language and Information 19 (2):137-161.
Tree Models and (Labeled) Categorial Grammar.Yde Venema - 1996 - Journal of Logic, Language and Information 5 (3-4):253-277.
Variations on a Theme by Weiermann.Toshiyasu Arai - 1998 - Journal of Symbolic Logic 63 (3):897-925.
Species, Genes, and the Tree of Life.Joel Velasco - 2010 - British Journal for the Philosophy of Science 61 (3):599-619.
Building Iteration Trees.Alessandro Andretta - 1991 - Journal of Symbolic Logic 56 (4):1369-1384.
Associative Grammar Combination Operators for Tree-Based Grammars.Yael Sygal & Shuly Wintner - 2009 - Journal of Logic, Language and Information 18 (3):293-316.

Analytics

Added to PP index
2011-07-16

Total views
32 ( #291,545 of 2,291,335 )

Recent downloads (6 months)
5 ( #232,253 of 2,291,335 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature