کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952268 1442025 2017 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computational complexity of finite asynchronous cellular automata
ترجمه فارسی عنوان
پیچیدگی محاسباتی از اتوماتای ​​سلولی ناسازگار محدود
کلمات کلیدی
محاسبات طبیعی، اتوماتای ​​سلول آسنکرون، پیچیدگی محاسباتی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper is concerned with two big classes of problems: reachability and preimage existence. For each class, both an existential and a universal version are considered. The following results are proved. Reachability is PSPACE-complete, its resource bounded version is NP-complete (existential form) or coNP-complete (universal form). The preimage problem is dimension sensitive in the sense that it is NL-complete (both existential and universal form) for one-dimensional ACA while it is NP-complete (existential version) or Π2P-complete (universal version) for higher dimension.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 664, 15 February 2017, Pages 131-143
نویسندگان
, , , , ,