Journal of Symbolic Logic · 2005 · 45 citations · 29 references
ComputingComputer ScienceMathematicsAlgorithmsLogicTheory Of ComputationModal LogicModel TheoryStructural ComplexityDecidability ProblemsFrames
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 l 1 and l 2 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 ∈ l 1 , ℑ 2 , ∈ l 2 } 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 Π 1 1 -complete. As a consequence, we give the first known examples of Kripke incomplete commutators of Kripke complete logics.
29
Introduction to automata theory, languages, and computation
Computer Languages · 1980 · 6.9K citations
Mathematical Social Sciences · 1994 · 3.6K citations
The undecidability of the domino problem
Robert E. Berger · Memoirs of the American Mathematical Society · 1966 · 974 citations
Krister Segerberg · Journal of Philosophical Logic · 1973 · 290 citations