کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
11021132 | 1715034 | 2018 | 31 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Multi-buffer simulations: Decidability and complexity
ترجمه فارسی عنوان
شبیه سازی چند بافر: تصمیم گیری و پیچیدگی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the decidability and complexity of multi-buffer simulations and obtain the following results: P-completeness for fixed bounded buffers, EXPTIME-completeness in case of a single unbounded buffer and high undecidability (in the analytic hierarchy) with two buffers of which at least one is unbounded. We also consider a variant in which the buffers are kept untouched or flushed and show PSPACE-completeness for the single-buffer case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 262, Part 2, October 2018, Pages 280-310
Journal: Information and Computation - Volume 262, Part 2, October 2018, Pages 280-310
نویسندگان
Milka Hutagalung, Norbert Hundeshagen, Dietrich Kuske, Martin Lange, Ãtienne Lozes,