{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T12:36:52Z","timestamp":1775738212971,"version":"3.50.1"},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3114,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2005,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We solve a major open problem concerning algorithmic properties of products of \u2018transitive\u2019 modal logics by showing that products and commutators of such standard logics as<jats:bold>K4<\/jats:bold>,<jats:bold>S4<\/jats:bold>,<jats:bold>S4.1<\/jats:bold>,<jats:bold>K4.3<\/jats:bold>,<jats:bold>GL<\/jats:bold>, or<jats:bold>Grz<\/jats:bold>are undecidable and do not have the finite model property. More generally, we prove that no Kripke complete extension of the commutator [<jats:bold>K4, K4<\/jats:bold>] with product frames of arbitrary finite or infinite depth (with respect to both accessibility relations) can be decidable. In particular, if<jats:italic>l<\/jats:italic><jats:sub>1<\/jats:sub>and<jats:italic>l<\/jats:italic><jats:sub>2<\/jats:sub>are classes of transitive frames such that their depth cannot be bounded by any fixed<jats:italic>n<\/jats:italic>&lt; \u03c9, then the logic of the class {5\u2111<jats:sub>1<\/jats:sub>\u00d7 \u2111<jats:sub>2<\/jats:sub>\u2223 \u2111<jats:sub>1<\/jats:sub>\u2208<jats:italic>l<\/jats:italic><jats:sub>1<\/jats:sub>, \u2111<jats:sub>2<\/jats:sub>, \u2208<jats:italic>l<\/jats:italic><jats:sub>2<\/jats:sub>} is undecidable. (On the contrary, the product of, say,<jats:bold>K4<\/jats:bold>and the logic of all transitive Kripke frames of depth \u2264<jats:italic>n<\/jats:italic>, for some fixed<jats:italic>n<\/jats:italic>&lt; \u03c9, is decidable.) The complexity of these undecidable logics ranges from r.e. to co-r.e. and \u03a0<jats:sub arrange=\"stack\">1<\/jats:sub><jats:sup arrange=\"stack\">1<\/jats:sup>-complete. As a consequence, we give the first known examples of Kripke incomplete commutators of Kripke complete logics.<\/jats:p>","DOI":"10.2178\/jsl\/1122038925","type":"journal-article","created":{"date-parts":[[2005,7,22]],"date-time":"2005-07-22T18:48:50Z","timestamp":1122058130000},"page":"993-1021","source":"Crossref","is-referenced-by-count":28,"title":["Products of \u2018transitive\u201d modal logics"],"prefix":"10.1017","volume":"70","author":[{"given":"D.","family":"Gabelaia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Kurucz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Wolter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Zakharyaschev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200006903_ref039","first-page":"1377","volume":"57","author":"Zakharyaschev","year":"1992","journal-title":"Canonical formulas for K4, Part I: Basic results"},{"key":"S0022481200006903_ref035","unstructured":"Spaan E. , Complexity of modal logics, Ph.D. thesis, Department of Mathematics and Computer Science, University of Amsterdam, 1993."},{"key":"S0022481200006903_ref034","first-page":"344","volume-title":"Proceedings of AiML-2004","author":"Shehtman","year":"2004"},{"key":"S0022481200006903_ref032","doi-asserted-by":"publisher","DOI":"10.1007\/BF02115610"},{"key":"S0022481200006903_ref029","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90003-0"},{"key":"S0022481200006903_ref026","first-page":"221","volume-title":"Advances in modal logic","volume":"4","author":"Kurucz","year":"2003"},{"key":"S0022481200006903_ref024","first-page":"371","article-title":"Dynamic topological logic","volume":"3","author":"Kremer","year":"1997","journal-title":"The Bulletin of Symbolic Logic"},{"key":"S0022481200006903_ref023","volume-title":"Proceedings of the 20th International Conference on Automated Deduction (CADE-20)","author":"Konev","year":"2005"},{"key":"S0022481200006903_ref020","first-page":"221","volume":"67","author":"Hirsch","year":"2002","journal-title":"On modal logics between K \u00d7 K \u00d7 K and S5 \u00d7 S5 \u00d7 S5"},{"key":"S0022481200006903_ref019","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90014-4"},{"key":"S0022481200006903_ref016","doi-asserted-by":"crossref","unstructured":"Gabelaia D. , Kurucz A. , Wolter F. , and Zakharyaschev M. , Non-primitive recursive decidability of products of modal logics with expanding domains. Submitted, available at http:\/\/dcs.kcl.ac.uk\/staff\/mz\/expand.pdf, 2005.","DOI":"10.1016\/j.apal.2006.01.001"},{"key":"S0022481200006903_ref012","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/6.1.73"},{"key":"S0022481200006903_ref009","first-page":"229","volume":"39","author":"Fine","year":"1974","journal-title":"Logics containing K4, Part I"},{"key":"S0022481200006903_ref008","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5803.001.0001","volume-title":"Reasoning about knowledge","author":"Fagin","year":"1995"},{"key":"S0022481200006903_ref007","doi-asserted-by":"publisher","DOI":"10.1109\/5.871305"},{"key":"S0022481200006903_ref004","article-title":"The undecidability of the domino problem","volume":"66","author":"Berger","year":"1966","journal-title":"Memoirs of the American Mathematical Society"},{"key":"S0022481200006903_ref003","doi-asserted-by":"publisher","DOI":"10.1080\/11663081.1995.10510854"},{"key":"S0022481200006903_ref036","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210114"},{"key":"S0022481200006903_ref040","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19950410103"},{"key":"S0022481200006903_ref031","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/11.6.909"},{"key":"S0022481200006903_ref021","volume-title":"Introduction to automata theory, languages, and computation","author":"Hopcroft","year":"2001"},{"key":"S0022481200006903_ref037","first-page":"23","volume-title":"Mathematical theory of automata","author":"Wang","year":"1963"},{"key":"S0022481200006903_ref015","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1613\/jair.1537","article-title":"Combining spatial and temporal logics: expressiveness vs. complexity","volume":"23","author":"Gabelaia","year":"2005","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S0022481200006903_ref025","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.06.004"},{"key":"S0022481200006903_ref002","doi-asserted-by":"publisher","DOI":"10.21236\/ADA344355"},{"key":"S0022481200006903_ref018","first-page":"51","article-title":"Recurring dominoes: Making the highly undecidable highly understandable","volume":"24","author":"Harel","year":"1985","journal-title":"Annals of Discrete Mathematics"},{"key":"S0022481200006903_ref010","first-page":"619","volume":"50","author":"Fine","year":"1985","journal-title":"Logics containing K4, Part II"},{"key":"S0022481200006903_ref022","first-page":"182","volume-title":"Proceedings of AiML-2004","author":"Konev","year":"2004"},{"key":"S0022481200006903_ref038","first-page":"175","volume-title":"Exploring Artificial Intelligence in the New Millenium","author":"Wolter","year":"2002"},{"key":"S0022481200006903_ref033","first-page":"417","article-title":"Two-dimensional modal logics","volume":"23","author":"Shehtman","year":"1978","journal-title":"Mathematical Notices of the USSR Academy of Sciences"},{"key":"S0022481200006903_ref001","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016636131405"},{"key":"S0022481200006903_ref030","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1305\/ndjfl\/1039700748","article-title":"A decidable temporal logic of parallelism","volume":"38","author":"Reynolds","year":"1997","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"S0022481200006903_ref027","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021312628326"},{"key":"S0022481200006903_ref028","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/9.6.897"},{"key":"S0022481200006903_ref005","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198537793.001.0001","volume-title":"Modal logic","volume":"35","author":"Chagrov","year":"1997"},{"key":"S0022481200006903_ref013","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021304426509"},{"key":"S0022481200006903_ref017","volume-title":"Proceedings of the Conference on Logic and Computation","author":"Harel","year":"1984"},{"key":"S0022481200006903_ref011","volume-title":"Many-dimensional modal logics: Theory and applications","volume":"148","author":"Gabbay","year":"2003"},{"key":"S0022481200006903_ref006","doi-asserted-by":"publisher","DOI":"10.1142\/9789812776471_0006"},{"key":"S0022481200006903_ref014","unstructured":"Gabelaia D. , Topological semantics and two-dimensional combinations of modal logics, Ph.D. thesis, King's College London, 2005."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200006903","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T16:28:44Z","timestamp":1735835324000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200006903\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,9]]}},"alternative-id":["S0022481200006903"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1122038925","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,9]]}}}