کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662609 1633554 2006 32 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complexity of monodic guarded fragments over linear and real time
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Complexity of monodic guarded fragments over linear and real time
چکیده انگلیسی

We show that the satisfiability problem for the monodic guarded, loosely guarded, and packed fragments of first-order temporal logic with equality is 2Exptime-complete for structures with arbitrary first-order domains, over linear time, dense linear time, rational number time, and some other classes of linear flows of time. We then show that for structures with finite first-order domains, these fragments are also 2Exptime-complete over real number time and hence over most of the commonly used linear flows of time, including the natural numbers, integers, rationals, and any first-order definable class of linear flows of time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 138, Issues 1–3, March 2006, Pages 94-125