Skip navigation
Full metadata record
DC FieldValueLanguage
dc.contributor.authorChampollion, Lucas-
dc.date.accessioned2012-12-26T17:24:49Z-
dc.date.available2012-12-26T17:24:49Z-
dc.date.issued2011-07-08-
dc.identifier.citationChampollion, Lucas. "Lexicalized Non-Local MCTAG with Dominance Links is NP-Complete." Journal of Logic, Language and Information 20.3 (2011): 343-359.en
dc.identifier.issn1572-9583-
dc.identifier.issn0925-8531-
dc.identifier.other10.1007/s10849-011-9133-1-
dc.identifier.urilink.springer.com/article/10.1007%2Fs10849-011-9133-1-
dc.identifier.urihttp://hdl.handle.net/2451/31681-
dc.description.abstractAn 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.en
dc.language.isoen_USen
dc.publisherSpringeren
dc.subjectTree Adjoining Grammar MCTAG NP-complete Dominance links Lexicalization Mildly context-sensitive Scramblingen
dc.titleLexicalized non-local MCTAG with dominance links is NP-completeen
dc.typeArticleen
Appears in Collections:Lucas Champollion's publications

Files in This Item:
File Description SizeFormat 
mctag_npcomplete_jolli.pdfLexicalized non-local MCTAG with dominance links is NP-complete115.99 kBAdobe PDFView/Open


Items in FDA are protected by copyright, with all rights reserved, unless otherwise indicated.