کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
422508 | 685097 | 2008 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An Algorithm for Approximating the Satisfiability Problem of High-level Conditions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The satisfiability problem is the fundamental problem in proving the conflict-freeness of specifications, or in finding a counterexample for an invalid statement. In this paper, we present a non-deterministic, monotone algorithm for this undecidable problem on graphical conditions that is both correct and complete, but in general not guaranteed to terminate. For a fragment of high-level conditions, the algorithm terminates, hence it is able to decide. Instead of enumerating all possible objects of a category to approach the problem, the algorithm uses the input condition in a constructive way to progress towards a solution. To this aim, programs over transformation rules with external interfaces are considered. We use the framework of weak adhesive HLR categories. Consequently, the algorithm is applicable to a number of replacement capable structures, such as Petri-Nets, graphs or hypergraphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 213, Issue 1, 5 May 2008, Pages 75-94
Journal: Electronic Notes in Theoretical Computer Science - Volume 213, Issue 1, 5 May 2008, Pages 75-94
نویسندگان
Karl-Heinz Pennemann,