{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T07:17:33Z","timestamp":1763623053453,"version":"3.45.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T00:00:00Z","timestamp":1761955200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T00:00:00Z","timestamp":1761955200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100012708","name":"Foundation for the Advancement of Theoretical Physics and Mathematics","doi-asserted-by":"publisher","award":["21-7-2-7-3"],"award-info":[{"award-number":["21-7-2-7-3"]}],"id":[{"id":"10.13039\/501100012708","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J of Log Lang and Inf"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s10849-025-09445-9","type":"journal-article","created":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T09:04:08Z","timestamp":1761987848000},"page":"635-664","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the expressive power of categorial grammars with unique category assignment"],"prefix":"10.1007","volume":"34","author":[{"given":"Maxim","family":"Vishnikin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,11,1]]},"reference":[{"key":"9445_CR1","unstructured":"Ajdukiewicz, K. (1935). \u201cDie syntaktische Konnexit\u00e4t\u201d, In: K. Ajdukiewicz, R. Ingarden, & K. Twardowski (Eds.), Studia Philosophica, vol.\u00a01, 1\u201327."},{"issue":"1","key":"9445_CR2","doi-asserted-by":"publisher","first-page":"47","DOI":"10.2307\/410452","volume":"29","author":"Y Bar-Hillel","year":"1953","unstructured":"Bar-Hillel, Y. (1953). A quasi-arithmetical notation for syntactic description. Language, 29(1), 47\u201358. https:\/\/doi.org\/10.2307\/410452","journal-title":"Language"},{"key":"9445_CR3","first-page":"155","volume":"9F","author":"Y Bar-Hillel","year":"1960","unstructured":"Bar-Hillel, Y., Gaifman, H., & Shamir, E. (1960). On categorial and phrase structure grammars. Bulletin of the Research Council of Israel, 9F, 155\u2013166.","journal-title":"Bulletin of the Research Council of Israel"},{"key":"9445_CR4","volume-title":"Language in Action: Categories, Lambdas, and Dynamic Logic. Studies in Logic and the Foundations of Mathematics","author":"J van Benthem","year":"1991","unstructured":"van Benthem, J. (1991). Language in Action: Categories, Lambdas, and Dynamic Logic. Studies in Logic and the Foundations of Mathematics (Vol. 130). Amsterdam: North-Holland."},{"issue":"5\u20136","key":"9445_CR5","first-page":"373","volume":"35","author":"W Buszkowski","year":"1987","unstructured":"Buszkowski, W. (1987). Solvable problems for classical categorial grammars. Bulletin of the Polish Academy of Sciences, Mathematics, 35(5\u20136), 373\u2013382.","journal-title":"Bulletin of the Polish Academy of Sciences, Mathematics"},{"key":"9445_CR6","doi-asserted-by":"publisher","unstructured":"Buszkowski, W. (2018). \u201cCategorial grammars and their logics\u201d, In: \u00c1. Garrido, & U. Wybraniec-Skardowska (Eds.), The Lvov\u2013Warsaw School. Past and Present. Studies in Universal Logic, 91\u2013115. https:\/\/doi.org\/10.1007\/978-3-319-65430-0_6","DOI":"10.1007\/978-3-319-65430-0_6"},{"key":"9445_CR7","doi-asserted-by":"publisher","unstructured":"Buszkowski, W. (2016). \u201cSyntactic categories and types: Ajdukiewicz and modern categorial grammars\u201d, In: A. Bro\u017cek et al. (Eds.) Tradition of the Lvov\u2013Warsaw School: Ideas and Continuations, Leiden, Boston, Brill-Rodopi, 35\u201371. https:\/\/doi.org\/10.1163\/9789004311763_004","DOI":"10.1163\/9789004311763_004"},{"key":"9445_CR8","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/BF00370157","volume":"49","author":"W Buszkowski","year":"1990","unstructured":"Buszkowski, W., & Penn, G. (1990). Categorial grammars determined from linguistic data by unification. Studia Logica, 49, 431\u2013454. https:\/\/doi.org\/10.1007\/BF00370157","journal-title":"Studia Logica"},{"key":"9445_CR9","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S1571-0661(05)82576-9","volume":"53","author":"A Foret","year":"2004","unstructured":"Foret, A. (2004). The emptiness of intersection problem for languages of k-valued categorial grammars (classical and Lambek) is undecidable. Electronic Notes in Theoretical Computer Science, 53, 81\u201393. https:\/\/doi.org\/10.1016\/S1571-0661(05)82576-9","journal-title":"Electronic Notes in Theoretical Computer Science"},{"issue":"3","key":"9445_CR10","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1145\/321341.321345","volume":"13","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg, S., & Ullian, J. S. (1966). Preservation of unambiguity and inherent ambiguity in context-free languages. Journal of the ACM, 13(3), 364\u2013368. https:\/\/doi.org\/10.1145\/321341.321345","journal-title":"Journal of the ACM"},{"key":"9445_CR11","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/321250.321254","volume":"12","author":"SA Greibach","year":"1965","unstructured":"Greibach, S. A. (1965). A new normal-form theorem for context-free phrase structure grammars. Journal of the ACM, 12, 42\u201352. https:\/\/doi.org\/10.1145\/321250.321254","journal-title":"Journal of the ACM"},{"issue":"4","key":"9445_CR12","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"SA Greibach","year":"1973","unstructured":"Greibach, S. A. (1973). The hardest context-free language. SIAM Journal on Computing, 2(4), 304\u2013310. https:\/\/doi.org\/10.1137\/0202025","journal-title":"SIAM Journal on Computing"},{"key":"9445_CR13","volume-title":"Introduction to Formal Language Theory","author":"MA Harrison","year":"1978","unstructured":"Harrison, M. A. (1978). Introduction to Formal Language Theory. Boston, MA: Addison Wesley."},{"key":"9445_CR14","unstructured":"Kanazawa, M. (1994). Learnable Classes of Categorial Grammars, Ph.D. Thesis, University of Amsterdam, ILLC Dissertation (DS) Series, DS-1994-08. https:\/\/eprints.illc.uva.nl\/id\/eprint\/1971"},{"issue":"2","key":"9445_CR15","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00173697","volume":"5","author":"M Kanazawa","year":"1996","unstructured":"Kanazawa, M. (1996). Identification in the limit of categorial grammars. Journal of Logic, Language, and Information, 5(2), 115\u2013155. https:\/\/doi.org\/10.1007\/BF00173697","journal-title":"Journal of Logic, Language, and Information"},{"key":"9445_CR16","doi-asserted-by":"publisher","unstructured":"Kuznetsov, S. (2013). \u201cConjunctive grammars in Greibach normal form and the Lambek calculus with additive connectives\u201d, Proceedings of Formal Grammar 2012 and Formal Grammar 2013, LNCS 8036, 242\u2013249. https:\/\/doi.org\/10.1007\/978-3-642-39998-5_15","DOI":"10.1007\/978-3-642-39998-5_15"},{"key":"9445_CR17","doi-asserted-by":"publisher","first-page":"946","DOI":"10.1017\/S1755020320000209","volume":"14","author":"S Kuznetsov","year":"2021","unstructured":"Kuznetsov, S. (2021). Complexity of the Infinitary Lambek Calculus with Kleene Star. The Review of Symbolic Logic, 14, 946\u2013972. https:\/\/doi.org\/10.1017\/S1755020320000209","journal-title":"The Review of Symbolic Logic"},{"key":"9445_CR18","doi-asserted-by":"crossref","unstructured":"Kuznetsov, S., & Okhotin, A. (2017 July 13\u201314). \u201cConjunctive categorial grammars\u201d, Proceedings of the 15th Meeting on the Mathematics of Language (MOL 2017, London, UK), ACL, 141\u2013151.","DOI":"10.18653\/v1\/W17-3414"},{"issue":"3","key":"9445_CR19","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1080\/00029890.1958.11989160","volume":"65","author":"J Lambek","year":"1958","unstructured":"Lambek, J. (1958). The mathematics of sentence structure. The American Mathematical Monthly, 65(3), 154\u2013170. https:\/\/doi.org\/10.1080\/00029890.1958.11989160","journal-title":"The American Mathematical Monthly"},{"key":"9445_CR20","doi-asserted-by":"publisher","unstructured":"Pentus, M. (1993). \u201cLambek grammars are context-free\u201d Proceedings of the 8th Annual IEEE Symposium on Logic in Computer Science (LICS), 429\u2013433. https:\/\/doi.org\/10.1109\/LICS.1993.287565","DOI":"10.1109\/LICS.1993.287565"},{"issue":"4","key":"9445_CR21","doi-asserted-by":"publisher","first-page":"168","DOI":"10.3103\/S0027132207040092","volume":"62","author":"AN Safiullin","year":"2007","unstructured":"Safiullin, A. N. (2007). Derivability of admissible rules with simple premises in the Lambek calculus. Moscow University Mathematics Bulletin, 62(4), 168\u2013171. https:\/\/doi.org\/10.3103\/S0027132207040092","journal-title":"Moscow University Mathematics Bulletin"},{"key":"9445_CR22","doi-asserted-by":"publisher","unstructured":"Weir, D. J., & Joshi, A. K. (1988). \u201cCombinatory Categorial Grammars: generative power and relationship to Linear Context-Free Rewriting\u201d, ACL, 278\u2013285. https:\/\/doi.org\/10.3115\/982023.982057","DOI":"10.3115\/982023.982057"}],"container-title":["Journal of Logic, Language and Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10849-025-09445-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10849-025-09445-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10849-025-09445-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T07:14:05Z","timestamp":1763622845000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10849-025-09445-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,1]]},"references-count":22,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["9445"],"URL":"https:\/\/doi.org\/10.1007\/s10849-025-09445-9","relation":{},"ISSN":["0925-8531","1572-9583"],"issn-type":[{"type":"print","value":"0925-8531"},{"type":"electronic","value":"1572-9583"}],"subject":[],"published":{"date-parts":[[2025,11,1]]},"assertion":[{"value":"22 August 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Maxim Vishnikin declares that he has no conflict of interest. Alexander Okhotin declares that he has no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}]}}