Skip to main content
Log in

Modal Logic over Finite Structures

  • Published:
Journal of Logic, Language and Information Aims and scope Submit manuscript

Abstract

We investigate properties of propositional modal logic over the classof finite structures. In particular, we show that certain knownpreservation theorems remain true over this class. We prove that aclass of finite models is defined by a first-order sentence and closedunder bisimulations if and only if it is definable by a modal formula.We also prove that a class of finite models defined by a modal formulais closed under extensions if and only if it is defined by a ♦-modal formula.

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

Access this article

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Andréka, H., van Benthem, J., and Németi, I., 1995, "Back and forth between modal logic and classical logic," Journal of the IGPL 3(5), 685–720.

    Google Scholar 

  • Barwise, J., 1977, "On Moschovakis closure ordinals," Journal of Symbolic Logic 42, 292–296.

    Google Scholar 

  • van Benthem, J., 1976, "Modal correspondence theory," Ph.D. Thesis, University of Amsterdam.

  • van Benthem, J., 1985, Modal Logic and Classical Logic, Naples: Bibliopolis.

    Google Scholar 

  • Fagin, R., Stockmeyer, L., and Vardi, M.Y., 1995, "On monadic NP vs monadic co-NP," Information and Computation 120, 78–92.

    Google Scholar 

  • Gurevich, Y., 1984, "Toward logic tailored for computational complexity," pp. 175–216 in Computation and Proof Theory, M. Richter et al., eds., Berlin: Springer-Verlag.

    Google Scholar 

  • Hennessy, M. and Milner, R., 1985, "Algebraic laws for nondeterminism and concurrency," Journal of the Association for Computing Machinery 32, 137–161.

    Google Scholar 

  • Hodges, W., 1993, Model Theory, Cambridge: Cambridge University Press.

    Google Scholar 

  • Sahlqvist, H., 1975, "Completeness and correspondence in the first and second order semantics for modal logic," pp. 110–143 in Proceedings of the Third Scandinavian Logic Symposium, S. Kanger, ed., Amsterdam: North-Holland.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rosen, E. Modal Logic over Finite Structures. Journal of Logic, Language and Information 6, 427–439 (1997). https://doi.org/10.1023/A:1008275906015

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008275906015

Navigation