The complexity of satisfiability for fragments of hybrid logic-part i

Arne Meier; Martin Mundhenk; Thomas Schneider; Michael Thomas; Volker Weber; Felix Weiss

doi:10.1007/978-3-642-03816-7_50

The complexity of satisfiability for fragments of hybrid logic-part i

Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Volker Weber, Felix Weiss

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

Abstract

The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments. In this paper, we investigate the effect of restricting the propositional part of the language on decidability and on the complexity of the satisfiability problem over arbitrary, transitive, total frames, and frames based on equivalence relations. We also consider different sets of modal and hybrid operators. We trace the border of decidability and give the precise complexity of most fragments, in particular for all fragments including negation. For the monotone fragments, we are able to distinguish the easy from the hard cases, depending on the allowed set of operators. © 2009 Springer Berlin Heidelberg.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)\|Lect. Notes Comput. Sci.
Pages	587-599
Number of pages	12
Volume	5734
DOIs	https://doi.org/10.1007/978-3-642-03816-7_50
Publication status	Published - 2009
Event	34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009 - Novy Smokovec, High Tatras Duration: 1 Jul 2009 → …

Conference

Conference	34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009
City	Novy Smokovec, High Tatras
Period	1/07/09 → …

Keywords

Complexity
Decidability
Hybrid logic
Post's lattice
Satisfiability

Access to Document

10.1007/978-3-642-03816-7_50

Cite this

Meier, A., Mundhenk, M., Schneider, T., Thomas, M., Weber, V., & Weiss, F. (2009). The complexity of satisfiability for fragments of hybrid logic-part i. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci. (Vol. 5734, pp. 587-599) https://doi.org/10.1007/978-3-642-03816-7_50

@inproceedings{f77c8ef865c04bceb33156494bd45268,

title = "The complexity of satisfiability for fragments of hybrid logic-part i",

abstract = "The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments. In this paper, we investigate the effect of restricting the propositional part of the language on decidability and on the complexity of the satisfiability problem over arbitrary, transitive, total frames, and frames based on equivalence relations. We also consider different sets of modal and hybrid operators. We trace the border of decidability and give the precise complexity of most fragments, in particular for all fragments including negation. For the monotone fragments, we are able to distinguish the easy from the hard cases, depending on the allowed set of operators. {\textcopyright} 2009 Springer Berlin Heidelberg.",

keywords = "Complexity, Decidability, Hybrid logic, Post's lattice, Satisfiability",

author = "Arne Meier and Martin Mundhenk and Thomas Schneider and Michael Thomas and Volker Weber and Felix Weiss",

year = "2009",

doi = "10.1007/978-3-642-03816-7_50",

language = "English",

isbn = "3642038158",

volume = "5734",

pages = "587--599",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.",

note = "34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009 ; Conference date: 01-07-2009",

}

Meier, A, Mundhenk, M, Schneider, T, Thomas, M, Weber, V & Weiss, F 2009, The complexity of satisfiability for fragments of hybrid logic-part i. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.. vol. 5734, pp. 587-599, 34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009, Novy Smokovec, High Tatras, 1/07/09. https://doi.org/10.1007/978-3-642-03816-7_50

The complexity of satisfiability for fragments of hybrid logic-part i. / Meier, Arne; Mundhenk, Martin; Schneider, Thomas et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.. Vol. 5734 2009. p. 587-599.

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

TY - GEN

T1 - The complexity of satisfiability for fragments of hybrid logic-part i

AU - Meier, Arne

AU - Mundhenk, Martin

AU - Schneider, Thomas

AU - Thomas, Michael

AU - Weber, Volker

AU - Weiss, Felix

PY - 2009

Y1 - 2009

N2 - The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments. In this paper, we investigate the effect of restricting the propositional part of the language on decidability and on the complexity of the satisfiability problem over arbitrary, transitive, total frames, and frames based on equivalence relations. We also consider different sets of modal and hybrid operators. We trace the border of decidability and give the precise complexity of most fragments, in particular for all fragments including negation. For the monotone fragments, we are able to distinguish the easy from the hard cases, depending on the allowed set of operators. © 2009 Springer Berlin Heidelberg.

AB - The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments. In this paper, we investigate the effect of restricting the propositional part of the language on decidability and on the complexity of the satisfiability problem over arbitrary, transitive, total frames, and frames based on equivalence relations. We also consider different sets of modal and hybrid operators. We trace the border of decidability and give the precise complexity of most fragments, in particular for all fragments including negation. For the monotone fragments, we are able to distinguish the easy from the hard cases, depending on the allowed set of operators. © 2009 Springer Berlin Heidelberg.

KW - Complexity

KW - Decidability

KW - Hybrid logic

KW - Post's lattice

KW - Satisfiability

U2 - 10.1007/978-3-642-03816-7_50

DO - 10.1007/978-3-642-03816-7_50

M3 - Conference contribution

SN - 3642038158

SN - 9783642038150

VL - 5734

SP - 587

EP - 599

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.

T2 - 34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009

Y2 - 1 July 2009

ER -

The complexity of satisfiability for fragments of hybrid logic-part i

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this