×

Non-finitely axiomatisable two-dimensional modal logics. (English) Zbl 1259.03032

In this very clearly structured paper, the authors consider the problem of axiomatizing products of two finitely axiomatizable unimodal propositional logics. The paper settles some open problems from the literature on product logics in the negative. It is shown that certain recursively enumerable product logics characterized by classes of product frames with a linearly ordered first component, including the decidable logic K4.3 \(\times\) K, cannot be axiomatized with only a finite number of propositional variables. Moreover, the notion of vertical depth of a bimodal formula is defined, and it is shown that for K4.3 \(\times\) K and certain two-dimensional modal logics extending K4.3 \(\times\) K, every axiomatization must contain formulas of arbitrarily large vertical depth. The paper ends with a list of open problems.

MSC:

03B45 Modal logic (including the logic of norms)
03B62 Combined logics
PDF BibTeX XML Cite
Full Text: DOI Euclid

References:

[1] H. Andréka Complexity of equations valid in algebras of relations. Part I: strong non-finitizability, Annals of Pure and Applied Logic , vol. 89(1997), pp. 149-209. · Zbl 0898.03023
[2] A. Artale and E. Franconi A survey of temporal extensions of description logics , Annals of Mathematics and Artificial Intelligence , vol. 30(2001), pp. 171-210. · Zbl 0998.03013
[3] F. Baader and H.J. Ohlbach A multi-dimensional terminological knowledge representation language , Journal of Applied Non-Classical Logics , vol. 5(1995), pp. 153-197. · Zbl 0845.68098
[4] P. Blackburn, M. de Rijke, and Y. Venema Modal logic , Cambridge University Press,2001. · Zbl 0988.03006
[5] A. Chagrov and M. Zakharyaschev Modal logic , Oxford Logic Guides, vol. 35, Clarendon Press, Oxford,1997. · Zbl 0855.03007
[6] J. Davoren and R. Goré Bimodal logics for reasoning about continuous dynamics , Advances in modal logic, volume 3 (F. Wolter, H. Wansing, M. de Rijke, and M. Zakharyaschev, editors), World Scientific,2002, pp. 91-112. · Zbl 1031.03030
[7] J. Davoren and A. Nerode Logics for hybrid systems , Proceedings of the IEEE , vol. 88(2000), pp. 985-1010.
[8] R. Fagin, J. Halpern, Y. Moses, and M. Vardi Reasoning about knowledge , MIT Press,1995. · Zbl 0839.68095
[9] D. Gabbay, A. Kurucz, F. Wolter, and M. Zakharyaschev Many-dimensional modal logics: Theory and applications , Studies in Logic and the Foundations of Mathematics, vol. 148, Elsevier,2003. · Zbl 1051.03001
[10] D. Gabbay and V. Shehtman Products of modal logics. Part I , Journal of the IGPL , vol. 6(1998), pp. 73-146. · Zbl 0902.03008
[11] D. Gabelaia, A. Kurucz, F. Wolter, and M. Zakharyaschev Products of ‘transitive’ modal logics , Journal of Symbolic Logic, vol. 70(2005), pp. 993-1021. · Zbl 1103.03020
[12] R. Hirsch and I. Hodkinson Relation algebras by games , Studies in Logic and the Foundations of Mathematics, vol. 147, Elsevier, North-Holland,2002. · Zbl 1018.03002
[13] —- Strongly representable atom structures of cylindric algebras , Journal of Symbolic Logic, vol. 74(2009), pp. 811-828. · Zbl 1207.03073
[14] I. Hodkinson and Y. Venema Canonical varieties with no canonical axiomatisation , Transactions of the American Mathematical Society , vol. 357(2005), pp. 4579-4605. · Zbl 1081.03062
[15] A. Kurucz On axiomatising products of Kripke frames , Journal of Symbolic Logic, vol. 65(2000), pp. 923-945. · Zbl 0963.03027
[16] —- Combining modal logics , Handbook of modal logic (P. Blackburn, J. van Benthem, and F. Wolter, editors), Studies in Logic and Practical Reasoning, vol. 3, Elsevier,2007, pp. 869-924. · Zbl 1114.03001
[17] —- On the complexity of modal axiomatisations over many-dimensional structures , Advances in modal logic, volume 8 (L. Beklemishev, V. Goranko, and V. Shehtman, editors), College Publications,2010, pp. 256-270. · Zbl 1254.03037
[18] F. Wolter R. Kontchakov, A. Kurucz and M. Zakharyaschev Spatial logic + temporal logic = ? , Handbook of spatial logics (J. van Benthem M. Aiello, I. Pratt-Hartmann, editor), Springer,2007, pp. 497-564.
[19] J. Reif and A. Sistla A multiprocess network logic with temporal and spatial modalities , Journal of Computer and System Sciences , vol. 30(1985), pp. 41-53. · Zbl 0565.68031
[20] M. Reynolds and M. Zakharyaschev On the products of linear modal logics , Journal of Logic and Computation , vol. 11(2001), pp. 909-931. · Zbl 1002.03017
[21] K. Segerberg Two-dimensional modal logic , Journal of Philosophical Logic , vol. 2(1973), pp. 77-96. · Zbl 0259.02013
[22] V. Shehtman Two-dimensional modal logics , Mathematical Notices of the USSR Academy of Sciences , vol. 23(1978), pp. 417-424, (Translated from Russian).
[23] E. Spaan Complexity of modal logics , Ph.D. thesis, Department of Mathematics and Computer Science, University of Amsterdam,1993. · Zbl 0831.03005
[24] F. Wolter and M. Zakharyaschev Temporalizing description logics , Frontiers of combining systems II (D. Gabbay and M. de Rijke, editors), Studies Press/Wiley,2000, pp. 379-401. · Zbl 0994.03026
[25] F. Wolter and M. Zakharyaschev Axiomatizing the monodic fragment of first-order temporal logic , Annals of Pure and Applied Logic , vol. 118(2002), pp. 133-145. · Zbl 1031.03023
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.