@inproceedings{9325ceda5f5240b5b95298ad9fb8874e,
title = "A road-map on complexity for hybrid logics",
abstract = "Hybrid languages are extended modal languages which can refer to (or even quantify over) states. Such languages are better behaved proof theoretically than ordinary modal languages for they internalize the apparatus of labeled deduction. Moreover, they arise naturally in a variety of applications, including description logic and temporal reasoning. Thus it would be useful to have a map of their complexity-theoretic properties, and this paper provides one. Our work falls into two parts. We first examine the basic hybrid language and its multi-modal and tense logical cousins. We show that the basic hybrid language (and indeed, multi-modal hybrid languages) are no more complex than ordinary uni-modal logic: all have pspace-complete K-satisfiability problems. We then show that adding even one nominal to tense logic raises complexity from pspace to exptime. In the second part we turn to stronger hybrid languages in which it is possible to bind nominals. We prove a general expressivity result showing that even the weak form of binding offered by the ↓ operator easily leads to undecidability.",
keywords = "Computational complexity, Description logic, Labeled deduction, Modal and temporal logic, Computational complexity, Description logic, Labeled deduction, Modal and temporal logic",
author = "Carlos Areces and Patrick Blackburn and Maarten Marx",
year = "1999",
doi = "10.1007/3-540-48168-0\_22",
language = "English",
isbn = "3540665366",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "307--321",
editor = "J{\"o}rg Flum and Mario Rodriguez-Artalejo",
booktitle = "Computer Science Logic - 13th International Workshop, CSL 1999 - 8th Annual Conference of the EACSL, Proceedings",
note = "13th International Workshop on Computer Science Logic, CSL 1999 and held as International Workshops on Computer Science Logic, EACSL 1999 ; Conference date: 20-09-1999 Through 25-09-1999",
}