Undecidability of Multi-modal Hybrid Logics

Martin Mundhenk; Thomas Schneider

doi:10.1016/j.entcs.2006.11.024

Undecidability of Multi-modal Hybrid Logics

Martin Mundhenk
, Thomas Schneider

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

Abstract

This paper establishes undecidability of satisfiability for multi-modal logic equipped with the hybrid binder ↓, with respect to frame classes over which the same language with only one modality is decidable. This is in contrast to the usual behaviour of many modal and hybrid logics, whose uni-modal and multi-modal versions do not differ in terms of decidability and, quite often, complexity. The results from this paper apply to a wide range of frame classes including temporally and epistemically relevant ones. © 2007 Elsevier B.V. All rights reserved.

Original language	English
Title of host publication	Electronic Notes in Theoretical Computer Science\|Electron. Notes Theor. Comput. Sci.
Publisher	Elsevier BV
Pages	29-43
Number of pages	14
Volume	174
DOIs	https://doi.org/10.1016/j.entcs.2006.11.024
Publication status	Published - 3 Jun 2007
Event	Int. Workshop on Hybrid Logic (HyLo) - Duration: 1 Jan 1824 → …

Conference

Conference	Int. Workshop on Hybrid Logic (HyLo)
Period	1/01/24 → …

Keywords

Computational Complexity
Downarrow Operator
Hybrid Logic
Modal Logic

Access to Document

10.1016/j.entcs.2006.11.024

Cite this

@inproceedings{4f04b924beb344c3a4786ce420769ace,

title = "Undecidability of Multi-modal Hybrid Logics",

abstract = "This paper establishes undecidability of satisfiability for multi-modal logic equipped with the hybrid binder ↓, with respect to frame classes over which the same language with only one modality is decidable. This is in contrast to the usual behaviour of many modal and hybrid logics, whose uni-modal and multi-modal versions do not differ in terms of decidability and, quite often, complexity. The results from this paper apply to a wide range of frame classes including temporally and epistemically relevant ones. {\textcopyright} 2007 Elsevier B.V. All rights reserved.",

keywords = "Computational Complexity, Downarrow Operator, Hybrid Logic, Modal Logic",

author = "Martin Mundhenk and Thomas Schneider",

year = "2007",

month = jun,

day = "3",

doi = "10.1016/j.entcs.2006.11.024",

language = "English",

volume = "174",

pages = "29--43",

booktitle = "Electronic Notes in Theoretical Computer Science|Electron. Notes Theor. Comput. Sci.",

publisher = "Elsevier BV",

address = "Netherlands",

note = "Int. Workshop on Hybrid Logic (HyLo) ; Conference date: 01-01-1824",

}

TY - GEN

T1 - Undecidability of Multi-modal Hybrid Logics

AU - Mundhenk, Martin

AU - Schneider, Thomas

PY - 2007/6/3

Y1 - 2007/6/3

N2 - This paper establishes undecidability of satisfiability for multi-modal logic equipped with the hybrid binder ↓, with respect to frame classes over which the same language with only one modality is decidable. This is in contrast to the usual behaviour of many modal and hybrid logics, whose uni-modal and multi-modal versions do not differ in terms of decidability and, quite often, complexity. The results from this paper apply to a wide range of frame classes including temporally and epistemically relevant ones. © 2007 Elsevier B.V. All rights reserved.

AB - This paper establishes undecidability of satisfiability for multi-modal logic equipped with the hybrid binder ↓, with respect to frame classes over which the same language with only one modality is decidable. This is in contrast to the usual behaviour of many modal and hybrid logics, whose uni-modal and multi-modal versions do not differ in terms of decidability and, quite often, complexity. The results from this paper apply to a wide range of frame classes including temporally and epistemically relevant ones. © 2007 Elsevier B.V. All rights reserved.

KW - Computational Complexity

KW - Downarrow Operator

KW - Hybrid Logic

KW - Modal Logic

U2 - 10.1016/j.entcs.2006.11.024

DO - 10.1016/j.entcs.2006.11.024

M3 - Conference contribution

VL - 174

SP - 29

EP - 43

BT - Electronic Notes in Theoretical Computer Science|Electron. Notes Theor. Comput. Sci.

PB - Elsevier BV

T2 - Int. Workshop on Hybrid Logic (HyLo)

Y2 - 1 January 1824

ER -

Undecidability of Multi-modal Hybrid Logics

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this