The Complexity of Hybrid Logics over Equivalence Relations

M. Mundhenk; T. Schneider

The Complexity of Hybrid Logics over Equivalence Relations

M. Mundhenk, T. Schneider

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

Abstract

This paper examines and classifies the computational complexity of modelchecking and satisfiability for hybrid logics over frames withequivalence relations. The considered languages contain all possiblecombinations of the downarrow binder, the existential binder, thesatisfaction operator, and the global modality, ranging from the minimalhybrid language to very expressive languages. For model checking, weseparate polynomial-time solvable from PSPACE-complete cases, and forsatisfiability, we exhibit cases complete for NP, PSpace, NExpTime, andeven N2ExpTime. Our analysis includes the versions of all these languageswithout atomic propositions, and also complete frames.

Original language	English
Title of host publication	host publication
Pages	81-90
Number of pages	10
Publication status	Published - 2007
Event	HyLo 2007 - Duration: 1 Jan 1824 → …

Conference

Conference	HyLo 2007
Period	1/01/24 → …

Cite this

@inproceedings{8cd0b4d263774cc5b9a896eae1878f10,

title = "The Complexity of Hybrid Logics over Equivalence Relations",

abstract = "This paper examines and classifies the computational complexity of modelchecking and satisfiability for hybrid logics over frames withequivalence relations. The considered languages contain all possiblecombinations of the downarrow binder, the existential binder, thesatisfaction operator, and the global modality, ranging from the minimalhybrid language to very expressive languages. For model checking, weseparate polynomial-time solvable from PSPACE-complete cases, and forsatisfiability, we exhibit cases complete for NP, PSpace, NExpTime, andeven N2ExpTime. Our analysis includes the versions of all these languageswithout atomic propositions, and also complete frames.",

author = "M. Mundhenk and T. Schneider",

year = "2007",

language = "English",

pages = "81--90",

booktitle = "host publication",

note = "HyLo 2007 ; Conference date: 01-01-1824",

}

TY - GEN

T1 - The Complexity of Hybrid Logics over Equivalence Relations

AU - Mundhenk, M.

AU - Schneider, T.

PY - 2007

Y1 - 2007

N2 - This paper examines and classifies the computational complexity of modelchecking and satisfiability for hybrid logics over frames withequivalence relations. The considered languages contain all possiblecombinations of the downarrow binder, the existential binder, thesatisfaction operator, and the global modality, ranging from the minimalhybrid language to very expressive languages. For model checking, weseparate polynomial-time solvable from PSPACE-complete cases, and forsatisfiability, we exhibit cases complete for NP, PSpace, NExpTime, andeven N2ExpTime. Our analysis includes the versions of all these languageswithout atomic propositions, and also complete frames.

AB - This paper examines and classifies the computational complexity of modelchecking and satisfiability for hybrid logics over frames withequivalence relations. The considered languages contain all possiblecombinations of the downarrow binder, the existential binder, thesatisfaction operator, and the global modality, ranging from the minimalhybrid language to very expressive languages. For model checking, weseparate polynomial-time solvable from PSPACE-complete cases, and forsatisfiability, we exhibit cases complete for NP, PSpace, NExpTime, andeven N2ExpTime. Our analysis includes the versions of all these languageswithout atomic propositions, and also complete frames.

M3 - Conference contribution

SP - 81

EP - 90

BT - host publication

T2 - HyLo 2007

Y2 - 1 January 1824

ER -

The Complexity of Hybrid Logics over Equivalence Relations

Abstract

Conference

Fingerprint

Cite this