کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4663035 1345221 2010 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complexity of hybrid logics over transitive frames
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Complexity of hybrid logics over transitive frames
چکیده انگلیسی

This article 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 over arbitrary frames (Areces et al. (1999) [2]). We also show 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. Furthermore, we establish 2EXPTIME and EXPTIME upper bounds for satisfiability over transitive frames and transitive trees, respectively, for the hybrid Until/SinceUntil/Since language and complement them with an EXPTIME lower bound for the modal UntilUntil language.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Applied Logic - Volume 8, Issue 4, December 2010, Pages 422–440
نویسندگان
, , , ,