Hybrid Logics: Characterization, Interpolation and Complexity

Journal of Symbolic Logic 66 (3):977-1010 (2001)
  Copy   BIBTEX

Abstract

Hybrid languages are expansions of propositional modal languages which can refer to worlds. The use of strong hybrid languages dates back to at least [Pri67], but recent work has focussed on a more constrained system called $\mathscr{H}$. We show in detail that $\mathscr{H}$ is modally natural. We begin by studying its expressivity, and provide model theoretic characterizations and a syntactic characterization. The key result to emerge is that $\mathscr{H}$ corresponds to the fragment of first-order logic which is invariant for generated submodels. We then show that $\mathscr{H}$ enjoys interpolation, provide counterexamples for its finite variable fragments, and show that weak interpolation holds for the sublanguage $\mathscr{H}$. Finally, we provide complexity results for $\mathscr{H}$ and other fragments and variants, and sharpen known undecidability results for $\mathscr{H}$.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 102,020

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Existence of some sparse sets of nonstandard natural numbers.Renling Jin - 2001 - Journal of Symbolic Logic 66 (2):959-973.
Expressive Power and Intensional Operators.Pablo Cubides Kovacsics & David Rey - 2024 - Journal of Logic, Language and Information 33 (2):107-141.
The complexity of the core model.William Mitchell - 1998 - Journal of Symbolic Logic 63 (4):1393-1398.
Forbidden Induced Subgraphs and the Łoś–Tarski Theorem.Yijia Chen & Jörg Flum - 2024 - Journal of Symbolic Logic 89 (2):516-548.
On the t-degrees of partial functions.Paolo Casalegno - 1985 - Journal of Symbolic Logic 50 (3):580-588.
Gentzen sequent calculi for some intuitionistic modal logics.Zhe Lin & Minghui Ma - 2019 - Logic Journal of the IGPL 27 (4):596-623.

Analytics

Added to PP
2009-01-28

Downloads
118 (#184,538)

6 months
14 (#248,888)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Patrick Blackburn
Roskilde University

References found in this work

Past, present and future.Arthur N. Prior - 1967 - Oxford,: Clarendon P..
Modal logic with names.George Gargov & Valentin Goranko - 1993 - Journal of Philosophical Logic 22 (6):607 - 636.
Hybrid languages.Patrick Blackburn & Jerry Seligman - 1995 - Journal of Logic, Language and Information 4 (3):251-272.
Hierarchies of modal and temporal logics with reference pointers.Valentin Goranko - 1996 - Journal of Logic, Language and Information 5 (1):1-24.

View all 18 references / Add more references