کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952021 1442001 2017 25 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Efficient abstraction algorithms for predicate detection
ترجمه فارسی عنوان
الگوریتم های انتزاعی کارآمد برای تشخیص پیش فرض
کلمات کلیدی
تشخیص پیش بینی، منطق زمانی الگوریتم آنلاین، الگوریتم توزیع،
ترجمه چکیده
تجزیه و تحلیل محاسبات توزیع یک مشکل سخت به طور کلی به علت انفجار ترکیبی در اندازه فضای حالت با تعداد فرآیندهای موجود در سیستم است. با انتزاع محاسبات، می توان از کاوش های غیر ضروری دولتی اجتناب کرد. برش محاسباتی روشی برای انتزاع محاسبات توزیع شده با توجه به یک پیش فرض خاص است. برای شناسایی یک پیش فرض در زمان تأیید در زمان اجرا، مهم است که قادر به محاسبه تکرار به صورت افزایشی و زمانی که یک رویداد جدید در سیستم ایجاد می شود. در این کار، ما چندین الگوریتم انتزاعی آنلاین را برای محاسبه تکه ای از یک محاسبات توزیع شده با توجه به پیش فرض های منظم و گسترش های زمانی آن ارائه می دهیم. خانواده محدوده های منظم نسبتا غنی است و بسیاری از مفاهیم استفاده شده برای تایید زمان اجرا را پوشش می دهد. ابتدا چندین الگوریتم آنلاین برای محاسبه تکه را با توجه به برخی از مفاهیم منظم منطقی منطقی ارائه می کنیم که همه آنها متمرکز هستند. سپس یک الگوریتم توزیع شده برای محاسبه تکه را با توجه به یک پیش فرض مبتنی بر حالت منظم ارائه می کنیم؛ آن را توزیع مورد نیاز کار و ذخیره سازی در سراسر سیستم، در نتیجه کاهش فضای و پیچیدگی محاسبات در هر فرآیند. ما همچنین با استفاده از الگوریتم های ارائه شده برای محاسبه قطعه برای دو اپراتور منطقی زمانی که پیش فرض مورد استفاده در اپراتور منظم نیست، تکنیک برش را به مفاد غیر منظم گسترش می دهیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
الگوریتم های انتزاعی کارآمد برای تشخیص پیش فرض
چکیده انگلیسی
Analyzing a distributed computation is a hard problem in general due to the combinatorial explosion in the size of the state-space with the number of processes in the system. By abstracting the computation, unnecessary state explorations can be avoided. Computation slicing is an approach for abstracting distributed computations with respect to a given predicate. To detect a predicate in a timely manner during run-time verification, it is important to be able to compute the slice in an incremental manner as and when a new event is generated in the system. In this work, we present several online abstraction algorithms for computing the slice of a distributed computation with respect to regular predicates and its temporal extensions. The family of regular predicates is fairly rich and covers many commonly used predicates for run-time verification. We first present several online algorithms for computing the slice with respect to certain temporal logical regular predicates all of which are centralized. We then present a distributed algorithm for computing the slice with respect to a regular state based predicate; it distributes the work and storage requirements across the system, thus reducing the space and computation complexity per process. We also extend the slicing technique to non-regular predicates by presenting algorithms for computing the slice for two temporal logic operators when the predicate used in the operator is not regular.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 688, 6 August 2017, Pages 24-48
نویسندگان
, , , ,