Skip to main content
SpringerLink
Log in

Hybrid Logic Meets IF Modal Logic

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

Abstract

The hybrid logic \({\mathcal{H}(@,\downarrow)}\) and the independence friendly modal logic IFML are compared for their expressive powers. We introduce a logic IFML c having a non-standard syntax and a compositional semantics; in terms of this logic a syntactic fragment of IFML is singled out, denoted IFML c . (In the Appendix it is shown that the game-theoretic semantics of IFML c coincides with the compositional semantics of IFML c .) The hybrid logic \({\mathcal{H}(@,\downarrow)}\) is proven to be strictly more expressive than IFML c . By contrast, \({\mathcal{H}(@,\downarrow)}\) and the full IFML are shown to be incomparable for their expressive powers. Building on earlier research (Tulenheimo and Sevenster 2006), a PSPACE-decidable fragment of the undecidable logic \({\mathcal{H}(@,\downarrow)}\) is disclosed. This fragment is not translatable into the hybrid logic \({\mathcal{H}(@)}\) and has not been studied previously in connection with hybrid logics. In the Appendix IFML c is shown to lack the property of ‘quasi-positionality’ but proven to enjoy the weaker property of ‘bounded quasi-positionality’. The latter fact provides from the IFML internal perspective an account of what makes the compositional semantics of IFML c possible.

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.

Institutional subscriptions

Similar content being viewed by others

References

  • Areces, C., Blackburn, P., & Marx, M. (1999). A road-map on complexity for hybrid logics. In Lecture Notes in Computer Science (Vol. 1683, pp. 307–321). Berlin: Springer.

  • Areces C., Blackburn P., Marx M. (2001) Hybrid logics: Characterization, interpolation and complexity. Journal of Symbolic Logic 66: 977–1010

    Article  Google Scholar 

  • Blackburn P., de Rijke M., Venema Y. (2002) Modal logic. Cambridge University Press, Cambridge

    Google Scholar 

  • Bradfield, J. (2000). Independence: Logics and concurrency. In Lecture Notes in Computer Science (Vol. 1862, pp. 247–261). London: Springer.

  • Bradfield J., Fröschle S. (2002) Independence-friendly modal logic and true concurrency. Nordic Journal of Computing 9: 102–117

    Google Scholar 

  • Börger E., Grädel E., Gurevich Y. (1997) The classical decision problem. Springer, Berlin

    Google Scholar 

  • Cameron P., Hodges W. (2001) Some combinatorics of imperfect information. Journal of Symbolic Logic 66: 673–684

    Article  Google Scholar 

  • Durand A., Lautemann C., Schwentick T. (1998) Subclasses of binary NP. Journal of Logic and Computation 8: 189–207

    Article  Google Scholar 

  • Ebbinghaus H.-D., Flum J. (1999) Finite model theory. Springer, Berlin

    Google Scholar 

  • Enç M. (1987) Anchoring conditions for tense. Linguistic Inquiry 18: 633–657

    Google Scholar 

  • Feferman S. (1968) Persistent and invariant formulas for outer extensions. Compositio Mathematica 20: 29–52

    Google Scholar 

  • Feferman S., Kreisel G. (1966) Persistent and invariant formulas relative to theories of higher order. Bulletin of the American Mathematical Society 72: 480–485 (Research announcement)

    Article  Google Scholar 

  • Fine K. (1971) Propositional quantifiers in modal logic. Theoria 36: 336–346

    Article  Google Scholar 

  • Grädel E., Walukiewicz I. (2006) Positional determinacy of games with infinitely many priorities. Logical Methods in Computer Science 2: 1–22

    Article  Google Scholar 

  • Hintikka J. (1996) Principles of mathematics revisited. Cambridge University Press, Cambridge

    Google Scholar 

  • Hintikka J., Sandu G. (1989) Informational independence as a semantical phenomenon. In: Fenstad J., Frolov I., Hilpinen R. (eds) Logic, methodology and philosophy of science Vol. 8. Elsevier, Amsterdam, pp 571–589

    Chapter  Google Scholar 

  • Hintikka J., Sandu G. (1997) Game-theoretical semantics. In: Benthem J., ter Meulen A. (eds) Handbook of logic and language. Elsevier, Amsterdam, pp 361–410

    Chapter  Google Scholar 

  • Hodges W. (1993) Model theory. Cambridge University Press, Cambridge

    Google Scholar 

  • Hodges W. (1997a) Compositional semantics for a language of imperfect information. Logic Journal of the IGPL 5: 539–563

    Article  Google Scholar 

  • Hodges, W. (1997b). Some strange quantifiers. In Lecture Notes in Computer Science (Vol. 1261, pp. 51–65). London: Springer.

  • Hornstein N. (1990) As time goes by: Tense and universal grammar. The MIT Press, Cambridge, MA

    Google Scholar 

  • Hyttinen T., Tulenheimo T. (2005a) Decidability of IF modal logic of perfect recall. In: Schmidt R., Pratt-Hartmann I., Reynolds M., Wansing H. (eds) Advances in modal logic Vol. 5. KCL Publications, London, pp 111–131

    Google Scholar 

  • Hyttinen, T., & Tulenheimo, T. (2005b). Decidability and undecidability results for some IF modal logics. Unpublished Manuscript.

  • Kuusisto A. (2008) A modal perspective on monadic second-order alternation hierarchies. In: Areces C., Goldblatt R. (eds) Advances in modal logic Vol. 7. College Publications, London, pp 231–247

    Google Scholar 

  • Sandu G. (1993) On the logic of informational independence and its applications. Journal of Philosophical Logic 22: 29–60

    Article  Google Scholar 

  • Sandu G., Hintikka J. (2001) Aspects of compositionality. Journal of Logic, Language and Information 10: 49–61

    Article  Google Scholar 

  • Sevenster, M. (2006). Branches of imperfect information. PhD. thesis, University of Amsterdam.

  • ten Cate, B. (2005). Model theory for extended modal languages. PhD. thesis, University of Amsterdam.

  • ten Cate B. (2006) Expressivity of second-order propositional modal logic. Journal of Philosophical Logic 35: 209–223

    Article  Google Scholar 

  • Tulenheimo T. (2003) On IF modal logic and its expressive power. In: Balbiani P., Suzuki N.-Y., Wolter F., Zakharyaschev M. (eds) Advances in modal logic (Vol. 4). KCL Publications, London, pp 475–498

    Google Scholar 

  • Tulenheimo, T. (2004). Independence-friendly modal logic: studies in its expressive power and theoretical relevance. PhD. thesis, University of Helsinki.

  • Tulenheimo T., Rebuschi M. (2009) Equivalence criteria for compositional IF modal logics. Electronic Notes in Theoretical Computer Science 231: 153–173

    Article  Google Scholar 

  • Tulenheimo T., Sevenster M. (2006) On modal logic, IF logic and IF modal logic. In: Governatori G., Hodkinson I., Venema Y. (eds) Advances in modal logic (Vol. 6). College Publications, London, pp 481–501

    Google Scholar 

  • Tulenheimo T., Sevenster M. (2007) Approaches to independence friendly modal logic. In: Benthem J., Gabbay D., Löwe B. (eds) Interactive logic (Texts in Logic and Games, Vol. 1). Amsterdam University Press, Amsterdam, pp 247–280

    Google Scholar 

  • Väänänen J. (2007) Dependence logic: A new approach to independence friendly logic. Cambridge University Press, Cambridge

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Philosophy, University of Helsinki, P.O. Box 9, Siltavuorenpenger 20 A, 00014, Helsinki, Finland

    Tero Tulenheimo

Authors
  1. Tero Tulenheimo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tero Tulenheimo.

Additional information

The research for the present paper was carried out within the project “Modalities, Games and Independence in Logic” (project no. 207188) funded by the Academy of Finland.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tulenheimo, T. Hybrid Logic Meets IF Modal Logic. J of Log Lang and Inf 18, 559–591 (2009). https://doi.org/10.1007/s10849-009-9092-y

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10849-009-9092-y

Keywords

Search

Navigation