Undecidability of Multi-modal Hybrid Logics

by    Martin Mundhenk, Thomas Schneider

Preprint series: 06-11, Reports on Computer Science

03B45 Modal logic {For knowledge and belief see 03B42; for temporal logic see 03B44; for provability logic see also 03F45}

Abstract: This paper establishes undecidability of satisfiability for multi-modal logic equipped with the hybrid downarrow-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.

Keywords: Computational Complexity, Downarrow Operator, Hybrid Logic, Modal Logic

Upload: 2006-07-20

Update: 2006 -07 -20

The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.