Skip to main content
SpringerLink
Log in

All Normal Extensions of S5-squared Are Finitely Axiomatizable

  • Published:
Studia Logica Aims and scope Submit manuscript

Abstract

We prove that every normal extension of the bi-modal system S52 is finitely axiomatizable and that every proper normal extension has NP-complete satisfiability problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Bezhanishvili, N., ‘Varieties of two-dimensional cylindric algebras. Part I: Diagonal-free case’, Algebra Universalis 48 (2002), 11–42.

    Google Scholar 

  2. Bezhanishvili, N., ‘Varieties of two-dimensional cylindric algebras. Part II’, Algebra Universalis 51 (2004) 177–206.

    Google Scholar 

  3. Bezhanishvili, N., and M. Marx, ‘All proper normal extensions of S5-square have the polynomial size model property’, Studia Logica 73 (2003), 367–382.

    Google Scholar 

  4. Blackburn, P., M. de Rijke, and Y. Venema, Modal Logic, Cambridge University Press, 2001.

  5. Gabbay, D., A. Kurucz, F. Wolter, and M. Zakharyaschev, Many-Dimensional Modal Logics: Theory and Applications, Studies in Logic, vol. 148, North-Holland, 2003.

  6. Grädel, E., P. Kolaitis, and M. Vardi, ‘On the decision problem for two-variable first order logic’, Bulletin of Symbolic Logic 3 (1997), 53–69.

    Google Scholar 

  7. Higman, G., ‘Ordering by divisibility in abstract algebras’, Proc. London Math. Soc. 2 (1952), 326–336.

    Google Scholar 

  8. Kracht, M., ‘Prefinitely axiomatizable modal and intermediate logics’, Mathematical Logic Quarterly 39 (1993), 301–322.

    Google Scholar 

  9. Laver, R., Better-quasi-orderings and a class of trees, in: Studies in Foundations and Combinatorics, Gian-Carlo Rota, ed., vol. 1 of Advances in Mathematics Supplementary Studies, Academic Press, 1978, pp. 31–48.

  10. Rado, R., ‘Partial well ordering of sets of vectors’, Mathematica 1 (1954), 89–95.

    Google Scholar 

  11. Segerberg, K., ‘Two-dimensional modal logic’, Journal of Philosophical logic 2 (1973), 77–96.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. ILLC, University of Amsterdam, Plantage Muidergracht 24 1018, TV Amsterdam, The Netherlands

    Nick Bezhanishvili

  2. Department of Computing, Imperial College London, South Kensington Campus, London, SW7 2AZ, UK

    Ian Hodkinson

Authors
  1. Nick Bezhanishvili
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ian Hodkinson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nick Bezhanishvili.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bezhanishvili, N., Hodkinson, I. All Normal Extensions of S5-squared Are Finitely Axiomatizable. Stud Logica 78, 443–457 (2004). https://doi.org/10.1007/s11225-004-6044-z

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11225-004-6044-z

Keywords

Search

Navigation