A road-map on complexity for hybrid logics

Carlos Areces, Patrick Blackburn, Maarten Marx

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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.

Original languageEnglish
Title of host publicationComputer Science Logic - 13th International Workshop, CSL 1999 - 8th Annual Conference of the EACSL, Proceedings
EditorsJörg Flum, Mario Rodriguez-Artalejo
Number of pages15
PublisherSpringer
Publication date1999
Pages307-321
ISBN (Print)3540665366, 9783540665366
DOIs
Publication statusPublished - 1999
Externally publishedYes
Event13th International Workshop on Computer Science Logic, CSL 1999 and held as International Workshops on Computer Science Logic, EACSL 1999 - Madrid, Spain
Duration: 20 Sep 199925 Sep 1999

Conference

Conference13th International Workshop on Computer Science Logic, CSL 1999 and held as International Workshops on Computer Science Logic, EACSL 1999
Country/TerritorySpain
CityMadrid
Period20/09/199925/09/1999
SponsorComision Interministerial de Ciencia y Tecnologia (CICYT), MEC, Departamento Arquitectura de Computadores y Automatica (DACYA), UCM, Departamento Sistemas Informaticos y Programacion (DSIP), UCM, Escuela Superior de Informatica – UCM, Esprit Working Group EP 22457 (CCL II), et al
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1683
ISSN0302-9743

Keywords

  • Computational complexity
  • Description logic
  • Labeled deduction
  • Modal and temporal logic

Cite this