{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T16:31:04Z","timestamp":1775061064747,"version":"3.50.1"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032224682","type":"print"},{"value":"9783032224699","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-22469-9_12","type":"book-chapter","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:58:08Z","timestamp":1775055488000},"page":"208-228","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of\u00a0Equational Theories for\u00a0Relational and\u00a0Language Action Lattices"],"prefix":"10.1007","author":[{"given":"Max","family":"Kanovich","sequence":"first","affiliation":[]},{"given":"Stepan L.","family":"Kuznetsov","sequence":"additional","affiliation":[]},{"given":"Andre","family":"Scedrov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,4,2]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","unstructured":"Abrusci, V.M.: A comparison between Lambek syntactic calculus and intuitionistic linear logic. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 36, 11\u201315 (1990). https:\/\/doi.org\/10.1002\/malq.19900360103","DOI":"10.1002\/malq.19900360103"},{"issue":"1","key":"12_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01066355","volume":"3","author":"H Andr\u00e9ka","year":"1994","unstructured":"Andr\u00e9ka, H., Mikul\u00e1s, S.: Lambek calculus and its relational semantics: completeness and incompleteness. J. Logic Lang. Inform. 3(1), 1\u201337 (1994). https:\/\/doi.org\/10.1007\/BF01066355","journal-title":"J. Logic Lang. Inform."},{"key":"12_CR3","doi-asserted-by":"publisher","unstructured":"Andr\u00e9ka, H., Mikul\u00e1s, S.: Axiomatizability of positive algebras of binary relations. Algebra Universalis 66, 7\u201334 (2011). https:\/\/doi.org\/10.1007\/s00012-011-0142-3","DOI":"10.1007\/s00012-011-0142-3"},{"key":"12_CR4","doi-asserted-by":"publisher","unstructured":"Buszkowski, W.: Compatibility of a categorial grammar with an associated category system. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 28, 229\u2013238 (1982). https:\/\/doi.org\/10.1002\/malq.19820281407","DOI":"10.1002\/malq.19820281407"},{"key":"12_CR5","doi-asserted-by":"publisher","unstructured":"Buszkowski, W.: Some decision problems in the theory of syntactic categories. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 28, 539\u2013548 (1982). https:\/\/doi.org\/10.1002\/malq.19820283308","DOI":"10.1002\/malq.19820283308"},{"issue":"1","key":"12_CR6","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1002\/malq.19860320104","volume":"32","author":"W Buszkowski","year":"1986","unstructured":"Buszkowski, W.: Completeness results for Lambek syntactic calculus. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 32(1), 13\u201328 (1986). https:\/\/doi.org\/10.1002\/malq.19860320104","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"12_CR7","doi-asserted-by":"publisher","unstructured":"Buszkowski, W.: On the complexity of the equational theory of relational action algebras. In: Schmidt, R.A. (ed.) RelMiCS 2006. LNCS, vol.\u00a04136, pp. 106\u2013119. Springer (2006). https:\/\/doi.org\/10.1007\/11828563_7","DOI":"10.1007\/11828563_7"},{"issue":"1","key":"12_CR8","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1093\/logcom\/exl036","volume":"17","author":"W Buszkowski","year":"2007","unstructured":"Buszkowski, W.: On action logic: equational theories of action algebras. J. Log. Comput. 17(1), 199\u2013217 (2007). https:\/\/doi.org\/10.1093\/logcom\/exl036","journal-title":"J. Log. Comput."},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11225-008-9116-7","volume":"89","author":"W Buszkowski","year":"2008","unstructured":"Buszkowski, W., Palka, E.: Infinitary action logic: complexity, models and grammars. Stud. Logica. 89(1), 1\u201318 (2008). https:\/\/doi.org\/10.1007\/s11225-008-9116-7","journal-title":"Stud. Logica."},{"key":"12_CR10","unstructured":"Galatos, N., Jipsen, P., Kowalski, T., Ono, H.: Residated lattices: an algebraic glimpse at substructural logics, Studies in Logic and the Foundations of Mathematics, vol.\u00a0151. Elsevier (2007). https:\/\/www.sciencedirect.com\/bookseries\/studies-in-logic-and-the-foundations-of-mathematics\/vol\/151\/"},{"key":"12_CR11","doi-asserted-by":"publisher","unstructured":"Girard, J.-Y.: Linear logic. Theoretical Computer Science 50, 1\u2013102 (1987). https:\/\/doi.org\/10.1016\/0304-3975(87)90045-4","DOI":"10.1016\/0304-3975(87)90045-4"},{"key":"12_CR12","unstructured":"Kanazawa, M.: Lambek calculus: Recognizing power and complexity. In: Gerbrandy, J., et\u00a0al. (eds.) JFAK. Essays Dedicated to Johan van Benthem on the Occasion of his 50th Birthday. Vossiuspers, Amsterdam University Press (1999)"},{"issue":"1","key":"12_CR13","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s10849-020-09320-9","volume":"30","author":"M Kanovich","year":"2021","unstructured":"Kanovich, M., Kuznetsov, S., Scedrov, A.: The multiplicative-additive Lambek calculus with subexponential and bracket modalities. J. Logic Lang. Inform. 30(1), 31\u201388 (2021). https:\/\/doi.org\/10.1007\/s10849-020-09320-9","journal-title":"J. Logic Lang. Inform."},{"key":"12_CR14","doi-asserted-by":"publisher","unstructured":"Kanovich, M., Kuznetsov, S., Scedrov, A.: Language models for some extensions of the Lambek calculus. Inform. Comput. 287, 104760, 16\u00a0pp. (2022). https:\/\/doi.org\/10.1016\/j.ic.2021.104760","DOI":"10.1016\/j.ic.2021.104760"},{"key":"12_CR15","doi-asserted-by":"publisher","unstructured":"Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Shannon, C., McCarthy, J. (eds.) Automata Studies, pp. 3\u201341. Princeton University Press (1956). https:\/\/doi.org\/10.1515\/9781400882618-002","DOI":"10.1515\/9781400882618-002"},{"issue":"2","key":"12_CR16","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s11225-009-9172-7","volume":"91","author":"M Kozak","year":"2009","unstructured":"Kozak, M.: Distributive full Lambek calculus has the finite model property. Stud. Logica. 91(2), 201\u2013216 (2009). https:\/\/doi.org\/10.1007\/s11225-009-9172-7","journal-title":"Stud. Logica."},{"key":"12_CR17","doi-asserted-by":"publisher","unstructured":"Kozen, D.: On action algebras. In: van Eijck, J., Visser, A. (eds.) Logic and Information Flow, pp. 78\u201388. MIT Press (1994). https:\/\/doi.org\/10.7551\/mitpress\/4286.003.0007","DOI":"10.7551\/mitpress\/4286.003.0007"},{"key":"12_CR18","doi-asserted-by":"publisher","unstructured":"Kozen, D.: On the complexity of reasoning in Kleene algebra. Inform. Comput. 179, 152\u2013162 (2002). https:\/\/doi.org\/10.1006\/inco.2001.2960","DOI":"10.1006\/inco.2001.2960"},{"key":"12_CR19","unstructured":"Krull, W.: Axiomatische Begr\u00fcndung der allgemeinen Idealtheorie. Sitzungsberichte der physikalisch-medizinischen Soziet\u00e4t zu Erlangen 56, 47\u201363 (1924), https:\/\/www.zobodat.at\/pdf\/Sitzber-physik-med-Soc-Erlangen_56-57_0047-0063.pdf"},{"key":"12_CR20","unstructured":"Kuznetsov, S.: $$*$$-continuity vs. induction: divide and conquer. In: Bezhanishvili, G., et\u00a0al. (eds.) Proceedings of AiML 2018. Advances in Modal Logic, vol.\u00a012, pp. 493\u2013510. College Publications (2018), https:\/\/www.aiml.net\/volumes\/volume12\/Kuznetsov.pdf"},{"key":"12_CR21","doi-asserted-by":"publisher","unstructured":"Kuznetsov, S.: Action logic is undecidable. ACM Trans. Comput. Logic 22(2), 10:1\u201310:26 (2021). https:\/\/doi.org\/10.1145\/3445810","DOI":"10.1145\/3445810"},{"key":"12_CR22","doi-asserted-by":"publisher","unstructured":"Kuznetsov, S.L.: Relational models for the Lambek calculus with intersection and constants. Logical Methods Comput. Sci. 19(4), 32, 27\u00a0pp. (2023). https:\/\/doi.org\/10.46298\/lmcs-19(4:32)2023","DOI":"10.46298\/lmcs-19(4:32)2023"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Kuznetsov, S.L.: Strong conservativity and completeness for fragments of infinitary action logic. Siberian Electr. Math. Rep. 21(2), 789\u2013809 (2024). https:\/\/math-semr.ru\/sites\/math-semr.ru\/files\/2024-11\/p0789-0809.pdf","DOI":"10.33048\/semi.2024.21.053"},{"issue":"2","key":"12_CR24","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s10469-020-09586-9","volume":"59","author":"SL Kuznetsov","year":"2020","unstructured":"Kuznetsov, S.L., Ryzhkova, N.S.: A restricted fragment of the Lambek calculus with iteration and intersection operations. Algebra and Logic 59(2), 129\u2013146 (2020). https:\/\/doi.org\/10.1007\/s10469-020-09586-9","journal-title":"Algebra and Logic"},{"key":"12_CR25","doi-asserted-by":"publisher","unstructured":"Kuznetsov, S.L., Speranski, S.O.: Infinitary action logic with exponentiation. Annals Pure Appli. Logic 173(2), 103057, 33\u00a0pp. (2022). https:\/\/doi.org\/10.1016\/j.apal.2021.103057","DOI":"10.1016\/j.apal.2021.103057"},{"key":"12_CR26","doi-asserted-by":"publisher","unstructured":"Lambek, J.: The mathematics of sentence structure. Am. Math. Monthly 65(3), 154\u2013170 (1958). https:\/\/doi.org\/10.1080\/00029890.1958.11989160","DOI":"10.1080\/00029890.1958.11989160"},{"key":"12_CR27","doi-asserted-by":"publisher","unstructured":"Mikul\u00e1s, S.: The equational theories of representable residuated semigroups. Synthese 192, 2151\u20132158 (2015). https:\/\/doi.org\/10.1007\/s11229-014-0513-3","DOI":"10.1007\/s11229-014-0513-3"},{"key":"12_CR28","doi-asserted-by":"publisher","unstructured":"Mikul\u00e1s, S.: Lower semilattice-ordered residuated semigroups and substructural logics. Studia Logica 103, 453\u2013478 (2015). https:\/\/doi.org\/10.1007\/s11225-014-9574-z","DOI":"10.1007\/s11225-014-9574-z"},{"key":"12_CR29","unstructured":"Odifreddi, P.: Classical recursion theory. The theory of functions and sets of natural numbers, Studies in Logic and Foundations of Mathematics, vol.\u00a0125. North-Holland Publishing Co., Amsterdam (1989). http:\/\/www.piergiorgioodifreddi.it\/wp-content\/uploads\/2010\/10\/CRT1.pdf"},{"issue":"1","key":"12_CR30","doi-asserted-by":"publisher","first-page":"169","DOI":"10.2307\/2273798","volume":"50","author":"H Ono","year":"1985","unstructured":"Ono, H., Komori, Y.: Logics without contraction rule. J. Symb. Log. 50(1), 169\u2013201 (1985). https:\/\/doi.org\/10.2307\/2273798","journal-title":"J. Symb. Log."},{"issue":"2","key":"12_CR31","doi-asserted-by":"publisher","first-page":"295","DOI":"10.3233\/FUN-2007-78206","volume":"78","author":"E Palka","year":"2007","unstructured":"Palka, E.: An infinitary sequent system for the equational theory of $$*$$-continuous action lattices. Fund. Inform. 78(2), 295\u2013309 (2007). https:\/\/doi.org\/10.3233\/FUN-2007-78206","journal-title":"Fund. Inform."},{"key":"12_CR32","doi-asserted-by":"publisher","unstructured":"Pentus, M.: Free monoid completeness of the Lambek calculus allowing empty premises. In: Larrazabal, J.M., Lascar, D., Mints, G. (eds.) Logic Colloquium 1996: Proceedings of the Colloquium Held in San Sebasti\u00e1n, Spain, 9\u201315 July 1996. Lecture Notes in Logic, vol.\u00a012, pp. 171\u2013209. Cambridge University Press (1998). https:\/\/doi.org\/10.1017\/9781316716816.008","DOI":"10.1017\/9781316716816.008"},{"key":"12_CR33","doi-asserted-by":"publisher","unstructured":"Pratt, V.: Action logic and pure induction. In: van Eijck, J. (ed.) Logics in AI. JELIA 1990. LNAI, vol.\u00a0478, pp. 97\u2013120. Springer (1991). https:\/\/doi.org\/10.1007\/BFb0018436","DOI":"10.1007\/BFb0018436"},{"issue":"4","key":"12_CR34","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1134\/S000143462409030X","volume":"116","author":"TG Pshenitsyn","year":"2024","unstructured":"Pshenitsyn, T.G.: Closure ordinal of immediate derivability operator of infinitary action logic. Math. Notes 116(4), 729\u2013744 (2024). https:\/\/doi.org\/10.1134\/S000143462409030X","journal-title":"Math. Notes"},{"key":"12_CR35","doi-asserted-by":"publisher","unstructured":"Sedl\u00e1r, I.: Iterative division in the distributive full non-associative Lambek calculus. In: Soares\u00a0Barbosa, L., Baltag, A. (eds.) Dynamic Logic. New Trends and Applications. DaL\u00ed 2019. LNCS, vol. 12005, pp. 141\u2013154. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-38808-9_9","DOI":"10.1007\/978-3-030-38808-9_9"},{"key":"12_CR36","doi-asserted-by":"crossref","unstructured":"Ward, M., Dilworth, R.P.: Residuated lattices. Trans. Am. Math. Soc. 45, 335\u2013354 (1939). https:\/\/www.ams.org\/journals\/tran\/1939-045-03\/S0002-9947-1939-1501995-3\/","DOI":"10.1090\/S0002-9947-1939-1501995-3"}],"container-title":["Lecture Notes in Computer Science","Relational and Algebraic Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-22469-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:58:10Z","timestamp":1775055490000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-22469-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032224682","9783032224699"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-22469-9_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"2 April 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RAMICS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Relational and Algebraic Methods in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"B\u0119dlewo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 April 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 April 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ramics2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ramics-conf.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}