{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:22:58Z","timestamp":1775053378532,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":7,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540926863","type":"print"},{"value":"9783540926870","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-92687-0_26","type":"book-chapter","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T04:25:38Z","timestamp":1234239938000},"page":"380-394","source":"Crossref","is-referenced-by-count":14,"title":["Product-Free Lambek Calculus Is NP-Complete"],"prefix":"10.1007","author":[{"given":"Yury","family":"Savateev","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1002\/malq.19950410405","volume":"41","author":"E. Aarts","year":"1995","unstructured":"Aarts, E., Trautwein, K.: Non-associative Lambek categorial grammar in polynomial time. Mathematical logic Quarterly\u00a041, 476\u2013484 (1995)","journal-title":"Mathematical logic Quarterly"},{"issue":"4","key":"26_CR2","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1002\/malq.19850312402","volume":"31","author":"W. Buszkowski","year":"1985","unstructured":"Buszkowski, W.: The equivalence of unidirectional Lambek categorial grammars and context-free grammars. Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik\u00a031(4), 369\u2013384 (1985)","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"key":"26_CR3","series-title":"Lecture Notes in Computer Science","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, vol.\u00a01617, pp. 128\u2013139. Springer, Heidelberg (1999)"},{"issue":"3","key":"26_CR4","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(3), 154\u2013170 (1958)","journal-title":"American Mathematical Monthly"},{"issue":"1\u20133","key":"26_CR5","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.tcs.2006.03.018","volume":"357","author":"M. Pentus","year":"2006","unstructured":"Pentus, M.: Lambek calculus is NP-complete. Theoretical Computer Science\u00a0357(1\u20133), 186\u2013201 (2006)","journal-title":"Theoretical Computer Science"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Pentus, M.: Lambek grammars are context free. In: Proceedings of the 8th Annual IEEE Symposium on Logic in Computer Science, pp. 429\u2013433 (1993)","DOI":"10.1109\/LICS.1993.287565"},{"key":"26_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/978-3-540-79709-8_28","volume-title":"Computer Science \u2013 Theory and Applications","author":"Y. Savateev","year":"2008","unstructured":"Savateev, Y.: Lambek grammars with one division are decidable in polynomial time. In: Hirsch, E.A., et al. (eds.) Computer Science \u2013 Theory and Applications. LNCS, vol.\u00a05010, pp. 273\u2013282. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Logical Foundations of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92687-0_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T02:46:16Z","timestamp":1551753976000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92687-0_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540926863","9783540926870"],"references-count":7,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92687-0_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}