{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T10:24:53Z","timestamp":1783506293038,"version":"3.55.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T00:00:00Z","timestamp":1650585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2022,7,31]]},"abstract":"<jats:p>We consider the operation of sum on Kripke frames, where a family of frames-summands is indexed by elements of another frame. In many cases, the modal logic of sums inherits the finite model property and decidability from the modal logic of summands [Babenyshev and Rybakov<jats:xref ref-type=\"bibr\">2010<\/jats:xref>; Shapirovsky<jats:xref ref-type=\"bibr\">2018<\/jats:xref>]. In this paper we show that, under a general condition, the satisfiability problem on sums is polynomial space Turing reducible to the satisfiability problem on summands. In particular, for many modal logics decidability in PSpace is an immediate corollary from the semantic characterization of the logic.<\/jats:p>","DOI":"10.1145\/3508068","type":"journal-article","created":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T15:23:31Z","timestamp":1650641011000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Satisfiability Problems on Sums of Kripke Frames"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7434-5894","authenticated-orcid":false,"given":"Ilya","family":"Shapirovsky","sequence":"first","affiliation":[{"name":"New Mexico State University, USA and Institute for Information Transmission Problems of Russian Academy of Sciences, Las Cruces, New Mexico, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,4,22]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/jzp047"},{"key":"e_1_3_2_3_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/978-3-642-04222-5_10","volume-title":"Frontiers of Combining Systems","author":"Balbiani Philippe","year":"2009","unstructured":"Philippe Balbiani. 2009. Axiomatization and completeness of lexicographic products of modal logics. In Frontiers of Combining Systems, Silvio Ghilardi and Roberto Sebastiani (Eds.). Lecture Notes in Computer Science, Vol. 5749. Springer, 165\u2013180."},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIME.2010.13"},{"key":"e_1_3_2_5_1","first-page":"78","volume-title":"Advances in Modal Logic, Vol. 11","author":"Balbiani Philippe","year":"2016","unstructured":"Philippe Balbiani and David Fern\u00e1ndez-Duque. 2016. Axiomatizing the lexicographic products of modal logics with linear temporal logic. In Advances in Modal Logic, Vol. 11, Lev Beklemishev, St\u00e9phane Demri, and Andr\u00e1s M\u00e1t\u00e9 (Eds.). College Publications, 78\u201396."},{"key":"e_1_3_2_6_1","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/978-3-642-40885-4_10","volume-title":"Frontiers of Combining Systems","author":"Balbiani Philippe","year":"2013","unstructured":"Philippe Balbiani and Szabolcs Mikul\u00e1s. 2013. Decidability and complexity via mosaics of the temporal logic of the lexicographic products of unbounded dense linear orders. In Frontiers of Combining Systems, Pascal Fontaine, Christophe Ringeissen, and Renate A. Schmidt (Eds.). Springer Berlin, Berlin, 151\u2013164."},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.11.030"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2009.06.011"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-013-9490-7"},{"key":"e_1_3_2_10_1","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/978-3-642-22303-7_2","volume-title":"Logic, Language, and Computation","author":"Bezhanishvili Guram","year":"2011","unstructured":"Guram Bezhanishvili, Leo Esakia, and David Gabelaia. 2011. Spectral and T0-spaces in d-semantics. In Logic, Language, and Computation, Nick Bezhanishvili, Sebastian L\u00f6bner, Kerstin Schwabe, and Luca Spada (Eds.). Springer Berlin, Berlin, 16\u201329."},{"key":"e_1_3_2_11_1","series-title":"Cambridge Tracts in Theoretical Computer Science","volume-title":"Modal Logic","author":"Blackburn Patrick","year":"2002","unstructured":"Patrick Blackburn, Maarten de Rijke, and Yde Venema. 2002. Modal Logic. Cambridge Tracts in Theoretical Computer Science, Vol. 53. Cambridge University Press."},{"key":"e_1_3_2_12_1","series-title":"Oxford Logic Guides","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198537793.001.0001","volume-title":"Modal Logic","author":"Chagrov Alexander","year":"1997","unstructured":"Alexander Chagrov and Michael Zakharyaschev. 1997. Modal Logic. Oxford Logic Guides, Vol. 35. Oxford University Press."},{"key":"e_1_3_2_13_1","first-page":"71","volume-title":"Advances in Modal Logic, Volume 4","author":"Chagrov A. V.","year":"2003","unstructured":"A. V. Chagrov and M. N. Rybakov. 2003. How many variables does one need to prove PSPACE-hardness of modal logics. In Advances in Modal Logic, Volume 4, Philippe Balbiani, Nobu-Yuki Suzuki, Frank Wolter, and Michael Zakharyaschev (Eds.). CSLI Publications, 71\u201382."},{"key":"e_1_3_2_14_1","first-page":"244","article-title":"Weak transitivity-restitution","volume":"8","author":"Esakia Leo","year":"2001","unstructured":"Leo Esakia. 2001. Weak transitivity-restitution. Logical Studies 8 (2001), 244\u2013255.","journal-title":"Logical Studies"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-47-1-57-103"},{"key":"e_1_3_2_16_1","volume-title":"Many-dimensional Modal Logics: Theory and Applications","author":"Gabbay D.","year":"2003","unstructured":"D. Gabbay, A. Kurucz, F. Wolter, and M. Zakharyaschev. 2003. Many-dimensional Modal Logics: Theory and Applications. North Holland Publishing Company."},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.2307\/2272344"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1122038925"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273287"},{"key":"e_1_3_2_20_1","series-title":"Perspectives in Mathematical Logic","first-page":"479","volume-title":"Model-Theoretic Logics","author":"Gurevich Y.","year":"1985","unstructured":"Y. Gurevich. 1985. Monadic second-order theories. In Model-Theoretic Logics, J. Barwise and S. Feferman (Eds.). Perspectives in Mathematical Logic, Vol. 8. Springer-Verlag, New York, Chapter XIII, 479\u2013506. https:\/\/projecteuclid.org\/euclid.pl\/1235417279."},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1040046086"},{"key":"e_1_3_2_22_1","volume-title":"The Modal Logical Means of Investigation of Provability","author":"Japaridze Giorgi K.","year":"1986","unstructured":"Giorgi K. Japaridze. 1986. The Modal Logical Means of Investigation of Provability. Ph.D. Dissertation. Thesis in Philosophy, in Russian, Moscow."},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206033"},{"key":"e_1_3_2_24_1","article-title":"The non-reflexive counterpart of Grz","volume":"36","author":"Litak Tadeusz","year":"2007","unstructured":"Tadeusz Litak. 2007. The non-reflexive counterpart of Grz. Bulletin of the Section of Logic 36 (1 2007).","journal-title":"Bulletin of the Section of Logic"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.2307\/2267454"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-014-0397-4"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/11.6.909"},{"key":"e_1_3_2_28_1","first-page":"269","volume-title":"Advances in Modal Logic","author":"Shapirovsky I.","year":"2005","unstructured":"I. Shapirovsky. 2005. On PSPACE-decidability in transitive modal logic. In Advances in Modal Logic, Vol. 5. College Publications, London, 269\u2013287. ISBN 1904987222."},{"key":"e_1_3_2_29_1","first-page":"289","volume-title":"Advances in Modal Logic (AiML)","author":"Shapirovsky I.","year":"2008","unstructured":"I. Shapirovsky. 2008. PSPACE-decidability of Japaridze\u2019s polymodal logic. In Advances in Modal Logic (AiML), Vol. 7. College Publications, London, 289\u2013304."},{"key":"e_1_3_2_30_1","first-page":"541","volume-title":"Advances in Modal Logic","author":"Shapirovsky I. B.","year":"2018","unstructured":"I. B. Shapirovsky. 2018. Truth-preserving operations on sums of Kripke frames. In Advances in Modal Logic, Vol. 12. College Publications, 541\u2013558. ISBN 978-1848902558."},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.2307\/1971037"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803408"},{"key":"e_1_3_2_33_1","volume-title":"Complexity of Modal Logics, PhD Thesis","author":"Spaan E.","year":"1993","unstructured":"E. Spaan. 1993. Complexity of Modal Logics, PhD Thesis. University of Amsterdam, Institute for Logic, Language and Computation."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3508068","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3508068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:29Z","timestamp":1750191149000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3508068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,22]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7,31]]}},"alternative-id":["10.1145\/3508068"],"URL":"https:\/\/doi.org\/10.1145\/3508068","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,22]]},"assertion":[{"value":"2020-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}