{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T23:41:28Z","timestamp":1725579688574},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642320231"},{"type":"electronic","value":"9783642320248"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32024-8_3","type":"book-chapter","created":{"date-parts":[[2012,7,14]],"date-time":"2012-07-14T03:58:00Z","timestamp":1342238280000},"page":"33-49","source":"Crossref","is-referenced-by-count":0,"title":["The Lambek-Grishin Calculus Is NP-Complete"],"prefix":"10.1007","author":[{"given":"Jeroen","family":"Bransen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/3-540-48754-9_14","volume-title":"Automated Reasoning with Analytic Tableaux and Related Methods","author":"P. Groote de","year":"1999","unstructured":"de Groote, P.: The Non-Associative Lambek Calculus with Product in Polynomial Time. In: Murray, N.V. (ed.) TABLEAUX 1999. LNCS (LNAI), vol.\u00a01617, pp. 128\u2013139. Springer, Heidelberg (1999)"},{"key":"3_CR2","unstructured":"Foret, A.: On the computation of joins for non associative Lambek categorial grammars. In: Proceedings of the 17th International Workshop on Unification (UNIF 2003), Valencia, Spain, June 8-9 (2003)"},{"key":"3_CR3","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"3","key":"3_CR4","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1093\/jigpal\/6.3.451","volume":"6","author":"R. Gor\u00e9","year":"1998","unstructured":"Gor\u00e9, R.: Substructural logics on display. Logic Jnl IGPL\u00a06(3), 451\u2013504 (1998)","journal-title":"Logic Jnl IGPL"},{"key":"3_CR5","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1075\/llsee.25.11kan","volume":"25","author":"M. Kandulski","year":"1988","unstructured":"Kandulski, M.: The non-associative Lambek calculus. Categorial Grammar, Linguistic and Literary Studies in Eastern Europe (LLSEE)\u00a025, 141\u2013151 (1988)","journal-title":"Categorial Grammar, Linguistic and Literary Studies in Eastern Europe (LLSEE)"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"154","DOI":"10.2307\/2310058","volume":"65","author":"J. Lambek","year":"1958","unstructured":"Lambek, J.: The Mathematics of Sentence Structure. American Mathematical Monthly\u00a065, 154\u2013170 (1958)","journal-title":"American Mathematical Monthly"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Lambek, J.: On the calculus of syntactic types. In: Structure of Language and Its Mathematical Aspects, pp. 166\u2013178 (1961)","DOI":"10.1090\/psapm\/012\/9972"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-642-20169-1_8","volume-title":"Formal Grammar","author":"M. Melissen","year":"2011","unstructured":"Melissen, M.: The Generative Capacity of the Lambek\u2013Grishin Calculus: A New Lower Bound. In: de Groote, P., Egg, M., Kallmeyer, L. (eds.) Formal Grammar. LNCS, vol.\u00a05591, pp. 118\u2013132. Springer, Heidelberg (2011)"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-540-73445-1_19","volume-title":"Logic, Language, Information and Computation","author":"M. Moortgat","year":"2007","unstructured":"Moortgat, M.: Symmetries in Natural Language Syntax and Semantics: The Lambek-Grishin Calculus. In: Leivant, D., de Queiroz, R. (eds.) WoLLIC 2007. LNCS, vol.\u00a04576, pp. 264\u2013284. Springer, Heidelberg (2007)"},{"issue":"6","key":"3_CR10","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/s10992-009-9118-6","volume":"38","author":"M. Moortgat","year":"2009","unstructured":"Moortgat, M.: Symmetric categorial grammar. Journal of Philosophical Logic\u00a038(6), 681\u2013710 (2009)","journal-title":"Journal of Philosophical Logic"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1109\/LICS.1993.287565","volume-title":"Proceedings of the 8th Annual IEEE Symposium on Logic in Computer Science","author":"M. Pentus","year":"1993","unstructured":"Pentus, M.: Lambek grammars are context free. In: Proceedings of the 8th Annual IEEE Symposium on Logic in Computer Science, pp. 429\u2013433. IEEE Computer Society Press, Los Alamitos (1993)"},{"key":"3_CR12","unstructured":"Pentus, M.: Lambek calculus is NP-complete. CUNY Ph.D. Program in Computer Science Technical Report TR\u20132003005. CUNY Graduate Center, New York (2003)"},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/978-3-540-92687-0_26","volume-title":"Logical Foundations of Computer Science","author":"Y. Savateev","year":"2008","unstructured":"Savateev, Y.: Product-Free Lambek Calculus Is NP-Complete. In: Artemov, S., Nerode, A. (eds.) LFCS 2009. LNCS, vol.\u00a05407, pp. 380\u2013394. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Formal Grammar"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32024-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,20]],"date-time":"2019-01-20T02:42:14Z","timestamp":1547952134000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32024-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642320231","9783642320248"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32024-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}