{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T04:12:44Z","timestamp":1750824764647,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662557501"},{"type":"electronic","value":"9783662557518"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-662-55751-8_26","type":"book-chapter","created":{"date-parts":[[2017,8,15]],"date-time":"2017-08-15T15:32:49Z","timestamp":1502811169000},"page":"326-340","source":"Crossref","is-referenced-by-count":9,"title":["Undecidability of the Lambek Calculus with Subexponential and Bracket Modalities"],"prefix":"10.1007","author":[{"given":"Max","family":"Kanovich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stepan","family":"Kuznetsov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andre","family":"Scedrov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,16]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/malq.19900360103","volume":"36","author":"VM Abrusci","year":"1990","unstructured":"Abrusci, V.M.: A comparison between Lambek syntactic calculus and intuitionistic linear propositional logic. Zeitschr. f\u00fcr math. Log. Grundl. Math. (Math. Logic Q.) 36, 11\u201315 (1990)","journal-title":"Zeitschr. f\u00fcr math. Log. Grundl. Math. (Math. Logic Q.)"},{"key":"26_CR2","first-page":"1","volume":"1","author":"K Ajdukiewicz","year":"1935","unstructured":"Ajdukiewicz, K.: Die syntaktische Konnexit\u00e4t. Studia Philos. 1, 1\u201327 (1935)","journal-title":"Studia Philos."},{"key":"26_CR3","doi-asserted-by":"crossref","first-page":"47","DOI":"10.2307\/410452","volume":"29","author":"Y Bar-Hillel","year":"1953","unstructured":"Bar-Hillel, Y.: A quasi-arithmetical notation for syntactic description. Language 29, 47\u201358 (1953)","journal-title":"Language"},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Barry, G., Hepple, M., Leslie, N., Morrill, G.: Proof figures and structural operators for categorial grammar. In: Proceedings of 5th Conference of the European Chapter of ACL, Berlin (1991)","DOI":"10.3115\/977180.977215"},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"Bra\u00fcner, T., de Paiva, V.: Cut elimination for full intuitionstic linear logic. BRICS report RS-96-10, April 1996","DOI":"10.7146\/brics.v3i10.19973"},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BFb0028011","volume-title":"Computer Science Logic","author":"T Bra\u00fcner","year":"1998","unstructured":"Bra\u00fcner, T., de Paiva, V.: A formulation of linear logic based on dependency-relations. In: Nielsen, M., Thomas, W. (eds.) CSL 1997. LNCS, vol. 1414, pp. 129\u2013148. Springer, Heidelberg (1998). doi: 10.1007\/BFb0028011"},{"issue":"5","key":"26_CR7","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1093\/jigpal\/8.5.629","volume":"8","author":"T Bra\u00fcner","year":"2000","unstructured":"Bra\u00fcner, T.: A cut-free Gentzen formulation of modal logic S5. Log. J. IGPL 8(5), 629\u2013643 (2000)","journal-title":"Log. J. IGPL"},{"key":"26_CR8","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1002\/malq.19820283308","volume":"28","author":"W Buszkowski","year":"1982","unstructured":"Buszkowski, W.: Some decision problems in the theory of syntactic categories. Zeitschr. f\u00fcr math. Logik und Grundl. der Math. (Math. Logic Q.) 28, 539\u2013548 (1982)","journal-title":"Zeitschr. f\u00fcr math. Logik und Grundl. der Math. (Math. Logic Q.)"},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-94-017-3598-8_12","volume-title":"Trends in Logic: 50 Years of Studia Logica","author":"W Buszkowski","year":"2003","unstructured":"Buszkowski, W.: Type logics in grammar. In: Hendricks, V.F., Malinowski, J. (eds.) Trends in Logic: 50 Years of Studia Logica, pp. 337\u2013382. Springer, Dordrecht (2003). doi: 10.1007\/978-94-017-3598-8_12"},{"key":"26_CR10","unstructured":"Buszkowski, W.: Lambek calculus with nonlogical axioms. In: Language and Grammar. CSLI Lecture Notes, vol. 168, pp. 77\u201393 (2005)"},{"key":"26_CR11","volume-title":"Type-Logical Semantics","author":"B Carpenter","year":"1997","unstructured":"Carpenter, B.: Type-Logical Semantics. MIT Press, Cambridge (1997)"},{"key":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/978-3-540-78127-1_13","volume-title":"Pillars of Computer Science","author":"M Dekhtyar","year":"2008","unstructured":"Dekhtyar, M., Dikovsky, A.: Generalized categorial dependency grammars. In: Avron, A., Dershowitz, N., Rabinovich, A. (eds.) Pillars of Computer Science. LNCS, vol. 4800, pp. 230\u2013255. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-78127-1_13"},{"key":"26_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-319-27683-0_7","volume-title":"Logical Foundations of Computer Science","author":"H Eades III","year":"2016","unstructured":"Eades III, H., de Paiva, V.: Multiple conclusion linear logic: cut elimination and more. In: Artemov, S., Nerode, A. (eds.) LFCS 2016. LNCS, vol. 9537, pp. 90\u2013105. Springer, Cham (2016). doi: 10.1007\/978-3-319-27683-0_7"},{"key":"26_CR14","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1007\/BF01201353","volume":"39","author":"G Gentzen","year":"1935","unstructured":"Gentzen, G.: Untersuchungen \u00fcber das logische Schlie\u00dfen I. Math. Z. 39, 176\u2013210 (1935)","journal-title":"Math. Z."},{"key":"26_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(87)90045-4","volume":"50","author":"J-Y Girard","year":"1987","unstructured":"Girard, J.-Y.: Linear logic. Theor. Comput. Sci. 50, 1\u2013102 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"26_CR16","unstructured":"de Groote, P.: On the expressive power of the Lambek calculus extended with a structural modality. In: Language and Grammar. CSLI Lecture Notes, vol. 168, pp. 95\u2013111 (2005)"},{"key":"26_CR17","volume-title":"JFAK. Essays dedicated to Johan van Benthem on the occasion of his 50th birthday","author":"M Kanazawa","year":"1999","unstructured":"Kanazawa, M.: Lambek calculus: recognizing power and complexity. In: Gerbrandy, J., et al. (eds.) JFAK. Essays dedicated to Johan van Benthem on the occasion of his 50th birthday. Vossiuspers, Amsterdam University Press, Amsterdam (1999)"},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"Kanovich, M.: The complexity of neutrals in linear logic. In: Proceedings of LICS 1995, pp. 486\u2013495 (1995)","DOI":"10.1109\/LICS.1995.523282"},{"key":"26_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-662-53042-9_14","volume-title":"Formal Grammar","author":"M Kanovich","year":"2016","unstructured":"Kanovich, M., Kuznetsov, S., Scedrov, A.: Undecidability of the Lambek calculus with a relevant modality. In: Foret, A., Morrill, G., Muskens, R., Osswald, R., Pogodalla, S. (eds.) FG 2015-2016. LNCS, vol. 9804, pp. 240\u2013256. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-53042-9_14 . arXiv:1601.06303"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Kanovich, M., Kuznetsov, S., Scedrov, A.: Undecidability of the Lambek calculus with subexponential and bracket modalities (extended technical report). arXiv:1608.04020 (2017)","DOI":"10.1007\/978-3-662-55751-8_26"},{"key":"26_CR21","unstructured":"Kanovich, M., Kuznetsov, S., Morrill, G., Scedrov, A.: A polynomial time algorithm for the Lambek calculus with brackets of bounded order. arXiv:1705.00694 (2017). Accepted to FSCD 2017"},{"issue":"4","key":"26_CR22","doi-asserted-by":"crossref","first-page":"173","DOI":"10.3103\/S0027132211040085","volume":"66","author":"SL Kuznetsov","year":"2011","unstructured":"Kuznetsov, S.L.: On the Lambek calculus with a unit and one division. Moscow Univ. Math. Bull. 66(4), 173\u2013175 (2011)","journal-title":"Moscow Univ. Math. Bull."},{"issue":"3","key":"26_CR23","doi-asserted-by":"crossref","first-page":"154","DOI":"10.2307\/2310058","volume":"65","author":"J Lambek","year":"1958","unstructured":"Lambek, J.: The mathematics of sentence structure. Amer. Math. Mon. 65(3), 154\u2013170 (1958)","journal-title":"Amer. Math. Mon."},{"key":"26_CR24","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/BFb0079385","volume-title":"Category Theory, Homology Theory and their Applications I","author":"J Lambek","year":"1969","unstructured":"Lambek, J.: Deductive systems and categories II. Standard constructions and closed categories. In: Hilton, P.J. (ed.) Category Theory, Homology Theory and their Applications I. LNM, vol. 86, pp. 76\u2013122. Springer, Heidelberg (1969). doi: 10.1007\/BFb0079385"},{"key":"26_CR25","first-page":"239","volume":"56","author":"P Lincoln","year":"1992","unstructured":"Lincoln, P., Mitchell, J., Scedrov, A., Shankar, N.: Decision problems for propositional linear logic. APAL 56, 239\u2013311 (1992)","journal-title":"APAL"},{"key":"26_CR26","first-page":"583","volume":"55","author":"A Markov","year":"1947","unstructured":"Markov, A.: On the impossibility of certain algorithms in the theory of associative systems. Doklady Acad. Sci. USSR (N.S.) 55, 583\u2013586 (1947)","journal-title":"Doklady Acad. Sci. USSR (N.S.)"},{"issue":"3\u20134","key":"26_CR27","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF00159344","volume":"5","author":"M Moortgat","year":"1996","unstructured":"Moortgat, M.: Multimodal linguistic inference. J. Log. Lang. Inform. 5(3\u20134), 349\u2013385 (1996)","journal-title":"J. Log. Lang. Inform."},{"key":"26_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31555-8","volume-title":"The Logic of Categorial Grammars: A Deductive Account of Natural Language Syntax and Semantics","author":"R Moot","year":"2012","unstructured":"Moot, R., Retor\u00e9, C.: The Logic of Categorial Grammars: A Deductive Account of Natural Language Syntax and Semantics. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-31555-8"},{"key":"26_CR29","unstructured":"Morrill, G.: Categorial formalisation of relativisation: pied piping, islands, and extraction sites. Technical report LSI-92-23-R, Universitat Polit\u00e8cnica de Catalunya (1992)"},{"key":"26_CR30","volume-title":"Categorial Grammar: Logical Syntax, Semantics, and Processing","author":"GV Morrill","year":"2011","unstructured":"Morrill, G.V.: Categorial Grammar: Logical Syntax, Semantics, and Processing. Oxford University Press, Oxford (2011)"},{"key":"26_CR31","doi-asserted-by":"crossref","unstructured":"Morrill, G.: CatLog: a categorial parser\/theorem-prover. In: System Demonstration, LACL 2012, Nantes (2012)","DOI":"10.1093\/oxfordhb\/9780199544004.013.0004"},{"issue":"2","key":"26_CR32","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/s10988-016-9197-0","volume":"40","author":"G Morrill","year":"2017","unstructured":"Morrill, G.: Grammar logicised: relativisation. Linguist. Philos. 40(2), 119\u2013163 (2017)","journal-title":"Linguist. Philos."},{"key":"26_CR33","doi-asserted-by":"crossref","unstructured":"Morrill, G., Valent\u00edn, O.: Computational coverage of TLG: nonlinearity. In: Proceedings of NLCS 2015. EPiC Series, vol. 32, pp. 51\u201363 (2015)","DOI":"10.29007\/96j5"},{"key":"26_CR34","doi-asserted-by":"crossref","unstructured":"Nigam, V., Miller, D.: Algorithmic specifications in linear logic with subexponentials. In: Proceedings of PPDP 2009, pp. 129\u2013140. ACM (2009)","DOI":"10.1145\/1599410.1599427"},{"issue":"1","key":"26_CR35","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 357(1), 186\u2013201 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20134","key":"26_CR36","first-page":"441","volume":"36","author":"M Pentus","year":"2010","unstructured":"Pentus, M.: A polynomial time algorithm for Lambek grammars of bounded order. Linguist. Anal. 36(1\u20134), 441\u2013471 (2010)","journal-title":"Linguist. Anal."},{"key":"26_CR37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2267170","volume":"12","author":"EL Post","year":"1947","unstructured":"Post, E.L.: Recursive unsolvability of a problem of Thue. J. Symb. Log. 12, 1\u201311 (1947)","journal-title":"J. Symb. Log."},{"key":"26_CR38","unstructured":"Ross, J.R.: Constraints on variables in syntax. Ph.D. thesis, MIT (1967)"},{"key":"26_CR39","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6591.001.0001","volume-title":"The Syntactic Process","author":"M Steedman","year":"2000","unstructured":"Steedman, M.: The Syntactic Process. MIT Press, Cambridge, MA (2000)"},{"key":"26_CR40","unstructured":"Thue, A.: Probleme \u00fcber Ver\u00e4nderungen von Zeichenreihen nach gegebener Regeln. Kra. Vidensk. Selsk. Skrifter. 10 (1914). (In: Selected Math. Papers, Univ. Forlaget, Oslo, pp. 493\u2013524 (1977))"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-55751-8_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T22:55:50Z","timestamp":1750805750000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-55751-8_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783662557501","9783662557518"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-55751-8_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}