Complexity of Hybrid Logics over Transitive Frames

Details Complexity of Hybrid Logics over Transitive Frames Complexity of Hybrid Logics over Transitive Frames

2008-06-25

arxiv.org/abs/0806.4130v1

Workshop "Methods for Modalities" (M4M-4), Informatik-Berichte, 194, pp. 62-78, 2005. ISSN 0863-095X

Computer Science

Logic in Computer Science

21 pages, 6 figures (only 2 thereof are in external files)

Scientific paper

This paper examines the complexity of hybrid logics over transitive frames, transitive trees, and linear frames. We show that satisfiability over transitive frames for the hybrid language extended with the downarrow operator is NEXPTIME-complete. This is in contrast to undecidability of satisfiability over arbitrary frames for this language (Areces, Blackburn, Marx 1999). It is also shown that adding the @ operator or the past modality leads to undecidability over transitive frames. This is again in contrast to the case of transitive trees and linear frames, where we show these languages to be nonelementarily decidable. Moreover, we establish 2EXPTIME and EXPTIME upper bounds for satisfiability over transitive frames and transitive trees, respectively, for the hybrid Until/Since language. An EXPTIME lower bound is shown to hold for the modal Until language over both frame classes.

Affiliated with

Also associated with

No associations

Rating

Complexity of Hybrid Logics over Transitive Frames does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity of Hybrid Logics over Transitive Frames, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Hybrid Logics over Transitive Frames will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-162926