{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T21:16:25Z","timestamp":1779138985876,"version":"3.51.4"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031479625","type":"print"},{"value":"9783031479632","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-47963-2_7","type":"book-chapter","created":{"date-parts":[[2023,11,22]],"date-time":"2023-11-22T21:41:26Z","timestamp":1700689286000},"page":"83-99","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On the\u00a0Complexity of\u00a0Reasoning in\u00a0Kleene Algebra with\u00a0Commutativity Conditions"],"prefix":"10.1007","author":[{"given":"Stepan L.","family":"Kuznetsov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,11,23]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1","volume-title":"Transductions and Context-Free Languages","author":"J Berstel","year":"1979","unstructured":"Berstel, J.: Transductions and Context-Free Languages. Teubner, Stuttgart (1979). https:\/\/doi.org\/10.1007\/978-3-663-09367-1"},{"issue":"1","key":"7_CR2","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."},{"key":"7_CR3","unstructured":"Cohen, E.: Hypotheses in Kleene algebra. Technical report, Bellcore (1994)"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-030-17127-8_12","volume-title":"Foundations of Software Science and Computation Structures","author":"A Doumane","year":"2019","unstructured":"Doumane, A., Kuperberg, D., Pous, D., Pradic, P.: Kleene algebra with hypotheses. In: Boja\u0144czyk, M., Simpson, A. (eds.) FoSSaCS 2019. LNCS, vol. 11425, pp. 207\u2013223. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17127-8_12"},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0304-3975(86)90101-5","volume":"48","author":"A Gibbons","year":"1986","unstructured":"Gibbons, A., Rytter, W.: On the decidability of some problems about rational subsets of free partially commutative monoids. Theoret. Comput. Sci. 48, 329\u2013337 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90101-5","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR6","doi-asserted-by":"publisher","unstructured":"Haase, C., Hofman, P.: Tightening the complexity of equivalence problems for commutative grammars. In: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), vol. 47 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 41:1\u201341:14. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.41","DOI":"10.4230\/LIPIcs.STACS.2016.41"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Kozen, D.: On action algebras. In: van Eijck, J., Visser, A. (ed.) Logic and Information Flow, pp. 78\u201388. MIT Press (1994)","DOI":"10.7551\/mitpress\/4286.003.0007"},{"key":"7_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/3-540-61042-1_35","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"D Kozen","year":"1996","unstructured":"Kozen, D.: Kleene algebra with tests and commutativity conditions. In: Margaria, T., Steffen, B. (eds.) TACAS 1996. LNCS, vol. 1055, pp. 14\u201333. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61042-1_35"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1006\/inco.2001.2960","volume":"179","author":"D Kozen","year":"2002","unstructured":"Kozen, D.: On the complexity of reasoning in Kleene algebra. Inf. Comput. 179, 152\u2013162 (2002). https:\/\/doi.org\/10.1006\/inco.2001.2960","journal-title":"Inf. Comput."},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-662-43951-7_24","volume-title":"Automata, Languages, and Programming","author":"D Kozen","year":"2014","unstructured":"Kozen, D., Mamouras, K.: Kleene algebra with equations. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 280\u2013292. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_24"},{"key":"7_CR11","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/3-540-44957-4_38","volume-title":"Computational Logic \u2014 CL 2000","author":"D Kozen","year":"2000","unstructured":"Kozen, D., Patron, M.-C.: Certification of compiler optimizations using Kleene algebra with tests. In: Lloyd, J., et al. (eds.) CL 2000. LNCS (LNAI), vol. 1861, pp. 568\u2013582. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44957-4_38"},{"key":"7_CR12","doi-asserted-by":"publisher","unstructured":"Kuznetsov, S.: Action logic is undecidable. ACM Trans. Comput. Logic 22(2), 1\u201326 (2021). https:\/\/doi.org\/10.1145\/3445810","DOI":"10.1145\/3445810"},{"issue":"2","key":"7_CR13","doi-asserted-by":"publisher","first-page":"103057","DOI":"10.1016\/j.apal.2021.103057","volume":"173","author":"SL Kuznetsov","year":"2022","unstructured":"Kuznetsov, S.L., Speranski, S.O.: Infinitary action logic with exponentiation. Ann. Pure Appl. Logic 173(2), 103057 (2022). https:\/\/doi.org\/10.1016\/j.apal.2021.103057","journal-title":"Ann. Pure Appl. Logic"},{"key":"7_CR14","doi-asserted-by":"publisher","unstructured":"Maarand, H., Uustalu, T.: Reordering derivatives on trace closures of regular languages. In: 30th International Conference on Concurrency Theory (CONCUR 2019), vol. 140 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 40:1\u201340:16. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2019.40","DOI":"10.4230\/LIPIcs.CONCUR.2019.40"},{"issue":"3","key":"7_CR15","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","volume":"46","author":"EW Mayr","year":"1982","unstructured":"Mayr, E.W., Meyer, A.R.: The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. Math. 46(3), 305\u2013329 (1982). https:\/\/doi.org\/10.1016\/0001-8708(82)90048-2","journal-title":"Adv. Math."},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1002\/malq.19550010205","volume":"1","author":"J Myhill","year":"1955","unstructured":"Myhill, J.: Creative sets. Z. Math. Logik Grundlagen Math. 1, 97\u2013108 (1955). https:\/\/doi.org\/10.1002\/malq.19550010205","journal-title":"Z. Math. Logik Grundlagen Math."},{"issue":"2","key":"7_CR17","first-page":"295","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)","journal-title":"Fund. Inform."},{"key":"7_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BFb0018436","volume-title":"Logics in AI","author":"V Pratt","year":"1991","unstructured":"Pratt, V.: Action logic and pure induction. In: van Eijck, J. (ed.) JELIA 1990. LNCS, vol. 478, pp. 97\u2013120. Springer, Heidelberg (1991). https:\/\/doi.org\/10.1007\/BFb0018436"},{"issue":"2","key":"7_CR19","first-page":"185","volume":"16","author":"VN Redko","year":"1964","unstructured":"Redko, V.N.: On the algebra of commutative events. Ukrainski\u012d Matematicheski\u012d Zhurnal 16(2), 185\u2013195 (1964). In Russian","journal-title":"Ukrainski\u012d Matematicheski\u012d Zhurnal"},{"key":"7_CR20","unstructured":"Rogers, H.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987)"},{"key":"7_CR21","unstructured":"Sipser, M.: Introduction to the Theory of Computation. Cengage Learning. 3rd edn (2012)"},{"key":"7_CR22","doi-asserted-by":"publisher","unstructured":"Speranski, S.O.: A note on hereditarily $$\\varPi ^0_1$$- and $$\\varSigma ^0_1$$-complete sets of sentences. J. Log. Comput. 26(5), 1729\u20131741 (2016). https:\/\/doi.org\/10.1093\/logcom\/exu066","DOI":"10.1093\/logcom\/exu066"}],"container-title":["Lecture Notes in Computer Science","Theoretical Aspects of Computing \u2013 ICTAC 2023"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-47963-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,26]],"date-time":"2023-12-26T07:03:32Z","timestamp":1703574212000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-47963-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031479625","9783031479632"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-47963-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"23 November 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICTAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Theoretical Aspects of Computing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lima","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Peru","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ictac2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ictac2023.compsust.utec.edu.pe\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}