@TechReport{Areces_et_al:1999,
AUTHOR = {Areces, Carlos and Blackburn, Patrick and Marx, Maarten},
TITLE = {Hybrid Logics: Characterization, Interpolation and Complexity},
YEAR = {1999},
MONTH = {February},
NUMBER = {108},
PAGES = {35},
ADDRESS = {Saarbrücken},
TYPE = {CLAUS-Report},
INSTITUTION = {Universität des Saarlandes},
URL = {ftp://ftp.coli.uni-sb.de/pub/coli/claus/claus108.ps ftp://ftp.coli.uni-sb.de/pub/coli/claus/claus108.dvi},
ABSTRACT = {Hybrid languages are extended modal languages which can refer to (or even quantify over) worlds. The use of strong hybrid languages dates back to at least 1967 (in the work of Arthur Prior), but recent work has focussed on more constrained systems. The purpose of the present paper is to examine one such system in detail. We begin by studying its expressivity, and provide both model theoretic characterizations (via a restricted notion of Ehrenfeucht-Fraisse game, and an enriched notion of bisimulation) and a syntactic characterization (in terms of bounded formulas). The key result to emerge is that the system corresponds precisely to the first-order fragment which is invariant for generated submodels. We further establish that it has (strong) interpolation, and provide failure results in the finite variable fragments. We also show that weak interpolation holds for an important sublanguage and provide complexity results for this sublanguage and other fragments and variants (the full logic being undecidable).},
ANNOTE = {COLIURL : Areces:1999:HLC.pdf Areces:1999:HLC.ps Areces:1999:HLC.dvi}
}
|
