{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T15:22:12Z","timestamp":1725895332244},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540882817"},{"type":"electronic","value":"9783540882824"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-88282-4_38","type":"book-chapter","created":{"date-parts":[[2008,9,24]],"date-time":"2008-09-24T07:46:38Z","timestamp":1222242398000},"page":"421-432","source":"Crossref","is-referenced-by-count":1,"title":["Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NP-Hard"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Perekrestenko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"38_CR1","unstructured":"Champollion, L.: Lexicalized non-local MCTAG with dominance links is NP-complete. In: Penn, G., Stabler, E. (eds.) Proceedings of Mathematics of Language 10. CSLI On-Line Publications UCLA (2007)"},{"key":"38_CR2","volume-title":"The Minimalist Program","author":"N. Chomsky","year":"1995","unstructured":"Chomsky, N.: The Minimalist Program. MIT Press, Cambridge (1995)"},{"key":"38_CR3","first-page":"1","volume-title":"Ken Hale: A Life in Language","author":"N. Chomsky","year":"2001","unstructured":"Chomsky, N.: Derivation by phase. In: Kenstowicz, M. (ed.) Ken Hale: A Life in Language, pp. 1\u201352. MIT Press, Cambridge (2001)"},{"key":"38_CR4","series-title":"Lecture Notes in Computer Science","volume-title":"LACL 2001","year":"2001","unstructured":"de Groote, P., Morrill, G., Retor\u00e9, C. (eds.): LACL 2001. LNCS, vol.\u00a02099. Springer, Heidelberg (2001)"},{"key":"38_CR5","unstructured":"Frey, W., G\u00e4rtner, H.: On the treatment of scrambling and adjunction in Minimalist Grammars. In: J\u00e4ger, G., Monachesi, P., Penn, G., Wintner, S. (eds.) Proceedings of the 7th Conference on Formal Grammar, pp. 41\u201352 (2002)"},{"key":"38_CR6","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1515\/9783110207552.161","volume-title":"Interfaces + Recursion = Language? Chomsky\u2019s Minimalism and the View from Syntax and Semantics","author":"H. G\u00e4rtner","year":"2007","unstructured":"G\u00e4rtner, H., Michaelis, J.: Some remarks on locality conditions and Minimalist Grammars. In: G\u00e4rtner, H., Sauerland, U. (eds.) Interfaces + Recursion = Language? Chomsky\u2019s Minimalism and the View from Syntax and Semantics, pp. 161\u2013195. Walter de Gruyter, Berlin (2007)"},{"key":"38_CR7","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/3-540-48199-0_12","volume-title":"Logical Aspects of Computational Linguistics","author":"H. Harkema","year":"2001","unstructured":"Harkema, H.: A characterization of Minimalist languages. In: de Groote, P., Morrill, G., Retor\u00e9, C. (eds.) LACL 2001. LNCS (LNAI), vol.\u00a02099, pp. 193\u2013211. Springer, Heidelberg (2001)"},{"key":"38_CR8","unstructured":"J\u00e4ger, G., Monachesi, P., Penn, G., Wintner, S. (eds.): FG-MOL 2005: Proceedings of the 10th conference on Formal Grammar and the 9th Meeting on Mathematics of Language, Edinburgh, Scotland (2005)"},{"key":"38_CR9","unstructured":"Kobele, G., Michaelis, J.: Two type 0-variants of Minimalist Grammars. In: J\u00e4ger, et al. (eds.) [8]"},{"key":"38_CR10","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/3-540-45738-0_11","volume-title":"Logical Aspects of Computational Linguistics","author":"J. Michaelis","year":"2001","unstructured":"Michaelis, J.: Derivational Minimalism is mildly context-sensitive. In: Moortgat, M. (ed.) LACL 1998. LNCS (LNAI), vol.\u00a02014, pp. 179\u2013198. Springer, Heidelberg (2001)"},{"key":"38_CR11","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/3-540-48199-0_14","volume-title":"Logical Aspects of Computational Linguistics","author":"J. Michaelis","year":"2001","unstructured":"Michaelis, J.: Transforming linear context-free rewriting systems into Minimalist Grammars. In: de Groote, P., Morrill, G., Retor\u00e9, C. (eds.) LACL 2001. LNCS (LNAI), vol.\u00a02099, pp. 228\u2013244. Springer, Heidelberg (2001)"},{"key":"38_CR12","unstructured":"Michaelis, J.: An additional observation on strict derivational Minimalism. In: J\u00e4ger, et al. (eds.) [8]"},{"key":"38_CR13","unstructured":"Michaelis, J., G\u00e4rtner, H.: A note on countercyclicity and Minimalist Grammars. In: J\u00e4ger, G., Monachesi, P., Penn, G., Wintner, S. (eds.) Proceedings of the 8th Conference on Formal Grammar, pp. 103\u2013114 (2003)"},{"key":"38_CR14","unstructured":"Perekrestenko, A.: A note on the complexity of the recognition problem for the Minimalist Grammars with unbounded scrambling and barriers. In: Madrigal, V.D., de Ros Salamanca, F.E. (eds.) Actas del XXIII Congreso de la Sociedad Espa\u00f1ola para el Procesamiento del Lenguaje Natural, Seville, Spain. Revista de la SEPLN, vol.\u00a039, pp. 27\u201334 (2007)"},{"key":"38_CR15","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/BFb0052152","volume-title":"Logical Aspects of Computational Linguistics","author":"E. Stabler","year":"1997","unstructured":"Stabler, E.: Derivational Minimalism. In: Retor\u00e9, C. (ed.) LACL 1996. LNCS (LNAI), vol.\u00a01328, pp. 68\u201395. Springer, Heidelberg (1997)"},{"key":"38_CR16","unstructured":"S\u00f8gaard, A., Lichte, T., Maier, W.: On the complexity of linguistically motivated extensions of tree-adjoining grammar. In: RANLP 2007: Proceedings of the Conference on Recent Advances in Natural Language Processing, Borovets, Bulgaria (2007)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-88282-4_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,20]],"date-time":"2023-05-20T02:02:23Z","timestamp":1684548143000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-88282-4_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540882817","9783540882824"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-88282-4_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}