zbMATH — the first resource for mathematics

Products of ‘transitive’ modal logics. (English) Zbl 1103.03020
Products of modal logics, introduced in the 1970s [see K. Segerberg, “Two-dimensional modal logic”, J. Philos. Log. 2, 77–96 (1973; Zbl 0259.02013), V. Shekhtman, “Two-dimensional modal logics”, Math. Notes 23, 417–424 (1978; Zbl 0403.03015), translation from Mat. Zametki 23, 759–772 (1978; Zbl 0384.03010)], have been intensively studied over the last decade [see D. Gabbay, A. Kurucz, F. Wolter, and M. Zakharyaschev, Many-dimensional modal logics: theory and applications. Amsterdam: Elsevier (2003; Zbl 1051.03001)]. In this paper, the authors introduce a novel technique for dealing with products of logics with transitive branching frames and solve a major open problem concerning algorithmic properties of products of ‘transitive’ modal logics by showing that products and commutators of standard logics such as K4, S4, S4.1, K4.3, GL and Grz are undecidable and do not have the finite model property. More generally, they prove that all products of two Kripke-complete modal logics with transitive frames of arbitrary finite or infinite depth are undecidable, in many cases these products are not axiomatizable and do not enjoy the abstract finite model property, and, sometimes they are even $$\Pi^1_1$$-hard. As a byproduct, the first known examples of Kripke-incomplete commutators of Kripke-complete logics are obtained.

MSC:
 03B45 Modal logic (including the logic of norms) 03B25 Decidability of theories and sets of sentences
Full Text:
References:
 [1] DOI: 10.1002/malq.19950410103 · Zbl 0818.03008 [2] Logics containing K4, Part II 50 pp 619– (1985) [3] Reasoning about knowledge (1995) · Zbl 0839.68095 [4] Canonical formulas for K4, Part I: Basic results 57 pp 1377– (1992) [5] DOI: 10.1109/5.871305 [6] Advances in modal logic 3 pp 91– (2002) [7] Exploring Artificial Intelligence in the New Millenium pp 175– (2002) [8] Modal logic 35 (1997) · Zbl 0871.03007 [9] Mathematical theory of automata pp 23– (1963) [10] Memoirs of the American Mathematical Society 66 (1966) [11] DOI: 10.1002/malq.19750210114 · Zbl 0317.02011 [12] DOI: 10.1080/11663081.1995.10510854 · Zbl 0845.68098 [13] Modal logics and topological semantics for hybrid systems (1997) [14] Proceedings of AiML-2004 pp 344– (2004) [15] Annals of Mathematics and Artificial Intelligence 30 pp 171– (2001) [16] Mathematical Notices of the USSR Academy of Sciences 23 pp 417– (1978) [17] DOI: 10.1007/BF02115610 · Zbl 0259.02013 [18] DOI: 10.1093/logcom/11.6.909 · Zbl 1002.03017 [19] DOI: 10.1305/ndjfl/1039700748 · Zbl 0904.03010 [20] DOI: 10.1016/0022-0000(85)90003-0 · Zbl 0565.68031 [21] DOI: 10.1093/logcom/9.6.897 · Zbl 0941.03018 [22] DOI: 10.1023/A:1021312628326 · Zbl 1010.03014 [23] Advances in modal logic 4 pp 221– (2003) [24] DOI: 10.1016/j.apal.2004.06.004 · Zbl 1067.03028 [25] The Bulletin of Symbolic Logic 3 pp 371– (1997) [26] Proceedings of the 20th International Conference on Automated Deduction (CADE-20) (2005) [27] Proceedings of AiML-2004 pp 182– (2004) [28] Introduction to automata theory, languages, and computation (2001) · Zbl 0980.68066 [29] On modal logics between K {$$\times$$} K {$$\times$$} K and S5 {$$\times$$} S5 {$$\times$$} S5 67 pp 221– (2002) [30] DOI: 10.1016/0022-0000(83)90014-4 · Zbl 0536.68041 [31] Annals of Discrete Mathematics 24 pp 51– (1985) [32] Proceedings of the Conference on Logic and Computation (1984) [33] Journal of Artificial Intelligence Research 23 pp 167– (2005) [34] DOI: 10.1023/A:1021304426509 · Zbl 1014.03023 [35] DOI: 10.1093/jigpal/6.1.73 · Zbl 0902.03008 [36] Many-dimensional modal logics: Theory and applications 148 (2003) [37] Logics containing K4, Part I 39 pp 229– (1974)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.