کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4663034 1345221 2010 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The complexity of satisfiability for fragments of hybrid logic-Part I
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
The complexity of satisfiability for fragments of hybrid logic-Part I
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Applied Logic - Volume 8, Issue 4, December 2010, Pages 409-421
نویسندگان
, , , , , ,