کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657405 | 1441790 | 2005 | 26 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Typestate verification: Abstraction techniques and complexity results
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Typestate verification: Abstraction techniques and complexity results Typestate verification: Abstraction techniques and complexity results](/preview/png/9657405.png)
چکیده انگلیسی
We consider the problem of typestate verification for shallow programs; i.e., programs where pointers from program variables to heap-allocated objects are allowed, but where heap-allocated objects may not themselves contain pointers. We prove a number of results relating the complexity of verification to the nature of the finite state machine used to specify the property. Some properties are shown to be intractable, but others which appear to be quite similar admit polynomial-time verification algorithms. Our results serve to provide insight into the inherent complexity of important classes of verification problems. In addition, the program abstractions used for the polynomial-time verification algorithms may be of independent interest.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Science of Computer Programming - Volume 58, Issues 1â2, October 2005, Pages 57-82
Journal: Science of Computer Programming - Volume 58, Issues 1â2, October 2005, Pages 57-82
نویسندگان
J. Field, D. Goyal, G. Ramalingam, E. Yahav,