Hostname: page-component-7b7567c8c-8tzhz Total loading time: 0 Render date: 2026-11-19T10:52:41.030Z Has data issue: false hasContentIssue false

Products of ‘transitive” modal logics

Published online by Cambridge University Press:  12 March 2014

D. Gabelaia
Affiliation:
Department of Computer Science, King's College London, Strand, London WC2R 2LS, UKE-mail:, gabelaia@dcs.kcl.ac.uk
A. Kurucz
Affiliation:
Department of Computer Science, King's College London, Strand, London WC2R 2LS, UKE-mail:, kuag@dcs.kcl.ac.uk
F. Wolter
Affiliation:
Department of Computer Science, King's College London, Strand, London WC2R 2LS, UKE-mail:, mz@dcs.kcl.ac.uk
M. Zakharyaschev
Affiliation:
Department of Computer Science, University of Liverpool, Liverpool L69 7ZF, UKE-mail:, frank@csc.liv.ac.uk

Abstract

We solve a major open problem concerning algorithmic properties of products of ‘transitive’ modal logics by showing that products and commutators of such standard logics as K4, S4, S4.1, K4.3, GL, or Grz are undecidable and do not have the finite model property. More generally, we prove that no Kripke complete extension of the commutator [K4, K4] with product frames of arbitrary finite or infinite depth (with respect to both accessibility relations) can be decidable. In particular, if l1 and l2 are classes of transitive frames such that their depth cannot be bounded by any fixed n < ω, then the logic of the class {5ℑ1 × ℑ2 ∣ ℑ1 ∈ l1, ℑ2, ∈ l2} is undecidable. (On the contrary, the product of, say, K4 and the logic of all transitive Kripke frames of depth ≤ n, for some fixed n < ω, is decidable.) The complexity of these undecidable logics ranges from r.e. to co-r.e. and Π11-complete. As a consequence, we give the first known examples of Kripke incomplete commutators of Kripke complete logics.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable