David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Logic, Language and Information 20 (3):343-359 (2011)
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
Aravind K. Joshi (2004). Starting with Complex Primitives Pays Off: Complicate Locally, Simplify Globally. Cognitive Science 28 (5):637-668.
Citations of this work BETA
No citations found.
Similar books and articles
Stephan Kepser & Jim Rogers (2011). The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-Free Tree Grammars. Journal of Logic, Language and Information 20 (3):361-384.
Makoto Kanazawa (2010). Second-Order Abstract Categorial Grammars as Hyperedge Replacement Grammars. Journal of Logic, Language and Information 19 (2):137-161.
Paul Larson (1999). An Smax Variation for One Souslin Tree. Journal of Symbolic Logic 64 (1):81 - 98.
Yde Venema (1996). Tree Models and (Labeled) Categorial Grammar. Journal of Logic, Language and Information 5 (3-4):253-277.
Katherine Forbes, Eleni Miltsakaki, Rashmi Prasad, Anoop Sarkar, Aravind Joshi & Bonnie Webber (2003). D-LTAG System: Discourse Parsing with a Lexicalized Tree-Adjoining Grammar. [REVIEW] Journal of Logic, Language and Information 12 (3):261-279.
Toshiyasu Arai (1998). Variations on a Theme by Weiermann. Journal of Symbolic Logic 63 (3):897-925.
Joel D. Velasco (2010). Species, Genes, and the Tree of Life. British Journal for the Philosophy of Science 61 (3):599-619.
Alessandro Andretta (1991). Building Iteration Trees. Journal of Symbolic Logic 56 (4):1369-1384.
Yael Sygal & Shuly Wintner (2009). Associative Grammar Combination Operators for Tree-Based Grammars. Journal of Logic, Language and Information 18 (3):293-316.
Added to index2011-07-16
Total downloads2 ( #347,873 of 1,100,746 )
Recent downloads (6 months)1 ( #289,565 of 1,100,746 )
How can I increase my downloads?