کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
11021132 1715034 2018 31 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Multi-buffer simulations: Decidability and complexity
ترجمه فارسی عنوان
شبیه سازی چند بافر: تصمیم گیری و پیچیدگی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , , , ,