Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T19:37:53.466Z Has data issue: false hasContentIssue false
  • English
  • Français

A BISIMULATION CHARACTERIZATION THEOREM FOR HYBRID LOGIC WITH THE CURRENT-STATE BINDER

Published online by Cambridge University Press:  26 February 2010

IAN HODKINSON  and
HICHAM TAHIRI
IAN HODKINSON*
Affiliation:
Imperial College London
HICHAM TAHIRI*
Affiliation:
Imperial College London
*
*DEPARTMENT OF COMPUTING, IMPERIAL COLLEGE, LONDON SW7 2AZ, UK. E-mail: [email protected], [email protected]
*DEPARTMENT OF COMPUTING, IMPERIAL COLLEGE, LONDON SW7 2AZ, UK. E-mail: [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that every first-order formula that is invariant under quasi-injective bisimulations is equivalent to a formula of the hybrid logic . Our proof uses a variation of the usual unravelling technique. We also briefly survey related results, and show in a standard way that it is undecidable whether a first-order formula is invariant under quasi-injective bisimulations.

Type
Research Article
Information
The Review of Symbolic Logic , Volume 3 , Issue 2 , June 2010 , pp. 247 - 261
Copyright
Copyright © Association for Symbolic Logic 2010

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

BIBLIOGRAPHY

Areces, C., Blackburn, P., & Marx, M. (2001). Hybrid logics: Characterization, interpolation, and complexity. Journal of Symbolic Logic, 66, 977–1010.CrossRefGoogle Scholar
Blackburn, P., de Rijke, M., & Venema, Y. (2001). Modal logic. Tracts in Theoretical Computer Science. Cambridge, UK: Cambridge University Press.CrossRefGoogle Scholar
Blackburn, P., & Seligman, J. (1998). What are hybrid languages? In Kracht, M., de Rijke, M., Wansing, H., and Zakharyaschev, M., editors. Advances in Modal Logic. Stanford, CA: CSLI Publications, pp. 41–62.Google Scholar
Franceschet, M., & de Rijke, M. (2006). Model checking hybrid logics (with an application to semistructured data). Journal of Applied Logic, 4(3), 279–304.CrossRefGoogle Scholar
Hodges, W. (1993). Model Theory, Volume 42 of Encyclopedia of Mathematics and Its Applications. Cambridge, UK: Cambridge University Press.Google Scholar
Karp, C. (1963). Finite-quantifier equivalence. In Addison, J., Henkin, L., and Tarski, A., editors. The Theory of Models. Amsterdam: North-Holland Publishing, pp. 407–412.Google Scholar
ten Cate, B. (2005). Model theory for extended modal languages. PhD Thesis, University of Amsterdam. ILLC Dissertation Series DS-2005-01.Google Scholar
van Benthem, J. (1985). Modal Logic and Classical Logic. Napoli, Italy: Bibliopolis.Google Scholar
van Benthem, J. (1996). Exploring Logical Dynamics. Studies in Logic, Language and Information. Stanford, CA: CSLI Publications & FoLLI.Google Scholar