Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-29T14:58:02.121Z Has data issue: false hasContentIssue false
  • English
  • Français

Non-finitely axiomatisable two-dimensional modal logics

Published online by Cambridge University Press:  12 March 2014

Agi Kurucz  and
Sérgio Marcelino
Agi Kurucz
Affiliation:
Department of Informatics, King's College London, Strand, London WC2R 2LS, UK, E-mail: [email protected]
Sérgio Marcelino
Affiliation:
Department of Informatics, King's College London, Strand, London WC2R 2LS, UK SQIG, IT-LISBOA, Instituto Superior Técnico - Torre Norte - Piso 10, AV. Rovisco Pais, 1, 1049 - 001 Lisboa, Portugal, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show the first examples of recursively enumerable (even decidable) two-dimensional products of finitely axiomatisable modal logics that are not finitely axiomatisable. In particular, we show that any axiomatisation of some bimodal logics that are determined by classes of product frames with linearly ordered first components must be infinite in two senses: It should contain infinitely many propositional variables, and formulas of arbitrarily large modal nesting-depth.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 77 , Issue 3 , September 2012 , pp. 970 - 986
Copyright
Copyright © Association for Symbolic Logic 2012

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.)

References

REFERENCES

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